Problem

Okapi je 21. jun 2011 ob 15:54 izjavil:

To je vse, kar imajo od informacij na voljo otočani in vse to vedo tudi brez guruja.

Ne nimajo. In ravno to mi gre tule na živce.

A group of people with assorted eye colors live on an island. They are all perfect logicians -- if a conclusion can be logically deduced, they will do it instantly. No one knows the color of her eyes. Every night at midnight, a ferry stops at the island. Any islanders who have figured out the color of their own eyes then leave the island, and the rest stay. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

Paragraph - odstavek?

P.S.: No ja, se posipam s pepelom, je res. Oni pač lahko preštejejo dejansko stanje. Ampak zase pa še vedno ne vedo kaj in kako.

Recimo, da guru rece samo: Tako, danes je 1. dan. Znajte se.
Recimo, da eni vidijo 34 modrookih, drugi pa 35 modrookih.
34ti dan gredo pogledat, ce se bo kdo vkrcal. Ker se nihce ne vkrca, se bodo 35ti dan vkrcali tisti, ki vidijo 34 modrookih.
Tako, da bi naceloma slo, ce vidijo vec kot enega modrookega. Ce vidijo samo enega, pa tisti, ki je modrook, sploh ne o vedel, da je modrook, in ne bo nikoli odsel.

Glede guruja- v nalogi je trik.

V bistvu guru ne posreduje informacije otočanom, ampak reševalcu.

Skozi "pomoč k nalogi" avtor sugerira reševalcu uporabo "plave rekurzije", ker je pač guru rekel "vidim enega plavega". To je enostavno vidno, ker bi guru komot rekel "vidim enega rjavega", pa bi stvar rešđevali skozi rjavo rekurzijo.

Poleg tega, ni očitno da je ta rešitev edina možna.

Pa tudi če je, ni videti, zakaj je ne bi mogli kombinirati z mojo in oditi prej.

Najprej se pustiš avtorju nategnit v to, da gredo itak lahko samo plavi, potem jih pa z "mod 2" trikom odpraviš v prvem šusu namesto 100-ti dan.

Okapi je 21. jun 2011 ob 15:54 izjavil:

Ker ne vedo, kdaj morajo iti.

Kako ne vedo? Vedo, da gredo lahko takoj, ko ugotovijo barvo svojih oči. In tega jim ni povedal guru. Guru jim pove samo, da vidi enega plavega, to pa vsi vedo tudi brez njega. Vedo tudi, da vidi tudi enega rjavega.

Vsak ima na voljo naslednje informacije:
Na otoku so ljudje z modrimi, rjavimi in mogoče še eden s tretjo barvo oči.
Na otoku je 200 ljudi, in pet možnih kombinacij barv:
100 rjavih + 100 modrih
99 rjavih + 101 modra
101 rjava + 99 modrih
100 rjavih + 99 modrih + ena neznana
100 modrih + 99 rjavih + ena neznana
Vsi so popolni logiki.
Ko ugotoviš, kakšne barve oči imaš, greš lahko z otoka.

To je vse, kar imajo od informacij na voljo otočani in vse to vedo tudi brez guruja.

O.

Potem reši primer za enega modrookega če se ti zdi da guru ni potreben. Vsi trdite da je ta informacija brezveze, nobeden pa še ni prispeval rešitve.

Oznanilo guruja je naravnost krucialno. Pa prispelo kaj informacije ali samo setiralo variablo.

Guruja si navsezadnje lahko predstavljamo tudi kot zelenookega naseljenca, ki je prekršil zapoved in ščvekal - vidim modrookca!

Tudi tako se nujna spremenljivka za ta algoritem lahko postavi!

Ja, če modrookci ne oddidejo v manj dneh, kot bi bilo modrookcev, če bi bil tudi ti modrook.

Guru je K R U C I A L E N, ko reče da vidi modrookca. K R U C I A L E N. Pa če je tudi 100 modrookih, 40 zelenookih, 200 rjavookih in 567 rdečeokih na otoku.

In kaj če se guru zlaže, da vidi rumenookega? Štala. Vsi gredo neupravičeno domov.

Potreben je kot triger, ki bo dal folku začetno kost za glodanje pri rekurzivni rešitvi in kot reseter števca in podatek, kaj se šteje pri nerekurzivni.

Oh yes!

Po tvoje bi šlo, vendar naloga dodatno signaliziranje eksplicitno prepoveduje.

In so perfektni logiki.

Pač. "Zapuščanje" otoka in signaliziranje tistim, ki ne ustrezajo, naj z zapuščanjem prenehajo, je neko dodatno sporazumevanje, o katerem v nalogi ni govora.

Vendar če si nalogo preoblikoval, jo lahko rešuješ na svoj način.

Ni ravno taka. Njo je nalogodajalec dopustil. To je pravica zastavljalca, da definira nalogo, kakor mu ljubo. Vse spremembe s strani reševalcev so lahko zgolj za namene analize. Ne moreš pa spremeniti pravil igre.

Odhod je v tej nalogi dovoljena komunikacija. In gurujevo oznanilo je tudi dovoljeno.

Manj ali več od tega, bi pomenilo trivializacijo naloge, je mislil zastavljalec problema.

Ti zdej lahko narediš zanimivejšo, magari na tej osnovi.

Ne smeš oditi, če ne veš barve svojih oči.

Thomas je 21. jun 2011 ob 16:21 izjavil:

Ja, če modrookci ne oddidejo v manj dneh, kot bi bilo modrookcev, če bi bil tudi ti modrook.

Kako pa potem veš a si rjavook al rumenook?

Jaz bi rekel takole:
Guru je samo nastavil števec dni na 1. Barva oči, ki jo je omenil, pa na nek način ni pomembna. Domov bodo lahko odšle vse osebe, ki ustrezajo dvema pogojema:
1.) Niso edina oseba z neko barvo oči (poleg nje obstaja vsaj še 1 oseba z isto barvo).
2.) Skupina oseb, ki ima njeno barvo oči, nima enako število članov kot katera izmed skupin druge barve.

Primer:
Sem na otoku in okoli sebe vidim 99 oseb z modrimi očmi, 47 z zelenimi in 52 z rjavimi. Če ustrezam zgoraj omenjenima pogojema, potem po 47. dnevu pogledam, če so osebe z zelenimi očmi odšle z otoka. Če niso, se jim naslednji dan pridružim, ker očitno čakajo samo še mene. Če so odšle, potem čakam do 52. dneva. Če takrat osebe z rjavimi očmi ne odidejo, se jim naslednji dan pridružim. Če odidejo, počakam do 99. dneva. Če takrat osebe z modrimi očmi ne odidejo, se jim naslednji dan pridružim.

Na tak način lahko otok zapustijo osebe vseh barv, ki ustrezajo danima pogojema. Tisti, ki jima ne ustrezajo, bodo žal ostali na otoku (vmes bodo sicer želeli oditi, vendar se bodo zmotili glede svoje barve, zato jim bo odhod onemogočen), razen če guru omeni njihovo barvo. Dejansko lahko guru koristi samo takim osebam.

V konkretnem primeru, ki ga podaja naloga, noben ne bi mogel oditi z otoka, ker nihče ne ustreza 2. pogoju (rjavih in modrih je enako število). Po 99 dneh nihče ne bi odšel, 100. dan pa bi vsi želeli oditi in posledično ne bi mogli vedeti svoje barve. Ker pa jim je guru namignil eno od barv, se lahko zgodi, da bodo vsi igrali samo na to barvo in v tem primeru bi res vsi modri odšli 100. dan, rjavi pa bi ostali.

Guru je K R U C I A L E N, ko reče da vidi modrookca.

Lahko napišeš s še večjimi črkami, dokler ne boš razložil, zakaj modri ne bi mogli sami, brez guruja, začeti svojega algoritma prepoznavanja svoje barve oči, in zakaj tega ne morejo storiti rjavi, je vse zaman. Izpadeš kot vernik, ki razlaga, da je bog krucialen, ker brez njega ni nič.

Sem na otoku. Vidim 99 modrih in 100 rjavih. Vem, da bom šel lahko dol samo, če ugotovim, kakšne barve oči imam. Guruja ni od nikoder. Kaj meni, in vsem drugim zbranim logikom na otoku brani, da bi se naloge ugotavljanja barve svojih oči lotili kar sami?

O.

100 krat je bilo povedano. Kdor ni razumel, ni razumel. Lahko sklepa na moč svoje logike iz tega.

Če od začetka vedo, da so plavi in rjavi, potem je to kakor da bi isto oznanil guru. Oboji lahko začnejo takoj štet.

Vendar ne vedo, da so samo od teh dveh barv. Tega vsi ne vedo do konca igre, ko tudi zadnja rasa zapusti otok.

Vendar zanimivo, tisti ki odhajajo, vedno vedo za vse barve. Tisti ki ostajajo - ne!

Hm, mogoče pa guru služi kot sinhronizacija - tako da se vsi modrooki takrat začnejo šteti dneve... Pa vendar - lahko bi začeli to s prvim dnem na otoku?

Nima to veze. Šteti začnejo takoj, ko izvedo, da gredo lahko dol, ko ugotovijo barvo svojih oči, ampak to informacijo so dobili drugje, ne od guruja.

100 krat je bilo povedano.

Čisto nič ni bilo povedano. Recimo, da guruja ni, vse drugo je pa enako. Katera informacija (ali karkoli pač, če ni informacija) manjka ljudem na otoku, da ne morejo uporabiti te logike oziroma algoritma? A se samo bedasto gledajo in vdajo v usodo? Zakaj ne morejo sami pogruntati, da če so 99. dne še vsi plavi gor, to očitno pomeni, da je plavih 100 in tisti, ki vidi 99 plavih in 100 rjavih ve, da je plav?

Predstavljaj si, da je na tem otoku 200 kloniranih (s pametjo vred) Thomasov, ki so jim pa naključno prebarvali oči, tako da nihče ne ve, kakšne barve jih ima. Vsi poznajo to uganko, pravila so enaka. Guruja pa od nikoder. Zakaj ne začnejo šteti dni in gledati, kdo odhaja?

Vendar ne vedo, da so samo od teh dveh barv.

Saj tudi ko guru omeni eno barvo, ne vedo, da so samo od teh dveh barv.

O.

Naloga je brez indukcije nerešljiva. Torej guru služi za to, da prebivalci otoka rešijo problem za N=2 in ga posplošijo za poljubno število. Kot sem že povedal: reši nalogo za N=1 oz. N=2 brez guruja, če misliš, da ni potreben.

Res Okapi WTF, napiši indukcijo za brez guruja ali pa bodi tiho. Matr narediš temo polno nepotrebnega spama, ko vztajaš pri nečem pa ti je zelo konkretno razloženo, zakaj ni tako.

In naloge je sicer težka za pogruntat, ampak po mojem mnenju dokaj lahka za razumet, ko enkrat ti en pove rešitev.

Guru pride lahko reč magari tudi samo "I am a Berliner!" pa bo stvar delala- posortirala bo barve v "enem prehodu" za vse barve- osamljeni reveži/srečniki pa ostanejo na otoku.

Ne bo.

No, v originalni nalogi ne. V tvoji modifikaciji pa že mogoče.

Se pravi, govoriš za svojo modifikacijo naloge?

Guru je potem odveč. Naloga je druga. Enostavnejša in (bistveno) manj zanimiva. Svojo barvo oči najdeš tako, da prešteješ vse po barvah in primerjaš z danimi številkami. Kjer je razlika, take barvo oči imaš.

Simple.

Ne, to ni res.

as far as she knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and she could have red eyes.