Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Učitel na mě vybafl s následujícím příkladem. Teorii grafů jsem dlouho neviděla, ale myslím, že by to na ni šlo aplikovat:
19 lidí si vyměňuje PFky, každý pošle PFku devíti ostatním. Dokažte, že existuje jedinec, který dostal PFku od někoho, komu ji sám neposlal.
Offline
Možná taky kombinatorika. Připomíná mi to jednu klasickou úlohu o podávání ruk, něco o tom jak každý podal ruku jinému počtu lidí a otázka byla, kolika lidem podala ruku paní Smithové (fakt si nedělám srandu). Řešilo se to buď přes teorii grafů nebo možná principem inkluze a exkluze - ale bez záruky, je to fakt dávno ..... . Zkuste pohledat tu úlohu, je to z nějaké klasické kombinatorické sbírky, třeba to pomůže.
Offline
Hm, teď mě napadlo, když jsem si začal malovat orientovaný graf s devatenácti uzly: neplyne to náhodou z toho, že PFek byl lichý počet :) ?
Offline
Ano, plyne, nicmene je treba se k tomu dopracovat. Je nebudu rikat cele reseni, abych nezkazil amebe radost z reseni prikladu ale alespon lehce naznacim:
Jak uz bylo receno, nejprve si uvedomime, ze vsech PFek v systemu je 171. Kazde z nich musi nekomu prijit. Nyni zauvazujeme (to je prvni cast, kterou necham na ctenari), ze staci zabyvat se pouze pripadem, kdy kazdemu cloveku prijde prave devet PFek.
A nyni dukaz sporem. Budeme se snazit PFka rozeslat tak, aby kazdemu cloveku prislo prave devet a to tak, ze vsechna prijdou prave od tech deviti lidi, kterym ten clovek poslal PFko. Dalsi uvahou (opet je na ctenari) zjistime,
ze to nejde. Tedy ze bude vzdy existovat jeden clovek, ktery PFko nekomu posle, ale zadne mu od nej neprijde zpet (tady se prave pouzije znalost toho, ze PFek je lichy pocet).
Jeste dodam, ze se hodi predstavovat si tento system jako orientovany graf, nicmene zadne poznatky z teorie grafu nejsou treba, jde to vyresit i bez jakekoliv grafove predstavy.
Offline
Já jsem uvažoval jednoduše, že pokud každé PFko které šlo od A do B mělo kamaráda co šel od B do A, tak PFek bude sudý počet. Tato úvaha nestačí?
Offline
Vcera pred usnutim jsem si uvedomil, ze vy jste vlastne uz na zacatku daleko jednoduseji vyresil daleko obecnejsi verzi tohoto problemu (klobouk dolu). Docela me to zaujalo, takze tady napisu obecny problem i jeho reseni, jak jste ho nespis mel na mysli. Kdyby mel nekdo proti takovemu reseni namitky, necht se nevaha ozvat...
VETA:
Necht kazdy z naprosto libovolneho poctu lidi posle naprosto libovolny (i nulovy) pocet PFek. Pokud je pocet vsech odeslanych PFek dohromady (oznacme ho k) lichy, existuje alespon jeden clovek takovy, ktery dostane PFko od nekoho, komu sam zadne neposlal.
DUKAZ:
Budeme postupne hledat takoveho cloveka. Nejdriv si nastavime pocet NEODESLANYCH PFek na "k" a opakovane provadime tento ukon:
----------------------------------------------------
Vybereme si libovolneho cloveka, ktery jeste ma nejaka PFka k odeslani a nechame ho jedno z nich odeslat cloveku C.
------------------------------------------------------
Vzdy kdyz provedeme tento ukon, mohou nastat dve moznosti:
1. Clovek C nam zpatky zadne PFko neposle (at uz proto, ze ho poslat nechce, nebo proto, z uz zadne nema). V tuto chvili muzeme skoncit, protoze C je nasim hledanym clovekem. Dostal PFko od nekoho, komu sam neposlal.
2. Clovek C nam posle zpatky svoje PFko. V tomto pripade snizime pocet neodeslanych PFek o dve a znovu provedeme ukon.
Takto pokracujeme dokud to jde. Dulezite je, ze pocet neodeslanych PFek vzdy snizime od dva. Dohromady byl ale pocet PFek lichy, cili na konci nam vzdy zbude jedno PFko. To nekomu patri, cili ho nekdo musi odeslat. Ale ten komu prijde uz nemuze nic poslat zpatky, protoze uz zadna neodeslana PFka nezbyla.
Cili at uz provedeme vyse popsanych ukonu kolik chceme, vdycky nakonec dojde na pripad 1.
Q.E.D.
Offline