George Sicherman sent in some solutions to Problem 51, which was to tile a certain torus with the proper polykings and a monomino hole. There were several optional challenges presented, and each of these solutions met two of them. (For the present post, we’ll pretend that challenge 4 asked specifically for a 4-coloring, rather than vaguely asking for a reduced number of colors.) The first satisfied the no-crossed bridges constraint and the no four-piece corner constraint:
The second is 4-colorable, and has no crossed bridges:
And the third is 4-colorable, and has no “fault lines” passing through it:
These results got me thinking about the combinatorics of independent optional challenges of a given problem. A realizable subset of optional challenges is “optimal” if it isn’t a proper subset of another realizable optional challenge set. From the perspective of a problem designer, a full set of optional challenges might be said to optimize interest if it maximizes the number of optimal realizable subsets. For example, problem 51, with four optional challenges, would be most interesting if all six pairs of challenges were realizable, but no triples of challenges were. In general, a problem with n optional challenges will be optimally interesting if all realizable subsets of size n/2 are optimal, if n is even. For odd n, optimal realizable subsets would have to be all of size (n + 1) / 2 or all of size (n – 1) / 2.
Problem 51a: Make Problem 51 “better” by finding solutions with that satisfy missing pairs of challenges.
Problem 51b: Make Problem 51 “worse” by finding solutions that satisfy a set of challenges that is a superset of two or more of the challenge pairs satisfied by the above solutions.
Metaproblem: Design an optimally interesting puzzle with four or more challenges!
