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