Câu hỏi 189
Cho $N$ là một số nguyên dương, và xét một lưới ô vuông $N \times N$. Một đường phải-xuống là một dãy các ô của lưới 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 phải-lên là một dãy các ô của lưới 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ể phân hoạch các ô của lưới $N \times N$ thành ít hơn $N$ đường phải-xuống hoặc phải-lên. Ví dụ, phân hoạch sau đây của lưới $5 \times 5$ dùng 5 đường.
Chứng minh rằng không thể phân hoạch các ô của lưới $N \times N$ thành ít hơn $N$ đường phải-xuống hoặc phải-lên. Ví dụ, phân hoạch sau đây của lưới $5 \times 5$ dùng 5 đường.