Two intelligent players play a game on a grid consists of unit squares, taking turns. On their turn, the first player chooses one of the unchosen cells and draws a unit line segment from the midpoint of its top side to the midpoint of its bottom side. In their turn, the second player chooses one of the free cells and draws a unit line segment from the midpoint of its right side to the midpoint of its left side. After steps, the game ends. The first player scores points equal to the length of the longest connected vertical line segment they have formed. The second player also scores points equal to the length of the longest connected horizontal line segment they have formed. At the end of the game, the player with the higher score wins; if scores are equal, there would be a draw. What will be the outcome of the game? Justify your answer.
Solution
The first player draws their first vertical line in the red-colored cell of the table shown. Then, they consider the cell above and below it (the blue ones) as a pair, and pairs up the other cells in that column two by two (the green dominoes). The rest of the table, which is a grid, is also partitioned into horizontal dominoes, indicated in the figure by yellow and orange colors. In this case, it is easily proven that they prevent their opponent from creating a line segment of length . Also, they will clearly draw one of the line segments in one of the blue cells, which, when placed next to the line drawn in the first step, achieves a line segment of length . Thus, the first player has a non-losing strategy.
Now, we also present a non-losing strategy for the second player. This strategy is as follows: After the first player's move, if the cell above it is empty, draw a horizontal line in that cell. If its upper cell is full, draw a horizontal line in the cell below it. If that is also full, draw a horizontal line in any other cell in the same column. And if such an action is also not possible (i.e., when that column becomes full), draw a horizontal line in a "good" cell (which will be specified later). In this case, it becomes clear that they prevent their opponent from achieving a vertical line of length . Now we proceed to prove that with the above strategy, the second player can achieve a line segment of length . For this purpose, consider the first time a column becomes completely full (we call it column ). It is clear that at such a stage, it is the second player's turn (because the -rd cell of a column has been filled, and is odd).
Now, the second player makes their move in a cell of an adjacent column to column , in the same row as a cell in column where player two has drawn a horizontal line, thus forming a horizontal line of length . If no such cell exists, it means that all possible cells in this adjacent column were previously occupied by the first player with vertical lines. Since every move by the second player so far has been in the same column as the first player's, another cells in this adjacent column have been filled with horizontal lines by the second player. Thus, these columns adjacent to column have filled cells (we call columns with filled cells "almost full columns"). Now, if second player again looks to the columns adjacent to these two columns for a suitable cell to draw a horizontal line to form a line of length , either they succeed, or those columns will also be in an almost full state. In this way, successively, all columns (except ) become 'almost full'. In this case, second player draws a horizontal line in one of the 'almost full' columns whose two adjacent columns are also in this state. It is clear that in their next turn, second player can also draw a horizontal line in one of its two adjacent 'almost full' columns. This results in two consecutive columns, say and , where column has all its cells filled ( vertical by first player, horizontal by second player) and column also has all its cells filled ( vertical by first player, horizontal by second player). So, second player has placed horizontal lines in column and horizontal lines in column . And since , Consider the rows, by the Pigeonhole Principle, there must be at least one row where second player has placed a horizontal line in column and also in column . This creates a horizontal line of length for second player. Thus, the second player also has a non-losing strategy, and the game will result in a draw if both players play intelligently. ■