Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Shopping at the store helps maintain the site. Thank you.
Ask a tutor for free
Learning Math Online

Sites for parents
Terms of use
Awards
Interactive Activities

CTK Exchange
CTK Wiki Math
CTK Insights - a blog
Math Help

III Millennium Olympiad

Games & Puzzles
What Is What
Arithmetic/Algebra
Geometry
Probability
Outline Mathematics
Make an Identity
Book Reviews
Stories for Young
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
Visual Illusions
My Logo
Math Poll
Cut The Knot!
MSET99 Talk
Other Math sites
Front Page
Movie shortcuts
Personal info
Privacy Policy

Guest book
News sites

Recommend this site

Sites for parents

Education & Parenting

Manifesto  |  Bookstore  |  Contents  |  Amazon store  |  Term index  |  What changed?  |  Contact  |  Recommend
RSS Feed: Recent changes at CTK

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.

Copyright © 1996-2009 Alexander Bogomolny

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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.

Copyright © 1996-2009 Alexander Bogomolny

34384609Page copy protected against web site content infringement by Copyscape

Search:
Keywords:

Google
Web CTK