Задача
COM-B2-M01-P016 Общие решённые задачи
Есть \(21\) ученик и \(10\) задач. Каждый ученик решил не меньше \(6\) задач. Докажите, что найдутся два ученика, решившие вместе не меньше \(4\) одних и тех же задач.
Считайте пары учеников, решивших одну и ту же задачу.
Пусть \(d_j\) — число учеников, решивших \(j\)-ю задачу. Тогда \(\sum d_j\ge21\cdot6=126\). Число троек \((\{u,v\}, задача)\), где оба ученика решили эту задачу, равно \(\sum_{j=1}^{10}\binom{d_j}{2}\). При сумме \(126\) по \(10\) задачам эта сумма минимальна при распределении \(13,13,13,13,13,13,12,12,12,12\), и равна \(6\binom{13}{2}+4\binom{12}{2}=732\). Пар учеников \(\binom{21}{2}=210\). Если бы каждая пара имела не более \(3\) общих задач, троек было бы не больше \(630\), противоречие. Значит, есть пара с не менее чем \(4\) общими задачами.
Сложная задача на двойной подсчёт плюс выпуклость.