Maths Olympiad Prep

Library / /477 of 520

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it

Player Zero and Player One play a game on an n×nn \times n board (n1)(n \geq 1). The columns of this n×nn \times n board are numbered with powers of two, so we have column 1, column 2, column 4, up to column 2n12^{n-1}. Taking turns, the players place their own number (so Zero places a 0 and One places a 1) in one of the empty squares. Player 0 starts. When the board is full, the game ends and in each row a (reverse binary) number is formed by summing the values of the squares with a 1 in them. So if n=4n=4, then a row with 0101 corresponds to the number 01+12+04+18=100 \cdot 1 + 1 \cdot 2 + 0 \cdot 4 + 1 \cdot 8 = 10.
a) For which natural numbers nn can Player One always ensure that at least one of the rows is divisible by 4?
b) And for which natural numbers nn can Player One always ensure that at least one of the rows is divisible by 3?
a) Solution 1. First note that if n=1n=1, the unique square gets a 0 because Player Zero starts, so in this case it is possible.
We will now prove that for all other nn, Zero can prevent One from winning. Since 42k4 \mid 2^{k} for all k2k \geq 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 will prove that for all n>1n>1, Zero can prevent One from winning.
We say "Zero blocks One" if Zero places a 0 next to a 1 in the first two squares of a row. We call the first two columns the left area; the entire board except the first two columns is the right area.
If nn is odd, Zero places a 0 in the right area first. There are then still an even number of squares in both the right area and the left area. Zero plays in such a way that this property is maintained after each of his moves, and that in addition, the neighboring square of each empty square in the left area is also empty. (In each row, the first two squares are thus both empty or both occupied.) Each time One places a 1 in one of the areas, there is still at least 1 more empty square in that area, and Zero plays a 0 in the same area. For the left area, Zero does this by immediately blocking the 1 just played by One.
If nn is even, Zero places a 0 in the left area first. There are now an odd number of squares left 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 plays a 1 on the left in a row where a 0 already stands, then Zero starts a new row on the left again if possible by playing a 0 in the left area so that the adjacent square (in the left area) is still empty. If there is no new row, then all rows on the left are filled with 01 or 10, and Zero plays on the right.

Solution

Player Zero has the following strategy: do not place a 0 in the first two columns unless you have no other choice. In that case, place a 0 in a row where the other cell of the first two cells already contains a 1, if possible. If such a cell does not exist, place it in a row that does not yet have a 0 in the first two cells. We will show that Zero can continue to do this all the time, so that Zero wins because there will never be a row that starts with two 0s.
We claim that with this strategy, at any moment, there is at most one row whose first two cells are (0,)(0, \emptyset). Suppose that Zero places a zero next to an empty cell. Then the right area is full due to the strategy. When One makes a move after this, it replaces the (0,)(0, \emptyset)-row with a (0,1)(0,1)-row, or a (1,)(1, \emptyset)-row is created where Zero can/must play. Zero is thus never forced to create a second (0,)(0, \emptyset)-row, or a (0,0)(0,0)-row.
b) Solution. Zero can only ensure that no row is divisible by 3 if n2mod4n \equiv 2 \bmod 4.

First note that modulo 3 the columns are numbered 1,2,1,2,1,2,1,2, \ldots. If nn is even, there are an even number of cells and One has the last turn; if nn is odd, there are an odd number of cells and Zero has the last turn.

If n=4kn=4k, both 1 and 2 appear an even number of times per row. Now One has the following strategy: mirror player Zero. If Zero places a zero in a cell with value 1, then One places a 1 in a cell in the same row that also has value 1. If Zero places a zero in a cell with value 2, then One places a 1 in a cell with value 2 in the same row. Since there is an even number of 1s and 2s in each row, One can always continue to do this. Now it holds that at the end kk cells with value 1 have the number 1 and kk cells with value 2 have the number 1 from One. So the sum of each row is 3k0mod33k \equiv 0 \bmod 3.

If n=4k+1n=4k+1, there are 2k+12k+1 cells with value 1 and 2k2k cells with value 2. One wants to create a row such that exactly kk cells with value 1 have a 1 and exactly kk cells with value 2. One now uses the mirror strategy again. However, if One cannot mirror, then One places a 1 in any cell with value 1. Only if this is also no longer possible does he place a 1 in a cell with value 2. Since there are exactly 2k2k cells per row with value 2, One can ensure with this strategy that in each row exactly kk cells with value 2 get the number 1. In addition, this strategy ensures that there is at least one row with k+1k+1 zeros in cells with value 1 (and thus kk with the number 1). For this row, the sum is k+2k=3k0mod3k+2k=3k \equiv 0 \bmod 3.

If n=4k+3n=4k+3, there are 2k+22k+2 cells with value 1 and 2k+12k+1 cells with value 2. One starts by placing a 1 in any cell with value 2 in one of the rows where Zero has not placed his first cell. One then applies the copy technique to this specific row. So if Zero places it outside, One does the same and if Zero places it inside, One also does this and places his 1 on a cell with the same value. Since there is now an odd number of empty cells outside this row, it can happen that One has to place a cell in the special row while Zero did not do so on the previous turn. There are still 2k2k cells with value 2 and 2k+22k+2 with value 1 for this move. By applying the copy technique again after this move (and the fact that Zero has the last move), One can ensure that both One and Zero choose kk cells with value 2 and k+1k+1 cells with value 1. Now the special row has exactly k+1k+1 cells with value 1 and k+1k+1 with value 2, so the sum is 3(k+1)0mod33(k+1) \equiv 0 \bmod 3 and One wins.

If n=4k+2n=4k+2, there are 2k+12k+1 cells with value 1 and 2k+12k+1 cells with value 2. Then Zero can prevent One from winning. This time it is Zero who applies the copy technique from his second turn. However, if there are no more cells with the same value in the same row, then Zero places the cell in the same row with the other value. Since in this case One has the last turn, Zero can ensure with this strategy that both exactly 2k+12k+1 cells in each row are occupied and that Zero occupies at least kk cells with value 1 and kk cells with value 2 in the row. This means that the sum in each row is either k+2(k+1)2mod3k+2(k+1) \equiv 2 \bmod 3 or k+1+2k1mod3k+1+2k \equiv 1 \bmod 3. In this case, Zero can always prevent One from winning.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.