Problem of the Week #2: Monday Jan. 16th, 2023 As before, these problems are the results of me following my curiosity, and I make no promises regarding the topics, difficulty, solvability of these problems. Please register for an account if you would like to join the discussion below or share your own problems. Please refrain from posting full solutions.
Consider a path in a grid with the following definition:
- It follows the lines of the grid.
- It’s connected.
- It does not branch.
- It does not loop (visit the same point twice).
For example, in a 3×3 grid, the top figure is a path, and the bottom four are not:
a) What’s the length of the longest path in the 3×3 grid above?
b) How many longest paths are there in the 3×3 grid? (For this entire problem, let’s say direction does not matter, but position and orientation do. I.e. going forward and backward counts as the same path, but moving the entire path one unit to the right, if the grid allows, or rotating it 90° clockwise, counts as a new path.)
c) How many paths of any length are there in the 3×3 grid?
d) What’s the length of the longest path in an nxn grid?
e) How many longest paths are there in an nxn grid?
f) How many paths of any length are there in an nxn grid?
g) Share your own problem inspired by this one.