Задача
COM-B1-M04-P024 Семнадцать троек
Из \(10\)-элементного множества выбраны \(17\) трёхэлементных подмножеств. Докажите, что найдутся два выбранных подмножества, имеющие не менее двух общих элементов.
Докажите противное: если любые две тройки имеют не более одного общего элемента, то пары элементов не повторяются.
Предположим, что любые две выбранные тройки имеют не более одного общего элемента. Тогда никакая пара элементов не может входить в две разные тройки, иначе эти две тройки имели бы общую пару, то есть два общих элемента. Каждая тройка содержит \(3\) пары, поэтому \(17\) троек содержали бы \(51\) различную пару элементов. Но всего пар в \(10\)-элементном множестве \(10\cdot9/2=45\). Противоречие. Значит две тройки имеют не менее двух общих элементов.
Сильная олимпиадная задача на ограничение через пары.