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 5 trên 5: Chứng minh cách xây dựng này có đúng đường
Phân tích chi tiết
Vì là thung lũng duy nhất, mọi đường lên dốc bắt đầu tại ô của nó. Phần ngoài không có hai ô kề nhau, nên sau khi rời một đường không thể có hai ô ngoài liên tiếp; cùng với thứ tự tăng trên cây, mỗi cạnh có hướng có đúng một phần tiếp nối tới một thung lũng. Vì vậy đường không tầm thường ở chặn dưới cùng với đường một ô tại là toàn bộ các đường, cho đẳng thức.