Matematické Fórum

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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 27. 12. 2007 20:05

ameba
Zelenáč
Příspěvky: 10
Reputace:   
 

Rozesílání zpráv

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

 

#2 27. 12. 2007 20:40 — Editoval robert.marik (27. 12. 2007 21:04)

robert.marik
Einstein
Příspěvky: 999
Reputace:   
 

Re: Rozesílání zpráv

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

 

#3 27. 12. 2007 21:08

robert.marik
Einstein
Příspěvky: 999
Reputace:   
 

Re: Rozesílání zpráv

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

 

#4 28. 12. 2007 22:27 — Editoval Lishaak (28. 12. 2007 22:29)

Lishaak
Moderátor
Místo: Praha
Příspěvky: 763
Reputace:   
Web
 

Re: Rozesílání zpráv

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.


Nothing in the world that's worth having comes easy.
Always do what you are most afraid of.

Offline

 

#5 28. 12. 2007 23:12

robert.marik
Einstein
Příspěvky: 999
Reputace:   
 

Re: Rozesílání zpráv

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

 

#6 28. 12. 2007 23:35

Lishaak
Moderátor
Místo: Praha
Příspěvky: 763
Reputace:   
Web
 

Re: Rozesílání zpráv

No, to je v podstate ta uvaha, ktera vyresi tu druhou cast prikladu, tedy to co jsem chtel, aby si ameba uvedomila...


Nothing in the world that's worth having comes easy.
Always do what you are most afraid of.

Offline

 

#7 28. 12. 2007 23:42

robert.marik
Einstein
Příspěvky: 999
Reputace:   
 

Re: Rozesílání zpráv

Aha, tak pardon .....

Offline

 

#8 29. 12. 2007 10:31

Lishaak
Moderátor
Místo: Praha
Příspěvky: 763
Reputace:   
Web
 

Re: Rozesílání zpráv

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.


Nothing in the world that's worth having comes easy.
Always do what you are most afraid of.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson