Problem 6
Let be a positive integer. A Nordic square is an board containing all the integers from to so that each cell contains exactly one number. An uphill path is a sequence of one or more cells such that: (a) the first cell in the sequence is a valley, meaning the number written is less than all its orthogonal neighbours; (b) each subsequent cell in the sequence is orthogonally adjacent to the previous cell; and (c) the numbers written in the cells in the sequence are in increasing order. Find, as a function of , the smallest possible total number of uphill paths in a Nordic square.
Step 1 of 5: Every adjacent pair yields a nontrivial uphill path
In plain words
Orient each edge from the larger entry to the smaller one and follow decreasing entries until a valley. Reversing the resulting walk gives an uphill path containing the chosen edge.
Detailed analysis
For each of the grid edges, orient it downhill and extend the downhill walk to a valley. Reversing gives a nontrivial uphill path. The paths obtained from different directed edges are distinct, so every square has at least nontrivial uphill paths.