7,8,9 |
| :---: | :---: | :---: |
|  | [ Pairing and grouping; bijections |  |
|  | [ Pigeonhole Principle (other). |  |
|  | Estimation + example |  |

![](https://cdn.mathpix.com/cropped/2024_05_06_ed1a9e9dd82795d4db2eg-26.jpg?height=55&width=297&top_left_y=1779&top_left_x=0)

At a joint conference of the party of liars and the party of truth-tellers, 32 people were elected to the presidium and seated in four rows of eight. During a break, each member of the presidium claimed that among their neighbors there were representatives of both parties. It is known that liars always lie, and truth-tellers always tell the truth. What is the minimum number of liars in the presidium for the described situation to be possible? (Two members of the presidium are neighbors if one of them sits to the left, right, in front of, or behind the other.)
Let's divide all the seats in the presidium into eight groups as shown in the figure. If there are fewer than eight liars, then in one of these groups sit only truth-tellers, which is impossible.

|  | $\pi$ |  |  |  | $\pi$ |  |  |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
|  |  |  | $\pi$ |  |  |  | $\pi$ |
| $\pi$ |  |  |  | $\pi$ |  |  |  |
|  |  | $\pi$ |  |  |  | $\pi$ |  |

The same figure also shows how eight liars can be seated.

## Answer

With eight liars.

Author: Shapovalov A. B.

Several travelers are moving at constant speeds along a straight road. It is known that during a certain period of time, the sum of the pairwise distances between them was monotonically decreasing. Prove that during the same period, the sum of the distances from some traveler to all the others was also monotonically decreasing.

## Solution

Let $n$ be the number of travelers, denoted by $P_{1}, P_{2}, \ldots, P_{n}$. Consider the quantity $V_{i j}$ - the speed of approach of $P_{i}$ and $P_{j}$ (for any $1 \leq i, j \leq n$; if $i=j$, then $V_{i j}=0$). This quantity can be either positive or negative (travelers are moving away from each other). Note that during the entire considered period of time, $V_{i j}$ does not increase (and can decrease only once - as a result of a meeting between $P_{i}$ and $P_{j}$ or one overtaking the other). According to the problem, at the end of the considered period of time, $\sum_{1 \leq i0$. Since $V_{i j}=V_{j i}$ (for any $1 \leq i0$. Therefore, there exists an index $j$ such that $\sum_{i=1}^{n} V_{i j}>0$.

Since all $V_{i j}$ did not increase during the entire period of time, the last inequality was also satisfied throughout the entire period of time, which is what we needed to prove.