Международное общество состоит из представителей шести различных стран. Список членов общества состоит из 1978 фамилий, занумерованных числами 1, 2, $\ldots$, 1978.
Докажите, что существует хотя бы один член общества, номер которого равняется сумме номеров двух членов из его страны или удвоенному номеру некоторого члена из его страны.
Международная математическая олимпиада школьников (XX, 1978 год)
Предположим, что заключение задачи не выполняется. Заметим, что одна из стран представлена в обществе не менее чем 330 членами. Действительно, если бы каждая делегация состояла не более чем из 329 членов, то всего в обществе было бы не больше чем $329\cdot6=1974$ члена. Аналогичным рассуждением (известным под названием принципа Дирихле) мы будем пользоваться ещё несколько раз, не поясняя его специально. Расположим номера учёных этой страны в порядке возрастания: $a_1$, $a_2$, $\ldots$, $a_{330}$. В силу нашего предположения учёные с номерами $a_2-a_1$, $a_3-a_1$, $\ldots$, $a_{330}-a_1$ представляют оставшиеся пять стран. Среди них не менее 66 представляют одну страну; пусть это учёные с номерами $b_1$, $b_2$, $\ldots$, $b_{66}$. Тогда учёные с номерами $b_2-b_1$, $\ldots$, $b_{66}-b_1$ представляют оставшиеся четыре страны. Среди них не меньше 17 учёных представляют одну страну; пусть их номера $c_1$, $c_2$, $\ldots$, $c_{17}$. Тогда учёные с номерами $c_2-c_1$, $\ldots$, $c_{17}-c_1$ живут в оставшихся трёх странах. Из них мы аналогичными образом найдём 5 учёных, представляющих две страны, а затем двух представителей одной страны, разность номеров которых не может быть номером учёного ни одной из стран. Противоречие!
Задача решена.
Если поставить теперь вопрос о том, сколько должно быть членов в обществе из представителей $k$ стран, чтобы заключение задачи наверняка выполнялось, то приведённый выше метод решения даёт ответ
$$
n_k=[k!e]=k!\left(2+\dfrac1{2!}+\dfrac1{3!}+\ldots+\dfrac{1}{k!}\right)
$$ (проверьте это самостоятельно). Однако эта оценка может быть улучшена уже для $k=3$. Как сообщил нам А. Ходулёв, для трёх стран достаточно не $16=[3!e]$, а 14 представителей. Для тринадцати представителей трёх стран заключение задачи не выполняется; соответствующий пример приведён на рисунке 1. А для четырёх стран достаточно 45 представителей; для 44 же представителей четырёх стран можно привести пример, когда заключение задачи не выполняется. Оценка снизу для количества членов общества из $k$ стран, для которых возможна такая нумерация, что заключение задачи М540 будет неверно; однако она очень далека от верхней оценки. Лучшей пока является оценка $m_k=\dfrac{3^k-1}2$.
