A 10 × 10 grid is divided into 100 unit squares and has a wall around its perimeter. A pawn starts at the square (1, 1).
Two players, the Wall-Setter and the Pawn-Pusher, play a game, taking alternate turns. The Wall-Setter takes the first turn. On the Wall-Setter’s turn, they can place any (possibly zero) number of walls on the grid lines between touching squares. However, they can never place walls in a way that completely blocks the pawn from reaching the square (10, 10). On the Pawn-Pusher’s turn, they move the pawn exactly one step up, down, left or right to an adjacent square, as long as a wall does not block the move.
The game ends when the pawn reaches the square (10, 10). The final score of the game is the total number of moves the Pawn-Pusher made. The Wall-Setter wants to make the score as high as possible and the Pawn-Pusher wants to make the score as low as possible.
What strategies would you suggest for them?
Answer format: Find an integer s and a strategy for each player such that the Wall-Setter can guarantee a score of at least s, and the Pawn-Pusher can guarantee a score of at most s. Prove the correctness of these strategies.
Please note, we will only take your first submission into account.
