MathLabs

Bài 6

Cho nn là một số nguyên dương. Một hình vuông Bắc Âu là một bảng n×nn\times n chứa tất cả các số nguyên từ 11 đến n2n^2 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 nn, 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 2 trên 5: Cộng thêm đường một ô tại thung lũng toàn cục
Bước trướcBước tiếp
2n2−2n+12n^2-2n+1
Phân tích chi tiết

Ngoài 2n(n−1)2n(n-1) đường không tầm thường này, ô chứa 11 luôn là một thung lũng và cho thêm một đường lên dốc chỉ gồm một ô. Do đó mọi hình vuông Bắc Âu có ít nhất 2n(n−1)+1=2n2−2n+12n(n-1)+1=2n^2-2n+1 đường lên dốc.