Maths Olympiad Prep

Library / /443 of 462

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Ireland

There are 220182^{2018} buckets placed in a circle. Their positions are numbered from 11 to 220182^{2018} according to their order in the circle. Initially only buckets at positions 20182018 and 20192019 are full of water, the others are empty.

Before the game starts, John is allowed to fill as many additional buckets as he wishes full of water. At the start of the game, John is given an integer nn (0n<20180 \le n < 2018) and two more buckets, one empty and the other full of water. John will then move around the circle, starting at position 2n2^n and moving forward by 2n2^n positions each time. At each position he reaches during his journey he has to replace the bucket he finds by one of those two he carries. He needs to replace an empty bucket by a full one and a full bucket by an empty one. If he cannot do so at any position he reaches, he lost the game.

Is it possible for John to fill the buckets before the start of the game in such a way that he will not lose the game, no matter which value of nn he will be given and no matter how long he will move in the circle?

Solution

If we let k=2nk = 2^n, the positions John visits during his journey are the positive integer multiples of kk. Because k22018k \mid 2^{2018}, he will arrive at position 220182^{2018} and then visit the same positions in the circle for each subsequent time he moves around the circle.

We will say "John carries empty-full" if he carries one full and one empty bucket. When John starts the game, he carries empty-full.

Claim 1. Suppose John carries empty-full when arriving at position ss. Then he can move to position s+2ks + 2k without losing the game exactly when one of the two buckets at positions ss and s+ks + k is empty and the other is full of water. Moreover, he will then carry empty-full when he arrives at position s+2ks + 2k.

Proof of Claim 1.

Case (i): There is a full bucket at position ss. In this case, John will move from position ss to position s+ks + k with two full buckets. He will lose the game if he finds a full bucket at position s+ks + k. Otherwise, he does not lose, drops one of the full buckets there and picks up the empty one, so that he leaves carrying empty-full.

Case (ii): There is an empty bucket at position ss. In this case, John will move from position ss to position s+ks + k with two empty buckets. He will lose the game if he finds an empty bucket at position s+ks + k. Otherwise he does not lose the game and drops one of the empty buckets there and picks up the full one, so that he leaves carrying empty-full. \square

Claim 2. A necessary and sufficient condition for John to win the game is that for each positive integer tt, one of the two buckets at positions (2t1)k(2t-1)k and 2tk2tk is empty and the other is full of water.

Proof of Claim 2. This follows easily from claim 1 using induction.

Because n<2018n < 2018 we see that 220182^{2018} is an even multiple of kk. Hence, when John leaves position 220182^{2018} without having lost the game, he will carry empty-full and the condition of claim 2 for the multiples of kk is still satisfied (because each full bucket was replaced by an empty one and vice versa). This means that John can move indefinitely without losing the game, if he can finish one circle successfully.

Claim 3. The filling level (full or empty) of the bucket at position 220182^{2018} determines the filling level of all other buckets if John does not lose the game.

Proof of Claim 3. Each position ss (1s<220181 \le s < 2^{2018}) can be written in a unique way in the form s=b2ms = b \cdot 2^m, where bb is odd and 0m<20180 \le m < 2018. Write
22018s=2m1+2m2+2m3++2mr 2^{2018} - s = 2^{m_1} + 2^{m_2} + 2^{m_3} + \dots + 2^{m_r}
with integers 0m1<m2<m3<<mr0 \le m_1 < m_2 < m_3 < \dots < m_r. This representation is unique and for each 1<ir1 < i \le r we see that 2mi2^{m_i} is the highest power of 22 that divides s+2m1+2m2++2mi1s + 2^{m_1} + 2^{m_2} + \dots + 2^{m_{i-1}} and 2mi2^{m_i} is the highest power of 22 that divides ss. Hence, according to claim 2, for i=r,r1,,2i = r, r-1, \dots, 2, the filling level of the bucket at position s+2m1+2m2++2mi1s + 2^{m_1} + 2^{m_2} + \dots + 2^{m_{i-1}} is determined by the filling level of the bucket at position s+2m1+2m2++2mi1+2mis + 2^{m_1} + 2^{m_2} + \dots + 2^{m_{i-1}} + 2^{m_i} in order to ensure that John can win if n=min = m_i was chosen. Moreover, the filling level of the bucket at position ss is determined by the filling level of the bucket at position s+2m1s + 2^{m_1}.

Claim 3 shows that there are at most two ways to fill the buckets before the game starts that guarantee John to win the game. We will now group the positions into two types, called type +1+1 and type 1-1, such that John will not lose the game if all the buckets of the same type have the same filling level and buckets of different types have different filling level.

Define the binary weight w(s)w(s) of a non-negative integer ss to be the number of digits 11 in the binary representation of ss. In other words, if s=2m1+2m2+2m3++2mrs = 2^{m_1} + 2^{m_2} + 2^{m_3} + \dots + 2^{m_r} with 0m1<m2<m3<<mr0 \le m_1 < m_2 < m_3 < \dots < m_r, then w(s)=rw(s) = r and w(0)=0w(0) = 0. We define the type t(s)t(s) of a position ss (1s220181 \le s \le 2^{2018}) as
t(s)=(1)w(s1). t(s) = (-1)^{w(s-1)}.

Claim 4. If all buckets at positions of type +1+1 are empty and all buckets at positions of type 1-1 are filled with water at the start of the game, the conditions of claim 2 are satisfied for each k=2nk = 2^n (0n<20180 \le n < 2018).

Proof of Claim 4. Let k=2nk = 2^n and s=(2t+1)ks = (2t+1)k for a non-negative integer tt.
Then s1=2tk+(k1)=t2n+1+(2n1)s-1 = 2tk + (k-1) = t \cdot 2^{n+1} + (2^n - 1). The binary representation of t2n+1t \cdot 2^{n+1} ends in at least n+1n+1 zeros. The binary representation of 2n12^n - 1 consists of nn digits 11 at the last nn places. Therefore, w(s1)=w(t)+nw(s-1) = w(t)+n. On the other hand, s+k1=(2t+1)k+(k1)=t2n+1+2n+(2n1)s+k-1 = (2t+1)k + (k-1) = t \cdot 2^{n+1} + 2^n + (2^n-1) has a digit 11 in its binary representation at place n+1n+1 (from the end), otherwise coincides with the binary representation of s1s-1. Hence, w(s+k1)=w(t)+1+n=w(s1)+1w(s+k-1) = w(t)+1+n = w(s-1)+1. This implies t(s+k)=t(s)t(s+k) = -t(s) as required. \square

Of course, claim 4 is true when we exchange filled and empty in its statement. Therefore, it will be possible for John win the game precisely when t(2018)=t(2019)t(2018) = t(2019). Because 2017=2016+1=6332+1=(261)25+202017 = 2016+1 = 63 \cdot 32 + 1 = (2^6-1) \cdot 2^5 + 2^0 has binary representation (1111100001), we have w(2017)=7w(2017) = 7, which gives t(2018)=(1)w(2017)=1t(2018) = (-1)^{w(2017)} = -1. The binary representation of 20182018 is (1111100010) and so w(2018)=7w(2018) = 7, which gives t(2019)=(1)w(2018)=1t(2019) = (-1)^{w(2018)} = -1. Therefore, when John fills all buckets of type 1-1 with water he will not lose the game.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.