There are chameleons standing in a circle. Some of them are colored red and the others are colored green. Every minute, some of the chameleons change their color from red to green or vice versa in accordance with the following rule: a chameleon changes its color if and only if both its neighbours have the same color. Suppose that after minutes all chameleons have the same color as at the beginning. Prove that there are two chameleons in the circle that have changed their color the same number of times.
, 2012
Solution
Because at the end the chameleons have the same color as at the beginning, they must have changed their color an even number of times, hence times, times, ... or times.
First suppose there exists a chameleon that has never changed its color. Its neighbours then have had the same color every minute, wherefore they have changed their color the same number of times. Similarly, if there exists a chameleon that has changed its color times, its neighbours have had different colors every minute. Then, again, the neighbouring chameleons have changed their color the same number of times.
Lastly, we need to consider the case when each of the chameleons has changed its color at least times and less than times. In this case, we only have possibilities for the number of times that a chameleon has changed its color. Then, according to the Dirichlet's principle, there exist two chameleons that have changed their color the same number of times.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.