On Chameleon Island exists a peculiar sort of chameleon. At any given time any given chameleon is either red, blue or green. When two chameleons of unlike color meet, both immediately change to the remaining possible color.

I scientist has collected 36 of these animals, 12 of each color, and kept them in 36 separate containers to prevent color change, but he wants to keep them in two terraria.

When kept together in small numbers, there's a danger that all the lizards will ultimately go to one color, as exemplified by the following scenario starting out with 1 red, 4 blue and 13 green chameleons. The two letters at the left of each line specify the meeting that changed the count to the one on the given line:

      r  b  g
      1  4 13
rg    0  6 12
bg    2  5 11
rg    1  7 10
rg    0  9  9
bg    2  8  8
bg    4  7  7
bg    6  6  6
bg    8  5  5
bg   10  4  4
bg   12  3  3
bg   14  2  2
bg   16  1  1
bg   18  0  0

From then on, this scenario has all 18 of its chameleons red.

How can the scientist divide his 36 chameleons between the two terraria without posing the possibility of all becoming one color in either terrarium? Assume that no births or deaths occur. There's more than one way.

The reason the example can go to all the chameleons in the same cage is the differences between the number of each color is always a multiple of 3 and the total is a multiple of 3.

(r,b,g) becomes (r-1,b-1,g+2) after a rb meeting.  If b-g is a multiple of 3 then so will (b-1)-(g+2) etc...

So we can eventually reach (18,0,0) or (0,18,0) or (0,0,18)

The key is to split our 12 of each so this is not the case.

(1,2,15) comes to mind which makes the other (11,10,3)

Posted by Jer on 2009-09-25 15:27:02