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 to . Encode the current state of affairs by starting at city , 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 down to city . Interpret the resulting list as the binary expansion of an integer between and .
Some thought (using modular arithmetic modulo , 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 then is added to , where encodes the state as above. After 12 months the magician starts once at all cities, and this has the net effect of adding
to the original which obviously leaves the state unchanged.
Solution:
We shall denote the state of the kingdom by a 12-tuple of 's and 's, with and meaning "free of spell" and "under spell," respectively. For example, suppose that the initial state is . This means that city #1 is free of the spell, city #2 is under the spell, city #3 is free, etc. Next, define , for to be the transformation of the kingdom after the magician makes a visit that starts at city . For example,
since she puts a spell on city #1, then comes to city #2 which is already under the spell, frees it, and stops. Likewise,
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:
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 transformations commute; i.e.
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:
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 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 , where we may choose the order in any way that we like.
Consider the state of the kingdom last Thanksgiving. Suppose cities are spell-free (where city is the capital) and cities are under the spell. Now we shall perform the transformations, in this order:
- : 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.)
- : Starting with , all cities get put under the spell (since they were previously all free), until the magician returns to , frees it, and stops. Now all cities are under the spell, except for the capital city .
- The remaining transformations Since all cities except are under the spell, each of these are again "single-city" transformations which end up freeing cities .
Thus, after the 12 visits, city 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 transformations are commutative. Specifically, we will show that
for any distinct and for any 12-tuple . 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 on this will make all except . Then performing will change to . The net result is that all values are except for . Clearly, we will have the same result if we perform first, and then .
2) Exactly one of the coordinates is .
(a) Suppose and all others are zero. Performing makes and hence now all values are zero. Then results in all values equalling except . Conversely, performing first will put all cities from to under the spell (travelling clockwise) until the magician reaches city which she then frees of the spell and stops. So now there is an "arc" of 's from to and all other values are . Performing on this turns the values of the arc from to into 's, until she reaches city , and then she frees this city and stops. The net result again is that all values are except . The figure below illustrates this. We assume clockwise travel and denote free/spell by white/black, respectively.
(b) Suppose and all others are zero. This case is exactly the same as 2(a) above; just interchange and .
(c) Suppose that and all others are zero, with and . The figure below illustrates the case where lies on the clockwise arc between and . The case where lies between and has a similar picture.
3) At least two coordinates equal .
(a) Suppose , where lies on the clockwise arc from to and lies on the arc from to (it is possible that or may equal one or both of and .) Then the order of and will not matter-each transformation alters non-overlapping arcs: only affects the arc from to , while affects the arc from to .
(b) One of the arcs described in 3(a) contains only zeros. Without loss of generality, suppose that the arc from to is all zeros (including ) and let be the first coordinate clockwise from such that . The picture below handles this case. The cities between and are not shaded, but they could be black or white; their state is not relevant, since they will be unaffected by or .
These cases encompass all possibilities, so we conclude that and commute for all 12-tuples and the proof is complete.