Задача от ЕМТ

[LazyWorker]

Всеки от участващите ученици в едно математическо състезание има не повече от d≥1 познати. Нека d1 и d2 са неотрицателни цели числа, за които d-1=d1+d2. Да се докаже, че учениците могат да бъдат разделени в две стаи по такъв начин, че всеки ученик в първата стая има не повече от d1 познати в неговата стая и всеки ученик във втората стая има не повече от d2 познати в неговата стая.

[drago]

Слагаме учениците произволно в две стаи A и B. След това започваме следната процедура. Ако учник в стая А има повече от [tex]d_1[/tex] приятели вътре в стаята го местим в стая B. Там той ще има не повече от [tex]d-(d_1+1)=d_2[/tex] приятели. Ако има ученик в стая B с повече от [tex]d_2[/tex] приятели, го местим в стая A. Там той ще има не повече от [tex]d_1[/tex] приятели. Така можем да си мести учениците назад-напред. Ако се получи ситуация, в която не можем да преместим никой, то това ще бъде търсеното разделяне. Въпросът е дали ще стигнем до такава ситуация? Нека проверим, че този процес не може да продължава безкрайно. Допускаме противното. Тогава ще има два момента [tex]t_1, t_2[/tex], в който и в двете стаи ще има едни и същи хора. Когато местим човек от А в В общия брой двойки приятели в стая А намалява с поне [tex]d_1+1[/tex]. Когато местим човек от В в А, общия брой двойки приятели в А се увеличава с не повече от [tex]d_1[/tex]. Тъй като между двата момента [tex]t_1[/tex] и [tex]t_2[/tex], броя на преместванията от A в В е равен на тези от В в А, то двойките приятели в A ще намалее. Това не може да е така, понеже учениците в А са едни и същи, противоречие.

Коментар. Тази задача я мислих известно време, но нещата не станаха. Явно пропусках нещо, щото задача от теория на графите давана на такова състезание, някак не би следвало да е чак толкова трудна. Както и да е, пуснах задачата в един друг форум, където дадоха решение. Имайки го предвид, ми хрумна това по-горе, което може и да не е толкова елегантно, но може би е по-логично. Всъщност ето го линка: http://www.artofproblemsolving.com/Foru ... 2&t=614297