Robert Kaplan's grid paths
In this video, Robert Kaplan is considering paths in a square grid. He is allowing horizontal and vertical moves only. The first question he asks: Are there any Hamiltonian paths that start at the top left of a 5x5 grid? There are of course many such paths easily found. For example, the path which zig-zags horizontally, and the one that zig-zags vertically. Another easy path to recognize is the spiral path. There are many easy to find paths, and after the students have found a few, he asks them how many paths can visit every square, when you're allowed to start at any square. You can ask provoking questions here if the students aren't speaking up. As examples: Are more than 10 such paths? Are there infinitely many? Then he shows a particular path, labelling the starting point, then asks the students to find another path from this drawing. Of course the other path just swaps the starting point for the end. Showing that each path counts for 2 shows that the total number of Hamiltonian paths in a square grid must be even. He then labels each square in the 5x5 grid with numbers, and asks if students can find a Hamiltonian path starting at the 2nd square. This is impossible, because there are more odd squares than even squares. A path which moves only vertically and horizontally alternates colors. So if the path starts at an even square, it cannot visit every odd square. Here's where the talk ends. However, there are many additional questions that could be asked. For example, what about mxn boards. What about 3D boards? What about moves across edges in other grids, such as a triangular grid or hexagonal grid. What shaped grids are interesting in those cases? For example, the triangular grid arranged in a triangle is uninteresting because every corner triangle is a dead-end. What other sets of moves can visit every square? hops? horizontal and diagonal moves only? Given some set of moves, how many squares can you visit? For undergrads, we can also ask them to model such problems in the language of graph theory. Possibly, SageMath could be used to solve these problems once modelled, if the models are unweildy.