ПВГ 2023, 7–8 класс, задача 1
В классе учится человек, и все они очень любят многопользовательские компьютерные игры. Каждый из учащихся играет в одну или две таких игры. При этом для любых учащихся найдется общая игра (в которую играют оба). Найдите наибольшее , такое, что гарантированно найдется игра, в которую играют не менее учащихся.
Ответ
Ответ: .
Решение: Покажем, что ситуация с учащимися возможна. Разобьем на группы: человек, пусть первая группа играет в игры и , вторая и , третья и . Все условия соблюдены.
Предположим, что возможна ситуация, когда в каждую из игр играет не более человек. Выберем самую популярную из игр (ту, в которую играет больше всего), обозначим ее . Участников не более , поэтому найдется человек, который в нее не играет. Обозначим его и рассмотрим в паре с каждым из участников игры . Должна найтись общая игра с каждым из , причем она не может совпадать с . Кроме того, это не может быть одна и та же игра для всех пар (иначе получится, что в нее играют человек). Значит это игры (больше быть не может по условию), обозначим их и . Рассмотрим теперь школьника из тех, кто не играет в игру . По условию, он должен иметь общую игру с теми, кто играет в и , но это не может быть игра , следовательно он играет в . Аналогично можно показать, что он играет в . Таким образом, все остальные играют в и , таким образом, все играют в игры , , и других игр нет. Обозначим — количество людей, играющих в и аналогично , . Получаем (каждого школьника посчитали раза), что невозможно, если , , .