Pósa problem

Can a chess knight visit every square on a board with 4 rows by a series of successive moves?

No, it can’t, and Hungarian mathematics prodigy Louis Pósa proved this while still in his early teens. Suppose that such a tour is possible. Then, on any board bearing the standard checkerboard pattern, the knight will land alternately on white and black squares. But now imagine that the board’s top and bottom rows have been colored red and the middle two rows are blue. Now a knight on any red square must jump to a blue square, and because the board has an equal number of red and blue squares, any knight on a blue square must jump to a red one (if it visits two blue squares in a row, it won’t be able to make up for this later by visiting two red ones in a row). So the knight’s tour on any 4 × n board must alternate strictly between red and blue squares.

“But this is impossible,” notes Colorado College mathematician John J. Watkins. “The same knight’s tour alternated between white and black squares in the one coloring, and between red and blue squares in the other coloring, which would mean the two color patterns must be the same, which of course they aren’t. Isn’t that a clever proof, especially for a teenager to discover?”

(John J. Watkins, Across the Board, 2004. Pósa’s proof is given more rigorously here, and it’s also presented in Ross Honsberger’s 1973 book Mathematical Gems.)

UPDATE: It’s important to note that it’s a “closed” knight’s tour that’s impossible — that’s one that ends where it began. An open tour, which can end anywhere, is possible — it breaks Pósa’s proof because it need not alternate strictly between red and blue squares. Thanks to reader Marjan Milanović for pointing this out.