Please feel free to give this question a more appropriate title, as I didn't really know how to describe the problem briefly. This question concerns a exercise from A Concise Introduction to Pure Mathematics, Third Edition by Martin Liebeck,more precisely 2nd chapter, exercise 8. I will paraphrase the question:

Imagine we have a total of 30 lizards, 15 red ones, 8 green ones, 7 blue ones. When two lizards of the same color come meet, they turn into the two other colors (for example, when two red lizards meet, one turns green and the other blue). When two lizards of different colors meet, they both turn into the third color. Is it possible to have all red lizards at some instant in the future? (Hint: Consider the remainder of each color when you divide by three.)

My first instinct is to play around a little with the numbers. It seems to me like it's not possible (instinctively, there's no way to get the number of Blues to match the number of Greens). Fair enough. Next instinct is to take the hint. If we look at the remainders when we divide by three, we obtain the following configuration: $$0R - 2G - 1B$$

After some playing around, it becomes evident that this whole modulo three thing actually describes the configuration. Any operation that I do on the actual numbers I can reflect on this modulo three business. (If I perform R + R on the numbers, and then take the remainders of division by three, I obtain the same results as performing R + R as directly on the modulo three configuration.) After some more playing around, it becomes obvious that the configuration is always going to be $$2- 1 -0$$

A short proof (I hope this actually proves it). Our initial configuration is $2- 1 -0$, therefore the only possible operations are: the two same objects meet, or the one lone object meets one of the two similar objects. In both cases we end up with a $2-1-0 $ configuration.

Therefore there can never be 30 red lizards at once, since that would imply a configuration $0 - 0 -0$.

My questions are:

  • is my reasoning correct?
  • Why does mod 3 "encompass" the operations so well? Why mod 3?
  • How can I formalize this argument? What kind of mathematics if this?
  • $\begingroup$ Is there something I missed in my answer? (except understandable English, but forgive me that, it is not my mother language and I am doing my best) I will add it there. $\endgroup$ – TStancek Jul 12 '17 at 14:12

If you want to get all lizards to be the same color, there must be two colors represented by the numbers, that have the same remainder modulo 3. But to your questions:

a) yes, your reasoning is correct

b) Because every time two lizards of the same color meet, the distance of the count of lizards of this color to the remaining two counts is decreased by three (the number itself is decrased by two, but the other two are increased by one, in total the distance is decreased by three). And the other two colors remain the same distance.

And when two lizards of different color meet, the distance of their count is unchanged, but distance of the count of the lizards of the third color to those two is increased by three. So all distances betwen the counts of the colors are unchanged modulo three under any meeting.

EDIT: c) there would be multiple ways to represent this mathematically, but one of them for instance is point in 3D grid, and you can move in directions (2,-1,-1),(-1,2,-1), (-1,-1,2) or their opposites. There you can actually show that the condition stated in the beginning must be true. You actually have to get to point $(0,0)$ in the projective 2D grid representing the two colors you are trying to cancel. But you can only move along diagonal or jump to a diagonal distant three points from your current position. And that means only diagonals intersecting multiples of three on both coordinates at one point are the set of states, from where you can end up in one color only state.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.