Câu hỏi 61
Cho $N$ là số nguyên dương, xét một bảng ô vuông $N \times N$. Một *đường đi phải-xuống* là một dãy các ô sao cho mỗi ô nằm ngay bên phải hoặc ngay bên dưới ô đứng trước nó trong dãy. Một *đường đi phải-lên* là một dãy các ô sao cho mỗi ô nằm ngay bên phải hoặc ngay bên trên ô đứng trước nó trong dãy.
Chứng minh rằng không thể chia các ô của bảng $N \times N$ thành ít hơn $N$ đường đi phải-xuống và/hoặc phải-lên. Ví dụ, cách chia bảng $5 \times 5$ dưới đây dùng 5 đường đi:
Chứng minh rằng không thể chia các ô của bảng $N \times N$ thành ít hơn $N$ đường đi phải-xuống và/hoặc phải-lên. Ví dụ, cách chia bảng $5 \times 5$ dưới đây dùng 5 đường đi: