![](https://cdn.mathpix.com/cropped/2024_05_06_d3d405875929faed9b27g-21.jpg?height=184&width=2021&top_left_y=917&top_left_x=16)

Koschei the Deathless has kidnapped the three daughters of the tsar. Ivan the Tsarevich set out to rescue them. He comes to Koschei, and Koschei says to him: "Tomorrow morning, you will see five enchanted girls. Three of them are the tsar's daughters, and the other two are mine. They will be indistinguishable to you, but they will be able to recognize each other. I will approach one of them and ask her about each of the five: 'Is this a tsarevna?' She can answer truthfully or falsely, but she is allowed to call exactly two of them tsarevnas (including herself). Then I will question each of the other girls in the same way, and they must also name exactly two tsarevnas. If you can guess who the real tsarevnas are, I will let you go unharmed. And if you can also figure out which one is the eldest, which one is the middle, and which one is the youngest, you can take them with you." Ivan can pass a note to the tsarevnas to instruct them whom to call tsarevnas. Can he, regardless of the answers of Koschei's daughters,

a) return alive?

b) take the tsarevnas with him?

#
a) Let all the princesses call Koshchei's daughters princesses (see the left image). Then Koshchei's daughters will be called at least three times, while princesses will be called no more than twice. This is how Ivan will distinguish them.
![](https://cdn.mathpix.com/cropped/2024_05_06_d3d405875929faed9b27g-21.jpg?height=540&width=1306&top_left_y=1852&top_left_x=384)

b) First method. Let the eldest daughter call the middle and youngest daughters princesses, the youngest call the middle and eldest daughters princesses, and the middle daughter call herself and the youngest (see the right image). Then Ivan will immediately recognize the middle princess - she is the only girl who called herself a princess, and she was called a princess by at least two other girls. After that, Ivan will recognize the youngest princess (she was called by the middle one), and then the eldest (she was called by the youngest).

Second method. Let the princess who will answer Koshchei first call the middle and youngest princesses, the second in line call the eldest and youngest, and the last call the eldest and middle. Then Koshchei's daughters are the two girls who were not called by the other three. There can be no mistake, since each princess is called by at least two others. Now Ivan knows who the princesses are, and the seniority is easily determined.

## [Mathematical Logic (Miscellaneous) $]$ Problem 109639 Topics: [ $\left.\begin{array}{cc}\text { Division with remainder } & \\ \text { [ } & \text { Cooperative algorithms }\end{array}\right]$

Difficulty: $4+$ Classes: $8,9,10,11$

Author: K. A. Knyop

The re-certification of the Council of Sages happens as follows: the king lines them up in a column, one by one, and puts a white, blue, or red hat on each of them. All sages can see the colors of the hats of all the sages in front of them, but they cannot see the color of their own or those behind them. Once a minute, one of the sages must shout out one of the three colors (each sage shouts out a color only once).

After this process is over, the king will execute every sage who shouted out a color different from the color of their hat.

On the eve of the re-certification, all one hundred members of the Council of Sages agreed and came up with a way to minimize the number of executions. How many of them are guaranteed to avoid execution?

## Solution

All 100 sages cannot be guaranteed to survive, since the color of the last sage's hat is not seen by anyone.

We will show how 99 sages can be saved. We will associate the numbers 0, 1, and 2 with the white, blue, and red colors, respectively. In the first minute, the sage standing at the back should shout out the color corresponding to the remainder of the division by 3 of the sum of all the numbers associated with the colors of the hats of the sages standing in front.

Then the sage standing directly in front of him will be able to calculate the color of his hat, since he can see the hats of all 98 sages in front; this color he should shout out in the second minute.

In the third minute, the sage standing 98th in line calculates, based on the information from the two previous shouts and seeing the hats of 97 standing in front, the color of his hat, shouts it out, and so on.

## Answer

99 sages.