Bariz - Problem

Ann and Max play a game on a $100 \times 100$ board. First, Ann writes an integer from 1 to 10 000 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 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

The answer is 500,000. At least 500,000. Ann writes numbers as follows: \[\begin{bmatrix} 1 & 200 & 201 & 400 & \dots & 9801 & 10000\\ 2 & 199 & 202 & 399 & \dots & 9802 & 9999\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 99 & 102 & 299 & 302 & \dots & 9899 & 9902\\ 100 & 101 & 300 & 301 & \dots & 9900 & 9901 \end{bmatrix}\]Split the board into 50 $100 \times 2$ blocks; it is clear that Max must pay at least $200(2a - 1)$ coins in the $a^{\text{th}}$ block. At most 500,000. The sum of all the numbers is 50,005,000. Hence there is a $2 \times 100$ block with sum at most 1,000,100. Let the top and bottom rows be $a_1, \dots, a_{100}$ and $b_1, \dots, b_{100}$ in order. Then Max can guarantee $\sum \min(a_k, b_k)$. Since all 200 numbers are distinct, this pays at most \[\sum \min(a_k, b_k) \le \sum \frac{a_k + b_k - 1}{2} \le \frac{1,\!000,\!100 - 100}{2} = 500,\!000\]coins.