## MSLC Semina — Exploring Knights Tours

At the MSLC Seminar we had an “improvisational seminar” this week. We started off chit-chatting about various problems, and a theme emerged. One participant posed the following problem:

The game of Knight Placement is played on an 8×8 chessboard. Two players alternately take turns placing knights on the board. A move consists of adding a knight to the board, such that no knight is under attack. A player loses if they’re unable to place a knight. Who wins under optimal play?

I followed this question up with:

Suppose that the Queen of Chess has a garrison of twenty-five knights. The knights are kept on a 5×5 chessboard. One fine morning, the Queen shows up and orders the knights to all switch places, or be severely punished. Can every knight switch places simultaneously?

This got us thinking about knights tours. In a knight’s tour, a knight travels to every cell of a chessboard by visiting each square exactly once. Notice that if the 5×5 board has a knight’s tour, then the garrison can re-arrange themselves by each stepping along the tour.

We found a couple small boards with and without closed knight’s tours. Wikipedia turned our attention to this paper:

Allen J. Schwenk (1991). “*Which Rectangular Chessboards Have a Knight’s Tour?*” Mathematics Magazine: 325–332. (link)

Working through that paper might make a good session at MSLC Seminar. If anyone knows the history / providence of the puzzles above, I would be hear about them.

## Dwarves with hats

This afternoon Mike Pawliuk told me the following problem:

A thousand dwarves are wearing standing around wearing red or blue hats. No one can see their own hat and no one can communicate with anyone. Can the dwarves devise a strategy to form a line so that all the red hatted dwarves are on one end, and all the blue hatted dwarves are on the other?

While thinking over the solution, it occurred to me that one can obfuscate the problem as follows:

Consider a group of n dwarves as above. Can the dwarves devise a strategy such that all but a uniformly bounded number of dwarves know the colour of their own hat correctly with absolute certainty?

I can’t see a route to the solution of the second problem that doesn’t go through Mike’s puzzle. This is a terrible case of solution induced blindness. Perhaps someone can point out a more direct solution.

**Edit**: After some reflection, Mike and I have concluded that this problem is too easy without placing restriction on how the dwarves can move around, since a lot can be encoded by in their movement patterns. It’s very easy to get absolute certainty for all but one dwarf as posed.

For the record, here is another dwarf problem that Michelle Boué told me about when I was an undergrad:

Suppose that three dwarves with red or blue hats are sitting in a circle. They decide on a strategy to guess the colour of their own hat without communicating. They all guess simultaneously. Can they do better than guessing uniformly at random?

leave a comment