Question 61
Let $N$ be a positive integer, and consider an $N \times N$ grid. A *right-down path* is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A *right-up path* is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence.
Prove that the cells of the $N \times N$ grid cannot be partitioned into fewer than $N$ right-down and/or right-up paths. For example, the following partition of the $5 \times 5$ grid uses 5 paths:
Prove that the cells of the $N \times N$ grid cannot be partitioned into fewer than $N$ right-down and/or right-up paths. For example, the following partition of the $5 \times 5$ grid uses 5 paths: