сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Сюжет 1.

В армии Шакти со­сто­ит 100 тро­гло­ди­тов; не­ко­то­рые тро­гло­ди­ты дру­жат друг с дру­гом, а не­ко­то­рые нет. Мно­же­ство тро­гло­ди­тов A на­зы­ва­ет­ся «об­щи­тель­ным», если любой дру­гой тро­гло­дит дру­жит с кем-то из A и «стран­ным об­щи­тель­ным», если при этом ни­ка­кие два тро­гло­ди­та из A не дру­жат. Ока­за­лось, что каж­дый тро­гло­дит с кем-то дру­жит.

1.1 В армии на­шлись тро­гло­ди­ты Вася и Петя, об­ра­зу­ю­щие об­щи­тель­ное мно­же­ство. Тогда Шакти может найти стран­ное об­щи­тель­ное мно­же­ство из не более, чем 50 тро­гло­ди­тов.

Спрятать решение

Ре­ше­ние.

Если Вася и Петя не дру­жат, то можно взять их. Иначе один из них (ска­жем, Вася) знает хотя бы 50 тро­гло­ди­тов. Нач­нем фор­ми­ро­вать стран­ное об­щи­тель­ное мно­же­ство A, на­чи­ная с Васи. Если какой-то из остав­ших­ся тро­гло­ди­тов не знает ни­ко­го из A, мы до­бав­ля­ем его в A. В конце A ста­нет стран­ным об­щи­тель­ным мно­же­ством. По­сколь­ку 50 тро­гло­ди­тов зна­ко­мы уже с Васей, в A ока­жет­ся не более 50 тро­гло­ди­тов.

1

1.2 Пусть не на­шлось таких че­ты­рех тро­гло­ди­тов A, B, C и D, что A дру­жит с B, C и D, а B, C и D между собой нет. Дас нашел об­щи­тель­ное мно­же­ство раз­ме­ра k. До­ка­жи­те, что Шакти смо­жет найти стран­ное об­щи­тель­ное мно­же­ство раз­ме­ра не более k.