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


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

Сюжет 1.

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

1.4 До­ка­жи­те, что Шакти все­гда смо­жет найти стран­ное об­щи­тель­ное мно­же­ство не более, чем из 82 тро­гло­ди­тов.

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

Ре­ше­ние.

Рас­смот­рим об­щи­тель­ное мно­же­ство A наи­мень­ше­го раз­ме­ра. За­ме­тим, что можно вы­брать A таким, что для каж­до­го тро­гло­ди­та a из A най­дет­ся тро­гло­дит va един­ствен­ный друг ко­то­ро­го в мно­же­стве A  — тро­гло­дит a. Дей­стви­тель­но, в про­тив­ном слу­чае, если a дру­жит с кем-то из A, то его можно про­сто уда­лить, а если не дру­жит ни с кем из A, то её можно по­ме­нять с любым его дру­гом.

По прин­ци­пу Ди­ри­х­ле не­ко­то­рый тро­гло­дит u при­над­ле­жит A зна­ком с хотя бы  дробь: чис­ли­тель: левая круг­лая скоб­ка 100 минус |A| пра­вая круг­лая скоб­ка , зна­ме­на­тель: |A| конец дроби тро­гло­ди­та­ми не из A.

Пусть B  — мно­же­ство мак­си­маль­но­го раз­ме­ра, со­дер­жа­щее u и такое, что в нем никто не дру­жит. За­ме­тим, что B яв­ля­ет­ся стран­ным об­щи­тель­ным, оце­ним его раз­мер. За­ме­тим, что B не со­дер­жит дру­зей u, а также не более од­но­го тро­гло­ди­та из каж­дой пары a, va, где a при­над­ле­жит A \backslash левая фи­гур­ная скоб­ка u пра­вая фи­гур­ная скоб­ка .

По­сколь­ку дру­зья u, не вхо­дя­щие в A, по по­стро­е­нию не вхо­дят в пары  левая круг­лая скоб­ка a, v_a пра­вая круг­лая скоб­ка и их не менее  дробь: чис­ли­тель: левая круг­лая скоб­ка 100 минус |A| пра­вая круг­лая скоб­ка , зна­ме­на­тель: |A| конец дроби , по­лу­ча­ем

 |B| мень­ше или равно 100 минус дробь: чис­ли­тель: 100 минус |A|, зна­ме­на­тель: |A| конец дроби минус левая круг­лая скоб­ка |A| минус 1 пра­вая круг­лая скоб­ка =102 минус дробь: чис­ли­тель: 100, зна­ме­на­тель: |A| конец дроби минус |A| мень­ше или равно 82,

что и тре­бо­ва­лось до­ка­зать.
1

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