Дано:
- 11 пионеров
- 5 кружков
Каждый пионер посещает определенное количество кружков, а каждый кружок может быть посещен одним или несколькими пионерами.
Найти:
- Докажите, что среди 11 пионеров есть два таких пионера, A и B, что все кружки, которые посещает A, посещает и B.
Решение:
1. Рассмотрим количество способов, которыми пионер может посещать кружки. Поскольку пионеры могут посещать любые комбинации из 5 кружков, общее количество возможных комбинаций посещения кружков равно 2^5 = 32. Здесь мы включаем и пустое множество (когда пионер не посещает никакого кружка).
2. Так как у нас 11 пионеров, а возможных комбинаций только 32, то, согласно принципу Дирихле (принципу голубятни), по крайней мере два пионера будут посещать кружки по одной и той же комбинации (по крайней мере, если не учитывать пустое множество).
3. Пусть A и B – два пионера, которые посещают кружки по одной и той же комбинации. Поскольку их комбинации одинаковы, все кружки, которые посещает A, посещает и B, так как у них одинаковые наборы кружков.
4. Таким образом, для любых двух пионеров, посещающих кружки по одинаковой комбинации, все кружки, которые посещает один из них, посещает и другой.
Ответ:
Среди 11 пионеров найдутся два таких, A и B, что все кружки, которые посещает A, посещает и B.