Bài 6

Cho

n

là một số nguyên dương. Một hình vuông Bắc Âu là một bảng

n\times n

chứa tất cả các số nguyên từ

1

đến

n^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

n

, 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 4 trên 5: Điền

T

trước để

1

là thung lũng duy nhất

Bước trước Bước tiếp

1\in T,\quad T\ \text{filled by adjacency, then the rest arbitrarily}

Phân tích chi tiết

Đặt $1$ vào một ô của $T$ , rồi điền phần còn lại của $T$ bằng $2,3,\ldots$ sao cho ô của mỗi số mới kề với một ô đã điền (luôn khả thi vì $T$ liên thông), và cuối cùng điền các ô còn lại (ngoài $T$ ) tùy ý bằng các số lớn hơn. Vì mọi ô ngoài chỉ kề với các ô $T$ đã điền trước mọi số ngoài, và $T$ được điền theo thứ tự liên thông tăng dần từ $1$ , thung lũng duy nhất trên toàn bảng là ô chứa $1$ .