Raskin M.A.

On an island, there live chameleons of five colors. When one chameleon bites another, the color of the bitten chameleon changes according to some rule, and the new color depends only on the color of the biter and the color of the bitten. It is known that $\$ 2023 \$$ red chameleons can agree on a sequence of bites, after which all of them will turn blue. For what smallest $\$ \mathrm{k} \$$ can we guarantee that $\$ \mathrm{k} \$$ red chameleons can agree to turn blue?

For example, the rules might be such that if a red chameleon bites a green one, the bitten one changes to blue; if a green chameleon bites a red one, the bitten one remains red, i.e., "changes to red"; if a red chameleon bites a red one, the bitten one changes to yellow, and so on. (The specific rules for color changes may be different.)

#
Let's start with an example of rules under which at least 5 red chameleons would be necessary for the described recoloring. Let's number the colors so that red is the first color and blue is the last. Then, let the rules be as follows: a chameleon of color $k 1$ can reduce the number of its color by a bite from a chameleon of color $\$ \mathrm{l}<\mathrm{k} \$$$. In other words, chameleons of colors $\$ 1$, \dots, $\mathrm{k} \$$ can become colors $\$ 1, \backslash d o t s, \mathrm{k}-1 \$$$. By applying this reasoning several times, we get that our chameleons can all change their color to blue.

Comment. It is not hard to notice that for $\$ n \$$ colors, $\$ n \$$ chameleons will be needed. In fact, this problem is one of many questions around (in general) Petri nets. With even minor changes to the problem, the minimum size of the initial population can increase significantly.

For example, suppose that upon biting, both chameleons can change their color differently, and the goal is to reach a state with one green chameleon and many blue ones. In this case, the minimum number can grow faster than any polynomial in $\$ n \$$, and even any function of the form $\$ n \wedge\{n \wedge\{n \wedge\{\backslash d o t s\}\}\} \$$! This was proven quite recently; the so-called Ackermann function appears in the answer.

Fortunately, if all chameleons must be of one color both at the beginning and at the end, the situation simplifies significantly. The requirement that only one of the chameleons changes color upon biting further simplifies the situation. It corresponds to "immediate observation" or "one-way communication" in Petri nets (immediate observation, one-way communication). In this variant, it has been shown, for example, using combinatorial methods accessible to school students, that if there are two sets of chameleon colors and after adding the same number of blue chameleons to the first, it becomes possible to obtain the second, then it is sufficient to add $\$$ d $^{\prime} \wedge 3 \$$ chameleons.

## Answer

for $\$ \mathrm{k}=5 \$$\.