Browse · MathNet
PrintEstonian Math Competitions
Estonia counting and probability
Problem
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?
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?
Solution
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.
---
Alternative solution.
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 for some integer . 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 for some integer . Thus , but this equation has no integral solutions.
b. Analogously, if the number of brown chameleons were 60 then the number of meets must be for an integer ; then the number of orange chameleons would be 0, requiring meets for an integer , but the equation has no integral solutions. If the number of brown chameleons were 0 then the number of meets must again be . If the number of orange chameleons were also 0 then the number of meets would be for an integer leading to the same equation; if the number of green chameleons were 0 then we would get the equation which also does not have integral solutions.
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.
---
Alternative solution.
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 for some integer . 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 for some integer . Thus , but this equation has no integral solutions.
b. Analogously, if the number of brown chameleons were 60 then the number of meets must be for an integer ; then the number of orange chameleons would be 0, requiring meets for an integer , but the equation has no integral solutions. If the number of brown chameleons were 0 then the number of meets must again be . If the number of orange chameleons were also 0 then the number of meets would be for an integer leading to the same equation; if the number of green chameleons were 0 then we would get the equation which also does not have integral solutions.
Final answer
a. No; b. No.
Techniques
Invariants / monovariants