Загатка за 4 затвореници. Затвореници и прекинувач. Загатката на затворениците

Во затворот има 10 затвореници, секој во самица. Тие не можат да комуницираат едни со други. Еден убав ден, шефот на затворот им соопштил дека им дава шанса на сите да бидат ослободени под следниве услови:

« Во подрумот на затворот има просторија со прекинувач која има две состојби: ON и OFF („вклучено“ и „исклучено“). Секоја вечер ќе носам точно по еден затвореник во оваа соба (избирајќи ја сосема случајно) и ќе ја однесам по некое време. Додека е во собата, секој од вас може или да ја смени положбата на прекинувачот или да не прави ништо со него. Затворскиот персонал нема да го допре овој прекинувач. Во одреден момент, еден од вас (било кој) мора да сфати дека сите затвореници биле во собата и да го пријави. Ако се покаже дека е во право, сите ќе бидат ослободени, ако не е во право, сите ќе останете во затвор засекогаш. Ветувам дека сите затвореници ќе бидат во собата и сите ќе бидат донесени таму неограничен број пати.».

После тоа, на затворениците им било дозволено да се соберат и да разговараат за стратегијата на дејствување, а потоа биле вратени во ќелиите.

Дали можатЗатворениците гарантирано ќе одат на слобода, и ако е така, тогаш какотие да го постигнат тоа?

Поим

Се чини, како затвореникот што е внесен во просторијата може да го искористи фактот што го гледа прекинувачот во положбата ВКЛУЧЕНО? И ако го вклучи во OFF - како следниот затвореник ќе го искористи ова?

Сепак, постои стратегија која гарантирано ќе ги води затворениците кон спасение. На пример, затворениците можат да ги поделат деновите во децении (интервали од 10 дена) и да се согласат дека чекаат таков настан: првиот од нив ќе биде однесен во просторијата на првиот ден од деценијата, вториот на вториот ден. , итн., десеттиот на последниот ден . Бидејќи веројатноста за таков настан е различна од нула, порано или подоцна тоа ќе се случи! Погодете како можат да постапат за да може 10-ти да разбере дека таков настан всушност се случил во оваа деценија.

Решение

1. Најлесната, но и најдолгата опција е да постапите како што е кажано во промптот. За да го сигнализира второто, секој од затворениците што бил донесен во просторијата НЕ НА НИВЕН ден мора да го сврти прекинувачот во положбата ВКЛУЧЕНО. Ако 10-тиот затвореник навистина бил во просторијата на 10-тиот ден од деценијата и го види прекинувачот во положбата OFF, веднаш му кажува на шефот на затворот дека сите затвореници биле во собата. Ако на 10-тиот ден некој друг е во собата, или на 10-тиот го види прекинувачот во позиција ON, тогаш сè започнува повторно ...

Ова решение, и покрај неговата едноставност, главно е лошо - кутрите затвореници ќе мора да чекаат премногу долго. Навистина, од сите можни 10 10 опции за да ја посетат собата во текот на деценијата, само една им одговара - така, веројатноста стрнивното пуштање во дивината во рок од една деценија е еднакво на 1/10 10 . Со релативно едноставни пресметки, можеме да докажеме дека просечното време потребно за нивно ослободување е 1/ стр= 10 10 децении, или 10 11 дена, или повеќе од 270 милиони години. Во принцип, толку многу луѓе не живеат.

2. Сепак, истата одлука сугерира како тие да го забрзаат нивното ослободување. За да го направат ова, тие мора да го чекаат следниот настан: во текот на деценијата, секој од 10 луѓе ја посетил просторијата точно еднаш. Како се „сигнализира“ таков настан? Да, речиси исто: ако некој се вклучи по втор пат во една деценија, тој го вклучува прекинувачот. Така, ако на 10-тиот ден од деценијата затвореник што бил однесен таму за прв пат (по една деценија) бил таму и го види прекинувачот во позиција OFF, тој го известува раководителот на затворот дека секој може да биде ослободен.

Овој метод веќе работи многу побрзо, бидејќи бројот на поволни исходи сега не е 1, туку 10! = 3628800. Тоа значи дека веројатноста стр"ослободувањето за првата деценија не е толку мало - тоа е еднакво на 0,00036288. Според тоа, очекуваниот број на децении пред излезот е 1/ стр"≈ 2755, односно ќе бидат објавени за околу 75 години. Така, некој, можеби, ќе доживее да види ослободување, иако не треба особено да се надеваме на ова.

Дали сето тоа е толку тажно?

3. За среќа, затворениците имаат фундаментално поинаков начин на вршење на работите.

На пример, тие би можеле да се согласат дека оној што ќе биде донесен во собата првата вечер, ќе го исклучува прекинувачот и ќе стане бројач. Останатите затвореници остануваат РЕДОВНИ. Секој обичен затвореник мора да даде точно еден сигнал на шалтерот за неговото влегување во просторијата со прекинувачот. Ова е направено вака: еднаш таму, обичен затвореник гледа во положбата на прекинувачот. Ако е ИСКЛУЧЕНО, тогаш затвореникот го поставува на ON и смета дека сигналот е поминат. Ако прекинувачот е веќе во позиција ON, тогаш затвореникот не прави ништо - со други зборови, тој ја чека следната соодветна прилика.

Бројачот, влегувајќи во камерата и гледајќи го прекинувачот во положбата ВКЛУЧЕНО, разбира дека му бил пренесен сигнал (се сеќава на ова), и за да може да се пренесе следниот сигнал, го поставува прекинувачот на OFF. Ако го види прекинувачот во ИСКЛУЧЕН, тогаш тој не прави ништо и исто така го чека следниот пат.

Штом шалтерот го добие 9-тиот сигнал, тој веднаш го известува тоа кај шефот на затворот.

До кога ќе им трае затворот со ваква стратегија? Пресметувањето на ова веќе не е лесно како порано, бидејќи веројатноста дека затвореникот следниот ден ќе може да пренесе сигнал постепено се намалува од 9/10 за првиот сигнал до 1/10 за последниот сигнал. Во исто време, веројатноста за удирање во собата на шалтер во секое време е 1/10. Сепак, механизмот за броење е генерално сличен: во просек ќе поминат 10/9 дена до моментот на пренос на првиот сигнал, а ќе поминат уште 10 дена до моментот кога ќе го прими бројачот. Тогаш вториот сигнал ќе потрае 10/8 + 10 дена, третиот - 10/7 + 10, и така натаму. Вкупно денови - не толку многу како во претходните решенија.

Послеговор

Зарем нема уште побрза стратегија на дејствување?

За 10 затвореници можеби не, но за поголем број да. Авторот на оваа стратегија Б. Фелгенауер ја нарече „пирамидална“.

За полесно да се разбере, да претпоставиме дека бројот на затвореници е моќност од два, на пример 64. Како и во претходното решение, секој мора или да даде сигнал (точно еден) или да ги собере сите сигнали. За да им биде поудобно да го прават тоа, сите ноќи се поделени на делови со различни „трошоци“: прво има „1 ноќи“, при што секој испраќа или прима поединечни сигнали, а потоа има „2 ноќевања“. “, при што сите даваат или добиваат „двојни“ сигнали, односно секој сигнал известува по двајца затвореници, па доаѓаат „4-ноќи“, „8-ноќ“ итн. Ако се оди добро, тогаш кога е во прашање „32 ноќи“ точно двајца затвореници остануваат носители на сигнали, а во рок од 32 ноќи едниот го дава својот сигнал на другиот, по што сфаќа дека собрал збирка од сите 64 сигнали, што значи дека сите биле во собата.

Се разбира, таков „успех“ можеби нема да се случи, па по 32 ноќи целиот циклус од 1-, 2-, 4-, 8-, 16-, 32-ноќевања се повторува од почеток.

Како е преносот и примањето на сигналите во пирамидалната шема?

И еве како: ако за време на к-Ноќта затвореникот влезе во собата и го гледа прекинувачот во положбата ВКЛУЧЕНО, а потоа прифаќа к-сигнализира и го поставува прекинувачот на OFF. Ако до овој момент тој веќе имал еден к-сигнал, сега има два такви сигнали, или еден 2 к-сигнал (кој ќе се обиде или да го даде или пак да го удвои во периодот 2 к- ноќи). Ако влезе во собата со своите к-сигнализира и гледа ИСКЛУЧЕНО, па се вклучува и брои к- даден сигнал.

Тука, воопшто, и сите. Останатото се веќе здодевни технички детали (колку долго треба да трае одреден тип на ноќ за да се одвива преносот на сите потребни сигнали со доволна веројатност, а во исто време да нема преголемо доцнење пред следниот тип на ноќи).

Оваа задача е директно поврзана со теоријата на информации - покажува дека дури и најтесниот (само 1 бит - ВКЛУЧЕНО / ИСКЛУЧЕНО) канал ви овозможува да пренесувате многу информации.

Кој е точно авторот на формулацијата „затвор“, не знам, но токму оваа смешна формулација буквално го освои светот. Покрај тоа, и покрај релативната младост на проблемот, тој веќе се здоби со еден куп најнеочекувани варијации и компликации. На пример:

Два прекинувачи.Во просторијата каде што се носат затворениците, нема еден, туку два прекинувачи (оттука, можете да излезете побрзо. Прашањето е: за колку?)

Две соби.Затворениците се носат не во една, туку во две различни соби, исто така избрани по случаен избор. Секоја соба има свој прекинувач.

Одвојување на предавателот и приемникот. Секоја полноќ, управникот го врти прекинувачот во положбата OFF. Во еден часот по полноќ го носи првиот затвореник таму, потоа го носи, а во два часот по полноќ го носи вториот затвореник таму. Така, првиот од нив треба да „работи“ како предавател на информации, а вториот - како приемник.

Злобниот шеф. Шефот на затворот ја знае стратегијата на затворениците и секој ден избира таков затвореник да ја посети просторијата за да им ја отежне работата на затворениците што е можно повеќе.

Момци, ја вложуваме душата во страницата. Благодарам за тоа
за откривање на оваа убавина. Ви благодариме за инспирацијата и охрабрувањето.
Придружете ни се во Фејсбуки Во контакт со

Овие задачи може да се решат во движење, џвакајќи сендвич за време на ручек. И можеш да го скршиш целиот мозок, но никогаш да не сфатиш каде е вистината и што е финтата.

Ви нудиме со веб-страницаистегнете го гирусот и кликнете логички задачикако ореви.

1. Загатка за затворениците

4 затвореници се осудени на смрт.

Тие ставија две бели капи и две црни капи. Мажите не знаат каква боја носат капи. Четворицата затвореници беа наредени еден зад друг (види слика) на таков начин што:

Затвореникот бр. 1 може да ги види затворениците бр. 2 и бр. 3.

Затвореникот бр. 2 може да го види затвореникот бр. 3.

Затвореникот број 3 не гледа никого.

Затвореникот број 4 не гледа никого.

Судијата му ветил слобода на секој затвореник кој ќе ја именува бојата на неговата капа.

Прашање:Кој прв ја именуваше нивната боја на капа?

Четвртиот и третиот затвореник молчат, бидејќи воопшто не гледаат ништо.

Првиот затвореник молчи, бидејќи пред себе гледа капи со различни бои: 2-ри и 3-ти. Според тоа, тој има или бела или црна капа.

Вториот затвореник, сфаќајќи дека 1-виот молчи, заклучува дека неговата капа не е во иста боја со третиот, имено бела боја.

Заклучок:Затвореникот број 2 беше првиот што ја именуваше бојата на неговата капа.

2. Тешкотии на патот

Едно лице, менувајќи го тркалото на својот автомобил, ги испушти сите 4 навртки за прицврстување во канализационата решетка. Невозможно е да ги извлечете од таму. Возачот веќе решил дека долго време е заглавен на патот, но потоа едно дете кое минувало предложило како да го поправи тркалото. Возачот го послушал советот и мирно се упатил до најблиската продавница за гуми.

Прашање:Што советувало детето?

3. Излезноста не успеа

Човекот требаше да се инфилтрира во тајниот клуб без да предизвика сомнеж. Забележал дека сите што дошле прво одговарале на прашањата на чуварот и дури потоа влегле внатре. На првиот човек што пристигнал му било поставено прашањето: „22? Тој одговори: "11!" - и помина. На вториот: "28?" Одговорот беше: „14“. И тој исто така беше во право. Човекот одлучи дека сè е едноставно и смело му пријде на чуварот. "42?" праша стражарот. "21!" - самоуверено одговорил човекот и веднаш бил избркан.

Прашање:Зошто?

4. Подарок на Баба Јага

Летото веќе завршило кога Иван Царевич, кој се упатил кон далечното кралство по невеста, побарал да преноќи во колиба на пилешки нозе. Баба Јага љубезно го поздрави гостинот, му даде да пие, го нахрани и го легна. Следното утро, таа го испрати Иван Царевич со следните разделни зборови: „Ако на патот сретнете река, нема мост преку неа, ќе мора да пливате. Земете го овој магичен кафтан. Облечете го - и смело брзајте во реката, кафтанот нема да ве остави да се удавите. Иван Царевич пешачеше сто дена и ноќи и конечно стигна до реката. Но, за да го надмине, не му требаше кафтан.

Прашање:Зошто?

5. Кафези со зајаци

Во дворот имаше 3 големи кафези по ред, обоени во различни бои: црвена, жолта и зелена. Зајаците живееле во кафези, а имало двојно повеќе зајаци во зелено отколку во жолто. Еднаш од левиот кафез беа земени 5 зајаци за жив агол, а половина од останатите беа префрлени во црвениот кафез.

Прашање:Каква боја беше левата ќелија?

Кафезот беше жолт. Задачата сугерира дека имало двојно повеќе зајаци во зелениот кафез - затоа, има парен број од нив. Откако беа извадени пет од левата ќелија, во неа остана и парен број (бидејќи лесно се делеше на половина). Тоа значи дека пред фаќањето, бројот на зајаци бил непарен. Така, левата ќелија не е зелена. Но, не е ниту црвено, што се гледа од состојбата на проблемот.

6. Кој е виновен?

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

1. Загатка за затворениците

4 затвореници осудени на смрт
Тие ставија две бели капи и две црни капи. Мажите не знаат каква боја носат капи. Четворицата затвореници беа наредени еден зад друг (види слика) на таков начин што:
Затвореникот бр. 1 може да ги види затворениците бр. 2 и бр. 3.
Затвореникот бр. 2 може да го види затвореникот бр. 3.
Затвореникот број 3 не гледа никого.
Затвореникот број 4 не гледа никого.
Судијата му ветил слобода на секој затвореник кој ќе ја именува бојата на неговата капа.
Прашање:Кој прв ја именуваше нивната боја на капа?
2. Тешкотии на патот
Едно лице, менувајќи го тркалото на својот автомобил, ги испушти сите 4 навртки за прицврстување во канализационата решетка. Невозможно е да ги извлечете од таму. Возачот веќе решил дека долго време е заглавен на патот, но потоа едно дете кое минувало предложило како да го поправи тркалото. Возачот го послушал советот и мирно се упатил до најблиската продавница за гуми.
Прашање:Што советувало детето?

3. Излезноста не успеа
Човекот требаше да се инфилтрира во тајниот клуб без да предизвика сомнеж. Забележал дека сите што дошле прво одговарале на прашањата на чуварот и дури потоа влегле внатре. На првиот човек што пристигнал му било поставено прашањето: „22? Тој одговори: "11!" - и помина. На вториот: "28?" Одговорот беше: „14“. И тој исто така беше во право. Човекот одлучи дека сè е едноставно и смело му пријде на чуварот. "42?" праша стражарот. "21!" - самоуверено одговорил човекот и веднаш бил избркан.
Прашање:Зошто?

4. Подарок на Баба Јага
Летото веќе завршило кога Иван Царевич, кој се упатил кон далечното кралство по невеста, побарал да преноќи во колиба на пилешки нозе. Баба Јага љубезно го поздрави гостинот, му даде да пие, го нахрани и го легна. Следното утро, таа го испрати Иван Царевич со следните разделни зборови: „Ако на патот сретнете река, нема мост преку неа, ќе мора да пливате. Земете го овој магичен кафтан. Облечете го - и смело брзајте во реката, кафтанот нема да ве остави да се удавите. Иван Царевич пешачеше сто дена и ноќи и конечно стигна до реката. Но, за да го надмине, не му требаше кафтан.
Прашање:Зошто?
5. Кафези со зајаци
Во дворот имаше 3 големи кафези по ред, обоени во различни бои: црвена, жолта и зелена. Зајаците живееле во кафези, а имало двојно повеќе зајаци во зелено отколку во жолто. Еднаш од левиот кафез беа земени 5 зајаци за жив агол, а половина од останатите беа префрлени во црвениот кафез.
Прашање:Каква боја беше левата ќелија?
6. Кој е виновен?
Доцна вечерта во една од коловозните ленти непознат автомобил удрил во маж и исчезнал. Полицаецот забележал дека автомобилот се движи со голема брзина. 6 луѓе кои случајно се нашле во близина пријавиле спротивставени информации: „Автомобилот бил сино, возел човек“. голема брзинаи со исклучени фарови. „Автомобилот имаше регистарска табличка и не одеше многу брзо“. „Автомобилот“ Москвич „беше со исклучени светла“. „Автомобил без регистарска табличка, возеше жена.“ „Победа кола, сиво“.
Кога автомобилот бил приведен, се покажало дека само еден сведок ги дал точните информации. Останатите пет - еден точен и еден неточен факт.
имемарка, боја и брзина на автомобилот. Дали автомобилот имал регистарска табличка, дали имало светло и кој го управувал: маж или жена?
7. Бонус
Значи, што прават сите луѓе на Земјата во исто време?

Одговори:

Четвртиот и третиот затвореник молчат, бидејќи воопшто не гледаат ништо. Првиот затвореник молчи, бидејќи пред себе гледа капи со различни бои: 2-ри и 3-ти. Според тоа, тој има или бела или црна капа. Вториот затвореник, сфаќајќи дека 1-виот молчи, заклучува дека неговата капа не е во иста боја со третиот, имено бела. Заклучок:Затвореникот број 2 беше првиот што ја именуваше бојата на неговата капа.
Отстранете по 1 навртка од преостанатите 3 тркала и прицврстете ја 4-тата со нив.
На прв поглед, се чини дека лозинката е резултат на делење на именуваниот број со 2. Всушност, ова е бројот на буквите во предложените броеви. Точниот одговор не е 21, туку 8.
Иван Царевич ја посети Баба Јага во септември. Одбројуваме 100 дена и дознаваме дека зимата е веќе во полн ек. Реката е врзана за мраз и можете безбедно да ја поминете дури и без кафтан.
Кафезот беше жолт. Задачата сугерира дека имало двојно повеќе зајаци во зелениот кафез - затоа, има парен број од нив. Откако беа извадени пет од левата ќелија, во неа остана и парен број (бидејќи лесно се делеше на половина). Тоа значи дека пред фаќањето, бројот на зајаци бил непарен. Така, левата ќелија не е зелена. Но, не е ниту црвено, што се гледа од состојбата на проблемот.
Беше „Виктори“, сино, со регистарска табличка. Возеше со голема брзина со исклучени фарови. Возеше жена. Се фокусираме на сведочењето на чуварот - големата брзина на автомобилот. Знаејќи дека доказите за мала брзина се очигледно лажни, ги одредуваме преостанатите опции.
Стареат.

Според Смекалка

1. Загатка за затворениците

4 затвореници се осудени на смрт.

Затвореникот бр. 1 може да ги види затворениците бр. 2 и бр. 3.

Затвореникот бр. 2 може да го види затвореникот бр. 3.

Затвореникот број 3 не гледа никого.

Затвореникот број 4 не гледа никого.

Судијата му ветил слобода на секој затвореник кој ќе ја именува бојата на неговата капа.

Прашање:Кој прв ја именуваше нивната боја на капа?

Четвртиот и третиот затвореник молчат, бидејќи воопшто не гледаат ништо.

Вториот затвореник, сфаќајќи дека 1-виот молчи, заклучува дека неговата капа не е во иста боја со третиот, имено бела.

Заклучок:Затвореникот број 2 беше првиот што ја именуваше бојата на неговата капа.

2. Тешкотии на патот

Прашање:Што советувало детето?

Отстранете по 1 навртка од преостанатите 3 тркала и прицврстете ја 4-тата со нив.

3. Излезноста не успеа

Прашање:Зошто?

На прв поглед, се чини дека лозинката е резултат на делење на именуваниот број со 2. Всушност, ова е бројот на буквите во предложените броеви. Точниот одговор не е 21, туку 8.

4. Подарок на Баба Јага

Прашање:Зошто?

Иван Царевич ја посети Баба Јага во септември. Одбројуваме 100 дена и дознаваме дека зимата е веќе во полн ек. Реката е врзана за мраз и можете безбедно да ја поминете дури и без кафтан.

5. Кафези со зајаци

Прашање:Каква боја беше левата ќелија?

6. Кој е виновен?

Доцна вечерта во една од коловозните ленти непознат автомобил удрил во маж и исчезнал. Полицаецот забележал дека автомобилот се движи со голема брзина. 6 луѓе кои се нашле во близина дале спротивставени информации:

„Автомобилот беше сино, човекот возеше“.
„Автомобилот се движеше со голема брзина и со исклучени фарови.
„Автомобилот имаше регистарска табличка и не одеше многу брзо“.
„Автомобилот“ Москвич „беше со исклучени светла“.
„Автомобил без регистарска табличка, возела жена“.
Автомобил „Победа“, сива боја.

Кога автомобилот бил приведен, се покажало дека само еден сведок ги дал точните информации. Останатите пет - еден точен и еден неточен факт.

имемарка, боја и брзина на автомобилот. Дали автомобилот имал регистарска табличка, дали имало светло и кој го управувал: маж или жена?

Беше „Виктори“, сино, со регистарска табличка. Возеше со голема брзина со исклучени фарови. Возеше жена. Се фокусираме на сведочењето на чуварот - големата брзина на автомобилот. Знаејќи дека доказите за мала брзина се очигледно лажни, ги одредуваме преостанатите опции.

7. Бонус

Значи, што прават сите луѓе на Земјата во исто време?

Стареат.