Two players are playing the following game. They are alternatively putting blue and red coins on the board $2018$ by $2018$. If first player creates $n$ blue coins in a row or column, he wins. Second player wins if he can prevent it. Who will win if: $a)n=4$; $b)n=5$? Note: first player puts only blue coins, and second only red.
Problem
Source: Serbian JBMO TST 2018, problem 4
Tags: combinatorics, combinatorics proposed, JBMO TST
22.05.2018 14:30
In my opinion this is the hardest junior combinatorics I've ever seen. By the way, I have a solution for $a)$, but it is very very uqly: After finishing the first (hardest) case I counted and realized that I placed $77$ coins on the table . The idea is that I don't know whether this solution can be optimized. So I will just sketch it. I am sorry because I can't draw the figures. But first ... MilosMilicev wrote: Note: first player puts only blue coins, and second only red. This is unnecessary. It is very easy to see that if we change the conditions and allow both to use both colors, if the players play optimal, than the first will use only blue coins and the second will use only red. Solution to $a)$: I will prove that Player 1 can win. Lemma $0$: Consider 4 consecutive squares (all in a row or in a column) such that the first is red, the following $3$ are blue, and the next consecutive in the line is empty and the player in turn is player 2. Then, the player 2 is forced to put his red coin on the empty square consecutive to the other $4$. Solution: Just suppose for the sake of the contradiction that Player 2 does not put his coin there. After that, the player 1 can put his coin on the empty square and obviousily he wins. Lemma $0$' Consider $3$ consecutive squares (all in a row or in a column) such that the first is red, the following $2$ are blue, and the next two consecutive in the line are empty and the player in turn is player 1. Then player 1 will put his square on the first empty square and then by Lemma $0$ player 2 will be forced to put his red coin on the second empty square. Lemma $0$'' Consider $3$ consecutive squares (all in a row or in a column) such that the first is red, the following $2$ are blue, and the next two consecutive in the line are empty and the player in turn is player 1. Then player 1 will put his square on the second empty square and then by a similar argument to that used in the solution of Lemma $0$, player 2 will be forced to put his red coin on the first empty square. Lemma $1$: Consider $5$ consecutive squares (all in a row or in a column) such that the first, the third and the last are empty, the second and the fourth' are blue, and player 2 is in turn. Then player 2 is forced to place his red square in the third square. Solution: Otherwise, he can place the next square in the third square, and after that independently of where player 2 places his square next time, the player 1 can form 4 consecutive squares. This lemma is very useful because it has a little number of conditions. Now his strategy: Let him place the first blue coin in one of the squares of the 4 in the center of the table. First case (hardest): Player 2 places his square adiacently to the one placed by player 1. Then, player 1 will place his square 2 squares after (only one empty will remain through them) the one placed by his first square, on a perpendicular direction to the last placed by player 2. Then, by Lemma 1, it follows in that the empty square between the last 2 squares, the player 2 will be forced to put a red square. It is easy to see that this strategy can be used again in the same manner. Consider this as Strategy 2. More precisely, let player 1 consider the first square of player 2 upper to the first of player 1 and without loss of generality put his second square on his left. Use this strategy going with the line formed clockwise 2 more times. Then let player 1 put his square in the square between his first square and the last placed on the table. Using Lemma 0 it follows that player 2 is forced to put his square four cells under the first square placed by player 1. Then place the next square by player 1 two squares to the right of the last placed by player 1. Now surround the figure using the Strategy 2 until you get to the following part of the table ($41$ placed coins until now): Without loss of generality consider $(0, 0)$ the first square placed by player 1. We will have squares $(1, 0)$, $(2, -1)$, $(1, -2)$, $(2, -4)$ and $(3, -3)$ red squares and $(2, 0)$, $(2, -2)$, $(2, -3)$ and $(4, -3)$ blue, with player 1 in turn. Then he will place on $(4,0)$ his blue coin and use once Lemma 1. Continuing to play with Lemma 1 and mainly with Lemma 0', after $36$ more placed coins he will win. The other cases, depending on the position of the first coin placed by player 2 can be treated much more easily, and I won't post them. This is just the solution to $a)$, and it is long enough. How can one write a this type of solution in a contest? Did anyone solve it completely? It is far the hardest junior combi I've ever seen!
28.09.2019 17:39
Solution for b)?
24.01.2020 16:21
VicKmath7 wrote: Solution for b)? Player 2 wins. We divide the table into 2x2 squares and color the new 1009x1009 table like a chessboard. Then we divide the black squares of the new board into 2 vertical dominoes and white squares into 2 horizontal dominoes. Now we notice that in every 5 consecutive squares(horizontal or vertical) there is a whole dominoe.Therefore, player 2 always puts a coin in the same dominoe as the first one did in his previous move. I didn't solve this, I just translated the solution, so I hope it's understandable to read.