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
2008 ambasadori
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata
-
Marcelina Popa
- Bernoulli
- Posts: 208
- Joined: Wed Mar 05, 2008 3:25 pm
- Location: Tulcea
- Contact:
-
Horia Nicolaescu
- Arhimede
- Posts: 5
- Joined: Wed May 05, 2010 11:59 am
- Location: Bucuresti
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.
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.