На острове было 13 красных, 15 зеленых и 17 синих хамелеонов. Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий (например, синий и зеленый - меняются на красный). Может ли случиться так, что через некоторое время все хамелеоны окажутся одного цвета?

На острове было 13 красных, 15 зеленых и 17 синих хамелеонов. Если встречаются два хамелеона разного цвета, то они одновременно меняют свой цвет на третий (например, синий и зеленый - меняются на красный).

Может ли случиться так, что через некоторое время все хамелеоны окажутся одного цвета?

Ответ: Обозначим цвета хамелеонов: красный=0, зелёный=1, синий=2.

Тогда получается, что встречи хамелеонов описываются суммами их цветов:

0+1 → 2+2

1+2 → 0+0

0+2 → 1+1

Заметим, что при встрече хамелеонов всегда неизменной остаётся сумма их цветов, взятая по модулю 3 (то есть, остаток от деления суммы цветов на 3). В самом деле,

0+1 (остаток = 1) → 2+2 = 4 (остаток = 1)

1+2 (остаток = 0) → 0+0 = 0 (остаток = 0)

0+2 (остаток = 2) → 1+1 = 2 (остаток = 2)

Это значит, что при любых встречах хамелеонов остаток от деления суммы всех цветов на 3 не изменится.

Изначально сумма цветов хамелеонов была равна 13*0 + 15*1 + 17*2 = 49.

49 mod 3 = 1, поэтому как бы ни меняли свой цвет хамелеоны, остаток от деления суммы их цветов на 3 останется 1.

В случае, если все хамелеоны стали бы одного цвета, остаток бы стал равен нулю (ведь 45*N всегда делится на три нацело), а значит, такого произойти не может.

Все хамелеоны никогда не станут одного цвета!

1. Количество хамелеонов каждого вида, после очередной встречи двух разноцветных хамелеонов, представим в виде последовательностей:

Rn, красные хамелеоны; Gn, зеленые хамелеоны; Bn, синие хамелеоны.

Первоначально, для каждого вида имеем:

R1 = 13; G1 = 15; B1 = 17.

3. Предположим, n-я встреча была между красным и зеленым хамелеонами. Тогда получим:

R (n+1) = Rn - 1; G (n+1) = Gn - 1; B (n+1) = Bn + 2.

Разность количества хамелеонов в каждой паре:

B (n+1) - R (n+1) = Bn + 2 - (Rn - 1) = Bn - Rn + 3; B (n+1) - G (n+1) = Bn + 2 - (Gn - 1) = Bn - Gn + 3; G (n+1) - R (n+1) = Gn - 1 - (Rn - 1) = Gn - Rn.

4. Полученные равенства показывают, что после очередной встречи, не меняется остаток этих разностей при делении на 3. Поскольку вначале ни в одной из трех пар разность не была кратна 3:

G1 - R1 = 15 - 13 = 2; B1 - G1 = 17 - 15 = 2; B1 - R1 = 17 - 13 = 4 = 3 + 1,

то невозможно, чтобы все хамелеоны оказались одного цвета, иначе разность двух остальных видов была бы равна нулю, т. е. кратна 3.