2022 IMO Shortlist C8

Alice fills the fields of an $n \times n$ board with numbers from 1 to $n^{2}$, each number being used exactly once. She then counts the total number of good paths on the board. A good path is a sequence of fields of arbitrary length (including 1) such that: (i) The first field in the sequence is one that is only adjacent to fields with larger numbers, (ii) Each subsequent field in the sequence is adjacent to the previous field, (iii) The numbers written on the fields in the sequence are in increasing order. Two fields are considered adjacent if they share a common side. Find the smallest possible number of good paths Alice can obtain, as a function of $n$. (Serbia)

Alice 用从 1 到 $n^{2}$ 的数字填充 $n \times n$ 棋盘的字段，每个数字仅使用一次。然后她计算板上好路径的总数。好的路径是任意长度(包括 1)的字段序列，这样：(i)序列中的第一个字段仅与数字较大的字段相邻，(ii)序列中的每个后续字段与前一个字段相邻，(iii)序列中字段上写的数字按递增顺序排列。如果两个字段共享公共边，则认为它们是相邻的。求 Alice 可以获得的尽可能少的好路径，作为 $n$ 的函数。 (塞尔维亚)