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.

find osama hiding in a cave

I read this puzzle a while back but was unable to solve it.

I have recently been going on a string of interviews and chanced upon the same puzzle again.
This time I sat down with a pen and paper, this is what I've got.

The Puzzle:
Osama is hiding in a series of interconnected caves, there are 15 of them in all numbered
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

Every day you are allowed to go into any one cave of your choosing and find osama. If you do not find him, you may only try again the following day.

Every night osama will move either to the right or to the left of the current cave he is in, but if he were in cave 1 or cave 15 he may only move 1 cave towards the center.
Eg: 4 -> 5 or 4 -> 3
15 -> 14
1 -> 2

Objective:
Name a series of cave visits that will definitely find osama or if there exists no such series prove it.

This puzzle is challenging and you should try it before proceeding down to the solution.









Solution:
Suppose we reduce the problems down to 1 cave, the obvious solution is 1

2 cave
the solution would be 1,1

3 cave
the solution would be 2,2

4 cave
the solution would be 2,3,3,2

5 caves, this is where it became too challenging to do it mentally,
the solution required a pen and paper and some efficient form of representation
By the way the solution is 2,3,4,2,3,4


you might want to verify this solution and arrive at your own form of representation.





















This is my representation:

Day	Possible locations of osama	Our choice of cave	Possible locations of osama after visit
1	1,2,3,4,5	2	1,3,4,5
2	2,3,4,5	3	2,4,5
4	1,3,4,5	4	1,3,5
5	2,4	2	4
6	3,5	3	5
7	4	4	FOUND

what about the solution for 15 caves? Why don't you do it and tell me.


How about writing a generic algorithm for n caves?