
Problem 5. Ann and Max play a game on a $100 \times 100$ board.

First, Ann writes an integer from 1 to 10000 in each square of the board so that each number is used exactly once.

Then Max chooses a square in the leftmost column and places a token on this square. He makes a number of moves in order to reach the rightmost column. In each move the token is moved to a square adjacent by side or by vertex. For each visited square (including the starting one) Max pays Ann the number of coins equal to the number written in that square.

Max wants to pay as little as possible, whereas Ann wants to write the numbers in such a way to maximise the amount she will receive. How much money will Max pay Ann if both players follow their best strategies?

(Lev Shabanov)

Answer: 500000 coins.


Solution. Lower bound / Ann's strategy. First we will prove that Ann can get at least 500000 coins. Suppose Ann has arranged the numbers in the way depicted on the fig. 1 .

| 1 | 200 | 201 | 400 | $\cdots$ | 9800 | 9801 | 10000 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 2 | 199 | 202 | 399 | $\cdots$ | 9799 | 9802 | 9999 |
| 3 | 198 | 203 | 398 | $\cdots$ | 9798 | 9803 | 9998 |
| 4 | 197 | 204 | 397 | $\cdots$ | 9797 | 9804 | 9997 |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| 98 | 103 | 298 | 303 | $\cdots$ | 9703 | 9898 | 9903 |
| 99 | 102 | 299 | 302 | $\cdots$ | 9702 | 9899 | 9902 |
| 100 | 101 | 300 | 301 | $\cdots$ | 9701 | 9900 | 9901 |

Figure 1: for the solution of problem 5.

Consider a path constructed by Max. For every integer $1 \leqslant n \leqslant 50$ there are two squares of the path in the columns $2 n-1$ and $2 n$, respectively, which are adjacent by a move of the token. It is easy to see that the sum of the numbers in such squares is at least $200(2 n-1)$. We obtain that the cost of this path is at least $200(1+3+5+\ldots+99)=500000$ coins.

Upper bound / Max's strategy. Now consider an arbitrary arrangement of the numbers. Then exclude the square with the greatest number in each column. The least of the numbers in excluded squares is not less than 100, the second least is not less than 200 , etc, the greatest number in excluded square is 10000 . Hence, the sum of the excluded numbers is at least $100+200+\ldots+10000=505000$, while the sum of
numbers in the whole square is 50005000 . It means that the sum of the remaining numbers is at most 49500000 .

The 9900 squares which are left can be split into 99 distinct paths. The first path consists of the lowest squares in each column which are not excluded, the second path consists of the lowest squares in each column which are not excluded and not included into the first path, etc. The last path will include the uppermost squares in each column which are not excluded. It is easy to see that all 99 paths are proper paths that Max's token can follow, because any two squares in two adjacent columns either lie in the same row or in two adjacent rows.

The total cost of the constructed 99 paths is not greater than 49500000 , therefore one of these paths costs at most 500000 coins. Thus in every arrangement of numbers Max can pay less than or equal to 500000 coins.

We proved that Max can pay 500000 coins or less while Ann can make Max pay at least 500000 coins, so the answer is 500000 .

Alternate proof of the upper bound. Split our board into 50 horizontal rectangles $2 \times 100$. Since the sum of numbers in the whole board is 50005000 , it is possible to choose a rectangle with the sum of at most 1000100 . Take a square with the minimum number in each column of the chosen rectangle. These squares form a path from the square in the left column to the square in the right column; denote the cost of this path as $S$. In each column of the rectangle, the minimal number is less than the other number by at least 1 . Hence, the total sum of the numbers in the rectangle is at least $2 S+100$. It follows that $2 S+100 \leqslant 1000100$ and $S \leqslant 500000$.
