Page 1 of 1
2008 ambasadori
Posted: Sat May 23, 2009 10:25 pm
by Marcelina Popa
La un banchet sunt invitaţi 2008 ambasadori. Fiecare ambasador are cel mult 1003 duşmani. Demonstraţi că ambasadorii pot fi aşezaţi la o masă rotundă astfel încât nimeni să nu stea lângă un duşman.
Concursul Modus Vivendi 2008
Posted: Thu May 06, 2010 4:34 pm
by Horia Nicolaescu
Consideram un graf cu 2008 puncte in care unim 2 puncte daca cei doi ambasadori sunt prieteni.
Din conditie deducem ca fiecare varf are gradul mai mare sau egal cu
1005>(2008+1)/2.
Din cate tin minte asta era o conditie suficienta ca varfurile grafului sa formeze un ciclu hamiltonian(Teorema lui Dirac) si atunci ii aranjam la masa conform acestui ciclu.
O rezolvare fara grafuri nu stiu si a-si fi interesat daca mi-ar putea da cineva.