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


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

В кру­жок ходит 10 че­ло­век, не­ко­то­рые из ко­то­рых между собой дру­жат. Может ли так быть, что в этом круж­ке один участ­ник дру­жит с 9 дру­ги­ми, один участ­ник  — с 7 дру­ги­ми, один участ­ник  — с 6 дру­ги­ми, два участ­ни­ка  — с 5 дру­ги­ми каж­дый, два участ­ни­ка  — с 3 дру­ги­ми каж­дый, один участ­ник  — с 2 дру­ги­ми, два участ­ни­ка  — с 1 дру­гим каж­дый?

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

Ре­ше­ние.

Введём граф, вер­ши­на­ми ко­то­ро­го будут чипы, а ребро между вер­ши­на­ми про­ведём в том и толь­ко том слу­чае, если со­от­вет­ству­ю­щие чипы со­еди­не­ны про­во­да­ми.

Будем опи­сы­вать граф в виде по­сле­до­ва­тель­но­сти целых чисел (a1, a2, ..., an), где ai озна­ча­ет сте­пень вер­ши­ны i. Будем на­зы­вать по­сле­до­ва­тель­ность целых чисел (a1, a2, ..., an) ре­а­ли­зу­е­мой, если су­ще­ству­ет граф, опи­са­ние ко­то­ро­го сов­па­да­ет с (a1, a2, ..., an). В усло­вии спра­ши­ва­ет­ся, ре­а­ли­зу­е­ма ли по­сле­до­ва­тель­ность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1).

За­ме­тим сле­ду­ю­щие два про­стых факта.

1.  Пусть a_i=0; тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a1, a2, ..., an), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

 левая круг­лая скоб­ка a_1, a_2, \ldots, a_i минус 1, a_i плюс 1, \ldots, a_n пра­вая круг­лая скоб­ка .

Для ре­а­ли­за­ции до­ста­точ­но от­ки­нуть вер­ши­ну с но­ме­ром i.

2.  Пусть a_i=n минус 1; тогда если ре­а­ли­зу­е­ма по­сле­до­ва­тель­ность (a1, a2, ..., an), то ре­а­ли­зу­е­ма и по­сле­до­ва­тель­ность

 левая круг­лая скоб­ка a_1 минус 1, a_2 минус 1, \ldots, a_i минус 1 минус 1, a_i плюс 1 минус 1, \ldots, a_n минус 1 пра­вая круг­лая скоб­ка .

Дей­стви­тель­но, если a_i=n минус 1, то вер­ши­на с но­ме­ром i долж­на быть со­еди­не­на со всеми осталь­ны­ми вер­ши­на­ми, по­это­му до­ста­точ­но от­ки­нуть её и все вы­хо­дя­щие из неё рёбра.

Пред­по­ло­жим про­тив­ное и пусть по­сле­до­ва­тель­ность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1) ре­а­ли­зу­е­ма. Поль­зу­ясь фак­та­ми 1 и 2 по­сле­до­ва­тель­но по­лу­ча­ем, что тогда ре­а­ли­зу­е­мы и по­сле­до­ва­тель­но­сти

 левая круг­лая скоб­ка 6, 5, 4, 4, 2, 2, 1, 0, 0 пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка 6, 5, 4, 4, 2, 2, 1 пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка 4, 3, 3, 1, 1, 0 пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка 4, 3, 3, 1, 1 пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка 2, 2, 0, 0 пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка 2, 2 пра­вая круг­лая скоб­ка ,

но по­сле­до­ва­тель­ность (2, 2), оче­вид­но, не ре­а­ли­зу­е­ма. Про­ти­во­ре­чие; зна­чит, наше пред­по­ло­же­ние не­вер­но и по­сле­до­ва­тель­ность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) не ре­а­ли­зу­е­ма.

 

Ответ: нет, не может.

 

При­ве­дем дру­гое ре­ше­ние.

Ана­ло­гич­но пер­во­му ре­ше­нию введём граф. За­ме­тим, что если (d1, d2, ..., dn) сте­пе­ни вер­шин не­ко­то­ро­го графа без пе­тель и крат­ных рёбер; то для каж­до­го k вы­пол­не­но не­ра­вен­ство

 d_1 плюс d_2 плюс \ldots плюс d_k мень­ше или равно k левая круг­лая скоб­ка k минус 1 пра­вая круг­лая скоб­ка плюс d_k плюс 1 плюс \ldots плюс d_n.

Дей­стви­тель­но, все рёбра, вы­хо­дя­щие из вер­шин с но­ме­ра­ми от 1 до k де­лят­ся на два типа:

1)  иду­щие в вер­ши­ны с но­ме­ра­ми от k плюс 1 до n  — таких не боль­ше d_k плюс 1 плюс \ldots плюс d_n;

2)  иду­щие в вер­ши­ны с но­ме­ра­ми от 1 до k  — таких не боль­ше  дробь: чис­ли­тель: k левая круг­лая скоб­ка k минус 1 пра­вая круг­лая скоб­ка , зна­ме­на­тель: 2 конец дроби , но каж­дое мы можем по­счи­тать по два раза.

В за­да­че нас спра­ши­ва­ют, су­ще­ству­ет ли граф со сте­пе­ня­ми вер­шин (9, 7, 6, 5, 5, 3, 3, 2, 1, 1). Пред­по­ло­жим, что он су­ще­ству­ет, и вос­поль­зу­ем­ся до­ка­зан­ным утвер­жде­ни­ем для пер­вых 5 вер­шин:

32=9 плюс 7 плюс 6 плюс 5 плюс 5 мень­ше или равно 5 умно­жить на 4 плюс 3 плюс 3 плюс 2 плюс 1 плюс 1=30,

про­ти­во­ре­чие.

 

Ответ: нет, не может.

Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­нияБалл
Вер­ное ре­ше­ние без су­ще­ствен­ных не­до­че­тов+
В целом за­да­ча ре­ше­на, хотя и с не­до­че­та­ми+ −
За­да­ча не ре­ше­на, но есть за­мет­ное про­дви­же­ние− +
За­да­ча не ре­ше­на, за­мет­ных про­дви­же­ний нет
За­да­ча не ре­ша­лась0

Аналоги к заданию № 4558: 4586 Все