6. 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 $k$ can it be guaranteed that $k$ red chameleons can agree to turn blue?

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

(2022-60, M. Raskin)
# Answer. For $k=5$. Solution.

First, let's provide an example of rules under which the described recoloring would require at least 5 red chameleons. Let's number the colors so that red is the first color and blue is the last. Then, let the rules be as follows: if a chameleon of color $k1$ can reduce the number of its color by means of a bite from a chameleon of color $l<k$. In other words, chameleons of colors $1, \ldots, k$ can become colors $1, \ldots, k-1$. By applying this reasoning several times, we will 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 slight modifications 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 faster than

![](https://cdn.mathpix.com/cropped/2024_05_06_fde2078dee7bae03239bg-09.jpg?height=60&width=1676&top_left_y=2631&top_left_x=156)
known as the Ackermann function.

Fortunately, if all chameleons must be of the same 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 even further simplifies the situation. It corresponds to "immediate observation" or "one-way communication" in Petri nets (immediate observation, one-way communication).

In this variant, for example, it is shown—using combinatorial methods accessible to school students—that if 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 $n^{3}$ chameleons.