Problem 7.4. (15 points) On an island, there live knights who always tell the truth, and liars who always lie. One day, 100 residents of this island lined up, and each of them said one of the following phrases:

- "To the left of me, there are as many liars as there are knights."
- "To the left of me, there are 1 more liar than there are knights."
- "To the left of me, there are 2 more liars than there are knights."
- "To the left of me, there are 99 more liars than there are knights."

It is known that each phrase was said by exactly one person. What is the smallest number of liars that can be among these 100 residents?
Answer: 50.

Solution. Suppose there are no fewer than 51 knights in the row. Consider the rightmost of them. To his left, there are at least 50 knights and no more than 49 liars, so he could not have said any of the listed phrases, leading to a contradiction. Therefore, the total number of knights cannot exceed 50.

Now let's provide an example where there are exactly 50 knights. Suppose the leftmost 50 people are liars, who respectively say the phrases "To my left, there are 99 more liars than knights," "To my left, there are 98 more liars than knights," ..., "To my left, there are 51 more liars than knights," and "To my left, there are as many liars as knights." The next 50 people are knights, who respectively say "To my left, there are 50 more liars than knights," "To my left, there are 49 more liars than knights," ..., "To my left, there is 1 more liar than knights." It is clear that the liars' statements are false, as there are no more than 49 liars to the left of each of them. The statement of the leftmost knight is true, as there are 50 liars and 0 knights to his left. The statements of the subsequent knights are also true, as for each subsequent knight, the number of liars remains unchanged, while the number of knights increases by 1, i.e., the difference between liars and knights decreases by 1.

## Criteria

The points for the estimate and example are summed:

+8 p. Estimate - it is proven that there are no fewer than 50 liars.

In the absence of a correct estimate, the following progress is evaluated:

+6 p. It is proven that if there are \( k \) liars, then the phrases starting from "To my left, there are \( k+1 \) more liars than knights" to "To my left, there are 99 more liars than knights" are false.

+7 p. Example - a correct arrangement of knights and liars with the phrases they say is provided (or it is otherwise proven that such an arrangement exists).

In the absence of a correct example, the highest applicable criterion is used:

+3 p. A suitable arrangement of knights and liars is provided without specifying the phrases they say.

+5 p. An arrangement of LL...LRR...R is provided, and it is incorrectly stated that the first liar says "To my left, there are as many liars as knights."

+6 p. An arrangement of LL...LRR...R is provided, and it is not specified what the first liar says.

The following progress is not evaluated:

0 p. Only the answer is provided.