![](https://cdn.mathpix.com/cropped/2024_05_06_ed1a9e9dd82795d4db2eg-07.jpg?height=235&width=2041&top_left_y=1283&top_left_x=0)

Authors: Shapovalov A.V., Yatsenno I.V.

At the "Come on, creatures!" competition, 15 dragons are standing in a row. The number of heads of neighboring dragons differs by 1. If a dragon has more heads than both of its neighbors, it is considered cunning; if it has fewer heads than both of its neighbors, it is considered strong; the rest (including those standing at the ends) are considered ordinary. In the row, there are exactly four cunning dragons with 4, 6, 7, and 7 heads, and exactly three strong dragons with 3, 3, and 6 heads. The first and last dragons have the same number of heads.

a) Provide an example of how this could be.

b) Prove that the number of heads of the first dragon is the same in all examples.
It is convenient to represent a row of dragons as a graph: instead of each dragon, we draw a point at a height corresponding to the number of heads the dragon has, and connect these points.

a) See the figure.

b) First, note that somewhere between every two cunning dragons stands a strong one. Indeed, if we walk along the row of dragons, after we pass a cunning dragon, the number of heads starts to decrease. At some point, it must start to increase again - this is the position where the strong dragon stands. Similarly, the increase will eventually end at a cunning dragon.

The first method. Let's look at the order in which strong and cunning dragons can stand. A strong dragon with six heads can only stand between two cunning dragons with seven heads. This gives rise to three cases: the two remaining strong dragons can stand either on the same side of this trio in one of two orders, or on opposite sides.
![](https://cdn.mathpix.com/cropped/2024_05_06_ed1a9e9dd82795d4db2eg-08.jpg?height=756&width=950&top_left_y=27&top_left_x=542)

Case ... $43 \ldots 6 \ldots 3$... 767 ...

![](https://cdn.mathpix.com/cropped/2024_05_06_ed1a9e9dd82795d4db2eg-08.jpg?height=380&width=1009&top_left_y=908&top_left_x=519)

In the first case, 14 dragons are already uniquely determined, and the only way to ensure that the first and last dragons have the same number of heads is to add another dragon with five heads at the far right.

The second and third variants are impossible, as they require more than 15 dragons (even without considering the condition that the first and last dragons have the same number of heads).

The second method (sketch). We can manage without enumeration. Choose a segment of the graph between some strong dragon and the nearest cunning dragons to it and "straighten" it, replacing the "valley" with a "hill" (see the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_ed1a9e9dd82795d4db2eg-08.jpg?height=298&width=352&top_left_y=1709&top_left_x=859)

The number of heads of the dragons will change, and instead of two cunning dragons and one strong one in this segment, there will now be only one cunning dragon. Note that the number of heads of the new cunning dragon will be equal to the sum of the number of heads of the original two cunning dragons minus the number of heads of the former strong dragon. This means that the value "sum of the number of heads of all cunning dragons minus the sum of the number of heads of all strong dragons" does not change.

Note also that the number of heads of the extreme dragons in the row does not change with such an operation. Now repeat this operation until all strong dragons disappear. We will be left with one cunning dragon, which, by symmetry, will be exactly in the middle of the row. Let's calculate how many heads it will have. We know that initially, the sum of the number of heads of cunning dragons minus the sum of the number of heads of strong dragons is

$4+6+7+7-3-3-6=12$. But now this sum is equal to simply the number of heads of the single cunning dragon!

Knowing that it has 12 heads, we can easily restore that the extreme dragons (which are seven positions away from it in the row) each have five heads.