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 1 trên 5: Mỗi cặp ô kề nhau cho một đường lên dốc không tầm thường
Hiểu nôm na
Định hướng mỗi cạnh từ số lớn hơn đến số nhỏ hơn rồi đi theo các số giảm dần cho tới một thung lũng. Đảo ngược lối đi thu được sẽ cho một đường lên dốc chứa cạnh đã chọn.
Phân tích chi tiết
Với mỗi một trong cạnh của lưới, định hướng cạnh xuống dốc rồi kéo dài lối đi xuống dốc tới một thung lũng. Đảo ngược cho một đường lên dốc không tầm thường. Các đường thu được từ những cạnh có hướng khác nhau là phân biệt, nên mọi hình vuông có ít nhất đường lên dốc không tầm thường.