Prijava     Registracija    

српски serbian srpski english ufl

cosak

Matematičke zagonetke

Zadatak 1
 

U zatvoru se nalazi 100 zatvorenika. Stražar je odlučio da igra sledeću igru. Stražar stavlja kapu na glavu svakom od zatvorenika. Svaka kapa sadrži jedan od brojeva iz skupa \( \{1,2,\dots, 100\} \). Različiti zatvorenici mogu a ne moraju da imaju različite broeve na svojim kapama. Svaki zatvorenik vidi sve kape osim svoje.

Svaki od zatvorenika na parče papira mora da zapiše broj sa svoje kape. Ako makar jedan od njih pogodi ispravno broj svoje kape, svi zatvorenici bivaju oslobođeni. Međutim, ako svi promaše brojeve, zatvorenici bivaju kažnjeni.

Pre početka igre, svi zatvorenici mogu da razgovaraju i prave strategiju. Međutim, stražar sluša razgovor i ukoliko strategija ima nesavršenosti, on to ima pravo da iskoristi pri izboru i rasporedu kapa.

Dokazati da postoji strategija koja omogućava zatvorenicima da pobede.

Zadatak 2
 

U zatvoru se nalazi 100 zatvorenika. Stražar odvodi zatvorenike jednog po jednog u sobu koja poseduje samo jedan prekidač. Prekidač ima dve pozicije (gore i dole). Dok se nalazi u sobi, svaki zatvorenik ima pravo da promeni poziciju prekidača ili da izgovori rečenicu "Svi zatvorenici su bili u ovoj sobi." Onog trenutka kada neko izgovori ovu rečenicu, igra se završava. Ukoliko je rečenica tačna, svi su slobodni. Ukoliko je netačna, svi bivaju kažnjeni.

Stražar ima uređenu tajnu listu po kojoj zatvorenike vodi u sobu sa prekidačem. Svaki zatvorenik se nalazi beskonačno mnogo puta na toj listi. Međutim, stražar ima slobodu da rasporedi zatvorenike na ovoj listi kako god on to želi. Na primer, on može da vodi zatvorenika \( X \) milion puta, pa tek onda da vodi ostale. Na taj način stražar može da zbuni zatvorenika \( X \) i navede ga na pomisao da su svi već bili u sobi.

Pre početka igre, zatvorenici imaju pravo da razgovaraju i naprave strategiju. Stražar je prisutan tokom ovog razgovora i ukoliko strategija ima nesavršenosti, stražar ima pravo da to iskoristi na štetu zatvorenika. Onog trenutka kada igra počne, zatvorenici ne vide jedni druge i jedina komunikacija koju imaju je preko prekidača.

Dokazati da svi zatvorenici mogu biti spašeni pod jednim od sledeća dva uslova.

  • (a) Početna pozicija prekidača je poznata.

  • (b) Početna pozicija prekidača nije poznata.

Zadatak 3
 

U zatvoru se nalazi 10 zatvorenika. Stražar ima 1000 flaša soka od grožđa: 999 flaša su prave, međutim jedna flaša umesto soka sadrži vino. Pretpostavimo sledeće:

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

  • (ii) Ko popije makar i kap vina uveče, ujutru se bude u stanju teškog pijanstva.

Dokazati da koristeći ovih deset zatvorenika, stražar može da otkrije koja flaša sadrži vino posle samo jedne noći.

Zadatak 4
 

U zatvoru se nalazi 100 zatvorenika. Stražar je odlučio da igra sledeću igru: On je poređao zatvorenike u red jednog za drugim i postavio kapu na glavu svakom od njih. Svaka kapa može 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 način, prvi zatvorenik ne vidi nijednu kapu, drugi vidi kapu samo prvog zatvorenika, i tako dalje. Poslednji vidi sve kape osim svoje.

Pošto su poređani u vrstu i pošto su im dodeljene kape, svaki od zatvorenika ima pravo da kaže samo jednu reč: crveno ili zeleno. Svaki zatvorenik koji pogodi boju svoje kape biva nagrađen. Svaki koji promaši, biva kažnjen.

Noć pre ove igre, svi zatvorenici imaju pravo da razgovaraju i odrede strategiju koja bi broj nagrađenih zatvorenika učinila što je moguće većim. Naravno, stražar prisluškuje ovaj razgovor i pokušava da pronađe svaku nesavršenost u strategiji kako bi to iskoristio na štetu zatvorenika.

  • (a) Dokazati da postoji strategija koja garantuje da \( 99 \) zatvorenika biva nagrađeno.

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

  • (v) Rešiti analogan problem u kome kape mogu biti crvene ili zelene, ali je broj zatvorenika beskonačan. Oni su poređani u redu i označeni 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 slučaju potrebno je dokazati da postoji strategija koja omogućava da svi zatvorenici osim jednog ostvare pobedu.

Zadatak 5
 

Neka je \( n> 3 \) ceo broj. U igri učestvuje \( n \) igrača koji mogu da obavljaju razgovore u parovima. Cilj igre je da svaki od igrača izabere broj iz skupa \( \{1,2,\dots, n\} \) tako da sledeći uslovi budu zadovoljeni:

  • (i) Svaki od brojeva \( 1,2,\dots, n \) je dodeljen tačno jednom igraču.

  • (ii) Za svaka dva različita igrača \( A \) i \( B \), \( A \) zna samo svoj broj i na osnovu tog broja ne može da pogodi broj igrača \( B \) sa verovatnoćom većom od \( \frac1{n-1} \).

Igrači smeju da vode razgovore samo u parovima. Kada dva igrača razgovaraju, ostali ne čuju sadržaj njihovog razgovora, ali su svesvni da se taj razgovor održava.

Dokazati da postoji pozitivan ceo broj \( D \) (koji zavisi samo od \( n \)) tako da igrači mogu da završe igru u najviše \( D \) razgovora.

Dozvoljeno je pretopstaviti da svaki od igrača ima savršenu memoriju, i da svaki od igrača ima savršen generator slučajnih brojeva.

cosak
cosak cosak