Two intelligent people playing a game on the $1403 \times 1403$ table with $1403^2$ cells. The first one in each turn chooses a cell that didn't select before and draws a vertical line segment from the top to the bottom of the cell. The second person in each turn chooses a cell that didn't select before and draws a horizontal line segment from the left to the right of the cell. After $1403^2$ steps the game will be over. The first person gets points equal to the longest verticals line segment and analogously the second person gets point equal to the longest horizonal line segment. At the end the person who gets the more point will win the game. What will be the result of the game?
Problem
Source: Iran 2024 3rd Round Test 1 P2
Tags: table, combinatorics, cells, game strategy, Game Theory
29.08.2024 23:51
I will post a solution later
01.09.2024 22:48
The game will end in a draw. Label the first player A (vertical) and the second player B (horizontal). We provide a strategy for player B to prevent A from getting more than $2$ points while ensuring $2$ points itself. We will use a $11\times 11$ grid for the sake of demonstration. Consider the following division of the gird: [asy][asy] add(grid(11,11,gray+linetype("4 4"))); int i; for(i=0; i<12; i=i+1) { draw((i,1)--(i,11)); } int i; for(i=0; i<6; i=i+1) { draw((0,2i+1)--(11,2i+1)); } draw((0,0)--(11,0)); draw((0,0)--(0,1)); draw((11,0)--(11,1)); [/asy][/asy] Whenever A draws a vertical segment in one of the dominoes B should draw a horizontal segment in the other cell of the domino. In this way, it is impossible for A to get $3$ vertical markings in a row. Then when A plays first in the bottom row, B should play in a cell in the bottom row at least $2$ away. Thus when A plays in the bottom row again, B is guaranteed a $2$ in a row. The strategy for A to get $2$ points while preventing B from getting $2$ points is almost identical. Thus each player can make sure the other does not win, the definition of a draw!