On an island live 13 purple, 15 yellow and 17 maroon chameleons. When two chameleons of different colors meet, they both change into the third color. Is there a sequence of pairwise meetings after which all chameleons have the same color?


A problem from Tournament of Towns, 1984.


Let <p, y, m> denote a population of p purple, y yellow and m maroon chameleons. Can population <13, 15, 17> can be transformed into <45, 0, 0> or <0, 45, 0> or <0, 0, 45> through a series of pairwise meetings? Define function X(p, y, m) = (0p + 1y + 2m) mod 3. An interesting property of X is that its value does not change after any pairwise meeting because X(p, y, m) = X(p-1, y-1, m+2) = X(p-1, y+2, m-1) = X(p+2, y-1, m-1). Now X(13, 15, 17) equals 1. However, X(45, 0, 0) = X(0, 45, 0) = X(0, 0, 45) = 0. This means that there is no sequence of pairwise meetings after which all chameleons will have identical color.

Design a 3-input 3-output logic circuit that negates the 3 signals. You have an infinite supply of AND and OR gates but only two NOT gates.

Next Puzzle: Pebble Piles

You are given three piles with 5, 49 and 51 pebbles respectively. Two operations are allowed: (a) merge two piles together or (b) divide a pile with an even number of pebbles into two equal piles. Is there a sequence of operations that would result in 105 piles with one pebble each?

20 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.