Индукция в комбинаторике

Будем доказывать, что, если в классе человек и выбрана различная тройка детей, то найдутся две тройки, пересекающиеся ровно по ребёнку, либо такой конфигурации не существует (для ). Доказывать будем индукцией по

База для верна.

Докажем переход. Предположим, то любые две тройки либо не пересекаются, либо пересекаются по детям. Для каждого ребёнка посмотрим на количество его участий в различных тройках. Если у всех детей количество участий не превосходит то всего троек не больше, чем (в каждой тройке 3 ребёнка)  — противоречие. Значит, найдется ребёнок участвующий хотя бы в тройках. Посмотрим на все тройки, в которые входит наш ребёнок. Обозначим множество детей, входящих хотя бы в одну из этих троек через Если выкинуть выбранного ребёнка из всех этих троек, то по нашему предположению мы получим хотя бы различные двойки, любые две из которых пересекаются. Легко проверить, что тогда они все будут пересекаться по одному ребёнку. Причем этот ребёнок не может входить в другие тройки (если он входит в тройку, в которую не входит первый ребенок, то данная тройка должна пересекаться по еще одному ребенку с хотя бы другими тройками из наших старых, что невозможно). Также легко проверить, что ни один другой ребёнок из не может входить в тройки, в которые не входит первый ребёнок. То есть ни один из детей множества не входит в другие тройки. Пусть в детей. Выкинем всех этих детей из рассмотрения. Осталось детей и тройки. Тогда можно воспользоваться предположением индукции. Переход доказан.