Log In     Register    

српски serbian srpski     english ufl

cosak

Matematichke zagonetke

Zadatak 1
 

U zatvoru se nalazi 100 zatvorenika. Strazhar je odluchio da igra sledec1u igru. Strazhar stavlja kapu na glavu svakom od zatvorenika. Svaka kapa sadrzhi jedan od brojeva iz skupa \( \{1,2,\dots, 100\} \). Razlichiti zatvorenici mogu a ne moraju da imaju razlichite broeve na svojim kapama. Svaki zatvorenik vidi sve kape osim svoje.

Svaki od zatvorenika na parche papira mora da zapishe broj sa svoje kape. Ako makar jedan od njih pogodi ispravno broj svoje kape, svi zatvorenici bivaju oslobodjeni. Medjutim, ako svi promashe brojeve, zatvorenici bivaju kazhnjeni.

Pre pochetka igre, svi zatvorenici mogu da razgovaraju i prave strategiju. Medjutim, strazhar slusha razgovor i ukoliko strategija ima nesavrshenosti, on to ima pravo da iskoristi pri izboru i rasporedu kapa.

Dokazati da postoji strategija koja omoguc1ava zatvorenicima da pobede.

Zadatak 2
 

U zatvoru se nalazi 100 zatvorenika. Strazhar odvodi zatvorenike jednog po jednog u sobu koja poseduje samo jedan prekidach. Prekidach ima dve pozicije (gore i dole). Dok se nalazi u sobi, svaki zatvorenik ima pravo da promeni poziciju prekidacha ili da izgovori rechenicu "Svi zatvorenici su bili u ovoj sobi." Onog trenutka kada neko izgovori ovu rechenicu, igra se zavrshava. Ukoliko je rechenica tachna, svi su slobodni. Ukoliko je netachna, svi bivaju kazhnjeni.

Strazhar ima uredjenu tajnu listu po kojoj zatvorenike vodi u sobu sa prekidachem. Svaki zatvorenik se nalazi beskonachno mnogo puta na toj listi. Medjutim, strazhar ima slobodu da rasporedi zatvorenike na ovoj listi kako god on to zheli. Na primer, on mozhe da vodi zatvorenika \( X \) milion puta, pa tek onda da vodi ostale. Na taj nachin strazhar mozhe da zbuni zatvorenika \( X \) i navede ga na pomisao da su svi vec1 bili u sobi.

Pre pochetka igre, zatvorenici imaju pravo da razgovaraju i naprave strategiju. Strazhar je prisutan tokom ovog razgovora i ukoliko strategija ima nesavrshenosti, strazhar ima pravo da to iskoristi na shtetu zatvorenika. Onog trenutka kada igra pochne, zatvorenici ne vide jedni druge i jedina komunikacija koju imaju je preko prekidacha.

Dokazati da svi zatvorenici mogu biti spasheni pod jednim od sledec1a dva uslova.

  • (a) Pochetna pozicija prekidacha je poznata.

  • (b) Pochetna pozicija prekidacha nije poznata.

Zadatak 3
 

U zatvoru se nalazi 10 zatvorenika. Strazhar ima 1000 flasha soka od grozhdja: 999 flasha su prave, medjutim jedna flasha umesto soka sadrzhi vino. Pretpostavimo sledec1e:

  • {w (i)} Niko nije u stanju da prepozna vino po boji, ukusu, mirisu, ili masi;

  • {w (ii)} Ko popije makar i kap vina uveche, ujutru se bude u stanju teshkog pijanstva.

Dokazati da koristec1i ovih deset zatvorenika, strazhar mozhe da otkrije koja flasha sadrzhi vino posle samo jedne noc1i.

Zadatak 4
 

U zatvoru se nalazi 100 zatvorenika. Strazhar je odluchio da igra sledec1u igru: On je poredjao zatvorenike u red jednog za drugim i postavio kapu na glavu svakom od njih. Svaka kapa mozhe biti crvena ili zelena. Svaki zatvorenik vidi kape na glavama zatvorenika ispred sebe, ali ne vidi svoju kapu niti kape na glavama onih koji su iza njega. Na taj nachin, prvi zatvorenik ne vidi nijednu kapu, drugi vidi kapu samo prvog zatvorenika, i tako dalje. Poslednji vidi sve kape osim svoje.

Poshto su poredjani u vrstu i poshto su im dodeljene kape, svaki od zatvorenika ima pravo da kazhe samo jednu rech: crveno ili zeleno. Svaki zatvorenik koji pogodi boju svoje kape biva nagradjen. Svaki koji promashi, biva kazhnjen.

Noc1 pre ove igre, svi zatvorenici imaju pravo da razgovaraju i odrede strategiju koja bi broj nagradjenih zatvorenika uchinila shto je moguc1e vec1im. Naravno, strazhar prislushkuje ovaj razgovor i pokushava da pronadje svaku nesavrshenost u strategiji kako bi to iskoristio na shtetu zatvorenika.

  • (a) Dokazati da postoji strategija koja garantuje da \( 99 \) zatvorenika biva nagradjeno.

  • (b) Reshiti analogan problem u kome kape mogu biti crvene, zelene, ili plave.

  • (v) Reshiti analogan problem u kome kape mogu biti crvene ili zelene, ali je broj zatvorenika beskonachan. Oni su poredjani u redu i oznacheni brojevima \( 1 \), \( 2 \), \( 3 \), \( \dots \). Zatvorenik \( 1 \) vidi sve kape osim svoje; zatvorenik \( 2 \) vidi sve osim svoje i kape na glavi zatvorenika \( 1 \), itd. U ovom sluchaju potrebno je dokazati da postoji strategija koja omoguc1ava da svi zatvorenici osim jednog ostvare pobedu.

Zadatak 5
 

Neka je \( n> 3 \) ceo broj. U igri uchestvuje \( n \) igracha koji mogu da obavljaju razgovore u parovima. Cilj igre je da svaki od igracha izabere broj iz skupa \( \{1,2,\dots, n\} \) tako da sledec1i uslovi budu zadovoljeni:

  • (i) Svaki od brojeva \( 1,2,\dots, n \) je dodeljen tachno jednom igrachu.

  • (ii) Za svaka dva razlichita igracha \( A \) i \( B \), \( A \) zna samo svoj broj i na osnovu tog broja ne mozhe da pogodi broj igracha \( B \) sa verovatnoc1om vec1om od \( \frac1{n-1} \).

Igrachi smeju da vode razgovore samo u parovima. Kada dva igracha razgovaraju, ostali ne chuju sadrzhaj njihovog razgovora, ali su svesvni da se taj razgovor odrzhava.

Dokazati da postoji pozitivan ceo broj \( D \) (koji zavisi samo od \( n \)) tako da igrachi mogu da zavrshe igru u najvishe \( D \) razgovora.

Dozvoljeno je pretopstaviti da svaki od igracha ima savrshenu memoriju, i da svaki od igracha ima savrshen generator sluchajnih brojeva.

cosak
cosak cosak