Answer: $2n(n-1) + 1$. Solution. Given a pair of adjacent cells, we can always continue walking "downhill" until we reach a valley, so any pair of adjacent cells is the highest pair in at least one uphill path. There are $2n(n-1)$ such pairs, and the cell containing $1$ alone also constitutes an uphill path, so there must be at least $2n(n-1) + 1$ uphill paths. A construction obtaining exactly $2n(n-1) + 1$ is given as follows. We first construct a tree of $T$ cells such that every cell not in the tree is only adjacent to cells in the tree. A diagram of such a tree for $n=9$ is given below; this readily generalizes to any multiple of $3$, and to non-multiples of $3$ by removing the leftmost and/or the rightmost column. We place the numbers from $1$ to $T$ as follows: $1$ is placed in an arbitrary cell of the tree, and then each number is placed adjacent to exactly one number that was already placed. (Using a depth-first-search order works, for example.) The numbers $T+1$ to $n^2$ are placed arbitrarily in the remaining cells. [asy][asy] unitsize(16); for(int i=0; i < 10; i=i+2) { fill((0,i)--(3,i)--(3,i+1)--(0,i+1)--cycle,grey); fill((6,i)--(9,i)--(9,i+1)--(6,i+1)--cycle,grey); } for(int i=1; i < 9; i=i+2) { fill((3,i)--(6,i)--(6,i+1)--(3,i+1)--cycle,grey); } for(int i=1; i < 10; i=i+3) { fill((i,1)--(i,9)--(i+1,9)--(i+1,1)--cycle,grey); } fill((3,0)--(4,0)--(4,1)--(3,1)--cycle,grey); fill((5,0)--(6,0)--(6,1)--(5,1)--cycle,grey); for(int i=0; i < 10; ++i) { draw((i,0)--(i,9)); draw((0,i)--(9,i)); } [/asy][/asy] Tree for $n=9$. It follows that each pair of adjacent cells is the highest pair in exactly one uphill path, because the lower number in the pair lies in the tree and there is a unique way to go downhill from there to the unique valley at $1$, so there must be exactly $2n(n-1) + 1$ uphill paths in total. $\blacksquare$

Pretty fun problem though I certainly overcomplicated my constructions in the end. The answer is $2n(n - 1) + 1$. We first prove the lower bound. Call a path ascending if it satisfies conditions (ii) and (iii). Notice that any ascending path can be prepended with some squares to form an ascending path -- if the first square of an ascending path isn't a valley then it has some neighbor with a smaller number, which we can prepend to the path and repeat this until we reach a valley. Consider the $2n(n - 1)$ pairs of adjacent cells. Each of these pairs forms an ascending path that can be extended into an uphill path as described. These paths are all distinct since no two of them end with the same two squares. Moreover the path containing only the $1$ cell is an uphill path by itself. This gives at least $2n(n - 1) + 1$ paths. We now prove that this is achievable. The main result we abuse is the following: Claim. For any $n$ it is possible to mark some squares in an $n \times n$ grid in such a way that no two marked squares are adjacent, and the graph generated by the adjacencies of the unmarked cells is a tree. Proof Stare at this imgur album for a while until you convince yourself that it contains a valid and generalizable construction for each residue of $n \bmod{6}$. This works by repeating the $6 \times n$ pattern in a red box repeatedly and then appending the pattern in a blue box. $\blacksquare$ Now we have a tree obtained from the previous claim. Start at any unmarked cell and do DFS on the unmarked cells, labeling each one with the order we visit it in. Label the remaining marked cells with the remaining numbers arbitrarily, which are all bigger than the numbers in the unmarked cells. We claim that this works. (The following diagram is an example of a possible labeling for the unmarked cells). [asy][asy] unitsize(0.75cm); void gr(real x, real y) { fill(shift(x, y) * unitsquare, gray); } void nu(real x, real y, int n) { label((x + 0.5, y + 0.5), "$" + string(n) + "$"); } gr(0, 3); gr(1, 2); gr(2, 3); gr(3, 2); gr(4, 4); gr(0, 0); gr(2, 0); gr(4, 0); nu(2, 4, 1); nu(1, 4, 2); nu(0, 4, 3); nu(1, 3, 4); nu(3, 4, 5); nu(3, 3, 6); nu(4, 3, 7); nu(4, 2, 8); nu(4, 1, 9); nu(3, 1, 10); nu(3, 0, 11); nu(2, 1, 12); nu(2, 2, 13); nu(1, 1, 14); nu(0, 1, 15); nu(0, 2, 16); nu(1, 0, 17); for(int i = 0; i < 6; ++i) { draw((0, i)--(5, i)); draw((i, 0)--(i, 5)); } [/asy][/asy] This is because each unmarked cell other than the initial one is adjacent to exactly one cell with a smaller label, and thus there exists exactly one uphill path ending in each non-starting unmarked cell. We can assign the last edge they use to each of these paths, and these assigned edges are all different since the last number is different. We are left with the edges adjacent to marked cells, which all also contain an unmarked cell since no two marked cells are adjacent. Since each unmarked cell has exactly one uphill path ending in it, these edges all contribute exactly one extra uphill path ending on the marked cell. We thus get exactly $2n(n - 1)$ uphill paths in this configuration, and adding the path that only contains $1$ we get $2n(n - 1) + 1$ paths as desired. Remark. Thinking like a competitive programmer as we often do in combo problems, we are counting paths in a directed acyclic graph that start with a source. We can do this with a simple dynamic programming -- letting $dp_v$ be the number of valid paths ending at vertex $v$ we have $$dp_v = \begin{cases} 1 & \text{if } v \text{ is a source} \\ \displaystyle\sum_{u < v, u \in N(v)} dp_u & \text{otherwise} \end{cases}$$ Where the sum in the second case runs over all neighbors $u$ of $v$ such that $u < v$. The answer we seek is $dp_1 + dp_2 + \dots + dp_{n^2}$, and the recursive computation pretty much motivates the entire solution.

So this is another problem where constructing an example is harder than proving the bound. The hardest part is to believe that the obvious bound is actually the answer and try to construct it! It reminds me of APMO 2011 P4 (easy to prove, hard to construct).

Here is the construction of the tree I found on the test: Label squares $(i,j)$ like coordinates where $1\le i,j\le n$. For $i,j\ge 3$ put it in the tree if and only if $3\nmid i-j$. Remove (2,2) and remove suitable cells in the first and second column, which is easy

Almost all the constructions have a similar structure. Here's few things that lead me to the construction -

After realising these points, the construction becomes far more natural to arrive at. Excellent construct problem, I believe this problem will have 25+ solves. Though arriving at the construction will take several failed tries before it dawns upon the contestant the flaws in their previous constructs and how to effectively fix it.

Just an extension and probably a way to find that structure, what is the maximum number of valleys of a Nordic square??

mszew wrote: Just an extension and probably a way to find that structure, what is the maximum number of valleys of a Nordic square?? You can have 2n^2 valleys for even 2n. Construct is to do a chessboard tiling, all numbers from 1 to 2n^2 in whites and all numbers from 2n^2 + 1 to 4n^2 in blacks, and you can force 2n^2 valleys. 1 9 2 10 11 3 12 4 5 13 6 14 15 7 16 8 Example for n = 2.

Maximum number of Valleys is $$ \left\lceil \frac{n^2}{2} \right\rceil $$The construction is to color the Nordic square like a chessboard, put all small numbers in black squares, and all of them will be Valleys. To prove this bound is optimal, note that no two Valleys can be neighbors. Now just divide the square into $ \left\lceil \frac{n^2}{2} \right\rceil $ rectangles with dimensions $1 \times 2$ (and possible $1 \times 1$ if $n$ odd). Since each rectangle has at most one Valley, so done. In fact for this chessboard coloring type construction, the number of uphill paths is

Consider any simple graph $ G(V,E)$. We are allowed to choose the direction on each edge of $ E$ in such a way that $ G$ becomes an acyclic directed graph. We call a vertex $ v\in V$ a root (a valley) if there are only out-edges incident with $ v$. We call a directed path that starts from a root, a up-path. The question asks for the minimum number of distinct up-paths. Indeed, assigning distinct integers to each vertex generates a direction from the smaller to the larger number. This operation makes the graph acyclic. On the other hand, to each vertex of an acyclic directed graph can be assigned a number that is consistent with the directions. Since any directed edge generates at least one path that can be found by going backward, the number of the up-paths that consist of at least one edge are at least $|E|.$ Add a path that consists of only a root (at least one) and we get at least $|E|+1$ paths. This is true for any graph. Not all graphs can be directed like described so that the the number of up-paths equals the minimum possible. Let's first analyze what directions we have to introduce, so that the number of up-paths is equal to the minimum possible, i.e. $ |E|+1$. Suppose we can make a configuration like that. There must be only one root, otherwise the up-paths would be more than needed. Further, starting from that root and following the directions, there do not exist two paths from the root to the same vertex, unless this vertex has only in-bounded edges. Let $ I$ be the set of all those vertices with only in-bounded edges. If we remove $ I$, (and the incident edges) the remaining graph is a directed tree. Moreover, $ I$ must be independent set of vertices, because it's impossible an edge between two vertices of $ I$ to exists. The conclusion is: A graph $ G$ (the undirected one) must admit a decomposition into a tree $ T$ and a set $ I$ of independent vertices in order the number of up-paths be the possible minimum. On the other hand, if we can do this, we can direct edges as needed. Indeed, take a root of $ T$ and direct its edges from this root to the leaves. Next, direct the edges, that connect $ T$ and $ I$, from $ T$ to $ I$. Apparently, our original graph admits a decomposition into a tree and independent vertex-set. One can find further comments on what kind of graphs can be partitioned like that here: Three Graph Problems on this year's IMO?!

Hello, I'm the author of the problem. I'll show you an alternate approach to proving the lower bound if one can't see the significance of looking at adjacent pairs right away. Let us create a Serbian board depicting the number of uphill paths that end in the corresponding field on the Nordic board. We are of course looking for the minumum sum of entries on the Serbian board. We will fill the Serbian board in the increasing order of the values of the corresponding fields on the Nordic board. We notice the following: 1) A $1$ will be written for each valley. 2) For each non-valley, we will write the sum of all already-written numbers on adjacent fields, since paths ending in that field can only come from extending paths that ended in adjacent fields of lower value. Taking the second point into account, it follows that we can decompose the sum of non-valley numbers as follows: for each pair of adjacent fields we select the smaller number (or either if equal) and sum the selected numbers across all pairs. The smallest sum of non-valley numbers is thus equal to the number of pairs $2n(n-1)$, since each number on the Serbian board is at least $1$. The smallest sum of valley numbers is $1$, since there is at least one valley, corresponding the the entry $1$ on the Nordic board. Thus, the sum of entries on the Serbian board is at least $2n(n-1)+1$. This approach very clearly indicates the conditions needed to achieve equality: There is only $1$ valley, the set of all $1$s on the Serbian board form a tree with the root in that valley and the remaining entries are exclusively adjacent to $1$s, i.e. no two such entries are adjacent to each other. The tree I found and used in the official solution is essentially the one talkon presented here.

Here is for $n = 17$ a valid tree such that for every $m < n$ its upper left $m \times m$ truncation is also a valid tree. It is straightforward to extend its systematics ad infinitum. In this sequence of trees thus every $n$-tree is obtained by extending in a systematic way the $(n-1)$-tree at the bottom and on the right. I leave it to the community to describe the systematics formally and prove that all requirements are met. X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

The answer is $2n^2 -2n +1$. It is not difficult to find the examples, so I will only prove that the number of uphill paths is not less than $2n^2-2n+1$. First, we can think about an easy dynamic programming by an array $dp$[number in each cell]. Initially set the values of the valleys to $1$ (otherwise $0$). Then in increasing order, calculate the value as the summation of the values of adjacent cells. The number of uphill paths $N$ is the summation of all values. For each cells, let $d_i$($i$ is a number in that cell) be the number of adjacent cells which has smaller number than $i$. Since all values in $dp$ are positive integers, we can say that $dp[i] \geq d_i$ for all cells except the valleys. $\therefore N=\displaystyle\sum_{i=1}^{n^2}dp[i]=n^2+\displaystyle\sum_{not\:valley}(dp[i]-1)\geq n^2+\displaystyle\sum_{not\:valley}(d_i -1)=n^2+\displaystyle\sum_{d_i \geq 2}(d_i -1)$ Now, let's think about a graph with $n^2$ vertices which the edges are connecting adjacent cells. Then, I will remove all vertices which satisfy $d_i \geq 2$. The remaining graph $G$ consists of cells such that $d_i\leq 1$. Hence, if we remove all vertices in $G$ one by one in decreasing order, the number of edges cannot decrease more than $1$. It means that $G$ is a union of trees. Thus, if $v$ and $e$ is the number of vertices and edges in $G$ respectively, $e\leq v-1$. The number of cells such that $d_i \geq 2$ is $n^2-v$, and the summation of $d_i$ for cells such that $d_i \geq 2$ is $2n(n-1)-e$. $\therefore N\geq n^2+\displaystyle\sum_{d_i \geq 2}(d_i -1)=n^2+(2n(n-1)-e)-(n^2-v)=2n(n-1)-(e-v)\geq 2n^2-2n+1$.

@NZP_IMOCOMP4, #12. What is a Serbian board?

neergard wrote: @NZP_IMOCOMP4, #12. What is a Serbian board? The original name of a Nordic square, probably. The problem was proposed by Serbia, so...

GianDR wrote: The original name of a Nordic square, probably. NZP_ IMOCOMP4 uses both terms; so there seems to be a distinction: "We will fill the Serbian board in the increasing order of the values of the corresponding fields on the Nordic board."

The Answer of the Problem is $2n(n-1) +1$. Same Solution : Lets prove the number of uphill paths not less than $2n^2-2n+1$. Think about a dynamic programming by an array $dp$[number in each cell]. The set the values of the valleys to $1$ (otherwise $0$) initially . Then in increasing order, calculate the value as the summation of the values of adjacent cells. The number of uphill paths $N$ is the summation of all values. For each cells, let $d_i$($i$ is a number in that cell) be the number of adjacent cells which has smaller number than $i$. Since all values in $dp$ are positive integers, we can say that $dp[i] \geq d_i$ for all cells except the valleys. $\therefore N=\displaystyle\sum_{i=1}^{n^2}dp[i]=n^2+\displaystyle\sum_{not\:valley}(dp[i]-1)\geq n^2+\displaystyle\sum_{not\:valley}(d_i -1)=n^2+\displaystyle\sum_{d_i \geq 2}(d_i -1)$ Think about a graph with $n^2$ vertices which the edges are connecting adjacent cells. Then, we shall remove all vertices which satisfy $d_i \geq 2$. The remaining graph $G$ consists of cells such that $d_i\leq 1$. Hence, if we remove all vertices in $G$ one by one in decreasing order, the number of edges cannot decrease more than $1$. It means that $G$ is a union of trees. Thus, if $v$ and $e$ is the number of vertices and edges in $G$ respectively, $e\leq v-1$. The number of cells such that $d_i \geq 2$ is $n^2-v$, and the summation of $d_i$ for cells such that $d_i \geq 2$ is $2n(n-1)-e$. $\therefore N\geq n^2+\displaystyle\sum_{d_i \geq 2}(d_i -1)=n^2+(2n(n-1)-e)-(n^2-v)=2n(n-1)-(e-v)\geq 2n^2-2n+1$.

neergard wrote: @NZP_IMOCOMP4, #12. What is a Serbian board? I said: ''Let us create a Serbian board depicting the number of uphill paths that end in the corresponding field on the Nordic board.'' So if the Nordic board was $(12)(34)$, the corresponding Serbian board would be $(11)(12)$ since each field in the Nordic square has one uphill path ending in it, $1,12,13$ except $4$ which has two uphill paths ending in it: $124$ and $134$.

NZP_IMOCOMP4 wrote: neergard wrote: @NZP_IMOCOMP4, #12. What is a Serbian board? I said: ''Let us create a Serbian board depicting the number of uphill paths that end in the corresponding field on the Nordic board.'' So if the Nordic board was $(12)(34)$, the corresponding Serbian board would be $(11)(12)$ since each field in the Nordic square has one uphill path ending in it, $1,12,13$ except $4$ which has two uphill paths ending in it: $124$ and $134$. I see. You define a "Serbian" square/board derived from the Nordic one. Both are $n \times n$ boards. Just the entries are different. Thank you for this clarification.

Nice problem! Did a video that also gave a bit of motivation on how to arrive at the construction: https://www.youtube.com/watch?v=-AII0ldyDww

Very nice problem! However I don't feel good about the marking scheme being 3+4 where 3 points are given for the whole understanding and analysis of the problem that proves the lower bound and concludes that it is sufficient to find a partition into a tree and an independent set and 4 points are for actually showing such tree. The last part is nothing really deep, just some playing on the paper. I don't want to say it's easy, but I definitely felt more satisfaction through unraveling the true meaning of this problem rather than finally finding that tree.

Swistak wrote: Very nice problem! However I don't feel good about the marking scheme being 3+4 where 3 points are given for the whole understanding and analysis of the problem that proves the lower bound and concludes that it is sufficient to find a partition into a tree and an independent set and 4 points are for actually showing such tree. The last part is nothing really deep, just some playing on the paper. I don't want to say it's easy, but I definitely felt more satisfaction through unraveling the true meaning of this problem rather than finally finding that tree. I might misremember this, but I was told that the marking scheme was 1+4 (1 for the lower bound, 4 for construction, but both parts add to a 7).

MarkBcc168 wrote: Swistak wrote: Very nice problem! However I don't feel good about the marking scheme being 3+4 where 3 points are given for the whole understanding and analysis of the problem that proves the lower bound and concludes that it is sufficient to find a partition into a tree and an independent set and 4 points are for actually showing such tree. The last part is nothing really deep, just some playing on the paper. I don't want to say it's easy, but I definitely felt more satisfaction through unraveling the true meaning of this problem rather than finally finding that tree. I might misremember this, but I was told that the marking scheme was 1+4 (1 for the lower bound, 4 for construction, but both parts add to a 7). Nah, I've just looked to ensure. In short it is 1+2+4, where 1 is for the lower bound, 2 for stating what kind of constructions will achieve lower bound (i.e. "tree+independent set" or some equivalent way) and 4 for actually finding that tree.

Beautiful problem. From every non-valley we can go downhill, i.e. to the adjacent cell with less number, etc. until we get stuck in valley. Since one of two numbers in any adjacent pair is less, this pair is matched to at least one uphill path as it's topmost. Also cell $1$ is definitely a valley and so is an uphill path, so the number of such paths is at least $2n(n-1)+1.$ To prove that this is the answer it's suffice to provide a Nordic square with exactly one valley; no different uphill paths with common pair of topmost cells. Firstly consider a graph with edges between adjacent cells; let's paint all cells black and white in such way, that no two black cells are adjacent and white cells forms a tree, as a generalization of the following diagram. [asy][asy] unitsize(16); for(int x = 0; x < 9; x=x+2){ if(x!=4){ for(int y = 1; y < 9; y=y+2){ fill((x,y)--(x+1,y)--(x+1,y+1)--(x,y+1)--cycle, black); } } } for(int x = 3; x < 6; x=x+2){ for(int y = 2; y < 9; y=y+2){ fill((x,y)--(x+1,y)--(x+1,y+1)--(x,y+1)--cycle, black); } } for(int i = 0; i < 10; ++i){ fill((4,0)--(5,0)--(5,1)--(4,1)--cycle, black); draw((i,0)--(i,9)); draw((0,i)--(9,i)); } [/asy][/asy] For case $n\equiv 0 \pmod 3$ take the coloring of full square. For case $n\equiv 2 \pmod 3$ remove from square the leftmost column and the upmost row. For case $n\equiv 1 \pmod 3$ remove both leftmost and rightmost columns and two upmost rows. Now put $1$ in any white cell; until there left a non-empty white cell which has empty white among adjacent, put in this adjacent cell the least number which haven't been used yet. Put remaining numbers in black cells arbitrary; then all cells except $1$ are adjacent with at least one white cell with less number, so the first condition holds. Moreover, for any adjacent pair the one with less number is white and there is exactly one downhill path from it (by edges of tree) to valley, so construction satisfies the second condition $\blacksquare$

I think that the sub-problem of proving the existence of a partition into an independent set is exceptional for being easy to explain to a wide audience, with many examples for small n. I have attached a construction based on diagonals that are 3 apart. Convention: black squares indicate the independent set.. The squares are for n=10, 11, 16, and 17. There are details in which the constructions for (6m+4) and (6m+5) are slightly different. It also turns out that there exists an infinite pattern such that a correct construction for n=k is found by cropping the top-left k-by-k square, except for k=6m+4 in which case 1 black and 1 white square need to be switched in the lower left corner, and similarly for the upper right corner. Besides an explicit construction, I found it fun to make a more difficult construction, which was the first method that I tried and took me several hours to complete. In this construction method, we aim to take a known construction for n=k and make constructions for n=2k-1 and n=2k. The former case is much easier. In order to do this, start with the n=k construction. Then insert one column of white squares in between each pair of columns, but not to the left or to the right, resulting in a grid with k rows and 2k-1 columns. Then insert one row of white squares in between each pair of rows, resulting in a 2k-1 square grid. Then, for each square whose row number and column number (1-indexing) are both even, color that black. I will not write a formal proof of this construction. Roughly, if we assume that there is a cycle among white squares for contradiction, then this cycle must move in the orthogonal directions an even number of squares at a time, and it would yield a cycle among white squares for the n=k grid, a contradiction. Note that repeating this construction k to 2k-1 yields Sierpinski-like patterns. The n=2k construction is much harder. There is an initial phase of construction in which we construct an independent set and tree, but their union is exactly three squares less than the entire square grid, or only n^2 - 3 squares. Then, there are several cases identified, and I state rules for each case for how to extend the construction to the entire n^2 - 3 square. For all but one of these cases, the adjustment is by adding either 0 or 1 squares to the independent set, and the other 3 or 2 to the tree. For one case, up to k-3 squares need to be adjusted, depending on the exact nature of the n=k construction. I have attached a PDF of this solution. I think that in principle, there are many ways to construct independent sets and that you could get very complicated patterns.

The first question is how to count the uphill paths. Let's count how many uphill paths conclude at each particular cell. At the cell labelled with $1$, it is $1$, and at every further cell, it is the sum of its neighbors with smaller labels. For instance, in the process of calculating these numbers, no value other than $1$ appears while each cell has at most neighbor before it. This recursive pattern reminds me of the following problem. If there are $n-1$ cells in an $n\times n$ board colored red, and then repeatedly, cells with at least two red neighbors become red, then the entire board cannot end up red. The reason for this is that the perimeter does not increase in the process. At first, it is at most $4(n-1)$. In the end, it would have to be $4n$. This is a contradiction. Whenever a new valley appears, the perimeter increases by $4$. Let this occur $a$ times. Whenever a new cell with one neighbor before it appears, the perimeter increases by $2$. Let this occur $b$ times. Similarly, for $2$, $3$, $4$ preceding neighbors, let the number of occurrences be $c$, $d$, $e$, respectively. Therefore, as the perimeter increases from $0$ to $4n$, $4a+2b-2d-4e=4n$, so $2a+b=2n+d+2e$. This provides a means for deducing a lower bound for $U$, the number of uphill paths. This is because a cell with $2$, $3$, $4$ preceding neighbors has at least $2$, $3$, $4$ uphill paths concluding at it. It follows that $U\ge a+b+2c+3d+4e$. However, $a+b+c+d+e=n^2$ equals the number of cells. Now $U-2n^2\ge -a-b+d+2e=a-2n$, due to the perimeter equation. Hence, $a\ge 1$ implies $U\ge 2n^2-2n+1$. Equality is reached in the lower bound if and only if there is exactly one valley and the cells with value more than $1$ never share an edge. There are many ways this could happen, and the image shows a way to accomplish this by starting to fill the first two columns, and then every third row, and then the rows in between alternately.

1. Bound We claim that the minimum number of uphill paths is $2n(n-1)+1$. Notice that from any square that is not a valley, we can always walk "downhill" until we reach a valley in a variety of different ways. This implies that every pair of adjacent squares has the possibility of being the last two squares in an uphill path with a length of at least 2. Notice that each valley in itself is also an uphill path, meaning that we must add at least $1$ to the number of pairs of adjacent squares (there must be at least one valley, since $1$ must be a valley). Since there are $2n(n-1)$ pairs of adjacent squares, we have at least $2n(n-1)+1$ uphill paths, proving our lower bound. 2. Definitions In a Nordic square, define an "arrow graph" as follows - - There is a directed arrow between every pair of adjacent unit squares in the Nordic square, - and the arrow points from the square labeled with the smaller number to the square labeled with the larger number. In Nordic squares, there are also many different "types" of squares, which we define as follows - - A "valley", or a unit square in which all of its arrows are pointing outwards, or away from the unit square, - A "summit", or a unit square in which all of its arrows are pointing inwards, or towards the unit square, - and a "directional", or a unit square with exactly one of its arrows pointing inwards, or towards the unit square. In a directional square, there are different types of directional squares, characterized by one defining feature - - A directional square "points" in a direction if its one arrow that points inwards towards the directional square points in that direction. 3. Construction - Odd $n$ First note that if such a Nordic square exists such that we have $2n(n-1)+1$ uphill paths, then we must have an "arrow graph" with exactly one "valley", and every other unit square must either be a "summit" or a "directional". We call such an arrow graph for such a working square to be "one-way". 3a. Arrow Construction, $n<7$ First, to begin induction, we claim that there is such an arrow graph for $n=3$, $n=5$, and $n=7$. 3b. Arrow Construction, $n>7$ Now we claim that from a "one-way arrow graph" for a $(2k-1)\times{}(2k-1)$, we can construct another $(2k+1)\times{}(2k+1)$ "one-way arrow graph". This can be done by "expanding the outer shell" of the previous square to create an empty "frame" with the $(2k-1)\times{}(2k-1)$ square in the center. Note that since the squares must all be "directionals" or "summits", the arrows pointing from the inner square to the outer square are fixed. Now, if we fix the top left corner as a summit, the remainder of the top row and left columns will be fixed as a result. Next, we continue along the graph, fixing the corner squares with the following rules - If all corner unit squares are empty, choose the top left corner square and label it as a directional in any direction you choose. - If a corner square currently has no arrows labeled yet, unless all other corner squares are also empty, do not label it yet. - If a corner unit square is labeled with one arrow pointing away from it, you must label the other arrow to be pointing towards it, or else it will end up as a valley. - If a corner unit square is labeled with one arrow pointing towards it, label the other arrow to be pointing away from it. In this way, the graph will be fixed, proving that there is such an arrow graph construction. 4. Construction - Even $n$ In order to get a "one-way arrow graph" for $n=2k$, simply take the $(2k)\times{}(2k)$ square with the same top right corner as the top right corner of the $(2k+1)\times{}(2k+1)$ construction to get the arrow graph. This should not have any valleys in it, since in our induction strategy, there are no directional squares that point from the outer square shell to the inner-square shell, meaning it works. 5. Arrow Graph to Nordic Square A pair of "non-interacting" paths is a pair of two paths such that you cannot walk from one path onto the other legally. The arrow graph should be able to be split into four distinct, non-interacting, paths originating from the center, as shown in the diagram (example $n=11$), and several summits. Begin by labeling the summits from $n^2$ to $n^2-k+1$ in any order, where $k$ is the number of summits. Then, obviously we must label the valley with $1$, and the numbers surrounding $1$ with $2$, $3$, $4$, and $5$, in any order. Finally, work your way down the four paths, in the order directed by the arrows, and label the paths with the numbers accordingly. An example is shown below for $n=11$. $\blacksquare{}$

I think the problem is origined from an earlier one, but I cannot remember it.

Fun problem, reminds me a little of this problem: https://artofproblemsolving.com/community/c6h2220242 . Ah, nostalgia Answer is $n^2 + (n-1)^2$. We say a unit square can be "sponsored" by a $2 \times 2$ square if it is the largest element in that square. Notice every square has at least one uphill path ending there (walking downwards), and if it is not a valley the number uphill paths ending there is exactly the sum of its smaller neighbor's numbers. Now subtract one from the number of every uphill paths at every cell to obtain its thickness. Create a bipartite graph whose left vertices are $2 \times 2$ squares and right vertices are cells. I claim we can make a map from the left to the right such that the thickness of every cell on the right is at least the size of its preimage in this map. Suppose there is a contradiction with minimal number of violating cells. Notice that if the cell has $1, 2, 3$ sponsors mapping to it then it must have at least $2, 3, 4$ smaller neighbors respectively, so there cannot be contradiction since it is not a valley. The only counterexamples arise when the cell has $4$ sponsors mapping to it, i.e. it is the biggest cell in its $3 \times 3$ neighborhood. However notice that one of the corner cells in this neighborhood must be the second biggest in its $2 \times 2$ cell, as otherwise there are at least $8$ uphill paths ending at the center cell. Then we can simply assign one of the sponsors of the contradicting cell to said example, which eliminates exactly one violating cell. This violates minimality of the counterexamples, so it follows that such a mapping is indeed constructible. This finishes immediately as we can double count the number of sponsorships to obtain a minimum of $n^2$ natural uphill paths (subtracted away to obtain thicknesses) together with $(n-1)^2$ uphill paths from the sponsorships. Now we show this bound is optimal. We perform strong induction with special restrictions on the claim that become evident in the construction. The base case $n = 1$ is trivial. First label each cell with its coordinates, describing its row and column respectively. Now delete every cell whose coordinates are both even, and promise every cell with one even and one odd coordinate will not be deleted. It follows that paths between the remaining cells with both coordinates odd are bijectively mapped to paths between the reduced grid where only the cells with both odd coordinates are kept. (size is half of the big grid). Thus it follows that the set of not deleted cells form a tree if and only if the set of not deleted cells form a tree in the reduced grid. Here, we utilize our inductive hypothesis that the smaller reduced grid has such a construction using such a tree that is optimal, and no two deleted cells are adjacent. This is the special condition in the induction which is clearly maintained. Now I claim this construction is optimal: We simply take all the non-deleted cells and assign them the Nordic numbers $1, 2, 3, \ldots$, so it is clear that since they form a tree, each one has exactly one uphill path. Now we fill in all the remaining deleted cells. By the inductive hypothesis, no two are adjacent, so each has a number of uphill paths ending there exactly equal to its degree. The total number of uphill sums is simply the sum of all the uphill paths ending at any given cell. By the inductive hypothesis, the cells with both odd coordinates contribute exactly $(\lceil n/2 \rceil)^2 + (\lceil n/2 \rceil - 1)^2$ to this sum, the cells with one odd and one even coordinate contribute exactly $\lfloor n^2/2 \rfloor$ to the sum, and the cells with both even coordinates contribute $(\lfloor n/2 \rfloor)^2 \cdot 4$ to the sum when $n$ is odd and $n^2 - n$ when $n$ is even (just count their degree, they are $4$ everywhere except the right and bottom edges, where they are $3$ at and $2$ for the bottom right corner). When $n$ is even, we have: $$\frac{n^2}{4}+\frac{n^2-4n+4}{4} + \frac{2n^2}{4} + \frac{4n^2 - 4n}{4} = \frac{8n^2-8n+4}{4} = n^2 + (n-1)^2$$ When $n$ is odd, we have: $$\frac{n^2+2n+1}{4}+\frac{n^2-2n+1}{4} + \frac{2n^2 - 2}{4} + \frac{4n^2 - 8n + 4}{4} = \frac{8n^2-8n+4}{4} = n^2 + (n-1)^2$$ Thus the induction finishes in all cases, so the bound is exact.

Surprisingly, my construction is apparently not the most common. I think it's much more fun/interesting. As suggested by an onlooking friend who doesn't do math competitions at all (!), we generalize to $m \times n$ boards (containing integers from $1$ to $mn$). The answer is then $m(n-1)+n(m-1)+1=2mn-m-n+1$. Draw a graph with cells as vertices and connect adjacent cells with an edge pointing from larger to smaller. A valley is a cell with indegree $4$, and by reversing uphill paths we are being asked to count the number of edge-following paths that end at a valley. Note that there exists such a path starting with every edge, and there's also a path containing a single vertex for every valley. Since there are exactly $m(n-1)+n(m-1)$ edges and at least one valley (namely $1$) the bound follows. Now note that equality holds in our proof of the bound when there is a single valley and every edge produces a unique path to this valley. Claim: We are done if we can color a set of non-adjacent cells whose complement is a tree. Proof: If we have such a coloring, then arbitrarily place $1$ in the tree and perform DFS (or BFS) from this cell (only on uncolored vertices, i.e. those in the tree), marking cells in the order they're visited. Within the tree, there is then a single valley and a unique path from each cell to this valley. Then place the rest of the numbers arbitrarily in the colored cells. Every edge points to a cell in the tree, so every edge induces a unique path to the unique valley. $\blacksquare$ Now we employ the following construction. WLOG let $m \geq n$ (i.e. we have at least as many rows as columns)—the reason we do this is that, informally, it ensures that our diagonals reach the right side of the grid by the time they reach the bottom. We start with a purple square in the top left corner, then fill in the dark gray diagonals, alternating between the blue and green ways of filling out the left two columns. When we reach the bottom we switch to the other side (using the red square to preserve tree-ness). More concretely, this should occur with the last diagonal that's fully present and doesn't start on the bottom row. Then we continue diagonals in the same way (shown in normal gray) and alternate between green and blue as before, this time starting from green. The one exception is in the case where we'd end up putting a blue cell on the second-rightmost cell of the bottom row, and there would be a blue cell two above it. In this case, we place the purple cell instead, mimicking the start. Examples where our second purple cell isn't placed is shown below. This finishes the problem. $\definecolor{dg}{RGB}{68,68,68}\fcolorbox{dg}{dg}{\rule{0pt}{2pt}\rule{2pt}{0pt}}$ $\definecolor{lg}{RGB}{153,153,153}\fcolorbox{lg}{lg}{\rule{0pt}{2pt}\rule{2pt}{0pt}}$ $\definecolor{p}{RGB}{204,153,255}\fcolorbox{p}{p}{\rule{0pt}{2pt}\rule{2pt}{0pt}}$ $\definecolor{r}{RGB}{255,163,163}\fcolorbox{r}{r}{\rule{0pt}{2pt}\rule{2pt}{0pt}}$ $\definecolor{lb}{RGB}{192,224,255}\fcolorbox{lb}{lb}{\rule{0pt}{2pt}\rule{2pt}{0pt}}$ $\definecolor{g}{RGB}{179,255,179}\fcolorbox{g}{g}{\rule{0pt}{2pt}\rule{2pt}{0pt}}$ Remark: This construction is motivated by the following heuristic: blocking things with a bunch of colored cells forming a wall is nice, since to make the tree simple I probably want long branches that don't split. However I cannot make a wall the easy way because I can't have adjacent colored cells. So instead I make walls diagonal. If you look at the more common and simpler construction, this principle is used as well, except the walls are vertical and constructed differently.

Let $G$ be the arrows graph of the grid where $a \to b$ if $a$ and $b$ are adjacent with $a<b$. Bound: We will show that for each pair of consecutive cells, there exists at least one uphill path ending at those cells. Assume for contradiction that no such path exists. Then we can reverse the direction of all the arrows so that we have an infinitely long sequence of decreasing numbers, which is impossible. Thus, there are at least $2n(n-1)$ paths with length at least $2$. Note that there is at least one path of length $1$: simply take $\{1\}$. This results in at least $2n(n-1)+1$ total uphill paths. Construction: The key idea is that we can shade several cells grey so that if those cells were to be deleted from $G$, then the resulting graph is a tree with root $1$. (Thus, no two grey cells can be adjacent.) Furthermore, we can assign the largest numbers to grey cells. This would imply the equality case in the bound: given two vertices $a \to b$, there is exactly one uphill path ending with $a, b$, because all vertices except $1$ have indegree exactly $1$, and similar logic shows this for all adjacent pairs $(a, b)$ with $a<b$, $a$ unshaded, and $b$ shaded. Construction for shading: There is a generalizable coloring that exists for each $n$ based off of its residue modulo $3$. [will add in future] It is easy to see in this construction that there exists a tree formable by placing arrows between unshaded cells. Construction for labeling: Perform DFS on the tree $T$ from the construction for shading, where the numbers $1$ through $|V(T)|$ are assigned to the unshaded cells, and randomly assign numbers between $|V(T)|+1$ and $n^2$, inclusive to the shaded cells. It is clear that this labeling works. Thus the construction is complete.

Solved with MathLuis. We initially got a atrociously wrong construction which I then somehow managed to fix with some extensive patching up. This solution is pretty long. Here goes! The answer is $N(n)=2n^2-2n+1$, where $N(n)$ is the minimum number of uphill paths in a $n\times n$ Nordic Square. Let a downhill path be a set of cells, which satisfy the same properties as an uphill path but are in the opposite order (from largest to smallest ending in a valley). We start off by proving the bound. Claim : For all $n\in \mathbb{N}$, we have $N(n) \geq 2n^2 - 2n+1$. Proof : Consider a pair of orthogonally adjacent cells, $c_1$ and $c_2$. WLOG, assume $c_1 < c_2$. Then, since every cell in a square has atleast 2 neighbours, $c_1$ must have neighbours besides $c_2$. If they are all less than $c_1$, then $c_1$ is a valley. Else we move from $c_1$ to this smaller cell $c_3$. Now, similarly, we can find a downhill path starting from $c_2$ passing through $c_1$ and reaching some valley $v$. Now, it is clear that tracing out this path $v \to \dots \to c_1 \to c_2$ is an uphill path. Further, if we consider the uphill path thus generated by any other pair of cells $c_1'< c_2'$, we have 2 cases. Case 1 : $c_2'=c_2$. Then, in order for the pair $(c_1,c_2)$ to be distinct from $(c_1',c_2')$ we must have $c_1 \neq c_1'$. Thus, the resulting uphill paths are distinct (since their second last cells are different). Case 2 : $c_2' \neq c_2$. This case is immediately clear that the resulting uphill paths are different since they have different end points. Thus, the uphill paths thus created by each pair of cells are distinct from each other. This means we have atleast $2n(n-1)$ (the number of pairs of cells in an $n \times n$ grid) uphill paths of length $l \geq 2$ and atleast 1 uphill path of length 1 (since 1 is obviously a valley). Thus, we have that \[N(n) \geq 2n(n-1)+1=2n^2-2n+1\]as claimed. Now we can look at the construction. We start off with some definitions. Let a $T$-tetromino be a structure composed of 4 cells in the shape of a $T$ and a $C-$pentomino be a structure composed of 5 cells in the shape of a $C$. Let a T-polytetromino of order n be a structure formed by connecting $n$ $T-$tetrominoes where the leg of each tetromino is placed on the middle square of the top of a tetromino. For example, $T-$polytetrominoes of orders 1, 2 and 3 are given below. A $T-$polytetromino is called upright if the top (part with 3 cells) is on the top, while it is called inverted if the leg (part with a single cell) is on the top. Now, we divide the construction into 6 cases. We start off by giving a tiling on the $n\times n$ Nordic square. Case 1 : $n=6k$ for some positive integer $k$. We place an inverted $T-$polytetromino of order $3k-1$ at the top-left hand corner. Then, we alternate between upright and inverted $T-$polytetrominoes of order $3k-1$ to fill up the top $6k-2$ rows. Then, in the last two rows. below each inverted $T-$polytetromino we place a $T-$tetromino and below each upright one we place a $C-$pentomino. For example, the tiling for a $12\times 12$ board is given below. Case 2 : $n=6k+1$ for some positive integer $k$. Here, we place an upright $T-$polytetromino of order $3k$ on the top-left corner, and alternate between inverted and upright as before. Then, for the bottom row, we place a rod tromino below every upright $T-$polytetromino and two single cells (monominoes) underneath every inverted one (adjacent to the right and left cells). Then, for the last column, we place rod trominos keeping a gap of 1 cell between each tromino, except for the last 3 cells. If this $k$ is odd, for the last 3 cells, we place a domino leaving the bottom-right cell untiled. When $k$ is even, we place an extra monomino on the bottom-right corner to finish. For example, the tilings for a $7\times 7$ Nordic Square and a $13\times 13$ Nordic Square are given below. Case 3 : $n=6k+2$ for some positive integer $k$. Here, we start with a inverted $T-$polytetromino of order $3k$ and alternate like before. For the bottom two rows, we place a $T-$tetromino below every inverted $T-$polytetromino and a $C-$pentomino below each upright one. For the rightmost two columns, we place $3k+1$ $L-$trominos. For example, the tiling for a $8\times 8$ board looks like this. Case 4 : $n=6k+3$ for some positive integer $k$. Here, we start with an upright $T-$polytetromino of order $3k+1$ and alternate as before. For the bottom row, we place a rod tromino below every upright $T-$polytetromino while we place two monominoes below each inverted one. For example, this tiling for a $9 \times 9$ board looks as follows. Case 5 : $n=6k+4$ for some positive integer $k$. Here, we place an inverted $T-$polytetromino of order $3k+1$ at the left most side of the board and switch between upright and inverted $T-$polytetrominoes like before. Then, for the bottom two rows, we place a $T-$tetromino below every inverted $T-$polytetromino and a $C-$pentomino below every upright one. This leaves the rightmost column. For this, place rod trominos starting from the top. if $k$ is even this completely tiles the board. If $k$ is odd, we can simply place a domino on the bottom-right corner two squares. For example, the tilings for a $10\times 10$ and $16 \times 16$ Nordic Square look as follows. Case 6 : $n=6k+5$ for some positive integer $k$. Here, we place an upright $T-$polytetromino of order $3k+2$ at the top-left corner and alternate between upright and inverted as before. For the bottom row, we place a rod tromino below every upright $T-$polytetromino while we place two monominoes below each inverted one. For the rightmost 2 columns, we place $3k+2$ $L-$trominos for the first $6k+4$ rows and then, place a single monomino on the cell left to the bottom-right corner, which is left untiled. For example, the described tiling for a $11 \times 11 $ board looks like this. Now, we describe the construction. Simply take a $n\times n$ Nordic Square which has been tiled as described above and place the number 1 on the top-left most square which has been tiled (or colored as we will refer to in what follows). Then, we recursively place each new number. Say we want to place a number $1<k\leq n^2$. The number $k$ can be placed in any square which is adjacent to some square in which a number has already been placed. For example, 2 can only be placed on the square neighboring 1, while 3 will have 2 possible positions for its placement. Continue likewise until all colored squares have been filled with the smaller numbers. Then, place all the remaining larger numbers as you wish in the uncolored squares. To show this works, we introduce the notion of a value matrix. A value matrix of order $n\times n$ is a matrix consisting of $n^2$ numbers in $n$ rows and columns, where the value assigned to each cell $i,j$ of the matrix is equal to the number of downhills paths starting from the cell $(i,j)$ of the $n \times n$ Nordic Square. In order for equality to hold in our bound, there must be exactly 1 valley and each pair of orthogonally adjacent squares must have exactly one downhill path which passes from these two cells to the unique valley. The first criterion is automatically confirmed by the nature of our construction. The smaller numbers are placed such that each number is adjacent to some number less than it and then larger numbers are placed in cells which are covered by only smaller numbers to them, by the nature of our tiling. Now, we note that the value of the cells of the value matrix depends on on the value of the cells corresponding to squares of the Nordic Square with numbers less than it, by the definition of a downhill path. Thus, the value matrix is filled recursively depending only on the value of its neighbours with a lesser number than it in the Nordic Square. Converting the second equality condition into the language of our value matrix, we note that we must never have two entries of the value matrix which are greater than 1 and orthogonally adjacent. We prove inductively that the value of each cell which is colored is 1. Clearly, 1 which is on a colored square has value 1. Say the cells which have the numbers $1,\dots , k$ have value 1. Then, the number $k+1$ is placed on a colored square $S$ which is adjacent to one of these cells. Say this square was adjacent to two squares in which numbers have already been placed. Then, these two neighboring cells are clearly not adjacent. Thus, there must exist two distinct tracks of colored squares (since we place numbers only on them) leading to $S$. But, by the nature of our tiling this is clearly impossible. Thus, $k+1$ is also placed on a square which acquires a value of 1 in our value matrix. Thus, we see that all colored squares have value 1. By the nature of our tiling every pair of adjacent squares have atleast one square which is tiled, and thus, every pair of orthogonally adjacent cells of the value matrix are forced to have atleast 1 cell of value 1 which confirms that the equality case indeed holds. Thus, this construction must work, and we are finally freaking done. Remark : Actually the value matrix can be completely removed here, but it's much easier to think about the problem using them. It involved much of the intuition along this solution so we include it anyways.

The answer is $2n(n-1)+1$. First, we'll prove that there are at least $2n(n-1)+1$ uphill paths. We'll accomplish this by showing that for any two adjacent squares, of which there are clearly $2n(n-1)$, there is a uphill path whose last two terms are a permutation of the two adjacent squares. Let our uphill path be have the first cell as $C_k$, second cell as $C_{k-1}$, and so on, with the last cell being $C_1$, where the entire path has length $k$. Then let $C_1$ and $C_2$ be the two adjacent squares and for each $i\ge 2$, choose $C_{i+1}$ so that $C_{i+1}$ is adjacent to $C_i$ and whose value is smaller than $C_i$. If $C_{i+1}$ does not exist then let $k=i$. This is an uphill path because $C_i$ is a valley. However, there are also uphill paths with only one term, which the previous does not account for, and the only such path is the one with only $1$. Now, we provide a construction. Our strategy for the construction will be as follows: color some of the squares blue in a way such that (i) the graph with vertices as blue squares and edges between vertices whose corresponding squares are adjacent is a tree. (ii) no two non-blue squares are adjacent. Let there be $b$ blue squares. Then, pick a single blue square to be a root and write $1$ in it. Then, write $2,3,4,\dots,b$ in the squares in any way that makes sure that if the path from a square $D$ to the root passes through $D'$ then the number in $D'$ is smaller than $D$. Then, write the number $b+1$, $b+2$, $\dots$, $n^2$ in the rest of the squares. It is easy to see why this strategy will result in a valid construction. For any blue square that isn't $1$, there is exactly one square adjacent to it whose value is less than it, and for any pair of starting cells, the smaller-valued one must be blue. Therefore, in constructing an uphill path that ends in these two squares, $C_1$, $C_2$, we are forced to choose a particular square $C_i$ for each $i$, until we get to the valley, so for each pair of cells, there is exactly one uphill path ending in them. Construction is left to reader as an exercise.

$ $

Also found a crack construction (though surprisingly I'm not the first to do so xd) We first recharacterize the way of finding the number of uphill paths by considering the following process. Have an empty $n \times n$ grid with each grid element empty or containing a number, potentially circled. Choose a square with no integer in it and circle it. We then place one plus up to the sum of the integers in the adjacent squares, and uncircle any circled adjacent squares. Repeat this $n^2$ times. Count the sum of the integers in all circled squares. Then consider placing $n^2, n^2-1, \dots, 1$ in the order of the squares circled. The integer in each square is the number of uphill paths starting at that square ignoring the valley condition, so the resulting sum is what is desired. Then the sum increases by $1$ for each placement, as well as by the amount in adjacent cells for each edge, and decrease for uncircled squares. Let $G$ be the grid, $n_c$ the number in each cell. As such, the sum ends up being \begin{align*} \sum_{c \in G} n_c \cdot \min(1 - f(c), 0) &= \sum_{c \in G} n_c \cdot \min(1, f(c)) - \sum_{c \in G} n_c f(c) \\ &= \sum_{c \in G} (n_c \cdot \min(0, f(c) - 1) + 1) \\ &\ge \sum_{c \in G} (f(c) + g(c)) \ge 2n(n-1) + 1. \end{align*}where $f(c)$ is the number of cells which are chosen after and adjacent to this cell and $g(c)$ is the indicator variable for $f(c) = 0$. We now want a construction which has exactly one valley and satisfies that if $f(c) > 1$, then $n_c = 1$. We thus want to find a coloring of black and white cells in $n \times n$ such that The graph of the black cells is a tree. The graph of white cells consists of disconnected singletons. Then we apply the algorithm with first choosing all white cells, then leaves of the black cells and so forth. Our construction works for $3k \times 3k$, with four $3 \times 3$ subgrids we which are a $H, +, D, \%$ as indicated in the diagram. [asy][asy] pen peh = purple+white; pen pep = green+white; pen ped = red+white; pen pepe = orange+white; int N = 4; filldraw(shift(0,0)*unitsquare, peh); filldraw(shift(0,1)*unitsquare, peh); filldraw(shift(0,2)*unitsquare, peh); filldraw(shift(1,1)*unitsquare, peh); filldraw(shift(2,0)*unitsquare, peh); filldraw(shift(2,1)*unitsquare, peh); filldraw(shift(2,2)*unitsquare, peh); filldraw(shift(N+1,1)*unitsquare, pep); filldraw(shift(N,1)*unitsquare, pep); filldraw(shift(N+2,1)*unitsquare, pep); filldraw(shift(N+1,0)*unitsquare, pep); filldraw(shift(N+1,2)*unitsquare, pep); filldraw(shift(0,2-N)*unitsquare, ped); filldraw(shift(0,0-N)*unitsquare, ped); filldraw(shift(2,0-N)*unitsquare, ped); filldraw(shift(0,1-N)*unitsquare, ped); filldraw(shift(2,1-N)*unitsquare, ped); filldraw(shift(1,0-N)*unitsquare, ped); filldraw(shift(1,2-N)*unitsquare, ped); filldraw(shift(0+N,2-N)*unitsquare, pepe); filldraw(shift(2+N,0-N)*unitsquare, pepe); filldraw(shift(0+N,1-N)*unitsquare, pepe); filldraw(shift(2+N,1-N)*unitsquare, pepe); filldraw(shift(1+N,0-N)*unitsquare, pepe); filldraw(shift(1+N,2-N)*unitsquare, pepe); [/asy][/asy] We then use the following construction which generalizes easily, and we can finish by taking a specific subgrid of it. [asy][asy] size(10cm); pen peh = purple+white; pen pep = green+white; pen ped = red+white; pen pepe = orange+white; void drawh(int i, int j) { filldraw(shift(0+i,0+j)*unitsquare, peh); filldraw(shift(0+i,1+j)*unitsquare, peh); filldraw(shift(0+i,2+j)*unitsquare, peh); filldraw(shift(1+i,1+j)*unitsquare, peh); filldraw(shift(2+i,0+j)*unitsquare, peh); filldraw(shift(2+i,1+j)*unitsquare, peh); filldraw(shift(2+i,2+j)*unitsquare, peh); } void drawplus(int i, int j) { filldraw(shift(i+1,j+1)*unitsquare, pep); filldraw(shift(i,j+1)*unitsquare, pep); filldraw(shift(i+2,j+1)*unitsquare, pep); filldraw(shift(i+1,j+0)*unitsquare, pep); filldraw(shift(i+1,j+2)*unitsquare, pep); } void drawd(int i, int j) { filldraw(shift(0+i,2+j)*unitsquare, ped); filldraw(shift(0+i,0+j)*unitsquare, ped); filldraw(shift(2+i,0+j)*unitsquare, ped); filldraw(shift(0+i,1+j)*unitsquare, ped); filldraw(shift(2+i,1+j)*unitsquare, ped); filldraw(shift(1+i,0+j)*unitsquare, ped); filldraw(shift(1+i,2+j)*unitsquare, ped); } void drawpe(int i, int j) { filldraw(shift(0+i,2+j)*unitsquare, pepe); filldraw(shift(2+i,0+j)*unitsquare, pepe); filldraw(shift(0+i,1+j)*unitsquare, pepe); filldraw(shift(2+i,1+j)*unitsquare, pepe); filldraw(shift(1+i,0+j)*unitsquare, pepe); filldraw(shift(1+i,2+j)*unitsquare, pepe); } int N = 8; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i + j == N) { drawd(3*i,3*j); } else if (i + j > N) { drawpe(3*i,3*j); } else if ((i + j - (N-1)) % 2 == 0) { drawplus(3*i,3*j); } else { drawh(3*i,3*j); } } } [/asy][/asy] which can be seen (and proven pretty boringly) to work.