На острове живут хамелеоны пяти цветов. Когда один хамелеон кусает другого, цвет укушенного хамелеона меняется на один из этих пяти цветов по некоторому правилу, причём новый цвет зависит только от цвета укусившего и цвета укушенного. Известно, что \(2023\) красных хамелеона могут договориться о последовательности укусов между собой, после которой все они станут синими. При каком наименьшем \(k\) можно гарантировать, что \(k\) красных хамелеонов, кусая только друг друга, смогут стать синими?

(Например, правила могут быть такими: если красный хамелеон кусает зелёного, укушенный меняет цвет на синий; если зелёный кусает красного, укушенный остаётся
красным, то есть «меняет цвет на красный»; если красный кусает красного, укушенный меняет цвет на жёлтый, и т. д. Правила смены цветов могут быть другими.)

Решение

Для начала приведём пример правил, при которых для описанной перекраски потребуется хотя бы \(5\) красных хамелеонов. Занумеруем цвета так, чтобы красный был первым цветом, а синий \(-\) последним. Пусть правила выглядят так: если хамелеон цвета \(k < 5\) кусает хамелеона того же цвета, укушенный меняет цвет на \(k + 1\). Кроме того, хамелеон, укушенный хамелеоном синего цвета, становится синим. Никакие другие ситуации цвета хамелеонов не меняют. Несложно заметить, что если изначально хамелеонов всего \(4\), то ни у одного из них не получится стать синим. (Действительно, никакой появившийся цвет не может исчезнуть раньше появления синего. Кроме того, никакой цвет не может появиться раньше, чем появятся все предыдущие. Тогда к моменту появления первого синего хамелеона есть хотя бы по одному хамелеону каждого из остальных цветов, то есть это \(4\) хамелеона разного цвета, но их укусы друг друга уже не изменят их окраски.) С другой стороны, если красных хамелеонов больше \(4\), то сначала четыре из них приобретают \(2\)-й цвет, потом три \(-\) \(3\)-й, два \(-\) \(4\)-й, после чего один становится синим и превращает в синих всех остальных.

Теперь докажем, что \(5\) хамелеонов хватит. Рассмотрим основную группу из \(2023\) хамелеонов, которые постепенно из красных становятся синими, и контрольную группу из пяти красных хамелеонов, которых предстоит превратить в синих.

\(\textbf{1-й этап.}\) Пусть в основной группе использовалось всего \(n \leqslant 5\) цветов. Пронумеруем эти цвета в соответствии с моментами их первого появления (\(1\)-й цвет будет красным). На этом этапе на \(m\)-м шаге \(\left( 1 < m \leqslant n \right)\) будем превращать одного из красных хамелеонов контрольной группы в хамелеона цвета \(m\) (после этого в контрольной группе будет по одному хамелеону цветов \(2, \dots, m\) и \(6 - m\) красных). Для этого рассмотрим момент, когда в основной группе впервые возник хамелеон \(X\) цвета \(m\). В начале он был красным и приобрел свой цвет после того, как его укусили несколько хамелеонов, имеющих цвета с меньшими номерами (других до этого момента в основной группе не было). Возьмём в контрольной группе красного хамелеона и устроим ему ту же последовательность кусаний (это возможно, поскольку среди оставшихся хамелеонов есть хамелеоны всех цветов от \(1\) до \(m - 1\)). В конце этого этапа в контрольной группе будет по одному хамелеону цветов \(2, \dots, n\) и \(6 - n\) красных.

\(\textbf{2-й этап.}\) Перенумеруем цвета в соответствии с моментами их последнего исчезновения в основной группе (\(n\)-й цвет будет синим). Рассмотрим момент исчезновения цвета \(1\). При этом последний хамелеон цвета \(1\) перекрасился после укуса хамелеона, имеющего цвет с большим номером (хамелеонов с номером \(1\) в основной группе больше нет). Пусть после окончания \(1\)-го этапа хамелеон контрольной группы с тем же номером укусит всех хамелеонов цвета \(1\) (если они красные, то их может быть больше одного). Далее аналогично уберём хамелеонов цвета \(2, \dots,\) пока все хамелеоны не станут синими.

Ответ: при \(k = 5\).