IMO Team Selection Test 1

a) Note first that if $n=1$, the unique box gets 0 because player Zero starts, so in this case it is possible. We will now prove that for all other $n$ Zero can prevent One from winning. Since $4\mid 2^k$ for all $k\ge 2$, only the first two columns determine who wins. If there is a row with two zeros at the beginning, then player One wins and otherwise player Zero wins. We are going to prove that for all $n>1$ Zero can prevent One from winning. We say "Zero blocks One" when Zero puts his 0 next to a 1 in the first two boxes of a row. We call the first two columns the left area; the whole board except for the first two columns precisely the right area. If $n$ is odd, Zero first puts a 0 in the right area. There are then an even number of squares left in both the right area and the left area. Zero now plays so that this property is preserved after every move of his, and in addition, the neighbouring square of every empty square in the left region is also empty. (So in each row, the first two squares are both empty or both occupied.) So every time One puts a 1 in one of the areas, there is at least 1 more empty square in that area and Zero plays a 0 in that same area. For the left area, Zero does this by blocking the 1 One just played each time. If $n$ is even, Zero puts a 0 in the left area first. There are now an odd number of squares on the left and an even number of squares on the right. If One plays a 1 on the right, Zero also plays a 0 on the right. If One plays a 1 on the left in a new row, Zero immediately blocks it. If One on the left plays a 1 in the row where there was already a 0, Zero starts a new row on the left if it can by playing a 0 in the left area so that the square next to it (in the left area) is still empty. If there is no new row, all rows on the left are filled with 01 or 10 and Zero plays on the right. $\square$

b) Zero can only ensure that no row is divisible by 3 if $n\equiv 2(\mathrm{mod}4)$. Note first that modulo 3 the columns are numbered as 1, 2, 1, 2, .... If $n$ is even, there are an even number of squares and One has the last turn; however, if $n$ is odd, there are an odd number of squares and Zero has the last turn. If $n=4k$, both the 1 and the 2 occur an even number of times per row. Now One has the following tactic: mirror player Zero. If Zero puts a zero in a row with value 1, then One puts a 1 in a square in the same row that also has value 1. If Zero puts a zero in a row with value 2, then One puts a 1 in a square with value 2 in that same row. Since there are an even number of 1s and 2s in each row, One can always keep doing this. Now, at the end, $k$ boxes with value 1 have the number 1 and $k$ boxes with value 2 that got the number 1 from One. So the sum of each row is $3k\equiv 0(\mathrm{mod}3)$. If $n=4k+1$, there are $2k+1$ squares of value 1 and $2k$ squares of value 2. One wants to make a row so that exactly $k$ squares of value 1 contain a 1 and exactly $k$ squares of value 2. However, if One can't mirror, One puts a 1 in any square of value 1. Only when this is also no longer possible does he put a 1 in a square of value 2. Since there are exactly $2k$ squares per row of value 2, One can use this tactic to ensure that in each row exactly $k$ squares of value 2 get the number 1. In addition, this tactic ensures that there is at least one row with $k+1$ zeros on squares of value 1 (and thus $k$ with the number 1). For this row, the sum is equal to $k+2k=3k\equiv 0(\mathrm{mod}3)$. If $n=4k+3$, there are $2k+2$ squares of value 1 and $2k+1$ squares of value 2. One starts by putting a 1 in any square of value 2 in one of the rows where Zero has not placed his first square. Then One applies the copy technique to this particular row. So if Zero places outside it, One does the same and if Zero places inside it, One does the same and puts its 1 on a square of the same value. Since there are now an odd number of empty squares outside this row, One may have to put a square in the special row when Zero did not do so the turn before. Before this move, there are $2k$ squares left with value 2 and $2k+2$ with value 1. By applying the copy tactic again after this move (and the fact that Zero has the last move), One can make sure that both One and Zero choose $k$ squares with value 2 and $k+1$ squares with value 1. Now the special row has exactly $k+1$ squares with value 1 and $k+1$ with value 2, making the sum $3(k+1)\equiv 0(\mathrm{mod}3)$ and One wins. If $n=4k+2$, there are $2k+1$ squares with value 1 and $2k+1$ squares with value 2. Then Zero can prevent One from winning. This time, it is precisely Zero who applies the copying tactic from his second turn. However, if there are no more squares with the same value in the same row, Zero chooses the square in the same row with the other value. Because in this case One has the last turn, this tactic allows Zero to ensure that both occupy exactly $2k+1$ squares in each row and that Zero occupies at least $k$ squares with value 1 and $k$ squares with value 2 in the row. This means that the sum in each row is either $k+2(k+1)\equiv 2(\mathrm{mod}3)$ or $k+1+2k\equiv 1(\mathrm{mod}3)$. So in this case, Zero can always prevent One from winning. $\square$