Пријава     Регистрација    

српски serbian srpski english ufl

cosak

Математичке загонетке

Задатак 1
 

У затвору се налази 100 затвореника. Стражар је одлучио да игра следећу игру. Стражар ставља капу на главу сваком од затвореника. Свака капа садржи један од бројева из скупа \( \{1,2,\dots, 100\} \). Различити затвореници могу а не морају да имају различите броеве на својим капама. Сваки затвореник види све капе осим своје.

Сваки од затвореника на парче папира мора да запише број са своје капе. Ако макар један од њих погоди исправно број своје капе, сви затвореници бивају ослобођени. Међутим, ако сви промаше бројеве, затвореници бивају кажњени.

Пре почетка игре, сви затвореници могу да разговарају и праве стратегију. Међутим, стражар слуша разговор и уколико стратегија има несавршености, он то има право да искористи при избору и распореду капа.

Доказати да постоји стратегија која омогућава затвореницима да победе.

Задатак 2
 

У затвору се налази 100 затвореника. Стражар одводи затворенике једног по једног у собу која поседује само један прекидач. Прекидач има две позиције (горе и доле). Док се налази у соби, сваки затвореник има право да промени позицију прекидача или да изговори реченицу "Сви затвореници су били у овој соби." Оног тренутка када неко изговори ову реченицу, игра се завршава. Уколико је реченица тачна, сви су слободни. Уколико је нетачна, сви бивају кажњени.

Стражар има уређену тајну листу по којој затворенике води у собу са прекидачем. Сваки затвореник се налази бесконачно много пута на тој листи. Међутим, стражар има слободу да распореди затворенике на овој листи како год он то жели. На пример, он може да води затвореника \( X \) милион пута, па тек онда да води остале. На тај начин стражар може да збуни затвореника \( X \) и наведе га на помисао да су сви већ били у соби.

Пре почетка игре, затвореници имају право да разговарају и направе стратегију. Стражар је присутан током овог разговора и уколико стратегија има несавршености, стражар има право да то искористи на штету затвореника. Оног тренутка када игра почне, затвореници не виде једни друге и једина комуникација коју имају је преко прекидача.

Доказати да сви затвореници могу бити спашени под једним од следећа два услова.

  • (а) Почетна позиција прекидача је позната.

  • (б) Почетна позиција прекидача није позната.

Задатак 3
 

У затвору се налази 10 затвореника. Стражар има 1000 флаша сока од грожђа: 999 флаша су праве, међутим једна флаша уместо сока садржи вино. Претпоставимо следеће:

  • (i) Нико није у стању да препозна вино по боји, укусу, мирису, или маси;

  • (ii) Ко попије макар и кап вина увече, ујутру се буде у стању тешког пијанства.

Доказати да користећи ових десет затвореника, стражар може да открије која флаша садржи вино после само једне ноћи.

Задатак 4
 

У затвору се налази 100 затвореника. Стражар је одлучио да игра следећу игру: Он је поређао затворенике у ред једног за другим и поставио капу на главу сваком од њих. Свака капа може бити црвена или зелена. Сваки затвореник види капе на главама затвореника испред себе, али не види своју капу нити капе на главама оних који су иза њега. На тај начин, први затвореник не види ниједну капу, други види капу само првог затвореника, и тако даље. Последњи види све капе осим своје.

Пошто су поређани у врсту и пошто су им додељене капе, сваки од затвореника има право да каже само једну реч: црвено или зелено. Сваки затвореник који погоди боју своје капе бива награђен. Сваки који промаши, бива кажњен.

Ноћ пре ове игре, сви затвореници имају право да разговарају и одреде стратегију која би број награђених затвореника учинила што је могуће већим. Наравно, стражар прислушкује овај разговор и покушава да пронађе сваку несавршеност у стратегији како би то искористио на штету затвореника.

  • (а) Доказати да постоји стратегија која гарантује да \( 99 \) затвореника бива награђено.

  • (б) Решити аналоган проблем у коме капе могу бити црвене, зелене, или плаве.

  • (в) Решити аналоган проблем у коме капе могу бити црвене или зелене, али је број затвореника бесконачан. Они су поређани у реду и означени бројевима \( 1 \), \( 2 \), \( 3 \), \( \dots \). Затвореник \( 1 \) види све капе осим своје; затвореник \( 2 \) види све осим своје и капе на глави затвореника \( 1 \), итд. У овом случају потребно је доказати да постоји стратегија која омогућава да сви затвореници осим једног остваре победу.

Задатак 5
 

Нека је \( n> 3 \) цео број. У игри учествује \( n \) играча који могу да обављају разговоре у паровима. Циљ игре је да сваки од играча изабере број из скупа \( \{1,2,\dots, n\} \) тако да следећи услови буду задовољени:

  • (и) Сваки од бројева \( 1,2,\dots, n \) је додељен тачно једном играчу.

  • (ии) За свака два различита играча \( A \) и \( B \), \( A \) зна само свој број и на основу тог броја не може да погоди број играча \( B \) са вероватноћом већом од \( \frac1{n-1} \).

Играчи смеју да воде разговоре само у паровима. Када два играча разговарају, остали не чују садржај њиховог разговора, али су свесвни да се тај разговор одржава.

Доказати да постоји позитиван цео број \( D \) (који зависи само од \( n \)) тако да играчи могу да заврше игру у највише \( D \) разговора.

Дозвољено је претопставити да сваки од играча има савршену меморију, и да сваки од играча има савршен генератор случајних бројева.

cosak
cosak cosak