Стоял 1492 год. Колумб, прибыв на новую неизведанную землю, встретил племя индейцев, в котором было ровно 100 человек.
Осмотревшись немного, он познакомился с вождем, который рассказал ему интересную историю:
Все наше племя разбито на 2^99 групп, при этом каждые три группы имеют хотя бы одного общего члена.
А теперь мы хотим спросить тебя, Христофор: есть ли среди нас человек, который бы состоял во всех группах?
Призадумался Колумб, а затем побрел на корабль, чтобы ещё подумать. На следующее утро он снова пришёл к индейцам, чтобы дать свой ответ.
— Да, — уверенно сказал он, — среди вас есть человек, состоящий во всех группах.
— Почему ты так решил? — спросил его вождь.
— Слушайте! — воскликнул Колумб, — Потому что:
1) Всего, с участием 100 человек, вы могли организовать 2^100 групп, но вы создали только 2^99, то есть в два раза меньше.
2) В это число не может входить группа и ее дополнение, так как пересечение их пусто, а вы говорили, что любые три имеют общего члена. Учитывая это и первый пункт, можно сказать, что для любой группы либо она, либо ее дополнение входит в ваше число.
3) Также, если группа A и группа B входят в это число, то и пересечение их входит, следуя предыдущему утверждению.
4) По индукции, пересечение всех 2^99 групп лежит в этом числе, а значит — не пусто.
— Ты абсолютно прав, — подтвердил вождь.