Hamiltonian Paths in Projective Checkerboards.
Margaret H. Forbush, Elizabeth Hanson, Hanna Kim, Andrew Mauer-Oats, Rhian Merris, Jennifer Oats-Sargent, Seth Oldham, Kate Sharkey, Dave Witte · 2000
. Place a checker in some square of an n \\Theta n checkerboard. The checker is allowed to step either to the east or to the north, and is allowed to step off the edge of the board in a manner suggested by the usual identification of the edges of the square to form a projective plane. We give an explicit description of all the routes that can be taken by the checker to visit each square exactly once. 1. Introduction Place a checker in some square of an n \\Theta n checkerboard. The checker is allowed to step (a distance of one square) either to the east or to the north --- in particular, it does not move diagonally. We ask whether it is possible to move the checker in this manner through a route that visits each square exactly once. We feel free to adopt graph-theoretic terminology whenever it is convenient, so we refer to such a route as a hamiltonian path. It is traditional to allow the checker to step off the edge of the board (otherwise, it is clear that no hamiltonian path exists)...