OlympiadBench / 2011 / Alice fills the fields of an n×n board with numbers from 1 to n²,…

Alice fills the fields of an n×n board with numbers from 1 to n², 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.

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$.