Problem 6.

  Let n  be a positive integer. A Nordic square is an nxn  board containing all the integers from 1 to  n²  so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) the numbers written in the cells in the sequence are in increasing order.

Find, as a function of n, the smallest possible total number of uphill paths in a Nordic square.