Қалалық Жәутіков олимпиадасы 9 сынып, 2004 жыл

Залда 100 адам бар. Олар әрқайсысы кем дегенде қалғандарының 67-мен таныс. Залда кез келген екеуі бір-бірімен таныс болатын төрт адамның табылатынын дәлелде.

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

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