Городская Жаутыковская олимпиада, 9 класс, 2004 год

В зале находятся 100 человек, каждый из которых знаком по крайней мере с 67 из остальных присутствующих. Докажите, что в зале найдутся четыре человека, из которых любые два знакомы друг с другом.

Комментарий/решение

Выберем двух людей (А и В), знакомых друг с другом. У каждого из них хотя бы по 66 знакомых среди остальных 98 людей. А это значит, что найдутся хотя бы 66+66-98=34 человека, знакомых и с А, и с В. Чтобы завершить доказательство, нам достаточно показать, что из этих 34 человек найдутся двое знакомых друг с другом. Пусть это не так, то есть никакие двое из 34 человек не знакомы между собой, но тогда оказывается, что у них не может быть больше 100-34=66 знакомых, что противоречит условию.