algoritem za tale problem?

En zanimiv problem, ki nam ga je postavu prfoks pri ars1 na fri.

V nekem samostanu z zelo strogo ureditvijo, so stanovali menihi. Vsak je imel svojo sobo v kateri se je posvečal svoji duhovnosti. Enkrat na dan so menihi prišli v skupen prostor na sredo samostana, kjer so obedovali. To je bil njihov edini enkrat dnevni stik.
Zaradi strogega režima, niso smeli duhovniki nikakor komunicirati (na čisto noben način, nobenih namigovanj, tajnih sporočil ipd.). Po obedu se menihi vrnejo nazaj v svoje prostore.
Nekega dne predstojnik samostana pri obedu pove, da se je v samostanu pojavila bolezen, ki jo prepoznaš po tem, da imaš sredi čela eno piko. Okuženih je več kot en in manj kot vseh menihov.
Okuženi morajo zapustiti samostan.
Klub ničelni komunikaciji so naslednji dan res vsi okuženi menihi zapustili samostan.
To pomeni, da jih zjutraj ni bilo več.
Pa v sobah niso imeli ogledal.

Samostan izgleda takole:


Naloga je sestaviti algoritem po katerem so ugotovili, da so okuženi in so odšli.
Prof. nam je namignil da matematična indukcija ni dovolj.

Že za tri je problem sila težak.

Kaj pa vi pravite?

Jst verjetno zvem rešitev ta četrtek.

rad bi imel algoritem za n
Ta algoritem deluje če imata dva piko, in veš da sta dva, kaj pa če ne veš da sta dva?
Če veš da ima piko samo eden je u izi.

No idea, morda pa so se slabo počutli, ker so bli bolani pa so šli joke, dej res rešitev tle napopej, ki me prou zanima.

1. Ni prfoks za ars1, ampak APS1.
2. Takole se pa resi ta problem:
Imas recimo 10 menihov. 4 okuzeni, 6 ne.
Kaj naredit, ce si eden od menihov? Pogledas koliko menihov(razen sebe) ima piko. Ce si okuzen vidis 3 pike, ce nisi vidis 4 pike. Ok? Vsak menih(ker so seveda intelektulci vsi to pogruntajo) rece: Po k dnevih bom zapustil samostan, kjer je k stevilo pik, ki jih je videl. Tisti, ki so videli 3 pike(okuzeni torej) bodo samostan zapustili dan pred neokuzenimi. In glej no glej, po 3 dnevih ostanejo samo se neokuzeni menihi. Ti seveda vedo, da to pomeni, da niso okuzeni.

Problem resen. Ups, zdaj vidim, odsli so ze naslednji dan. Moja resitev deluje, samo za vec dni. Si siguren, da je rekel, da ze naslednji dan okuzenih ni vec?

LP
kyon

kyon:

ampak tvoja resitev zahteva poprejsen dogovor menihov.

O.K., recimo da vzames kot casovno enoto vsak nalsednji shod ob vecerji. Ker pa toliko casa ni vec na razpolago, se je treba za vse ostale enote zmenit.

Poleg tega bi morala biti ta resitev edina mozna, da torej odpadejo dogovori okrog uporabljene resitve...

Brane - pojdi še enkrat skozi in skozi link, ki sem ga dal. Stvar je kristalno jasna. VEČ DNI rabijo.

Impresiven link, Thomas.

Ali po domače rečeno - I was right all along!

Tvoj prvi odgovor me ni čisto prepričal
Sicer pa link vse pove... nisem si mislil da je rešitev tako enostavna

Sem sel skozi link.

In opazil nekaj razlik. Prva je ta, da je tam podano, da je samostan "ociscen" po treh vecerjah, tu pa takoj naslednje jutro, druga pa ta, da je tam podano, da je bolan vsaj en duhovnik, tu pa vsaj dva.

Aja, poleg tega tu udelezencem ni dano posiljanje informacije skozi samomor.

Edina resitev, ki jo vidim, je da najdejo nek arbitracijski protokol, ki je obenem edini mozen, tako da se ni treba o njem posebej pogajati.

In tretjic, dogovorjen je nacin razmisljanja. Vsak duhovnik se torej mora vprasati prvi vecer, ali sploh vidi koga s piko itd.

Kaj pa, ce prvi vecer opazijo vsi, da imata dva/trije duhovniki piko ? Torej okuzeni duhovniki vidijo dve piki in ne morejo vedeti, ali imajo na svojem celu tretjo, neokuzeni pa vidijo 3 in razmislajo o cetrti.

Stvar dela samo, ce duhovnik zapre oci na vsaki vecerji do spanja, ko vidi novo piko...

Naloga OP je bila zastavljena precej drugace...

Thomas. Izbereš šest kuglic in jih oštevilčiš od 1 do 6. Izžrebaš eno in če ima številko 1, pošlješ. [In upaš, da so vsi storili enako.] ;)

O.K. Recimo da je pet duhovnikov z belo piko na celu in da se lahko hecajo vec dni.

Kako bi sla resitev ?

Za 1,2,3 mi je jasno. Kako gre, ce jih je pet ?

S tem, da je tudi to sleparjenje, ker vsak duhovnik s svojim (ne)odhodom poslje svoj bit informacije ostalim, a naj bo...

Zakaj velja to za vsak k ? Jasno mi je, zakaj velja za k=1,2,3. Za naprej pa ne...

McHusch, you are correct.

Ne ni "le kockanje". Tako si maksimiziraš verjetnost, da boš kaj dobil.

Zagotavlja ti je ne. Ampak če se odločiš za algoritem ki ima manjšo ali večjo vrednost od 1/6, si možnosti še zmanjšaš. Pa kaj grdo gledaš?

Grdo gledam ker ne maram da verjetnost odloča o tem ali bom dobil nagrado