Oslav s námi Mezinárodní den čárových kódů a získej 90 % extra kreditů ZDARMA při nákupu od 1199 kreditů. Použij promo kód BARCODE90 pouze dnes!
NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!
Avatar
coells
Tvůrce
Avatar
coells:25.4.2015 22:23

A když už jsme u těch hádanek:

Máme skupinu vězňů, se kterými se [krutý] ředitel rozhodne hrát hru. Každý vězeň dostane na hlavu černý nebo bílý klobouk. Každý vidí barvu klobouku svých spoluvězňů, ale svoji vlastní nevidí. Pokud uhádne svoji vlastní barvu, bude propuštěn, pokud neuhádne, bude popraven.

Vězni si smí připravit strategii, než dostanou klobouky. Ale poté, co je dostanou, už spolu nesmí nijak komunikovat.

Jakou strategii si mají vězni zvolit, aby jich přežilo co nejvíce? Podvod se trestá smrtí celé skupiny.

EDIT: stačí připravit strategii, nemusíte dokazovat, že právě tohle je nejlepší strategie (pro zájemce to lze dokázat přes očekávanou hodnotu binomiální distribuce)

Editováno 25.4.2015 22:24
 
Odpovědět
25.4.2015 22:23
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na coells
Honza Bittner:25.4.2015 22:48

Tuto hádanku znám - viděl jsem na Khan Academy... Dost dobrá hádanka. :)

!!! SPOILER !!!
vysvětlení jak na to přijít, jaké jsou možnosti atd. :
https://www.khanacademy.org/math/recreational-math/puzzles/brain-teasers/v/alien-abduction-brain-teaser
Editováno 25.4.2015 22:50
Nahoru Odpovědět
25.4.2015 22:48
FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.
Avatar
coells
Tvůrce
Avatar
Odpovídá na Honza Bittner
coells:25.4.2015 22:55

Vězni spolu nesmí komunikovat, jakmile první zakřičí, všechny popraví :-)

 
Nahoru Odpovědět
25.4.2015 22:55
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na coells
Honza Bittner:25.4.2015 23:01

Vězni si dohodnou strategii (jak popisuje Khan), poté je dají do řady a jeden po druhém říkají svojí barvu... Tam není žádná komunikace, ne? :)

(nechci spoilerovat pro ty, kteří si to chtějí vyřešit sami, takže to neříkám napřímo)

Nahoru Odpovědět
25.4.2015 23:01
FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.
Avatar
coells
Tvůrce
Avatar
Odpovídá na Honza Bittner
coells:25.4.2015 23:05

To je určitě forma komunikace, stejně jako kdyby se tahali za rukáv nebo plácali po zádech. Prostě mezi nimi nesmí dojít k žádné vyměně informací. Můžeš si to představit tak, že se podívají na klobouky ostatních, pak jdou na samotku a tam musí odpovědět.

 
Nahoru Odpovědět
25.4.2015 23:05
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na coells
Honza Bittner:25.4.2015 23:09

Jasně - takže máš trochu jiná pravidla, než ta Khanova verze... :)

V tom případě vůbec nevím co s tím, haha. :D A to tvoje "přes očekávanou hodnotu binomiální distribuce" netuším co je - nevadí. Jednou se to naučím a vyřeším to, jsem trpělivý člověk! ;)

Nahoru Odpovědět
25.4.2015 23:09
FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.
Avatar
coells
Tvůrce
Avatar
Odpovídá na Honza Bittner
coells:25.4.2015 23:12

Nee, to byla jen poznámka pro pokročilé :-D

 
Nahoru Odpovědět
25.4.2015 23:12
Avatar
*smoky*
Člen
Avatar
*smoky*:26.4.2015 15:11

Takže, mají 50% šanci na černý klobouk, může vidět klobouky ostatních (nepodstatné), ale nijak nemůže dostat informace o tom, jaký on má klobouk, ano?
Co kdyby se zaklonil a klobouk si shodil? Poté by viděl jeho barvu.

Nahoru Odpovědět
26.4.2015 15:11
Pít, žít, umřít.
Avatar
coells
Tvůrce
Avatar
Odpovídá na *smoky*
coells:26.4.2015 15:30

To by mohl ... ale ostatní by asi byli naštvaní, protože by všechny popravili za podvádění. A také nikde není řečeno, jaká je šance na barvu klobouku.

 
Nahoru Odpovědět
26.4.2015 15:30
Avatar
*smoky*
Člen
Avatar
*smoky*:26.4.2015 15:37

jsou dvě možnosti, nijak blíže nejsou stanoveny, tudíž 50%, nemůže uhádnout svou barvu z barvy klobouků ostatních (i když by měli všichni černé, stejně on bude mít stále jen 50%). Jak je definováno podvádění?

Nahoru Odpovědět
26.4.2015 15:37
Pít, žít, umřít.
Avatar
MadaraCZech
Tvůrce
Avatar
MadaraCZech:26.4.2015 15:52

50% šance je docela dost, to by šlo tipnout :D .

 
Nahoru Odpovědět
26.4.2015 15:52
Avatar
coells
Tvůrce
Avatar
Odpovídá na *smoky*
coells:26.4.2015 15:57

Jestliže ti dám nefér minci, kde hlava padá s pravděpodobností p: 0<=p<=1, pak máš pravděpodobnost p, že padne hlava, nikoliv 50%. To, o čem mluvíš, je a priori pravděpodobnost, ale nás zajímá a posteriori, i když to ze zadání možná není tak úplně zřejmé, ale sem bych nerad zabředával, protože k řešení hádanky to není potřeba.

Podvádění definujeme ve smyslu porušení pravidel hádanky: vidí barvu ostatních, nevidí svoji vlastní barvu, nesmí spolu komunikovat.

 
Nahoru Odpovědět
26.4.2015 15:57
Avatar
Lukáš Hruda
Tvůrce
Avatar
Lukáš Hruda:26.4.2015 18:10

Když na konci hádají ty barvy, slyší co kdo hádá?

 
Nahoru Odpovědět
26.4.2015 18:10
Avatar
coells
Tvůrce
Avatar
Odpovídá na Lukáš Hruda
coells:26.4.2015 18:27

Nevidí, ani neslyší. Poté, co dostanou klobouk už mezi nimi nesmí dojít ke komunikaci, a to ani k náhodné.

 
Nahoru Odpovědět
26.4.2015 18:27
Avatar
Petr Nymsa
Tvůrce
Avatar
Petr Nymsa:26.4.2015 18:31

Pár vězňů se obětuje a řekne naschvál barvu toho co má před sebou. Teoreticky jeden by měl přežít ne? :D

Nahoru Odpovědět
26.4.2015 18:31
Pokrok nezastavíš, neusni a jdi s ním vpřed
Avatar
coells
Tvůrce
Avatar
Odpovídá na Petr Nymsa
coells:26.4.2015 18:34

Člověče, a já si myslel, že zadání je poměrně jasné :-D Podvod se trestá smrtí celé skupiny. Dokonce jsem to tu napsal dvakrát!

 
Nahoru Odpovědět
26.4.2015 18:34
Avatar
alfonz
Člen
Avatar
alfonz:26.4.2015 18:47

Vězeň se podívá na ostatní a tipne si barvu, kterou má většina vězňů?

Nahoru Odpovědět
26.4.2015 18:47
lmao
Avatar
Honza Bittner
Tvůrce
Avatar
Odpovídá na coells
Honza Bittner:26.4.2015 18:49

Podívají se všichni vězni na sebe v jeden čas a pak se rozhodují, nebo se koukne vždy jeden a rozhodne se (=> umře/neumře) a pak jde další? :`

Nahoru Odpovědět
26.4.2015 18:49
FIT ČVUT alumnus :-) Sleduj mě na https://twitter.com/tenhobi a ptej se na cokoli na https://github.com/tenhobi/ama.
Avatar
coells
Tvůrce
Avatar
Odpovídá na alfonz
coells:26.4.2015 18:51

Vezmu si 10 vězňů, 5 jich dostane bílou, 5 černou, kolik jich přežije podle tvé strategie?

 
Nahoru Odpovědět
26.4.2015 18:51
Avatar
coells
Tvůrce
Avatar
Odpovídá na Honza Bittner
coells:26.4.2015 18:56

Zadání je jasné a úplné, opravdu není potřeba dávat další informace.

 
Nahoru Odpovědět
26.4.2015 18:56
Avatar
Neaktivní uživatel:26.4.2015 19:48

Vězni se domluví, že se prohlídnou vždy 2 navzájem a když uvidí bílou tak se poškrabou na ruce a když černou tak na noze.(vím, že to je komunikace, ale nemyslím si, že by na to přišli)

Nahoru Odpovědět
26.4.2015 19:48
Neaktivní uživatelský účet
Avatar
alfonz
Člen
Avatar
Odpovídá na Neaktivní uživatel
alfonz:26.4.2015 19:58

A hádáš se s učitelem když na písemce si někdo koupí 50 ananasů?

Nahoru Odpovědět
26.4.2015 19:58
lmao
Avatar
Odpovídá na coells
Michael Škrášek:26.4.2015 20:07

Vězni se domluví že se postaví do řady, 1. se postaví, 2. se postaví, když 3. uvidí že jsou vedle sebe 2 stejní - postaví se mezi ne, pokud ne postaví se před 2. ... takhle to pokračuje dál, kámen úrazu by nastal pokud by jedné brvy bylo víc jak 6 kusů :D

Nahoru Odpovědět
26.4.2015 20:07
"I choose a lazy person to do a hard job. Because that person will find an easy way to do it. " Bill Gates
Avatar
Odpovídá na alfonz
Neaktivní uživatel:26.4.2015 20:07

Nějak nechápu..

Nahoru Odpovědět
26.4.2015 20:07
Neaktivní uživatelský účet
Avatar
Petr Gürth
Tvůrce
Avatar
Petr Gürth:26.4.2015 20:08

Vězni si určí dvojici a předem se domluví, že pokud bude mít ten druhý např. bílý klobouk, tak půjde do jednoho rohu a když černý, tak do druhého rohu :D Když pak dostanou klobouk, tak půjdou do toho rohu podle klobouku kolegy a zároveň tam, kde bude kolega, tak z toho poznají jaký mají klobouk :D Co takhle? :D Jo, asi určitá komunikace to je.. :D

 
Nahoru Odpovědět
26.4.2015 20:08
Avatar
alfonz
Člen
Avatar
Odpovídá na Neaktivní uživatel
alfonz:26.4.2015 20:11

Bylo to myšleno tak, že ať je zadání jakékoliv nemělo by se v něm hledat smysl a dodržet ho.

Nahoru Odpovědět
26.4.2015 20:11
lmao
Avatar
Neaktivní uživatel:26.4.2015 20:21

Otázka je,co se považuje za komunikaci ?

Editováno 26.4.2015 20:25
Nahoru Odpovědět
26.4.2015 20:21
Neaktivní uživatelský účet
Avatar
Odpovídá na Neaktivní uživatel
Michael Škrášek:26.4.2015 20:24

Když se jeden obětuje, popraví ho, není to hra jako hra pro vězně, ale pro popravčí :D

Nahoru Odpovědět
26.4.2015 20:24
"I choose a lazy person to do a hard job. Because that person will find an easy way to do it. " Bill Gates
Avatar
hogs1397
Člen
Avatar
hogs1397:26.4.2015 20:33

Domluví se že nikdo z nich se nepodívá na černý klobouk, a když s dotyčným nikdo nenaváže oční kontakt, má černý klobouk, ti co po čase zbydou zakřičí bílý klobouk. Myslím že to není komunikace, vyhýbáním se očního kontaktu je jako vyhýbání komunikace, zadání je nekomunikovat.

 
Nahoru Odpovědět
26.4.2015 20:33
Avatar
coells
Tvůrce
Avatar
Odpovídá na hogs1397
coells:26.4.2015 20:46

V našem binárním světě má FALSE (nepodívat se) zcela stejnou informační hodnotu jako TRUE (podívat se). Navíc bych moc rád věděl, jak by věděli barvu klobouku, kdyby se na něj nepodívali? :-D

Tahle úloha opravdu má reálné řešení, není potřeba snažit se obcházet pravidla.

 
Nahoru Odpovědět
26.4.2015 20:46
Avatar
Odpovídá na coells
Neaktivní uživatel:26.4.2015 20:48

Nemyslím si, v podstatě nic, kromě dívat se ostatním na hlavu nemůžou.

Nahoru Odpovědět
26.4.2015 20:48
Neaktivní uživatelský účet
Avatar
coells
Tvůrce
Avatar
coells:26.4.2015 21:07

Přijde mi zajímavé, kolik energie všichni vložili do toho, aby obešli poměrně jednoznačné zadání. Není lepší to využít na samotné řešení?

Když řešíte podobné problémy, bývá nejlepší začít řešení od nejjednodušší úlohy:

Mám jenom jednoho vězně. Jak se může zachránit? Asi nijak, nemá žádné informace a musí tipovat. Má tedy šanci 50%, že přežije.

Takže mám dva vězně. Dokážu alespoň jednoho zachránit?

Kupodivu Petr Nymsa byl blízko, ale porušil pravidla. Také Michael Škrášek měl pravdu, když mluvil o popravčích, naše strategie bude drsná. Jednoho vězně obětujeme, aby druhý přežil. Otázkou je, jak?

A dá se to zobecnit? Očekávaná hodnota přežití vězně je 50%, takže více jich nedokážeme zachránit. Jak z nich vždy zachránit polovinu?

 
Nahoru Odpovědět
26.4.2015 21:07
Avatar
Odpovídá na coells
Neaktivní uživatel:26.4.2015 21:16

Udělají trojici a ten který z trojice uvidí ve své trojici více barev, je zavede na určitou stranu(třeba B B Č , bílý vidí bílého a černého to stejný 2. bílý, ale černý vidí 2x bílé a zavede je na stranu k bílým) 1 se obětuje pro 2.. v případě že by ale zbyl jeden nebo dva tak musí tipovat.

Editováno 26.4.2015 21:18
Nahoru Odpovědět
26.4.2015 21:16
Neaktivní uživatelský účet
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na coells
Lukáš Hruda:26.4.2015 21:22

Vězni se rozdělí do dvojic a v každé dvojici první vězeň řekne barvu toho druhého a druhý vězeň řekne barvu opačnou, než má ten první. Takto vždy přežije z dvojice právě jeden vězeň.

Akceptované řešení
+20 Zkušeností
+2,50 Kč
Řešení problému
 
Nahoru Odpovědět
26.4.2015 21:22
Avatar
Odpovídá na Lukáš Hruda
Neaktivní uživatel:26.4.2015 21:24

To je ale komunikace a to by popravili celou skupinu :D

Nahoru Odpovědět
26.4.2015 21:24
Neaktivní uživatelský účet
Avatar
Odpovídá na Neaktivní uživatel
Neaktivní uživatel:26.4.2015 21:26

*Když by zbyla dvojice tak utvoří pětici a podle stejného pravidla se dovedou na stranu.

Nahoru Odpovědět
26.4.2015 21:26
Neaktivní uživatelský účet
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Neaktivní uživatel
Lukáš Hruda:26.4.2015 21:27

To není komunikace, protože si ty barvy neříkají navzájem a barvy ostatních vězňů vidí. Stačí, aby si předem domluvily, kdo bude s kým ve dvojici a kdo bude říkat barvu toho druhého a kdo barvu opačnou.Na druhou stranu to co navrhuješ ty, to podle zadání komunikace je.

 
Nahoru Odpovědět
26.4.2015 21:27
Avatar
hogs1397
Člen
Avatar
Odpovídá na coells
hogs1397:26.4.2015 21:29

Špatně jsem to napsal, všichni se podívají na klobouky všem ale nebudou se dívat osobě s černým kloboukem do očí.


Nebo mě napadlo jestli se mohou vodit po místnosti a tak tak se domluví: Budeme běhat za černými klobouky a utíkat před bílími klobouky. Pak když osoba za kterou běžíš stojí, znamená to že máš černý klobouk a když za tebou běží někdo taky to znamená že máš černý klobouk. Když za někým utíkáš ale on zdrhá jako o život, ty máš bílý on černý.. win x win situace se zdravým pohybem.

 
Nahoru Odpovědět
26.4.2015 21:29
Avatar
Neaktivní uživatel:26.4.2015 21:32

Ten co vidí většinu prostě jde na nějakou stranu neupozorní je na to aby šli za ním protože vidí víc barev..

Nahoru Odpovědět
26.4.2015 21:32
Neaktivní uživatelský účet
Avatar
Odpovídá na hogs1397
Martin Konečný (pavelco1998):26.4.2015 21:33

To je ale pořád určitá forma komunikace, ne? Předávají si informaci tím, že běhaj za tímhle a utíkaj od tamtoho.

coells: Chápu správně, že může mít i ze 100 vězňů 99 z nich černý klobouk a jeden bílý a opačně?

Nahoru Odpovědět
26.4.2015 21:33
Aktuálně připravuji browser RPG, FB stránka - https://www.facebook.com/AlteiraCZ
Avatar
Odpovídá na Martin Konečný (pavelco1998)
Neaktivní uživatel:26.4.2015 21:36

V tom případě to nejde, nic by nemohli dělat

Nahoru Odpovědět
26.4.2015 21:36
Neaktivní uživatelský účet
Avatar
hogs1397
Člen
Avatar
Odpovídá na Neaktivní uživatel
hogs1397:26.4.2015 21:45

Taky myslím že to nejde, přecejen je šance 50/50 protože nevíme kolik bílých/černých klobouků mají, a všechny varianty dají 50/50 a ne pravděpodobnost p. Takže vězeň co vezme v úvahu všechny varianty dojde k tomu samému.

A nebo že by udělali dokonalý podvod,. Tedy věc, stejnou jako dokonalý zločin, kdybych Vám to tu vysvětlil, nebyl by to dokonalý podvod, protože by se na něj přišlo. Když Vám to nevysvětlím, dokonalý podvod to je. --> Stačí vymyslet strategii, ta zní udělat dokonalý podvod.
Těpni mi tu už správné řešení a jdem o dům dál :D

 
Nahoru Odpovědět
26.4.2015 21:45
Avatar
Odpovídá na hogs1397
Neaktivní uživatel:26.4.2015 21:49

Ten "dokonalý" podvod jsem tu už taky psal. Ale chtělo by to i vědět co se bere za komunikaci a co ne..

Nahoru Odpovědět
26.4.2015 21:49
Neaktivní uživatelský účet
Avatar
Odpovídá na coells
Michael Škrášek:26.4.2015 21:49

Psal jsi: ', pak jdou na samotku a tam musí odpovědět.', takže to nemůže být řešení - neslyší jak ten 2. z dvojce hádá ....

Nahoru Odpovědět
26.4.2015 21:49
"I choose a lazy person to do a hard job. Because that person will find an easy way to do it. " Bill Gates
Avatar
coells
Tvůrce
Avatar
coells:26.4.2015 21:53

Takže Lukáš Hruda na to přišel, pěkně, Lukáši!

Naše strategie bude jednoduchá. Jak píše Lukáš, vězni se na začátku domluví a rozdělí do dvojic a v každé dvojici se označí A a B. Když se jich později zeptají na barvu jejich vlastního klobouku, A řekne barvu B a B řekne opačnou barvu A. Díky tomu právě jeden z dvojice vždy přežije. Pokud zbývá nějaký lichý vězeň, musí si tipnout.

K ostatním dotazům, ano, klidně můžeme mít 100 bílých nebo 100 černých klobouků nebo 50/50.

Šance není 50/50, jak už jsem psal na začátku, a priori šance je 50%, ale a posteriori šance je daná distribucí, kterou zná jen ředitel, a kterou nelze při nízkém počtu vězňů ani přesně odhadnout.

 
Nahoru Odpovědět
26.4.2015 21:53
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na coells
Lukáš Hruda:26.4.2015 21:56

Napadla mě ještě strategie, která by teoreticky měla zachránit minimálně 50% vězňů, ale mohla by jich zachránit i více.

 
Nahoru Odpovědět
26.4.2015 21:56
Avatar
Odpovídá na coells
Neaktivní uživatel:26.4.2015 22:00

co když se ředitel rozhodne, že všichni budou mít bílé klobouky ? :D

Nahoru Odpovědět
26.4.2015 22:00
Neaktivní uživatelský účet
Avatar
Odpovídá na Lukáš Hruda
Michael Škrášek:26.4.2015 22:01

Jestli jsem to pochopil správně, tak se rozdělí do dvojic, 1. řekne barvu toho druhého, ten 2. tu stejnou, co řekl 1. či opačnou ... , ale ten 2. ho neslyší ... jak jsem už psal nad tím

Odpovídá na coells
Psal jsi: ', pak jdou na samotku a tam musí odpovědět.', takže to nemůže být řešení - neslyší jak ten 2. z dvojce hádá ....

pokud jsem to pochopil špatně tak jsem asi jelito, tato strategie mě napadla už včera, ale nenapsal jsem to kvůli 4. komentáři ...

Nahoru Odpovědět
26.4.2015 22:01
"I choose a lazy person to do a hard job. Because that person will find an easy way to do it. " Bill Gates
Avatar
hogs1397
Člen
Avatar
Odpovídá na coells
hogs1397:26.4.2015 22:01

Protože to zná jen ředitel, vězeň si řekne: "sákryš dyť já nevím koliko klobouků tu je, to může být: (př. s 6ti vězni) ČČČČČČ, ČČČČČB, ČČČČBB, ČČČBBB, ČČBBBB, ČBBBBB, BBBBBB, No to mi snad dá stejný počet klobouků ne?" no poškrábe se a selským rozumem řekne 50/50, a takový vězeň neřeší priori a posteriori. Protože není řečena ta distribuce tak se musí počítat se všemi možnostmi. A to 50/50 prostě hodí.

 
Nahoru Odpovědět
26.4.2015 22:01
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na Michael Škrášek
Lukáš Hruda:26.4.2015 22:07

První řekne barvu druhého a druhý řekne opačnou barvu prvního, kdo co řekl vůbec nezohledňují.

 
Nahoru Odpovědět
26.4.2015 22:07
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 50 zpráv z 69.