3 Sea $N$ un entero positivo, y considere una cuadrícula de $N \times N$ . Un camino derecha-abajo es una sucesión de celdas de la cuadrícula tal que cada celda está una celda a la derecha o una celda debajo de la celda anterior en la sucesión. Un camino derecha-arriba es una sucesión de celdas de la cuadrícula tal que cada celda está una celda a la derecha o una celda encima de la celda anterior en la sucesión. Demuestre que las celdas de la cuadrícula de $N \times N$ no pueden particionarse en menos de $N$ caminos derecha-abajo o derecha-arriba. Por ejemplo, la siguiente partición de la cuadrícula de $5 \times 5$ usa $5$ caminos. [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] Propuesto por Zixiang Zhou, Canadá