На одном тропическом острове живёт 45 хамелеонов. Из них красных - 13, зелёных - 15, а остальные 17 - синие.
Два хамелеона разного цвета при встрече меняют цвет на третий. То есть, при встрече зелёного и красного хамелеона, они оба поменяют цвет на синий.
Может ли так оказаться, что по прошествии некоторого времени все хамелеоны на острове окажутся одного цвета?
Ответ:
Обозначим цвета хамелеонов: красный=0, зелёный=1, синий=2.
Тогда получается, что встречи хамелеонов описываются суммами их цветов:
0+1 → 2+2
1+2 → 0+0
0+2 → 1+1
Заметим, что при встрече хамелеонов всегда неизменной остаётся сумма их цветов, взятая по модулю 3 (то есть, остаток от деления суммы цветов на 3). В самом деле,
Это значит, что при любых встречах хамелеонов остаток от деления суммы всех цветов на 3 не изменится.
Изначально сумма цветов хамелеонов была равна 13*0 + 15*1 + 17*2 = 49.
49 mod 3 = 1, поэтому как бы ни меняли свой цвет хамелеоны, остаток от деления суммы их цветов на 3 останется 1.
В случае, если все хамелеоны стали бы одного цвета, остаток бы стал равен нулю (ведь 45*N всегда делится на три нацело), а значит, такого произойти не может.