[ Milosh Milosavljevic1 @ 27.05.2013. 00:36 ] @
Car zeli da sagradi dvorac u kome ce biti 1990 soba u jednom nivou, tako da vaze
sledeci uslovi:
-Broj vrata na svakoj sobi je 0, 1 ili 2.
-Izmedju svake dve sobe su najvise jedna vrata, a iz svake sobe na ulicu vode najvise
jedna vrata.
-Broj vrata prema ulici je 19, a broj soba sa jednim vratima 90.
Da li je moguce sagraditi ovakav dvorac?
[ Milosh Milosavljevic1 @ 28.05.2013. 01:37 ] @
Nasao sam resenje. Neka ulica i sobe predstavljaju cvorove grafa, ima ih 1991. Jedan cvor je stepena 19, njih 90 je stepena 1, a ostali su stepena 0 ili 2. To znaci da je suma svih stepena u grafu neparan broj, pa je to kontradikcija. (Stepen cvora je broj grana koje izlaze iz njega. Suma svih stepena je 2x broj svih grana, sto je ocigledno)