Generalization That Solves the Problem

Manifesto | Index | What's new | rss feed

| Bookmark |

| Follow us

| Recommend | Contact |

Generalization That Solves the Problem

I was sent the following problem that was offered at the 2008 Rasor-Bareis-Gordon contest at the Ohio State University:

Chameleons on an island come in three colors. They wander and meet in pairs. When two chameleons of different colors meet, they both change to the third color. Given that the initial amounts of the chameleons of the three colors are 13, 15, and 17, show that it may not happen that, after a while, all of them acquire the same color.

Three solutions have been posted after the competition.

Solution 1. Let x be the number of times colors A and B meet, y the number of times colors A and C meet, and z the number of times colors B and C meet. If we end up with all of color A, then we have the system of three linear equations 13 - x - y + 2z = 45, 15 - x + 2y - z = 0, 17 + x - y - z = 0. This system has no solution all in integers, for example by Gaussian elimination. The same reasoning works for right-hand sides 0, 45, 0 and for 0, 0, 45. So it is impossible.

Solution 2. Let a, b, c be the number of chameleons of each color. Note that under any of the three possible changes, the value b - a changes by a multiple of 3. [a and b both decrease by 1 so b - a remains unchanged; or a decreases by 1 and b increases by 2 so b - a increases by 3; or a increases by 2 and b decreases by 1 so b - a decreases by 3.] But b - a begins at 2, so it can never reach 0, it can never reach 45, and it can never reach -45.

Solution 3. Represent the colors by 0, 1, and 2, for, respectively, the 13, 15, and 17 chameleons. Let a and b be the distinct colors of two chameleons who meet and let c be the third color. Then a + b = -c (mod 3). When the two chameleons change color, they both become color c, and c + c = 2c = -c (mod 3); so color changes do not change, modulo 3, the sum of the colors of all chameleons. Since the total number of chameleons is a multiple of 3, if all acquired the same color, then the color sum would be 0 (mod 3). However, the initial color sum is 13×0 + 15×1 + 17×2 = 1 (mod 3).

The same problem has been discussed at the wu:forums under the rubric Political slugfest, where ecoist offered a generalization:

Members of n > 2 political parties gather to debate each other. Whenever n - 1 of these guys meet to debate, no two belonging to the same party, they each become so disillusioned that all n - 1 switch to the party none belong to. If initially no two parties have numbers of members at the gathering which are congruent modulo n, show that it cannot happen that, after awhile, everyone at the gathering belongs to the same party.

Curiously, not only the generalization is as easy as the original problem, but, by pointing to a property of the triple 13, 15, 17 that did not stand out otherwise, the generalization actually spelled its own solution.

Indeed, when n - 1 members of different parties defect to some other party, the latter acquires n - 1 new members, whilst the remaining parties lose a member each. However -1 ≡ n - 1 (mod n), meaning that modulo n the number of members in every of n parties changes by -1. Assuming that all memberships were different modulo n, to start with, we see that the operation of subtracting -1 modulo n does not affect this fact: all memberships remain different modulo n.

40617653