IOM 2018 Problem 5

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