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
❗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
Stránky: 1
- Hlavní strana
- » Zajímavé úlohy z diskrétní matematiky
- » Pět karet II (TOTO TÉMA JE VYŘEŠENÉ)
#1 03. 12. 2009 23:01
Pět karet II
Mám jednu úlohu, kterou umím vyřešit jen částečně. Umím určit n, znám existenční důkaz, nikoliv konstruktivní. Jednoduchý konstruktivní důkaz by byl mnohem hezčí.
Úloha:
Tento karetní trik provádí kouzelník a společně s asistentkou. K dispozici je jeden promíchaný balíček n karet. Asistentka poprosí některého diváka, aby vylosoval 5 libovolných karet. Divák vrátí těchto pět karet asistentce, která se na ně podívá a vybere jednu kartu, kterou podá zpět divákovi. Asistentka pak přerovná zbylé čtyři karty a předá je (všechny stejně otočené a pěkně srovnané do balíčku) kouzelníkovi. Ten se na tyto čtyři karty podívá a určí, jaká byla pátá karta, kterou drží divák v ruce.
Otázky:
Pro jaké největší n může fungovat tento "trik"? Ukažte, jak trik provést pro n karet a dokažte, že pro počet karet větší než n již není trik možno povést.
Poznámka
Nejedná se o žádný trik založený na tajných signálech, zmanipulovaných balíčcích a podobně. Jediná informace předávaná mezi asistentkou a kouzelníkem je obsažena ve čtyřech předávaných kartách.
Offline
- (téma jako vyřešené označil(a) petrkovar)
#3 04. 12. 2009 09:52 — Editoval petrkovar (04. 12. 2009 15:42)
Re: Pět karet II
↑ halogan:Řekněme, že karty jsou "dvouhlavé", aby se nedal poznat otočení, a s čísly 1,2,...,n, aby byly různé.
P.S. Nedal jsem to tu jen proto, aby mi úlohu někdo vyřešil. Myslím, že je to velmi problém a chtěl jsem se o něj podělit.
Analogickou úlohu s balíčkem 52 karet mám dořešenou tak, že jsme si s kolegou říkali, že to můžeme předvést na přednášce pro pobavení (=motivaci) studentů.
Offline
#4 04. 12. 2009 23:05
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Pět karet II
Jeden horní odhad je zřejmý:
Nějak to souvisí s maximálním tokem v bibartitním grafu, ale nevím, jestli to je správný směr.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#5 04. 12. 2009 23:56
- Pavel Brožek
- Místo: Praha
- Příspěvky: 5694
- Škola: Informatika na MFF UK
- Pozice: Student
- Reputace: 194
Re: Pět karet II
Tak přidám jeden dolní odhad:
Offline
#6 04. 12. 2009 23:58
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Pět karet II
↑ BrozekP:Zajímaost úlohy je v tom, že si asistentka vybírá, kterou kartu zahodí. Pokud by vybíral divák, byl by tvůj odhad i horní. Pokud asistentka vždy zahazuje nejmenší kartu, lze dolní odhad o 4 zlepšit.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#7 05. 12. 2009 10:16
Re: Pět karet II
↑ Kondr:Ano, je to správný směr - tedy alespoň tímto směrem jsem se dostal až existenčnímu důkazu řešení.
Pro ty, kteří si nechtějí přijít na dolní odhad sami, je tu spoiler.
Řekl bych, že "tok" není ten úplně nejvhodnější pojem.Proč? No, kde je zdroj a kde stok (source and sink)? Odkud kam co teče? A pokud bipartitní graf o něco nedoplním, tak nevím, k čemu bude ta MAXIMALITA toku.
Maximální tok se dá použít ve speciálně upraveném bipartitiním grafu jako prostředek pro nalezení něčeho jiného.
Offline
#8 05. 12. 2009 12:41
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Pět karet II
↑ petrkovar:Ano, tok je nesmysl, myslel jsem maximální párování.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#10 06. 12. 2009 16:12
Re: Pět karet II
↑ Olin:Počty sedí, ale přijde mi, že jsi zapomněl na jeden důležitý požadavek. Ještě musí obraz KAŽDÉ neuspořádané pětice být taková uspořádaná čtveřice, která je PODMNOŽINOU té pětice.
Offline
#11 07. 12. 2009 09:54
Re: Pět karet II
↑ petrkovar:
Jejda, to je pravda, na to jsem v tom triumfálním tažení zcela zapomněl. Tak aspoň máme jinak dokázaný Kondrův horní odhad.
Offline
#12 18. 12. 2009 21:16 — Editoval petrkovar (19. 12. 2009 21:18)
Re: Pět karet II
Váhal jsem zda přidat tento další spoiler (třeba existují jiné přístupy, které povedou k řešení):
Strategie tedy existuje, ale kdo si má to párování pamatovat :-(
O nějakém lépe zapamatovatelném algoritmu domluvy kouzelníka a asistentky zatím nevím. Nějaký nápad?
Offline
#13 03. 01. 2010 16:55 — Editoval petrkovar (03. 01. 2010 16:58)
Re: Pět karet II
↑ petrkovar:Koukám, že toto téma je označeno jako vyřešené ?!?
Je to věc vkusu, ale já ho za vyřešené nepokládám, protože bych rád znal nějaké konstuktivní řešení (ne jen existenční). Neříkám, že ho někdo musí najít (je to mezi zajímavými příklady), ale když je téma označeno jako vyřešené, tak se bojím, že pěkné řešení už nikdo ani hledat nebude.
Offline
#14 03. 01. 2010 16:56
Re: Pět karet II
Tak jsem ho odznačil. Bylo totiž označeno jako vyřešené při plošném označení všech témat, které proběhlo při zavedení této nové funkce.
Offline
#17 24. 02. 2010 21:08
Re: Pět karet II
↑ petrkovar:konečně znám řešení úlohy. Dostal jsem podněty z internetu a vskutku je možné najít takový algoritmus komunikace (vhodný výběr karty asistentkou spolu se zakódováním informace do předávaných karet), který lze bez větších obtíží zvládnout. Popis a důkaz postupu jsou však na cca 2 stránky a protože to je moje vlastní téma, nebudu ho sem přepisovat.
Offline
Stránky: 1
- Hlavní strana
- » Zajímavé úlohy z diskrétní matematiky
- » Pět karet II (TOTO TÉMA JE VYŘEŠENÉ)