Problem 1055

a) Consider the field $X_{1}$, centrally symmetric to the field $X$. A figure $F$, standing on $X_{1}$, attacks all fields that are centrally symmetric to the fields from which it attacks the field $X$ ( $\left.\overline{X_{1} A_{1}}=\overline{A X}\right)$. There are no more than 20 such fields.

b) We will place figures alternately on arbitrary "admissible" fields. Suppose $n$ figures are already placed. They occupy $n$ fields, attack no more than 20n fields, and can be attacked by the $(n+1)$-th figure from no more than 20n fields.

!

Author: S.Koopenoov A.B.

In the Duma, there are 1600 deputies who have formed 16000 committees, each with 80 members.

Prove that there are two committees with at least four common members.

## Solution

Let $n=16000$. Suppose that any two committees have no more than three common members. Let two secretaries, $A$ and $B$, compile lists of all possible chairmen for three sessions of the Duma. $A$ believes that any deputy can be the chairman at each of these sessions, so he has $1600^{3}$ lists. $B$ believes that at each session, only members of one (any) committee can be the chairman, so he first requested the corresponding lists from each committee and received $80^{3} n$ lists. After that, $B$ discarded from the lists submitted by the $i$-th committee the triples that had already appeared in the lists of one of the previous $i-1$ committees. Since each pair of committees (of which there are $C_{n}^{2}$) nominated all their common members, $B$ discarded no more than $C_{n}^{2} \cdot 3^{3}$ lists when forming his lists. Clearly, the number of lists compiled by $A$ is no less than the number of lists compiled by $B$, that is, $1600^{3} \geq 80^{3} \cdot n - 1 / 2 n(n-1) \cdot 3^{3} > 80^{3} \cdot n - 16 n^{2} = (80^{3} - 16 n) n = (2^{9} \cdot 10^{3} - 2^{8} \cdot 10^{3}) = 1600^{3}$. Contradiction.