1.4 Докажите, что Шакти всегда сможет найти странное общительное множество не более, чем из 82 троглодитов.
Сюжет 1.
В армии Шакти состоит 100 троглодитов; некоторые троглодиты дружат друг с другом, а некоторые нет. Множество троглодитов A называется «общительным», если любой другой троглодит дружит с кем-то из A и «странным общительным», если при этом никакие два троглодита из A не дружат. Оказалось, что каждый троглодит с кем-то дружит.
Рассмотрим общительное множество A наименьшего размера. Заметим, что можно выбрать A таким, что для каждого троглодита a из A найдется троглодит va единственный друг которого в множестве A — троглодит a. Действительно, в противном случае, если a дружит с кем-то из A, то его можно просто удалить, а если не дружит ни с кем из A, то её можно поменять с любым его другом.
По принципу Дирихле некоторый троглодит 
знаком с хотя бы 
троглодитами не из A.
Пусть B — множество максимального размера, содержащее u и такое, что в нем никто не дружит. Заметим, что B является странным общительным, оценим его размер. Заметим, что B не содержит друзей u, а также не более одного троглодита из каждой пары a, va, где 
Поскольку друзья u, не входящие в A, по построению не входят в пары 
и их не менее 
получаем
