Answer to the Insane King Puzzle


Alas, the king is trapped:

This picture is one way the demoness could confine our lost-marbled king. The circles represent bars on the king's forthcoming cage.

Specifically, here is the demoness's strategy:
Around the king is an imaginary window of the eight surrounding squares (the window is rectangular in shape). Each time the king makes a move so that his window overlaps a circle, the demoness removes the circle from the board. As long as the demoness can ensure that every circle in his window is removed as soon as he sees it, then the demoness is guaranteed victory.

We must be absolutely certain that the demoness can satisfy this condition. As the king moves, most of his windows will only gain a single circle at a time. Hence those windows are easy to deal with. However, there are 4 places where a move of the king will increase the number of circles in his window by two at once. This happens whenever the king moves from a colored square toward the same-colored circles. But the demoness can deal with this by coloring in one of those same-colored circles in advance, i.e., as soon as the king moves onto one of the colored squares (in which case his window is empty, giving the demoness the necessary opportunity to fill in this out-of-window circle).

From here it is easy to verify that we have covered all possible cases of window-moves on the king's part, and that the king is in fact, royally hosed.

It turns out that there are much smaller cages than this one. This one just allows for a sort of elegant (-ish) proof.

So the question becomes: what is the smallest cage in which the demoness can always confine the king? Actually, this might be sort of a trick question, since the demoness could do things such as continue to shrink the cage after the king is stuck in it. So we could declare the cage size to be set as soon as the king is confined. But then she could also postpone her "closing" of the cage until it has been shrunk quite a bit. Still, it is an interesting question (to which I don't know the answer (yet)).

www. Tyler Neylon .com