Maths Olympiad Prep

Library / /74 of 86

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it United States

Problem:
A kingdom consists of 12 cities located on a one-way circular road. A magician comes on the 13th of every month to cast spells. He starts at the city which was the 5th down the road from the one that he started at during the last month (for example, if the cities are numbered 1-12 clockwise, and the direction of travel is clockwise, and he started at city #9 last month, he will start at city #2 this month). At each city that he visits, the magician casts a spell if the city is not already under the spell, and then moves on to the next city. If he arrives at a city which is already under the spell, then he removes the spell from this city, and leaves the kingdom until the next month. Last Thanksgiving the capital city was free of the spell. Prove that it will be free of the spell this Thanksgiving as well.

Solution

Solution:
Number the cities from 00 to 1111. Encode the current state of affairs by starting at city 1111, writing "1" if the city is not under a spell, and a "0" if it is under a spell. Do the same thing for each city, from city 1010 down to city 00. Interpret the resulting list as the binary expansion of an integer XX between 00 and m=2121m=2^{12}-1.
Some thought (using modular arithmetic modulo mm, and the way that addition works in base 2) shows that the rules can be interpreted as saying that if the magician starts at city kk then 2k2^{k} is added to YY, where YY encodes the state as above. After 12 months the magician starts once at all cities, and this has the net effect of adding
1+2+22+23++211=2121=m 1+2+2^{2}+2^{3}+\ldots+2^{11}=2^{12}-1=m
to the original XX which obviously leaves the state unchanged.

Solution:
We shall denote the state of the kingdom by a 12-tuple of 00's and 11's, with 00 and 11 meaning "free of spell" and "under spell," respectively. For example, suppose that the initial state is (0,1,0,0,0,0,1,0,0,0,0,0)(0,1,0,0,0,0,1,0,0,0,0,0). This means that city #1 is free of the spell, city #2 is under the spell, city #3 is free, etc. Next, define SjS_{j}, for j=1,2,,12j=1,2, \ldots, 12 to be the transformation of the kingdom after the magician makes a visit that starts at city jj. For example,
S1(0,1,0,0,0,0,1,0,0,0,0,0)=(1,0,0,0,0,0,1,0,0,0,0,0), S_{1}(0,1,0,0,0,0,1,0,0,0,0,0)=(1,0,0,0,0,0,1,0,0,0,0,0) \text{,}
since she puts a spell on city #1, then comes to city #2 which is already under the spell, frees it, and stops. Likewise,
S8(0,1,0,0,0,0,1,0,0,0,0,0)=(1,0,0,0,0,0,1,1,1,1,1,1), S_{8}(0,1,0,0,0,0,1,0,0,0,0,0)=(1,0,0,0,0,0,1,1,1,1,1,1) \text{,}
because she puts cities #8-12 under spell, then continues around the circle to #1, puts it under spell, then finally stops after freeing city #2. One more example:
S3(0,0,0,0,0,0,0,0,0,0,0,0)=(1,1,0,1,1,1,1,1,1,1,1,1), S_{3}(0,0,0,0,0,0,0,0,0,0,0,0)=(1,1,0,1,1,1,1,1,1,1,1,1) \text{,}
because she puts every city under the spell, starting with #3, until she comes to a city that is already under the spell, and this happens when she comes to city #3 for the second time.
The key to this problem is the remarkable fact that the SjS_{j} transformations commute; i.e.
SiSj=SjSi for all i,j{1,2,3,,12} S_{i} S_{j}=S_{j} S_{i} \quad \text{ for all } i, j \in\{1,2,3, \ldots, 12\}
Let us assume this fact, to see how it quickly solves the problem. Without loss of generality, suppose the magician starts a visit at city #1. Then during the course of the year, her subsequent visits will start at the following cities, in this order:
6,11,4,9,2,7,12,5,10,3,8 6,11,4,9,2,7,12,5,10,3,8
In other words, during the year she will make 12 visits, and each visit will start at a different city. In other words, the kingdom will be transformed, in order, by S1,S6,S11,S_{1}, S_{6}, S_{11}, \ldots But since these transformations are commutative, we can rearrange the order that we perform the transformations. So, during the course of the year, the kingdom will be transformed by S1,S2,S3,,S12S_{1}, S_{2}, S_{3}, \ldots, S_{12}, where we may choose the order in any way that we like.
Consider the state of the kingdom last Thanksgiving. Suppose cities a,b,c,a, b, c, \ldots are spell-free (where city aa is the capital) and cities A,B,A, B, \ldots are under the spell. Now we shall perform the transformations, in this order:
- SA,SB,S_{A}, S_{B}, \ldots : Each of these are "single-city" transformations that merely free the starting city and then stop. In other words, after these transformations have been performed, all the cities which were under the spell are now free, and hence at this point, all cities in the kingdom are free. (It may be that no cities were under the spell in the first place, so this step may not take place.)
- SaS_{a} : Starting with aa, all cities get put under the spell (since they were previously all free), until the magician returns to aa, frees it, and stops. Now all cities are under the spell, except for the capital city aa.
- The remaining transformations Sb,ScS_{b}, S_{c} \ldots Since all cities except aa are under the spell, each of these are again "single-city" transformations which end up freeing cities b,c,b, c, \ldots.
Thus, after the 12 visits, city aa is still free. In fact, we have shown more, namely that the state of each of the 12 cities of the kingdom will repeat every 12 months. For example, if city #5 was free last Thanksgiving, it will be free this Thanksgiving; if city #7 was under the spell last Thanksgiving, it will also be under the spell this Thanksgiving, etc.

It remains to prove the key fact that the SjS_{j} transformations are commutative. Specifically, we will show that
Sj(Si(x1,x2,,x12))=Si(Sj(x1,x2,,x12)) S_{j}\left(S_{i}\left(x_{1}, x_{2}, \ldots, x_{12}\right)\right)=S_{i}\left(S_{j}\left(x_{1}, x_{2}, \ldots, x_{12}\right)\right)
for any distinct i,ji, j and for any 12-tuple (x1,x2,,x12)(x_{1}, x_{2}, \ldots, x_{12}). We can do this by examining several cases which depend on the 12-tuple.
1) All the coordinates are zero. In other words, all towns are currently free of the spell. It is easy to check that performing SiS_{i} on this will make all xk=1x_{k}=1 except xi=0x_{i}=0. Then performing SjS_{j} will change xjx_{j} to 00. The net result is that all values are 11 except for xi=xj=0x_{i}=x_{j}=0. Clearly, we will have the same result if we perform SjS_{j} first, and then SiS_{i}.
2) Exactly one of the coordinates is 11.
(a) Suppose xi=1x_{i}=1 and all others are zero. Performing SiS_{i} makes xi=0x_{i}=0 and hence now all values are zero. Then SjS_{j} results in all values equalling 11 except xj=0x_{j}=0. Conversely, performing SjS_{j} first will put all cities from jj to i1i-1 under the spell (travelling clockwise) until the magician reaches city ii which she then frees of the spell and stops. So now there is an "arc" of 11's from xjx_{j} to xi1x_{i-1} and all other values are 00. Performing SiS_{i} on this turns the values of the arc from ii to j1j-1 into 11's, until she reaches city jj, and then she frees this city and stops. The net result again is that all values are 11 except xj=0x_{j}=0. The figure below illustrates this. We assume clockwise travel and denote free/spell by white/black, respectively.
Figure 1

(b) Suppose xj=1x_{j}=1 and all others are zero. This case is exactly the same as 2(a) above; just interchange ii and jj.
(c) Suppose that xk=1x_{k}=1 and all others are zero, with kik \neq i and kjk \neq j. The figure below illustrates the case where kk lies on the clockwise arc between ii and jj. The case where kk lies between jj and ii has a similar picture.
Figure 2

3) At least two coordinates equal 11.
(a) Suppose xk=x=1x_{k}=x_{\ell}=1, where kk lies on the clockwise arc from ii to jj and \ell lies on the arc from jj to ii (it is possible that kk or \ell may equal one or both of ii and jj.) Then the order of SiS_{i} and SjS_{j} will not matter-each transformation alters non-overlapping arcs: SiS_{i} only affects the arc from ii to kk, while SjS_{j} affects the arc from jj to \ell.
(b) One of the arcs described in 3(a) contains only zeros. Without loss of generality, suppose that the arc from ii to jj is all zeros (including i,ji, j ) and let kk be the first coordinate clockwise from jj such that xk=1x_{k}=1. The picture below handles this case. The cities between kk and ii are not shaded, but they could be black or white; their state is not relevant, since they will be unaffected by SiS_{i} or SjS_{j}.
Figure 3

These cases encompass all possibilities, so we conclude that SiS_{i} and SjS_{j} commute for all 12-tuples and the proof is complete.

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.