Задача 67286

Темы:    [ Доказательство от противного ] [ Инварианты ]

Сложность: 4 Классы: 6,7,8

Условие

Автор: Русских И.

На острове живут красные, синие и зелёные хамелеоны. 35 хамелеонов встали в круг. Через минуту все они одновременно поменяли цвет, каждый на цвет одного из своих соседей. Ещё через минуту снова все одновременно поменяли цвета на цвет одного из своих соседей. Могло ли оказаться, что каждый хамелеон побывал и красным, и синим, и зелёным?

Решение 1

Предположим, такое случилось. В первый раз никакой хамелеон не мог отдать свой цвет обоим соседям — иначе он будет стоять между двумя хамелеонами этого же цвета и во второй раз будет вынужден окраситься в этот цвет вновь. Но никакой хамелеон не мог отдать свой цвет обоим соседям и во второй раз: если так произошло, то этот хамелеон минуту назад получил этот цвет от одного из соседей, значит, один из его соседей принимал этот цвет два раза — в начале и в конце. Поэтому каждый хамелеон каждый раз отдаёт свой цвет не более чем одному соседу, то есть количество хамелеонов каждого цвета не увеличивается. Но хамелеонов 35, а цветов 3, значит, изначально хамелеонов какого-то цвета не больше 11 (иначе суммарно хамелеонов хотя бы 12 · 3 = 36). Тогда хамелеонов этого цвета за всё время было не больше 11 · 3 = 33, и какой-то из хамелеонов точно в этот цвет не окрашивался.

Решение 2

Предположим, что такое могло быть. Пронумеруем хамелеонов по кругу от 1 до 35 и нарисуем таблицу из 3 строк и 35 столбцов, в которой каждому хамелеону соответствует столбец (будем считать таблицу зацикленной, то есть после 35-го столбца будет вновь идти первый). Закрасим каждую клетку в первой (верхней) строке в изначальный цвет соответствующего хамелеона, во второй строке — в его цвет через минуту и в третьей строке — в итоговый цвет. Итоговый цвет каждый хамелеон мог позаимствовать от правого или от левого соседа, но, поскольку каждый хамелеон каждый цвет принимал ровно один раз, правый сосед мог получить этот цвет после первой минуты только от своего правого соседа, а левый — только от своего левого. То есть в таблице от каждой клетки третьей строки вверх идёт одна или две одноцветные диагонали (см. рис.).

Посмотрим на первого хамелеона. Без ограничения общности, пусть от его клетки в третьем ряду одноцветная диагональ идёт вправо. Посмотрим на хамелеона номер 3: в его столбце первая и третья клетки должны быть разного цвета, а значит, диагональ от его нижней клетки может идти только вправо. Рассуждая аналогично, получаем, что и у хамелеонов с номерами 5, 7, ..., 35 диагональ от нижней клетки идёт вправо.

Но те же самые рассуждения можно применить к хамелеонам 35 и 2 — то есть и от нижних клеток хамелеона 2, а также хамелеонов 4, 6, ..., 34 диагонали могут идти только вправо! Значит, вся таблица раскрашена в диагональные «полоски». При этом диагонали соседних хамелеонов или хамелеонов, сидящих через одного, должны быть разного цвета: иначе один из хамелеонов два раза примет один и тот же цвет. Это означает, что цвета полосок повторяются (первый, второй, третий, первый, второй, третий, ...), тогда итоговый цвет 35-го хамелеона совпадает с итоговым цветом 2-го—противоречие.

Ответ

Не могло.

Замечания

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

Источники и прецеденты использования

олимпиада
Название	Математический праздник
год
Год	2024
класс
Класс	7
задача
Номер	5