4 затворници с различни шапки. Интересни логически задачи
В затвора има 10 лишени от свобода, всеки в единична килия. Те не могат да общуват помежду си. Един прекрасен ден началникът на затвора им съобщи, че дава шанс на всеки да бъде освободен при следните условия:
« В сутерена на затвора има стая с превключвател, който има две състояния: ON и OFF („включено“ и „изключено“). Всяка вечер ще въвеждам точно един затворник в тази стая (избирайки го напълно произволно) и след известно време ще го отвеждам. Докато сте в стаята, всеки от вас може или да промени позицията на превключвателя, или да не прави нищо с него. Персоналът на затвора няма да докосва този ключ. В един момент един от вас (всеки) трябва да разбере, че всички затворници са били в стаята и да докладва за това. Ако се окаже прав, всички ще бъдат освободени, ако греши, всички ще останете в затвора завинаги. Обещавам, че всички затворници ще посещават стаята и всеки ще бъде довеждан там неограничен брой пъти».
След това на затворниците беше позволено да се съберат и да обсъдят стратегията си за действие, след което бяха върнати обратно в килиите си.
Могат лизатворниците гарантирано ще бъдат освободени и ако е така, тогава какмогат ли да постигнат това?
Улика
Изглежда, как може затворник, който е въведен в стая, да се възползва от факта, че вижда превключвателя в положение ВКЛЮЧЕНО? И ако го превключи на OFF - как следващият затворник може да се възползва от това?
Въпреки това съществува стратегия, която гарантирано ще доведе затворниците до спасение. Например, затворниците могат да разделят дните на десетилетия (10-дневни интервали) и да се споразумеят, че ще изчакат такова събитие: първият от тях ще бъде отведен в стаята на първия ден от десетилетието, вторият на втория ден и т.н., десетият на последния ден . Тъй като вероятността от такова събитие е ненулева, рано или късно то ще се случи! Познайте как могат да действат, така че 10-ият да разбере, че такова събитие наистина се е случило в дадено десетилетие.
Решение
1. Най-простият, но и най-дългият вариант е да действате, както е посочено в подсказката. За да сигнализира за последното, всеки затворник, който е бил въведен в стая НЕ В ТЕХНИЯ ден, трябва да завърти ключа на позиция ВКЛ. Ако 10-ият затворник действително е в стаята на 10-ия ден от десетилетието и види превключвателя в положение ИЗКЛЮЧЕНО, той незабавно казва на надзирателя, че всички затворници са били в стаята. Ако на 10-ия ден някой друг е в стаята или на 10-ия ден види превключвателя в позиция ON, тогава всичко започва отначало...
Това решение, въпреки цялата си простота, е лошо в основното нещо - бедните затворници ще трябва да чакат твърде дълго. Наистина, от всичките възможни 10 10 варианта за тях да посещават стая в продължение на десетилетие, само един ги устройва - следователно вероятността стросвобождаването им в природата в рамките на едно десетилетие е равно на 1/10 10. С относително прости изчисления може да се докаже, че средното време, необходимо за тяхното освобождаване, е 1/ стр= 10 10 десетилетия, или 10 11 дни, или повече от 270 милиона години. По принцип хората не живеят толкова дълго.
2. Въпреки това, същото решение подсказва как те могат да ускорят освобождаването им. За да направят това, те трябва да изчакат следното събитие: през десетилетието всеки от 10-те души е посетил стаята точно веднъж. Как се „сигнализира“ такова събитие? Да, почти същото: ако някой е запален за втори път през същото десетилетие, той превключва превключвателя на ON. По този начин, ако на 10-ия ден от десетилетието затворник, който е бил отведен там, е там за първи път (от десетилетие) и види превключвателя в положение OFF, той информира надзирателя, че всички могат да бъдат освободени.
Този метод работи много по-бързо, тъй като броят на благоприятните резултати вече не е 1, а 10! = 3628800. Това означава, че вероятността п"освобождаването през първите десет дни не е толкова малко - то е равно на 0,00036288. Следователно очакваният брой десетилетия преди излизане е 1/ п"≈ 2755, тоест ще бъдат пуснати след около 75 години. Така че някой може би ще доживее да види освобождение, въпреки че не трябва да се надявате на това.
Наистина ли е толкова тъжно?
3. За щастие, затворниците имат коренно различен начин да правят нещата.
Например, те могат да се съгласят, че който и да е въведен в стаята през първата вечер, обръща превключвателя на ИЗКЛЮЧЕНО и става БРОЯЧ. Останалите затворници остават РЕДОВНИ. Всеки редовен затворник трябва да подаде точно един сигнал на гишето, когато влезе в стаята с превключвателя. Това се прави по следния начин: веднъж там, обикновен затворник гледа позицията на превключвателя. Ако е ИЗКЛЮЧЕНО, тогава затворникът го настройва на ВКЛЮЧЕНО и счита, че сигналът е преминал. Ако превключвателят вече е в позиция ON, тогава затворникът не прави нищо - с други думи, чака следващата подходяща възможност.
Броячът, влизайки в камерата и виждайки превключвателя в положение ON, разбира, че към него е предаден сигнал (помни това) и за да направи възможно предаването на следващия сигнал, той поставя превключвателя на OFF. Ако види превключвателя в положение OFF, значи не прави нищо и също чака следващия път.
Веднага щом броячът получи 9-ия сигнал, той незабавно докладва това на началника.
Докога ще им трае затвора с подобна стратегия? Изчисляването на това вече не е толкова лесно, колкото беше преди, защото вероятността затворникът да успее да предаде сигнала на следващия ден постепенно намалява от 9/10 за първия сигнал до 1/10 за последния сигнал. В същото време вероятността да уцелите Counter room по всяко време е 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-нощи се повтаря отначало.
Как е предаването и приемането на сигнали в пирамидалната схема?
Ето как: ако по време на к-през нощта затворникът влиза в стаята и вижда превключвателя в положение ВКЛ., след което приема к-сигнал и поставя превключвателя на ИЗКЛ. Ако до този момент вече е имал такъв к-сигнал, сега има два такива сигнала или един 2 к-сигнал (който той ще се опита да даде или да удвои отново в период 2 к-нощувки). Ако той влезе в стаята със своите к-сигнализира и вижда OFF, след което слага ON и брои к- подаден сигнал.
Това, общо взето, е всичко. Останалото са скучни технически подробности (колко дълги трябва да бъдат нощите от определен тип, така че всички необходими сигнали да се предават с достатъчна вероятност и да няма твърде голямо забавяне преди началото на следващия тип нощ).
Тази задача има най-много пряка връзкакъм теорията на информацията - демонстрира, че дори и най-тесният (само 1 бит - ON/OFF) канал ви позволява да предавате доста информация.
Не знам кой точно е авторът на формулировката „затвор“, но именно тази забавна формулировка буквално завладя света. Освен това, въпреки относителната младост на проблема, той вече е придобил куп неочаквани вариации и усложнения. Например:
Два превключвателя.В стаята, в която се въвеждат затворниците, има не един, а два превключвателя (следователно можете да излезете по-бързо. Въпрос: колко?)
Две стаи.Затворниците се водят не в една, а в две различни стаи, също избрани на случаен принцип. Всяка стая има собствен ключ.
Разделяне на предавател и приемник. Всяка полунощ надзирателят обръща превключвателя на позиция ИЗКЛ. В един през нощта той довежда там първия затворник, след което го отвежда, а в два през нощта води втория затворник. Така първият от тях трябва да "работи" като предавател на информация, а вторият - като приемник.
Ядосан шеф. Началникът на затвора познава стратегията на затворниците и всеки ден избира такъв затворник, който да посещава стаята, за да затрудни максимално затворниците да си вършат работата.
Тези проблеми могат да бъдат решени в движение, дъвчейки сандвич обедна почивка. А може и да си счупиш целия мозък, но пак да не разбереш къде е истината и каква е уловката.
1. Гатанката за затворниците
4 затворници са осъдени на смърт.
Слагат две бели и две черни шапки. Мъжете не знаят какъв цвят шапка носят. Четирима затворници бяха подредени един след друг (вижте снимката) по такъв начин, че:
Затворник №1 може да види затворници №2 и №3.
Затворник №2 може да види Затворник №3.
Затворник №3 не вижда никого.
Затворник №4 не вижда никого.
Съдията обеща свобода на всеки затворник, който назове цвета на шапката си.
Въпрос:Кой пръв посочи цвета на шапката си?
Четвъртият и третият затворник мълчат, защото не виждат абсолютно нищо.
Първият затворник мълчи, защото вижда пред себе си шапки с различни цветове: 2-ри и 3-ти. Съответно той има или бяла, или черна шапка.
2-рият затворник, разбирайки, че 1-вият мълчи, заключава, че шапката му не е от същия цвят като 3-тия, а именно бяло.
Заключение:Затворник номер 2 пръв назова цвета на шапката си.
2. Трудности по пътя
Един човек, сменяйки колелото на колата си, изпусна всичките 4 закрепващи гайки в решетката на канализацията. Невъзможно е да ги вземете оттам. Шофьорът вече бил решил, че е закъсал дълго време на пътя, но тогава минаващо дете подсказало как да оправят колелото. Шофьорът последвал съвета и спокойно потеглил към най-близкия магазин за гуми.
Въпрос:Какво посъветва детето?
Развийте 1 гайка от останалите 3 колела и закрепете 4-тото с тях.
3. Неуспешна избирателна активност
Човекът трябваше да проникне в тайния клуб, без да събуди подозрение. Той забеляза, че всеки, който идваше първи, отговаряше на въпросите на пазача и едва след това влизаше. Първият пристигнал човек беше попитан: "22?" Той отговори: "11!" - и премина. На втория: "28?" Отговорът беше: „14“. И той също беше прав. Човекът реши, че всичко е просто и смело се приближи до пазача. "42?" – попита пазачът. "21!" - отговори мъжът уверено и веднага беше изгонен.
Въпрос:Защо?
На пръв поглед изглежда, че паролата е резултат от разделянето на посоченото число на 2. Всъщност това е броят на буквите в предложените числа. Верният отговор не е 21, а 8.
4. Подаръкът на Баба Яга
Лятото вече беше приключило, когато Иван Царевич, който се отправяше към далечното царство за булката си, поиска нощувка в колиба на пилешки бутчета. Баба Яга любезно посрещна госта, даде му нещо да пие, нахрани го и го сложи да спи. На следващата сутрин тя изпрати Царевич Иван със следните думи на раздяла: „По пътя ще срещнете река, няма мост през нея - ще трябва да плувате. Вземете този магически кафтан. Облечи го и смело се хвърли в реката, кафтанът няма да те остави да се удавиш.” Иван Царевич вървял сто дни и нощи и накрая стигнал до реката. Но той не се нуждаеше от кафтан, за да го преодолее.
Въпрос:Защо?
Иван Царевич посети Баба Яга през септември. Отброяваме 100 дни и установяваме, че зимата вече е в разгара си. Реката е замръзнала и можете безопасно да я прекосите без кафтан.
5. Клетки със зайци
В двора имаше 3 големи клетки в редица, боядисани различни цветове: червено, жълто и зелено. Зайците живееха в клетки и в зелената клетка имаше два пъти повече от тях, отколкото в жълтата клетка. Един ден от лявата клетка бяха взети 5 заека за жилищен кът, а половината от останалите бяха прехвърлени в червената клетка.
Въпрос:Какъв цвят беше лява клетка?
Клетката беше жълта. Проблемът предполага, че в зелената клетка е имало два пъти повече зайци - следователно там има четен брой. След като бяха взети пет от лявата клетка, в нея остана четно число (тъй като лесно се раздели наполовина). Това означава, че преди улавянето броят на зайците е бил нечетен. Така лявата клетка не е зелена. Но не е и червено, както се вижда от условията на задачата.
6. Кой е виновен?
Късно вечерта в една от уличките неизвестен автомобил блъсна мъж и изчезна. Полицаят забелязал, че колата се движи с висока скорост. 6 души, които бяха наблизо, съобщиха противоречива информация:
- "Кола от син цвятШофираше мъж."
- „Колата се движеше с висока скорост и със загасени фарове.“
- „Колата имаше регистрационен номер и не се движеше много бързо.“
- „Автомобилът „Москвич“ се движеше на изгасени светлини.
- „Колата беше без регистрационна табела и беше шофирана от жена.
- „Колата Победа, сива.“
При задържането на колата се оказало, че само един свидетел е дал вярна информация. Останалите пет - по един верен и един неверен факт.
Имемарка, цвят и скорост на автомобила. Имаше ли колата номер, имаше ли светлини и мъж ли я караше или жена?
Беше лек автомобил "Победа", син, с табела. Тя вървеше с висока скорост и със загасени фарове. Шофираше жена. Фокусираме се върху показанията на пазача - висока скоросткола. Знаейки, че доказателствата за ниска скорост са очевидно неправилни, ние определяме останалите опции.
7. Бонус
И така, какво правят всички хора на Земята едновременно?
остаряват.
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-ти. Съответно той има или бяла, или черна шапка. Вторият затворник, разбирайки, че първият мълчи, заключава, че шапката му не е в същия цвят като тази на 3-тия, а именно бяла. Заключение:Затворник номер 2 пръв назова цвета на шапката си.
- Развийте 1 гайка от останалите 3 колела и закрепете 4-тото с тях.
- На пръв поглед изглежда, че паролата е резултат от разделянето на посоченото число на 2. Всъщност това е броят на буквите в предложените числа. Верният отговор не е 21, а 8.
- Иван Царевич посети Баба Яга през септември. Отброяваме 100 дни и установяваме, че зимата вече е в разгара си. Реката е замръзнала и можете безопасно да я прекосите без кафтан.
- Клетката беше жълта. Проблемът предполага, че в зелената клетка е имало два пъти повече зайци - следователно там има четен брой. След като бяха взети пет от лявата клетка, в нея остана четно число (тъй като лесно се раздели наполовина). Това означава, че преди улавянето броят на зайците е бил нечетен. Така лявата клетка не е зелена. Но не е и червено, както се вижда от условията на задачата.
- Беше лек автомобил "Победа", син, с табела. Тя вървеше с висока скорост и със загасени фарове. Шофирала жена. Фокусираме се върху показанията на пазача - висока скорост на автомобила. Знаейки, че доказателствата за ниска скорост са очевидно неправилни, ние определяме останалите опции.
- остаряват.
Според Смекалка
Момчета, влагаме душата си в сайта. Благодаря за това
че откривате тази красота. Благодаря за вдъхновението и настръхването.
Присъединете се към нас FacebookИ Във връзка с
Тези задачи могат да бъдат решени в движение, докато хапвате сандвич по време на обедната почивка. А може и да си счупиш целия мозък, но пак да не разбереш къде е истината и каква е уловката.
Предлагаме ви заедно с уебсайтразтегнете мозъците си и разбийте логически проблеми като ядки.
1. Гатанката за затворниците
4 затворници са осъдени на смърт.
Слагат две бели и две черни шапки. Мъжете не знаят какъв цвят шапка носят. Четирима затворници бяха подредени един след друг (вижте снимката) по такъв начин, че:
Затворник №1 може да види затворници №2 и №3.
Затворник №2 може да види Затворник №3.
Затворник №3 не вижда никого.
Затворник №4 не вижда никого.
Съдията обеща свобода на всеки затворник, който назове цвета на шапката си.
Въпрос:Кой пръв посочи цвета на шапката си?
Четвъртият и третият затворник мълчат, защото не виждат абсолютно нищо.
Първият затворник мълчи, защото вижда пред себе си шапки с различни цветове: 2-ри и 3-ти. Съответно той има или бяла, или черна шапка.
Вторият затворник, разбирайки, че първият мълчи, заключава, че шапката му не е в същия цвят като тази на 3-тия, а именно бяла.
Заключение:Затворник номер 2 пръв назова цвета на шапката си.
2. Трудности по пътя
Един човек, сменяйки колелото на колата си, изпусна всичките 4 закрепващи гайки в решетката на канализацията. Невъзможно е да ги вземете оттам. Шофьорът вече бил решил, че е закъсал дълго време на пътя, но тогава минаващо дете подсказало как да оправят колелото. Шофьорът последвал съвета и спокойно потеглил към най-близкия магазин за гуми.
Въпрос:Какво посъветва детето?
3. Неуспешна избирателна активност
Човекът трябваше да проникне в тайния клуб, без да събуди подозрение. Той забеляза, че всеки, който идваше първи, отговаряше на въпросите на пазача и едва след това влизаше. Първият пристигнал човек беше попитан: "22?" Той отговори: "11!" - и премина. На втория: "28?" Отговорът беше: „14“. И той също беше прав. Човекът реши, че всичко е просто и смело се приближи до пазача. "42?" – попита пазачът. "21!" - отговори мъжът уверено и веднага беше изгонен.
Въпрос:Защо?
4. Подаръкът на Баба Яга
Лятото вече беше приключило, когато Иван Царевич, който се отправяше към далечното царство за булката си, поиска нощувка в колиба на пилешки бутчета. Баба Яга любезно посрещна госта, даде му нещо да пие, нахрани го и го сложи да спи. На следващата сутрин тя изпрати Царевич Иван със следните думи на раздяла: „По пътя ще срещнете река, няма мост през нея - ще трябва да плувате. Вземете този магически кафтан. Облечи го и смело се хвърли в реката, кафтанът няма да те остави да се удавиш.” Иван Царевич вървял сто дни и нощи и накрая стигнал до реката. Но той не се нуждаеше от кафтан, за да го преодолее.
Въпрос:Защо?
5. Клетки със зайци
В двора имаше 3 големи клетки в редица, боядисани в различни цветове: червено, жълто и зелено. Зайците живееха в клетки и в зелената клетка имаше два пъти повече от тях, отколкото в жълтата клетка. Един ден от лявата клетка бяха взети 5 заека за жилищен кът, а половината от останалите бяха прехвърлени в червената клетка.
Въпрос:Какъв цвят беше лявата клетка?
Клетката беше жълта. Проблемът предполага, че в зелената клетка е имало два пъти повече зайци - следователно там има четен брой. След като бяха взети пет от лявата клетка, в нея остана четно число (тъй като лесно се раздели наполовина). Това означава, че преди улавянето броят на зайците е бил нечетен. Така лявата клетка не е зелена. Но не е и червено, както се вижда от условията на задачата.
6. Кой е виновен?
Късно вечерта в една от уличките неизвестен автомобил блъсна мъж и изчезна. Полицаят забелязал, че колата се движи с висока скорост. 6 души, които са били наблизо, са съобщили противоречива информация.