Indukcione slagalice

Indukcione slagalice su logičke slagalice koje se rešavaju principom indukcije. U većini slučajeva, scenario slagalice uključuje nekoliko učesnika sa sposobnošću rasuđivanja i rešenje slagalice je zasnovano na identifikaciji šta bi se desilo u očiglednom slučaju, i onda ponavljanjem rasuđivanja da: "Čim jedan od učesnika shvati da se očigledni slučaj nije desio, može da ga eliminiše iz rasuđivanja, i tako stvori novi očigledan slučaj".

Tipična slagalica s pričanjem priče, je ona gde učesnik dobija informaciju o svim drugim učesnicima, samo ne o sebi. Takođe, daje se neka vrsta pomoći koja predlaže da učesnici mogu verovati inteligenciji drugih učesnika.

Primeri

Kraljev pametni čovek: Kralj je pozvao tri najpametnija čoveka u zemlji na njegov sud da bi odabrao novog konsultanta. Stavio je po kapu u svaku od njihovih ruku, tako da svaki čovek može da vidi kape drugih, ali ne i svoje. Svaka kapa je ili bela ili plava. Kralj je rekao da makar jedan od njih trojice nosi plavu kapu; drugim rečima, mogla je da bude jedna, dve ili tri plave kape, ali ne nula. Kralj je takođe rekao da je takmičenje fer za svu trojicu. Ljudima je takođe bilo zabranjeno da međusobno komuniciraju. Kralj je proglasio da koji od njih ustane prvi i tačno kaže koja je boja njegove kape će postati konsultant. Dugo su sedeli dok jedan od njih nije ustao i rekao tačan odgovor. Šta je rekao i kako je uspeo da reši problem?

Džozefinin problem: U džozefininom kraljevstvu svaka žena mora da prođe logički ispit pre nego što dobije dozvolu da se uda. Svaka udata žena u kraljevstvu zna o vernosti svakog muža sem njenog, i etiketa kaže da ni jedna žena ne treba da govori o vernosti svoga muža. Takođe, hitac ispaljen iz bilo koje kuće će se čuti u svakoj kući. Kraljica Džozefina je objavila da je najmanje jedan neverni čovek otkriven u kraljevstvu, i da svaka žena koja sazna da joj je muž neveran treba da ga upuca u ponoć, dan kasnije nego što je otkrila neverstvo. Kako su žene ovo postigle?

Alisa na konvenciji logičara: Na tajnoj konvenciji logičara, glavni logičar je stavio poveze na glavu svakog pristunog, tako da svi mogu da vide sve poveze sem svog. Postojalo je puno različitih boja poveza. Logičari su seli u krug, i glavni je rekao da će zazvoniti zvono u šumi u određenim intervalima: u trenutku kada neko shvati koje mu je boje povez treba da napusti sobu i zazvoni sledećezvono u šumi. Nisu smeli da razgovaraju, niti da koriste ogledalo ili kameru, u suprotnom ne smeju da koriste logiku da saznaju boju poveza. U slučaju prevaranata u konvenciji, svako ko pokuša da izađe ranije bi bio zadržan i kasnije pušten u određeno vreme, i svako ko ne bi uspeo da izađe na vreme bi bio isteran. Glavni logičar je uverio grupu da je slagalica nije nemoguća za svakog pravog logičara prisutnog. Kako su to rešili?

Rešenja

Kraljev pametni čovek: Ovaje je jedan od najjednostavnijih slagalici i najčistije indikuje koji je metod korišćen.

• Pretpostavimo da postoji jedan plavi šešir. Osoba s tim šeširom bi viela dva bela šešira i odmah bi znala boju sopstvenog. Međutim druga dvojica bi videla jedan plavi i jedan beli i stoga ne bi mogli da iz toga izvuku nikakvu informaciju. Dakle, ovaj scenario bi prekršio kraljevu rečenicu da svaki od njih ima jednake šanse da pogodi. Dakle moraju da postoje bar dva plava šešira.
• Pretpostavimo da ima dva plava šešira. Svaki od ljudi sa plavim šeširom bi video jedan plavi i jedan beli šešir. Pretpostavljajući da su shvatili da ne može biti samo jedan (koristeći prethodni scenario), oni bi znali da svaki od njih nosi plavi šešir. Međutim, čovek koji nosi beli šešir bi video dva plava šešira i ne bi mogao da izvuče nikakvu informaciju o tome koji mu je šešir na glavi. Ovaj scenario, onda, bi takođe remetio pravilo da svi imaju jednake šanse da pogode. Tako da moraju da postoje tri plava šešira.

Jer mora da postoji tri plava šešira, prvi koji to shvati će ustati i reći plavi.

Džozefinin problem: Ovo je dobar primer generalnog slučaja.

• Ako postoji samo jedan neverni muž, onda svaka žena u kraljevstvu to zna osim njegove žene, koja veruje da su svi verni. Međutim, čim čuje od kraljice da nevernik postoji, zna da je to njen muž, i ubija ga. 
• Ako postoje dva neverna muža, onda obe njihove žene veruju da postoji samo jedan neverni. Premda, očekivaće da će se dogoditi prvi slučaj, i da će druga žena ubiti muža sledećeg dana u ponoć. Kada se pucnji ne budu začuli, znaće da se nije dogodio prvi scenario, tako da mora da postoji još jedan nevernik (jer znaju da su svi ostali verni) jedan više mora da je njihov muž.
• Ako postoji 3 nevernih muževa, svaka od žena veruje da ih ima 2, tako da misle da će se dogoditi prethodni slučaj i da će obojica biti upucani sledećeg dana. Kada se ne čuje pucanj, znaće da se prethodni slučaj nije dogodio, stoga mora da postoji više od 2 neverna muža i tako je njihov muž kandidat za trećeg.
• Generalno, ako ima n nevernih muževa, svaka od njihovih žena će verovati da postoji n-1 neveran i očekivaće pucanj n-1og dana u ponoć. Kada ne čuju, znaće da je njihov muž n-ti.

Ovaj problem je takođe poznat kao problem muževa koji varaju, problem žena koje varaju, problem nemirne dece. Logički je identičan problemu plavih očiju.

Ovaj problem se pojavljuje i kao problem koji uključuje bele i crne šešire u C. L. Liuovoj klasičnoj knjizi 'Elements of Discrete Mathematics'.

Alisa na konvenciji logičara: Ovo je generalna indukcija sa skokom u logici.

• Skok u logici: Svaka boja mora da se pojavi bar dva puta u celom krugu. Ovo je istina jer je glavni logičar rekao da svako može da reši slagalicu od logičara. Ako se neka boja pojavila samo jednom, taj koji je nosio tu boju ne bi ni znao da ta boja uopšte postoji, i nikada ne bi pogodio.
• Svaki od njih može da pogleda u krug i vidi koja se boja koliko puta pojavljuje. Pretpostavi da si ti jedan od logičara i neku boju vidiš samo jednom. S obzirom da znaš da moraju da postoje barem dve iste boje, jedino objašnjenje je to da je to boja tvojeg poveza. Iz istog razloga, postoji samo jedna takva boja, i otišao bi na prvo zvono.
• Slično svaki od logičara koji vide neku boju samo jednom bi napustili s dostojanstvom ili bili izbačeni kao infiltratori. Ekvivalentno, svaka boja koja se pojavljuje dva putabi bila eliminisana na prvo zvono. Nakon toga mora da postoji bar tri poveza neke od preostalih boja.
• Pretpostavi da nisi video ni jednu boju jednom, ali si neku video dva puta. Ako je postojalo samo dve onda bi logičari s tom bojom otišli na prvo zvono. Meljutim nisu, to je jedino jer je tvoj povez te boje, tako da odlaziš na drugo zvono.
• Dakle, svaki logičar bi gledao dok grupa sa bojom koju su oni očekivali da ode, ne ode. Onda bi oni znali da imaju povez te boje i da trebaju da izađu na sledeće zvono.
• Kada ostane samo jedna boja, logičari s tom bojom bi svi otišli na sledeće zvono, jer bi znali da oni nemaju ni jednu od drugih boja (jer bi onda bilo nemoguće da saznaju svoju boju).

Vidi još

• Zatvorenici i kape
• Epistemska logika