Greenwich Maths Challenge 5

The problem posed was as follows:

"In the small country of Mathsland, the citizens are obsessed with politics. Each one passionately supports one of the three political parties, which are the Coffee, Milk and Water parties.

Whenever two citizens meet, they discuss politics. If they support the same party, they don’t change their allegiance, but if two citizens who support different parties meet, they are both so persuasive that each of them abandons their previous allegiance and supports the third party. Thus if Milk and Water supporters meet, they both change to support Coffee.

The repressive laws of Mathsland forbid any gathering of more than two people so all political discussions are limited to the above. If at any time all citizens support a single party, that party will declare a dictatorship and the other two parties will be abolished.

Initially there are 13 supporters of Coffee, 15 of Milk and 17 of Water. Find the shortest possible sequence of meetings which results in a dictatorship, or prove that under these conditions no party will ever command the support of every citizen."

This was the most popular Greenwich Maths Challenge yet, with entries almost equally divided between those who claimed to have found such a sequence and those who claimed to have proved it was impossible. The latter were correct, with several excellent answers submitted. In the opinion of the judges, the first completely valid proof came from Aaron Lang, who wins the prize.

The puzzle is an old one: the traditional scenario involves chameleons but we didn't want it to be too easy to google so we changed the setting. It can be found in several books of puzzles. One solution, given in Terence Tao's Solving Mathematical Problems, is to assign values of 0 to supporters of Coffee, 1 to Milk and 2 to Water. The initial total is 49, which gives a remainder of 1 when divided by 3. One can verify that each of the three possible moves changes the total - for example Coffee meeting Milk removes one of each, subtracting one from the total, but adds two Waters, adding 4 - but that each change does not alter the remainder after division by 3. So at any stage the remainder must remain at 1, but any of the desired solutions needs remainder zero, so they are impossible.