MathDB

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 less than

N

right-down or right-up paths. For example, the following partition of the

5 \times 5

grid uses

5

paths. [asy] size(4cm); draw((5,-1)--(0,-1)--(0,-2)--(5,-2)--(5,-3)--(0,-3)--(0,-4)--(5,-4),gray+linewidth(0.5)+miterjoin); draw((1,-5)--(1,0)--(2,0)--(2,-5)--(3,-5)--(3,0)--(4,0)--(4,-5),gray+linewidth(0.5)+miterjoin); draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,black+linewidth(2.5)+miterjoin); draw((0,-1)--(3,-1)--(3,-2)--(1,-2)--(1,-4)--(4,-4)--(4,-3)--(2,-3)--(2,-2),black+linewidth(2.5)+miterjoin); draw((3,0)--(3,-1),black+linewidth(2.5)+miterjoin); draw((1,-4)--(1,-5),black+linewidth(2.5)+miterjoin); draw((4,-3)--(4,-1)--(5,-1),black+linewidth(2.5)+miterjoin); [/asy] Proposed by Zixiang Zhou, Canada

Problem Statement