Bài 6
Cho là một số nguyên dương. Một hình vuông Bắc Âu là một bảng chứa tất cả các số nguyên từ đến sao cho mỗi ô chứa đúng một số. Một đường lên dốc là một dãy gồm một hoặc nhiều ô sao cho: (a) ô đầu tiên trong dãy là một thung lũng, nghĩa là số ghi ở đó nhỏ hơn tất cả các ô kề trực giao với nó; (b) mỗi ô tiếp theo trong dãy kề trực giao với ô trước đó; và (c) các số ghi trong các ô của dãy tăng dần. Tìm, theo hàm của , tổng số đường lên dốc nhỏ nhất có thể trong một hình vuông Bắc Âu.
Bước 3 trên 5: Xây dựng một cây sao cho không có hai ô ngoài nào kề nhau
Hiểu nôm na
Nếu mọi ô nằm ngoài một cây được chọn chỉ được bao quanh bởi các ô trong cây, thì không đường lên dốc nào có thể đi qua hai ô ngoài liên tiếp, giới hạn chặt chẽ cách các đường có thể phát triển.
Phân tích chi tiết
Một cách xây dựng tuần hoàn chuẩn (cắt bớt hàng hoặc cột biên khi cần) cho một cây liên thông sao cho không có hai ô ngoài kề trực giao. Ta chỉ dùng tính chất cấu trúc này trong phép đếm.