We are placing red and blue balls on the circle. In the beginning there are exactly two red balls on the circle. We are allowed to perform the following operations: i) add one red ball and change the colour of its neighbouring two balls (red to blue and vice versa); ii) remove one red ball and change the colour of its neighbouring balls. Is it possible that after a finite number of operations we obtain
a) 2013 red and 2013 blue balls; b) exactly two blue balls? (Kvant 8/1981)
Solution
a. We consider three different cases of adding a red ball depending on the colours of its neighbours. If we add the ball between two blue balls, then we have the case PP→CCC in which the number of blue balls decreases by two. If we add the ball between two red balls, we have CC→PCP and the number of blue balls increases by two. In the third case, we add the ball between one blue and one red ball (CP→PCC) and the number of blue balls stays the same. We conclude that adding a red ball does not change the parity of the number of blue balls. Also removing a red ball does not change the parity of the number of blue balls.
In the beginning there is no blue balls, so after each operation the number of blue balls is even. Hence it is not possible that we obtain exactly 2013 blue balls.
b. In a given configuration of balls, we label the blue balls clockwise P1,P2,…,P2k starting with an arbitrary blue ball. Let mi (i∈{1,2,…,2k}) be the number of red balls between balls Pi and Pi+1 (Pn+1=P1). For example, in the following picture we have m1=2,m2=3,m3=1,m4=0,m5=4,m6=1.
Furthermore, let us denote S=m1−m2+m3−⋯+m2k−1−m2k. If the configuration consists of n red balls and no blue balls we denote S=n. Let us prove that either S is divisible by three for all configurations or S is not divisible by three for all configurations. We again consider three cases:
1. We add a red ball between two blue balls, Pi and Pi+1: Pi−1mi−1…Pimi=0…Pi+1→Pi−1′mi′…CC↓…Pi′
2. We add a red ball between two red balls: Pimi…CC…Pi+1→Pimi′…Pi+1mi+1′=1C↓Pi+1mi+2′…Pi+3 Similiarly as before, S=S0+mi, a S′=S0+mi′−1+mi+2. But now mi=mi′+mi+2′+2, so S′=S−3.
(Analogous statement holds in the case if there is no blue balls on the circle.)
3. We add a red ball between one red and one blue ball (to the right of the blue ball Pi): Pi−1Pimi−1C…Pi+1mi→Pi−1mi′…Cmi−1′C↓Pi…Pi In this case S=S0+mi−1−mi and S′=S0+mi−1′−mi′. Since mi−1′=mi−1+2 and mi′=mi−1, we have S′=S+3.
In any case, S either decreases or increases by 3. In the beginning number S is 2 and hence S can never be divisible by three. We cannot obtain exactly two blue balls since S would be 0.
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.