|
|
 |
Условие
На острове живут хамелеоны пяти цветов. Когда один хамелеон кусает другого, цвет укушенного хамелеона меняется по некоторому правилу, причём новый цвет зависит только от цвета укусившего и цвета укушенного. Известно, что $2023$ красных хамелеона могут договориться о последовательности укусов, после которой все они станут синими. При каком наименьшем $k$ можно гарантировать, что $k$ красных хамелеонов смогут договориться так, чтобы стать синими?
Например, правила могут быть такими: если красный хамелеон кусает зелёного, укушенный меняет цвет на синий; если зелёный кусает красного, укушенный остаётся красным, то есть «меняет цвет на красный»; если красный хамелеон кусает красного, укушенный меняет цвет на жёлтый, и так далее. (Конкретные правила смены цветов могут быть устроены иначе.)
Решение
Для начала приведём пример правил, при которых для описанной перекраски будет необходимо хотя бы 5 красных хамелеонов. Занумеруем цвета так, чтобы красный был первым цветом, а синий — последним. Тогда пусть правила выглядят следующим образом: если хамелеон цвета $k < 5$ кусает хамелеона цвета $k$, укушенный меняет цвет на $k + 1$. Кроме того, все хамелеоны, укушенные синим хамелеоном, тоже становятся синими. Никакие другие ситуации цвета хамелеонов не меняют. Несложно заметить, что если изначально хамелеонов всего $4$, то, при таких правилах, ни у одного из них не получится стать синим. Действительно, никакой появившийся цвет не может исчезнуть раньше появления синего. Кроме того, никакой цвет не может появиться раньше, чем появятся все предыдущие. Таким образом, в момент появления первого синего хамелеона есть хотя бы по одному хамелеону каждого из цветов.Теперь докажем, что пяти хамелеонов хватит. Процесс перекрашивания будет состоять из двух этапов. На первом этапе наши пять выделенных хамелеонов должны следить за тем, как перекрашиваются $2023$ хамелеона из красного в синий и перекрашиваться параллельно с ними «забегами», заботясь о том, чтобы после каждого забега воспроизводились два условия: 1) среди них должно быть не более одного хамелеона каждого цвета, остальные — красные, 2) палитра цветов наших пяти хамелеонов расширяется и всегда содержит в себе палитру цветов $2023$ хамелеонов.
В рамках забега наши пять хамелеонов ждут, когда среди цветов $2023$ хамелеонов появится новый цвет, отсутствующий у наших пяти хамелеонов. Пусть этот цвет представляет хамелеон $X$. Далее пять хамелеонов прослеживают, как перекрашивался хамелеон $X$ из красного цвета, выбирают любого красного хамелеона из пяти и перекрашивают его тем же путём. Это всегда возможно, поскольку палитра цветов остальных четырёх хамелеонов, которые будут его кусать, содержит палитру цветов $2023$ хамелеонов. После этого забега условия 1, 2 воспроизведутся и можно будет перейти к следующему забегу. Первый этап заканчивается в тот момент, когда в палитре $2023$ хамелеонов перестанут появляться новые цвета.
На втором этапе хамелеоны всех встретившихся нам цветов должны перекраситься в синий. Для этого для каждого цвета найдём последний момент его присутствия в алгоритме для $2023$ хамелеонов и упорядочим цвета в соответствии с этими моментами в обратном порядке. Таким образом, синий цвет будет первым, предыдущий цвет хамелеона, ставшего синим в последнюю очередь, — вторым и так далее. Тогда, в силу построенного порядка, хамелеон цвета $k>1$ может уменьшить номер своего цвета посредством укуса от хамелеона цвета $l < k$. Другими словами, хамелеоны цветов $1, \dots, k$ могут стать цветов $1, \dots, k-1$. Применив это рассуждение несколько раз, получим, что наши хамелеоны могут все поменять свой цвет на синий.
Комментарий. Нетрудно заметить, что для $n$ цветов понадобится $n$ хамелеонов. На самом деле это задача — один из многих вопросов вокруг (в общем случае) сетей Петри. От совсем небольших изменений задачи минимальный размер стартовой популяции может значительно увеличиться.
Например, пусть при укусе оба хамелеона могут по-разному менять свой цвет, а достичь надо состояния с одним зелёным хамелеоном и многими синими. В таком случае минимальное количество может расти быстрее не только любого многочлена от $n$, но и любой функции вида $n^{n^{n^{\ldots}}}$! Это было доказано совсем недавно; в ответе появляется так называемая функция Аккермана.
К счастью, если все хамелеоны должны быть одного цвета и в начале, и в конце, ситуация заметно упрощается. Требование же, что при укусе меняет цвет только один из хамелеонов, даже само по себе упрощает ситуацию ещё сильнее. Оно соответствует «немедленному наблюдению», или «одностороннему взаимодействию» в сетях Петри (immediate observation, one-way communication).
В этом варианте показано, например — вполне доступными школьникам комбинаторными методами, — что если есть два набора цветов хамелеонов и после добавления к ним одинакового количества синих хамелеонов из первого становится можно получить второй, то достаточно добавить $n^3$ хамелеонов.
