Problem

HeMan je 26. jun 2011 ob 16:06 izjavil:

Morda pa sedaj razumem kaj je trik guruja. Namreč v njegovem stavku se ne skriva nič nove informacije. Vendar ker so vsi logiki na otoku, lahko preko logike iz njegovega stavka sedaj s 100% verjetnostjo vejo, da tudi drugi vejo za modro barvo. Oz, tole še ni čisto pravilno, ker to tudi prej vejo, namreč da imajo vsi modro barvo. Ha, dejansko ne znam v besede spravit.

Tricky zadeva in zabavna :)

Mislim, da se ti počasi odpira.

Namreč v njegovem stavku se ne skriva nič nove informacije.

Na prvi pogled, v resnici pa se ravno v tem stavku skriva tista ključna informacija, zadnja, ki je logikom na otoku še manjkala za rešitev naloge.

O.

Sam stavek pove toliko informacije, kot stavek da je trava zelena. To ja vsi vemo.

Predpostavljamo, nismo pa 100% prepričani, da res vsi vedo. Mogoče je kakšen barvno slep:-) Ko nekdo pove naglas, smo pa 100% prepričani, da vsi vedo.

O.

preko logičnega sklepanja pridejo do neke nove informacije.

Preko logičnega sklepanja ali preko računanja ne prideš do nove informacije. Nikoli. FYI.

Okapi, ti rabš težke inštrukcije za osnovne zadeve, gobcaš pa neverjetno.

Guru lahko z izbiro barve vpliva na to, koliko ljudi bo zapustilo otok. Če v tvoji nalogi izbere modro, bo otok zapustilo manj ljudi, kot če izbere rjavo.

Thomas, ti pa znaš zakomplicirat. Laiku lahko preprosteje rečeš. Lahko rečemo simpl da Guru da informacijo, KI BI bila nova v primeru dveh ali manj modrih. In z tem omogoči induktivno sklepanje. A to je zate Okapi preveč za lase prvlečeno? Ja too bad, pa pejt na kake lažje naloge.

Kajti če je 100 ljudi na otoku, vsak vidi 99 modrookov in dopušča da so ti edini. Če so ti edini, vidijo samo po 98 in vsak dopušča, da so to edini. Od teh 98 vsak vidi 97 in dopušča da so to edini, ... In tako pride do 3, do 2 in na koncu do enega.

Ja, tako je, to je cel point. Ključno je, da oni sklepajo na podlagi tega, za kar vedo, da drugi lahko sklepajo. Zadevo si je malo težje predstavljat pri velikem številu oseb, ker gre v bistvu za to, kaj prvi dopušča, da drugi dopušča, da tretji dopušča ... Ampak princip je isti kot pri treh.

Gre v bistvu za to, da pri iskanju rešitve otočani postopoma eliminirajo nepravilne variante iz svojih množic možnih variant. Da se zadeva lahko začne razpletati, je potreben guru, ki da vstopno informacijo - npr. da vidi modrookega. Na podalgi te informacije lahko naslednji dan, ko so modrooki še vedno v enakem številu, vsi otočani z gotovostjo sklepajo, da nihče v svoji množici dopustnih variant ne more več imeti tiste, pri kateri nekdo dopušča le enega modrookega (to je nekoga, ki ne vidi nikogar z modrimi očmi).

Mogoče se zdi, da je to dejstvo očitno že ves čas. Ampak zavedati se je treba, da ne govorimo o tem, kaj otočani vejo, da drugi vidijo, ampak o tem, kaj otočani vejo, da drugi potencialno lahko sklepajo. Že res, da je vsak otočan lahko gotov, da vsak modrook vidi vsaj m-1 modrookih, kjer je m število modrookih, ki jih vidi on sam. Ampak znotraj variante, kjer posameznik vzame, da modrooki vidijo enega modrookega manj kot on (z drugimi besedami, da on ni modrook), bodo ti sklepali na identičen način - prav tako ne vedo, če so sami modri, torej bodo tisti modri, ki jih oni vidijo, lahko videli enega modrega manj. In tako naprej, vse dokler ne pridemo do potenicalnega edinega modrega. In to se vse nanaša na varianto v glavi prvega otočana, ki jo mora preveriti na poti do rešitve.

Meni se zdi zanimivo, kako je naloga za otočane rešljiva samo postopoma. Recimo na primeru samo treh modrih (in nič drugih): čeprav vsak zase ve, da prvo noč po gurujevi informaciji še nihče ne bo zapustil otoka (ker vsi vejo, da drugi vidijo vsaj enega modrega), vseeno morajo počakati, saj so šele po prvi noči lahko sigurni, da nihče več ne sklepa, da bi bil lahko le en moder. Po drugi noči podobno sklepajo, da nihče več ne sklepa, da bi bila lahko samo dva modra - torej mora biti moder tudi on sam.

V bistvu otočani prek svojih ne-odhodov vzajemno sporočajo drug drugemu, koliko oseb barve x, ki jo je povedal guru, vidijo. To, da N-ti dan ne odidejo, je enako kot če bi vsi rekli: "Vidim vsaj N oseb z x barvo oči." Ko je ta N enak številu oseb z x barvo, ki jo ti vidiš, veš, da si tudi ti med njimi. Če pa nisi, pa itak že v štartu nisi imel nobenih možnosti, saj bojo odšli že dan prej, preden bo N dosegel tisto število oseb z x barvo, ki si jo videl.

(edit: v prid boljše razumljivosti sem drugače postavil nekaj stavkov)

@Okapi

Sej ne da bi se hotel kregat, ampak vseeno moram rečt, da je pa res precej neokusno, da zdaj kot glavni šef tu nastopaš in Thomasu očitaš, kako da nima pojma. Ko sem včeraj bral to temo, si se ti sam motil in to svojo preočitno zmoto še precej arogantno zagovarjal. Ostali, na čelu s Thomasom, so ti pa poskušal razložiti, česar si se seveda vneto otepal. Zato zdaj, ko veš (če veš), da je guru potreben pogoj, res ni primerno zmerjat tistih, ki jim je to že ves čas jasno.

Še vedno ne veš, ja, kar je jasno sicer vsem. Plus se peteliniš, da te ni mogoče jemati drugače kot s krohotom.

Sitna pojava, ker distraktaš teme.

Bodisi zvejo, da vsi ostali otočani vidijo vsaj enega modrega več od števila, za katerega so bili lahko gotovi dan prej, bodisi zvejo, da niso modri (če vsi modri že zapustijo otok).

Tukaj bi moral napisat da zvejo, da vsi ostali sklepajo, da vsi vidijo vsaj enega modrega več od števila, za katerega so bili gotovi dan prej.

Drugač pa IMO tole "gnezdeno" sklepanje (kaj nekdo sklepa, da drugi sklepa, da tretji sklpea, itd.) tudi najbolj otežuje predstavo problema.

Thomas je 26. jun 2011 ob 15:18 izjavil:

če guru ne pove nič novega, potem ni potreben, če je potreben, pa nujno pove nekaj, česar prej niso vedeli.

To je tvoja neumna ideja, ja.

Guru pove nekaj novega, pove nekaj zelo pomembnega. To je, da ima vsaj ena oseba modre oči naprimer. Brez tega podatka se odhodi nikdar nebi pričeli.

Ubistvu bi lahko tudi rekli, da je gurujev stavek pogoj, da lahko algoritem izpelješ z logiko. Brez tega stavka, se algoritma samo z logiko ne da izpeljat?

Skratka iščem opis, zakaj je guru pomemben, da ga bo vsak laik razumel. Thomasovih besed še sam ne razumem dobro. Sploh ne vem o kateri spremenljivki govori, ki jo guru nastavi.

Guru je nujen, da lahko rešiš primer pri enem modrem in nato potegneš indukcijo na 100.

Guru je nujen, da lahko rešiš primer pri enem modrem in nato potegneš indukcijo na 100.

V resnici je guru nujen zato, ker otočani brez njega ne morejo sami priti do ključne informacije, potrebne, da steče indukcija. Da otočani nikakor ne morejo sami s kakšnim sklepanjem priti do te informacije, ni pa še nihče tule zares dokazal. Zaenkrat samo nihče ne zna dokazati, da je to mogoče.

Ti bi pa lahko do takrat tudi vsaj dopustil možnost, da take rešitve res ni

Saj jo dopuščam, v bistvu že ves čas. Ampak na začetku te debate ni bilo slišati ugovorov na trditev, da guru ne pove nič novega. Thomas je sam trdil, da guru ne pove nobene nove informacije. In če bi bilo to res, je nekako logično, da guru ni potreben.

O.

Porečem to, da se ne pogovarjamo, ali je koristen, ampak ali je nujno potreben. Denar pod posteljo bi lahko našel tudi brez njega in torej ni potreben. Potreben (v smislu, kot se tule pogovarjamo) bi bil, če brez njega nikakor ne bi mogel najti denarja.

O.

technolog je 26. jun 2011 ob 22:23 izjavil:

Gurujev stavek je pogoj, da lahko algoritem izpelješ z logiko na enoličnen način.

Tole je res še na najbolj razumljiv način povedano.

Vprašanje za razmislek: Če guruja ni in imamo 100 modrih in eden od teh modrih reče, da vidi nekoga z modrimi očmi. Je naloga rešljiva ali ne? Ta, ki je to izjavil, ne gre nikamor.

Ne razumem. Zakaj bi guru spraševal ljudi, če je barva njegovih oči modra?

Pa tudi zakaj bi se kdorkoli spraševal, če ga je guru videl, ko pa je v nalogi podano, da se vsi vidijo med sabo? Ker je odgovor jasno ja.

In veste kaj? Kadar sta najmanj dva z isto barvo oči, bi bilo dovolj, če bi guru samo pokazal nekoga od naseljencev in algoritem bi stekel. Kazanje bi pomenilo - vidim človeka s tako barvo oči!

Hm, kaj pa če bi pokazal vsakega na otoku. Tudi tukaj bi kazanje pomenilo vidim človeka s tako barvo oči. Bi algoritem stekel?

Seveda pomaga. Ko uni so šli, ta ve katerih ni več in da ima tako barvo oči.

Algoritem steče, tak (ali nekoliko modificiran), če je bila opravljena funkcija izbire. S strani guruja, ker pač oni se ne smejo med sabo pogovarjati in kazati.

In veste kaj? Kadar sta najmanj dva z isto barvo oči, bi bilo dovolj, če bi guru samo pokazal nekoga od naseljencev in algoritem bi stekel. Kazanje bi pomenilo - vidim človeka s tako barvo oči!

Torej če imaš 2 modra in guru pokaže na enega, kar pomeni da vidi nekoga s tako barvo oči, kako točno lahko onadva rešita nalogo? Ali sem te narobe razumel?

PS: je ta naloga rešljiva:
- imamo 100 modrih in eden od teh modrih reče, da vidi nekoga z modrimi očmi?

Ta, ki to izjavi, ne gre nikamor.

Vztrajam na tem kar sem rekel in kakor sem rekel.

Če modri spregovori namesto guruja, ta nikoli ne zapusti otoka in vsi grejo hkrati dol en dan prej.

In sicer zakaj? Čisto vseeno je, kdo otočanom pove, da je vsaj en med njimi moder.

O.

Ni res. Še enkrat, ni važno od kje je informacija, lahko je tudi od modrega, če bi lahko govoril. Izid je isti.

Imaš 2 modra z imeni A in B, da bo ločevanje lažje.
- oba ne vesta za svojo barvo oči
- A reče da vidi modre oči

Po tvoje gresta oba domov 2. dan?