Wednesday, April 6, 2011

chamelions of the same color

I was given this puzzle during one of my interviews

Puzzle:
There are 16 red, 14 green and 12 blue chamelions living on an island,
every time two chamelions of the same color meet they will both change to the other color.
nothing happens when two chamelions of the same color meet.
every meeting of chamelions only involve two chamelions
Eg: the meeting of 1 red and 1 blue chamelion will result in the both of them changing to green


Name a series of chamelion meet ups that will result in all the chamelions being of the same color, and if there exists no such series, prove it.



The solution:
There does not exits such a series


The proof is induced backwards starting from the ideal state where all chamelions are of the same color.

All chamelions are of the same color implies that two of the three colors have zero chamelions.

Since for each meet up two colors are decremented by one (-1) and the other color is incremented by (+2).

These operations of -1,-1,+2 implies that in order to achieve two colors having 0 chamelions at some point prior these two colors are of the same equal positive number.
Eg:
R = 1, G=40, B=1
R-1,G+2,B-1
R=0,G=40,B=0

The paired difference between any two colors of chamelions are (R,G) = 2, (R,B) = 4, (G,B) = 2

Looking closely at the operation -1,-1,+2 regardless of how they are assigned to the colors will only alter these paired differences by -3,0,+3.
Eg:
-1,-1 will result in no change in difference; 0
-1,+2 will result in a change of difference; +-3

Therefore the paired difference of 2,4,2 can never be reduced to 0 by the any number of operations that alter their paired differences by -3,0,+3.

This also implies that there does not exists a series of operations that will result in two colors having the same positive number (difference = 0) and therefore never result in all camelions being of the same color.

No comments:

Post a Comment