2019-01-20
В Думе 1600 депутатов, которые образовали 16000 комитетов по 80 человек в каждом. Докажите, что найдутся два комитета, имеющие не менее четырех общих членов.
Решение:
Предположим, что любые два комитета имеют не более трех общих членов. Пусть двое депутатов составляют списки всевозможных председателей на три заседания Думы. Первый считает, что любой депутат может быть председателем на каждом из этих заседаний, поэтому у него получилось 16003 списков. Второй считает, что на каждом заседании могут председательствовать только члены одного (не важно какого именно) комитета, поэтому сначала он запросил соответствующие списки от каждого комитета и получил $16000 \cdot 80^3$ списков. После этого второй депутат выбросит из списков, поданных $i$-м комитетом, те тройки, которые уже вошли в списки одного из предыдущих $i - 1$ комитетов. Так как каждые два комитета (а таких пар $\frac{16000 \cdot (16000 - 1)}{2}$) выдвинули всех своих общих членов, то второй депутат при формировании своих списков выбросил не более, чем $\frac{16000 \cdot (16000 - 1)}{2} \cdot 3^3$ из списков, поданных комитетами. Очевидно, что списков, которые составил первый депутат, не меньше, чем списков, которые составил второй депутат, т. е.
$1600^3 \geq 16000 \cdot 80^3 - \frac{16000 \cdot (16000 - 1)}{2} \cdot 3^3$, но $16000 \cdot 80^3 - \frac{16000 \cdot (16000 - 1)}{2} \cdot 3^3 > 16000 \cdot 80^3 - \frac{16000 \cdot (16000 - 1)}{2} \cdot \frac{4^3}{2} = \frac{16000 \cdot 4^3}{4} + 2^{13} \cdot 10^6 - 2^{12} \cdot 10^6 > 2^{12} \cdot 10^6 = 1600^3$.
Получили противоречие.