M. Murraikin

On an island, there live 100 knights and 100 liars, each of whom has at least one friend. Knights always tell the truth, while liars always lie. One morning, each resident either said the phrase "All my friends are knights" or the phrase "All my friends are liars," and exactly 100 people said each phrase. Find the smallest possible number of pairs of friends, one of whom is a knight and the other a liar.
Let's show that it is possible to find no less than 50 pairs of friends, one of whom is a knight, and the other is a liar. If the phrase "All my friends are liars" was said by no less than 50 knights, then each of them knows at least one liar, and the 50 required pairs are found. Otherwise, the phrase "All my friends are liars" was said by no less than 50 liars. Since liars lie, each of them knows at least one knight, and the 50 required pairs are also found. Let's show that a situation is possible where the number of pairs of friends, knight-liar, is exactly 50. Denote the knights as $k_{1}, k_{2}, .$. , $k 100$, and the liars as $l_{1}, l_{2}, . ., l 100$. Let knight $k_{1}$ be friends only with liar $l_{1}$, knight $k_{2}$ - only with liar $l_{2}$, knight $k 50$ - only with liar 150 (and at the same time liars $l_{1}, l_{2}, \ldots, l 50$ do not befriend anyone else). Knights $k 51, k 52$, .., $k 100$ let them be friends only with each other, and liars $l 51,152, \ldots, l 100$ - also only with each other. Then the number of pairs knight-liar is exactly 50, 100 people $k_{1}, k_{2}, . ., k 50, l_{1}, l_{2}, \ldots, 150$ say the phrase "All my friends are liars," and the other 100 people say the phrase "All my friends are knights."

## Answer

## [ Average values ] Problem 111808 Topics: [ Extreme principle (other) ] [ Theory of algorithms (other) ]

Difficulty: $4+$

Classes: $8,9,10$

Authors: Khramtsov D.: Emelyanov L.A., Bogdanov I.I., Volienkov S.G.

On an infinitely long tape of paper, all integers are written, each exactly once.

Could it be that between any two numbers, their arithmetic mean is not located?

## Solution

Suppose it was possible to write the numbers in the required manner. Let $\Delta$ be the segment of the tape between the numbers 0 and 1 (including 0 and 1). Let $M$ be the maximum absolute value of a number that falls within this segment. Then each number $x$, with an absolute value greater than $M$, is located either to the right or to the left of $\Delta$. Suppose some number $x>M$ is located on one side of $\Delta$, for definiteness, to the right. The arithmetic mean of the numbers $x$ and $-x$ is 0, so the number $-x$ is also located to the right of $\Delta$. The arithmetic mean of the numbers $-x$ and $x+2$ is 1, so $x+2$ is also located to the right of $\Delta$. Reasoning in this way and so on, we get that the numbers $x, x+2, x+4$ and all subsequent numbers of the same parity are located to the right of $\Delta$. Now, among all numbers greater than $M$ and located to the right of $\Delta$, choose the number $a$ that is located to the left of all the others. The numbers $a+2, a+4, a+6$ are to the right of $\Delta$ and, therefore, to the right of $a$. The number $a+4$ is not written to the right of $a+2$, since $a+2$ is the arithmetic mean of $a$ and $a+4$. Thus, $a+4$ is located between $a$ and $a+2$. Similarly, the number $a+8$ is located between $a$ and $a+4$, $a+16$ is located between $a$ and $a+8$, and so on. Thus, between $a$ and $a+2$ an infinite set of numbers $a+4, a+8, \ldots, a+2^{n}, \ldots$ should be placed. Contradiction.

## Answer

It could not.