05 februára 2011

Tri sochy

Kto nám do komentárov ako prvý napíše správne riešenie nasledovnej úlohy, dostane odo mňa knihu "Professor Stewart's Cabinet of Mathematical Curiosities" od Iana Stewarta (to aby som Vás motivoval túto úlohu aspoň dočítať do konca). Zadanie pochádza od Braňa Novotného (ďakujeme) a sponzorom tejto súťaže je, hoci o tom nevie, Thomas Klein (tiež ďakujeme; keď ma bol navštíviť, doniesol mi knižku, ktorú už vlastním :).

  Na ceste za pokladom je chrám, z ktorého vedú dve cesty - vľavo a vpravo. Jedna vedie k pokladu a jedna do záhuby. V chráme sú tri sochy. Jedna vždy hovorí pravdu, jedna vždy klame (hovorí nepravdu - tj. nesnaží sa zavádzať), a jedna odpovedá náhodne.

  O sochy sa starajú dvojičky, ktoré môžu položiť sochám dve otázky denne, vždy sa musí pýtať práve jeden z nich práve jednej sochy a tá odpovie podľa svojej prirodzenosti, ale keďže sú to iba sochy, tak zvládnu iba A a O, jedno znamená áno, druhé nie. Sochy majú dosť informácií: tj. rozoznajú bratov, vedia ktoré dvere sú správne, majú rozumný prehľad o svojom okolí a ak sa ich niekto spýta otázku, na ktorú nevedia korektne odpovedať A, alebo O, tak odpovedia náhodne.

  Hľadačovi pokladu vysvetlia bratia pravidlá a za dostatočnú odmenu sú ochotní spýtať sa sôch dve pútnikove otázky a to tak, že (hľadačom) vybraný brat otázku presne zopakuje vybranej soche a vypočuje si odpoveď a tú povie hľadačovi, lenže starší brat odpoveď vždy zmení na opačnú. Samozrejme bratia neprezradia ktorý z nich je starší, ktoré z A a O je áno a ktoré nie a sochu, ktorej sa budú pýtať, môže hľadač určiť iba ako vľavo, vpravo a v strede.

Aké dve otázky sa má hľadač spýtať, aby sa dozvedel ktorá cesta vedie k pokladu?

8 komentárov:

Anonymný povedal(a)...

Nie som si ista, ci je v zadani myslene, ze nahodna socha odpoveda uplne nahodne, alebo si pri kazdej otazke nahodne zvoli, ci bude klamat alebo hovorit pravdu a toho sa potom pri tej jednej odpovedi drzi. Predpokladala som, ze je to ta druha moznost. Takze tu je moje riesenie (dufam, ze je spravne):
najskor polozim jednym bratom jednej soche otazku: "hovoris prave pravdu?". Na tuto otazku kazda socha odpovie ano. a nech uz to acka ocka a bratia akokolovek skomolili, viem, ze socha odpovedala ano. potom tym istym bratom polozim tej istej soche otazku: "je pravda, ze ak prave teraz hovoris pravdu, tak je poklad vlavo a ak prave klames, je poklad vpravo?". Ak je poklad vlavo, tak na tuto otazku kazda socha odpovie ano, ale ak je poklad vpravo, tak na nu kazda socha odpovie nie. A nech uz acka, ocka a bratia odpoved akokolvek skomolili, dolezite je, ze ju skomolili uplne rovnako ako v prvom pripade, takze ak je poklad vlavo, dostanem rovnaku odpoved ako na prvu otazku, ale ak je vpravo, dostanem opacne pismenko.
lubka

Brano povedal(a)...

Ak by sa nahodna socha chovala tak ako si to predpokladala, tak by sa to dalo zvladnut na jednu otazku. Myslene to bolo tak, ze ona proste nahodne vygeneruje odpoved nezavysle na otazke.
Dve otazky su kvoli nahodnej soche, teda mozno bude najlepsie vyriesit ulohu, ked sochy odpovedaju ano a nie a da sa ich pytat priamo.

Anonymný povedal(a)...

Tak sa mi podarilo vyriesit to aj s takymto zadanim. Staci celkom jednoducha obmena predoslej odpovede. Opytat sa sochy v strede: "je pravda, ze ak si pravdiva, je socha nalavo anhodna a ak si klamiva, je socha napravo od teba nahodna?". ak je nahodna nalavo, dostanem odpoved ano, ak je nalavo odpoved je nie a ak je v stredem odpoved je nahodna. kazdopadne viem o jednom mieste, kde nie je nahodna socha a tej sa opytam: "je pravda, ze ak si pravdiva socha, je poklad nalavo a ak si klamiva socham je napravo?" a rovnakym sposobom sa dostanem k tomu, kde je poklad.
Ak mame nezjednodusenu ulohu, tak staci pridat par implikacii navyse: "je pravda, ze ak si pravdiva socha, A je ano a pyta sa ta starsi brat, tak je socha nalavo nahodna, a ak si pravdiva socha, A je ano a pyta sa ta mladsi brat, tak je socha napravo od teba nahodna, a ak si pravdiva socha a O je ano a pyta sa ta starsi brat, tak je socha napravo od teba nahodna, a ak si pravdiva socha, O je ano a pyta sa ta mladsi brat, tak je socha nalavo od teba nahodna, a ak si klamiva socha a A je ano a pyta sa ta starsi brat, tak je socha napravo od teba nahodna, a ak si klamiva socha a A je ano a pyta sa ta mladsi brat, tak je socha nalavo od teba nahodna, a ak si klamiva socha a O je ano a pyta sa ta starsi brat, tak je socha nalavo od teba nahodna, a ak si klamiva socha a O je ano a pyta sa ta mladsi brat, tak je socha napravo od teba nahodna?". Ak je socha nalavo nahodna, dostanem v kazdom pripade odpoved O a ak je nahodna napravo, dostanem odpoved A. ak je v strede, je to jedno, mam uz jedno miesto, kde urcite nahodna socha nie je a tej poslem podobny pamflet, len sa nebudem pytat na to ci je napravo/nalavo nahodna socha, ale poklad. a ak dostanem O, poklad je vlavo a ak A, je vpravo.
Len velmi dufam, ze toto nie je najelegantnejsie riesenie, ake sa da najst, labo to uz clovek potrebuje poriadne basnicke crevo, aby za takymi sochami siel.
lubka

Brano povedal(a)...

Je to spravne (teda asi, ma to spravnu strukturu a detaily sa mi nechce pozerat:), ale ak si napises vyrok ktoreho pravdivostnu hodnotu skumas do beznych symbolov z logiky a trosku poupravujes a povynimas pred zatvorky atd, tak sa to da zjednodusit.

Anonymný povedal(a)...

Zjednodusenie lubkinho vyrazu - ak chceme zistit od sochy vyrok X: "Je pravda, ze plati: A je ano prave vtedy, ked sa ta pyta mladsi brat a to cele prave vtedy, ked si pravdovravna socha a to cele prave vtedy, ked plati X". Ak plati X, odpoved od brata je A, ak neplati, je O (ak sa nepytame nahodnej sochy).

Radoslav Harman povedal(a)...

Ľubka: napíš mi email (radoslav.harman na gmail.com) a dohodneme sa kedy sa u mňa môžeš zastaviť pre knihu.

Brano povedal(a)...
Tento komentár bol odstránený autorom.
Brano povedal(a)...

Mna este napadla taka uprava otazky, ktora je, myslim, zrozumitelnejsia.
P(A)-pravdivostna hodnota A
P(A<=>B)=P(A)+P(B)+1 kde + je v Z_2 a teda
P(A<=>(B<=>(C<=>D)))=P(A)+P(B)+P(C)+P(D)+1
cize A<=>(B<=>(C<=>D)) je ekvivalentne vyroku: "Z nasledujucich moznosti je parny pocet pravdivych: A,B,C,D"