Существуют сто депутатов, которые сформировали 450 комиссий. Ни одни две комиссии не имеют более трех общих депутатов

Мишка

18

Давайте докажем, что существуют четыре комиссии, которые пересекаются ровно по одному депутату.

Предположим, что существует комиссия, которая пересекается с больше чем четырьмя другими комиссиями. Пусть это комиссия X, и пусть она пересекается с комиссиями A, B, C и D. Тогда X содержит по крайней мере пять депутатов (один из каждой комиссии), а также эти депутаты должны быть уникальными и не встречаться в других комиссиях, так как ни одни пять комиссий не должны иметь более одного общего депутата.

Однако, если X содержит пять депутатов, то это значит, что каждый из этих депутатов должен быть в одной из оставшихся 446 комиссий (450 комиссий в общей сложности минус пять комиссий, уже рассмотренных). Но, если каждый из этих пяти депутатов находится в отдельной комиссии из оставшихся 446, то они должны пересекаться между собой по меньшей мере по одному депутату. Это противоречит утверждению, что ни одни две комиссии не должны иметь более трех общих депутатов.

Из этого противоречия следует, что предположение о существовании комиссии X, пересекающейся с больше чем четырьмя другими комиссиями, неверно. Следовательно, найдутся четыре комиссии, пересекающиеся ровно по одному депутату.

Надеюсь, это пошаговое решение помогло вам понять, как доказать данное утверждение. Если у вас остались вопросы, пожалуйста, не стесняйтесь задать их.