Bavili smo se do sada, Istinitim (koji uvijek govori istinu), Lažnim (koji uvijek govori neistinu), Slučajnim (koji slučajno odabire hoće li odgovoriti istinu ili neistinu) i Pravim Slučajnim (koji slučajno odabire hoće li odgovorit „ku“ ili „lo“ – što znači „da“ ili „ne“ ali ne znamo koje znači što).

Izvorni Boolosov „najteži logički problem“ bio je da s tri pitanja otkrijemo tko je Istiniti, tko je Lažni a tko Slučajni.

„Još teži problem“ Raberna i Raberna bio je da s tri pitanja otkrijemo tko je Istiniti, tko je Lažni, a tko Pravi Slučajni. Ta smo dva problema riješili.

Za rješenje je bilo bitno razumjeti sljedeće.

Ako Istinitoga pitate „je li P“ odgovor „da“ znači da je P istina, a odgovor „ne“ da je P neistina i to je svima jasno.

Ako Istinitoga, Lažnoga ili Slučajnoga pitate:

Bi li „ku“ bio tvoj odgovor na pitanje „je li P“?

svi oni odgovaraju „ku“ ako je P istina, a odgovaraju „lo“ ako P nije istina i to je ključno.

Složeno pitanje:

Bi li „ku“ bio tvoj odgovor na pitanje „je li P“?

kraće ćemo zapisivati:

Je li P???

(uočite 3 upitnika).

Dakle, bez obzira odgovara li naš ispitanik istinito ili neistinito i bez obzira je li  ku=da, a  lo=ne  ili je obratno, njegov odgovor na „Je li P ???“ jest „ku“ kada je P istina i jest „lo“ kada je P neistina.

Ukratko, odgovorom Istinitog, Lažnog ili Slučajnog na pitanje „Je li P ???“ dolazimo do iste informacije do koje bismo došli da smo Istinitom postavili pitanje „Je li P?“.

To znači da smo problem ispitivanja Istinitog, Lažnog i Slučajnog sveli na problem ispitivanja tri Istinita.

Još je teži problem (Raberna i Raberna) postavljen u prethodnom postu:

Možete li identitete Istinitog, Lažnog i Slučajnog otkriti sa samo 2 pitanja?

Za rješenje tog problema ključno je razumjeti da Istiniti i Lažni na neka pitanja naprosto ne mogu odgovoriti nego ih moraju odšutjeti. Naime, što Istiniti može odgovoriti na :

Je li tvoj odgovor na ovo pitanje „ne“?

Ako odgovori „da“ onda bi njegov odgovor trebao biti „ne“,  što je nemoguće. Ako odgovori „ne“ onda bi njegov odgovor trebao biti „da“, što je opet nemoguće.

Dakle, odgovor mora odšutjeti.

Na isti način zaključujemo da Lažni mora odšutjeti odgovor na:

Je li tvoj odgovor na ovo pitanje „da“?

Naravno, naši Istiniti i Lažni ne odgovaraju s „da“ i „ne“ nego s „ku“ i „lo“, pa su pitanja koja oni moraju odšutjeti zapravo ova:

Je li tvoj odgovor na ovo pitanje riječ koja u tvojem jeziku znači „ne“?

Je li tvoj odgovor na ovo pitanje riječ koja u tvojem jeziku znači „da“?

(Usput, s ova dva pitanja možete odrediti identitet svake pojedine osobe. Zatim, s još jednim pitanjem, možete odrediti identitet preostale dvije osobe. Tako dobivate alternativno rješenje izvornog „najtežeg logičkog problema“.)

No, vratimo se problemu određivanja identiteta Istinitog, Lažnog i Slučajnog sa samo dva pitanja.

Krenimo od (na prvi pogled) lakšeg problema. Marko, Luka i Ivan uvijek govore istinu. Možemo li sa samo dva pitanja odrediti koji je koji? Možemo!

Prvo osobi A postavljamo sljedeće pitanje:

(1A)        Je li točno:

                [(Odgovorit ćeš „ ne“ na ovo pitanje) i (B je Marko)] ili [B je Luka]?

Ako A odgovori „da“ onda je B Luka.

Ako A odgovori „ne“ onda je B Ivan.

Ako A odšuti odgovor onda je B Marko.

Evo i dokaza da je tomu tako.

Pretpostavimo da A odgovori „da“ i da B nije Luka. To znači da A odgovara „da“ na: „odgovorit ćeš „ne“ na ovo pitanje?“, što nije moguće jer A (kao istiniti) odgovor na to pitanje mora odšutjeti. Dakle, nije moguće da A odgovori „da“ i da B nije Luka.

Drugim riječima, ako A odgovori „da“ onda B jest Luka.

Pretpostavimo da A odgovori „ne“ i da B nije Ivan. To znači da A odgovara „ne“ na oba pitanja u uglatim zagradama. Odgovor „ne“ na drugo od ta dva pitanja znači da B nije Luka. Budući smo pretpostavili da nije ni Ivan, slijedi da je B Marko. Odgovor „ne“ na pitanje u prvoj uglatoj zagradi znači da je „ne“ odgovor na oba pitanja u okruglim zagradama. No, to je nemoguće jer odgovor na prvo od ta dva pitanja A (kao istiniti) mora odšutjeti, dok bi drugi odgovor „ne“ značio da B nije Marko, što je u suprotnosti s gornjim zaključkom da on je Marko. Dakle, nije moguće da A odgovori „ne“ i da B nije Ivan.

Drugim riječima, ako A odgovori „ne“ onda B jest Ivan.

Pretpostavimo na kraju da A odšuti svoj odgovor i da B nije Marko. Tada slijedi da B nije ni Luka (jer da je, A bi odgovorio „da“) . Ali ako B nije ni Luka ni Marko onda su obje tvrdnje u uglatim zagradama neistinite, pa bi A morao odgovoriti „ne“, što je u suprotnosti s pretpostavkom da šuti. Dakle, nije moguće da A šuti i da B nije Marko.

Drugim riječima ako A odšuti svoj odgovor onda B jest Marko.

Sve u svemu, iz odgovora na prvo pitanje jednoznačno možemo odrediti tko je B.

Nakon što smo to odredili, osobu B (za koju npr. znamo da je Luka) pitamo:

(2B)      Je li C Marko?

Ako B odgovori „da“ onda je C Marko i A je tada Ivan.

Ako B odgovori „ne“ tada je A Marko, a C je Ivan.

Dakle, svi su identiteti poznati nakon odgovora na samo dva pitanja.

Sada je lako riješiti i problem identifikacije Istinitog, Lažnog i Slučajnog sa samo dva pitanja.

Pitanja su:

(1A)        Je li točno:

                [(Odgovorit ćeš „ ne“ na ovo pitanje) i (B je Marko)] ili [B je Luka]???

 

(2B)        Je li C Marko???

S obzirom na ranije objašnjenu vezu „pitanja?“ i “pitanja???“ jasno je da ta pitanja rješavaju naš problem.

Preostaje pitanje je li moguće sa samo dva pitanja riješiti problem identifikacije Istinitog, Lažnog i Pravog  Slučajnog?

G.Uzquiano je dokazao da jest, ali je odmah postavio i teži problem:

Je li moguće s tri pitanja  riješiti problem identifikacije Istinitog, Lažnog i Istinski  Slučajnog, koji slučajno odabire hoće li reći „ku“ , „lo“ ili će šutjeti (za razliku od Pravog Slučajnog koji slučajno odabire hoće li reći „ku“ ili „lo“, ali nešto od toga sigurno kaže).

Da je i to moguće dokazali su G.Wheeler i P.Barahona. Također su dokazali da ovaj problem nije moguće riješiti sa samo dva pitanja.

Koga zanima kako se rješavaju ovi problemi neka uz natuknicu  Hardest Logic Puzzle  u tražilicu ukuca imena gore spomenutih autora.

Oglasi

About zsikic

https://www.fsb.unizg.hr/matematika/sikic/

Odgovori

Please log in using one of these methods to post your comment:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava / Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava / Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava / Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava / Izmijeni )

Spajanje na %s