Maths Olympiad Prep

Library / /72 of 92

Geometry Difficulty 7.1 National olympiad, round 2 Prove it Iran

Let nn be a positive integer. Two players are playing a game in a field of a shape of a 2n×2n2n \times 2n grid. Initially, the first player is on the top right point and second player is on the bottom left point. Each player, in his turn, moves to an adjacent point, by passing on an edge, such that none of the players have reached it previously. The first player wants to get back to his start position finally and make a non-self-intersecting closed polygon with maximum possible area. On the other hand, the second player wants to minimize this area. Without considering second's player moves, what would be the maximum possible area that first player can always achieve?

Solution

Let AA be the first player and BB the second one. Since AA plays first, they can reach point CC sooner, making nn moves downwards and then nn moves to the left. Then they can get back to their start point, making nn moves upwards and nn moves to the right. In this case, the first player wins the upper right square with an area of n2n^2.

Now we prove that the second player can play in a way that the first player won't be able to win an area of more than n2n^2.

Without loss of generality, assume that AA moves down in their first move. Their distance from XX will be 2n12n-1, while BB is 2n2n moves away from XX. Clearly BB can make their 2n2n first moves upwards and AA won't be able to stop them. After BB has reached XX, he/she shall move right. If they can make 2n2n moves in that direction, AA will not be able to go back to their start point. So let's assume BB

nAC \begin{array}{c|c} n & A \\ \hline C & \end{array}

has come to a halt after moving xx times on the upper side of the square. Thus the area that AA has won, will be a subset of the hatching area and therefore, less than it. The circumference of the hatching area equals 4n4n, since AA has reached point KK after 2n+x+12n+x+1 moves and AK=2nx+1|AK| = 2n-x+1.

Thus it suffices to prove that the area of a shape, which its circumference equals 4n4n, would be n2n^2 at most. Assume one has started moving from SS, making xx moves upwards, xx moves downwards, yy moves to the right and yy moves to the left (in some order) where 2x+2y=4n2x+2y=4n, and then they has reached SS after all. So the final shape fits in a rectangle with x,yx, y as its length and height; which means the area of the final shape is less than xyxy

AB \begin{array}{c|c} A & \\ \hline & \\ B & \end{array}

and we have

2x+2y=4n    x+y=2n    2n=x+y2xy    xyn2 \begin{aligned} 2x + 2y &= 4n \implies x + y = 2n \implies 2n = x + y \geq 2\sqrt{xy} \\ \implies xy &\leq n^2 \end{aligned}

The proof is completed.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.