Maths Olympiad Prep

Library / /58 of 86

Combinatorics Difficulty 6.5 National olympiad Prove it Estonia

There are 25 green, 20 brown and 15 orange chameleons in a zoo. Whenever exactly two chameleons of distinct colours meet, both change their colour to the third one. Otherwise, the chameleons do not change their colours. Is it possible that:

a. at some time instant, we have the same number of chameleons of each colour?

b. at some time instant, all chameleons are of the same colour?

Solutions — 2

Solution 1

*Answer:* (a) No; (b) No.

After each meet of two chameleons, the numbers of chameleons of two colours decrease by 1 and the number of chameleons of the remaining colour increases by 2. Thus the difference of the numbers of chameleons of each two colours is constant modulo 3. As the remainders modulo 3 of the numbers of chameleons of different colours are pairwise distinct in the beginning, the numbers of chameleons of no two colours can become equal. This also implies that all chameleons cannot be of the same colour since then the numbers of chameleons of two other colours would be equal to 0.

Solution 2

a. If there were equally many chameleons of each colour, the common number of chameleons of each colour would be 20. To keep the number of brown chameleons all in all unchanged, there must be 2 decreases by 1 per each increase by 2. Hence the total number of meets must be 3x3x for some integer xx. For changing the number of green chameleons from 25 to 20, there must be 5 decreases by 1 and, in addition, 2 decreases by 1 per each increase by 2. Hence the total number of meets must be 5+3y5 + 3y for some integer yy. Thus 3x=5+3y3x = 5 + 3y, but this equation has no integral solutions.

b. Analogously, if the number of brown chameleons were 60 then the number of meets must be 20+3x20 + 3x for an integer xx; then the number of orange chameleons would be 0, requiring 15+3y15 + 3y meets for an integer yy, but the equation 20+3x=15+3y20 + 3x = 15 + 3y has no integral solutions. If the number of brown chameleons were 0 then the number of meets must again be 20+3x20 + 3x. If the number of orange chameleons were also 0 then the number of meets would be 15+3y15 + 3y for an integer yy leading to the same equation; if the number of green chameleons were 0 then we would get the equation 20+3x=25+3y20 + 3x = 25 + 3y which also does not have integral solutions.

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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.