Меню

Решение задачи про выключатели

Заключенные и переключатель

Задача

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:

«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».

После этого заключенным разрешили собраться и обсудить стратегию действий, а потом развели обратно по камерам.

Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?

Подсказка

Казалось бы, как заключенный, которого привели в комнату, может воспользоваться тем, что видит переключатель в положении ON? И если он переключит его на OFF — как следующему заключенному воспользоваться этим?

Тем не менее стратегия, гарантированно приводящая узников к спасению, существует. Например, узники могут разбить дни на декады (10-дневные промежутки) и договориться, что дожидаются такого вот события: первого из них заведут в комнату в первый день декады, второго — во второй день и т. д., десятого — в последний день. Поскольку вероятность такого события отлична от нуля, то рано или поздно оно произойдет! Догадайтесь, как они могут действовать, чтобы 10-й смог понять,что такое событие в данной декаде на самом деле произошло.

Решение

1. Самый простой, но и самый долгий вариант — действовать так, как было сказано в подсказке. Чтобы просигнализировать последнему, каждый из заключенных, которого завели в комнату НЕ В СВОЙ день, должен поставить переключатель в положение ON. Если же 10-й заключенный действительно оказался в комнате на 10-й день декады и видит переключатель в положении OFF, он немедленно говорит начальнику тюрьмы, что в комнате побывали все заключенные. Если в 10-й день в комнате оказался кто-то другой или же 10-й видит переключатель в положении ON, то всё начинается заново.

Это решение, несмотря на всю свою простоту, плохо в главном — бедным узникам придется слишком долго ждать. Действительно, из всех возможных 10 10 вариантов посещения ими комнаты в течение декады их устраивает только один — таким образом, вероятность p их выхода на волю в течение одной декады равна 1/10 10 . Сравнительно несложными вычислениями можно доказать, что среднее время, которое потребуется им на освобождение, равно 1/p = 10 10 декад, или 10 11 дней, или более 270 миллионов лет. В общем, столько люди не живут.

2. Однако это же решение подсказывает, как они могут ускорить свой выход на свободу. Для этого они должны дожидаться следующего события: в течение декады каждый из 10 человек побывал в комнате ровно один раз. Как такое событие «сигнализируется»? Да почти так же: если кого-нибудь заводят второй раз в одной декаде, он ставит переключатель на ON. Таким образом, если на 10-й день декады узник, которого туда отвели, оказался там впервые (за декаду) и видит переключатель в положении OFF, он сообщает начальнику тюрьмы, что всех можно освобождать.

Этот способ работает уже существенно быстрее, потому что количество благоприятных исходов теперь не 1, а 10! = 3628800. Это означает, что вероятность p’ выхода на свободу за первую же декаду не так уж и мала — она равна 0,00036288. Следовательно, ожидаемое число декад до выхода равно 1/p’ ≈ 2755, то есть освободятся они примерно через 75 лет. Так что кто-нибудь, может быть, и доживет до освобождения, хотя особо надеяться на это не стоит.

Читайте также:  Выключатель конечный ls31p41b11 abb 1sbv010141r1211

Неужели всё так печально?

3. К счастью, у заключенных существует принципиально другой способ действий.

Например,они могут договориться о том, что тот, кого заведут в комнату в первую ночь, выставляет переключатель на OFF и становится СЧЕТЧИКОМ. Остальные заключенные остаются ОБЫЧНЫМИ. Каждый обычный заключенный должен передать счетчику ровно один сигнал о своем попадании в комнату с переключателем. Это делается так: попав туда, обычный заключенный смотрит на положение переключателя. Если оно OFF, то заключенный ставит его на ON и считает сигнал переданным. Если же выключатель уже находится в положении ON, то заключенный ничего не делает — иначе говоря, ждет следующего подходящего случая.

Счетчик, попадая в камеру и видя переключатель в положении ON, понимает, что ему передали сигнал (запоминает это), а чтобы сделать возможной передачу следующего сигнала — ставит переключатель в OFF. Если же он видит переключатель в 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-ночей повторяется сначала.

Как же происходит отдача и прием сигналов в пирамидальной схеме?

А вот как: если во время k-ночи заключенный пришел в комнату и видит переключатель в положении ON, то он принимает k-сигнал и ставит переключатель в OFF. Если к этому моменту у него уже был один k-сигнал, то теперь у него есть два таких сигнала, или один 2k-сигнал (который он попытается либо отдать, либо снова удвоить в период 2k-ночей). Если же он пришел в комнату со своим k-сигналом и видит OFF, то он ставит ON и считает k-сигнал отданным.

Читайте также:  Микрофоны проводные с выключателем

Вот, в целом, и всё. Остальное уже является занудными техническими подробностями (какова должна быть продолжительность ночей определенного типа для того, чтобы передача всех нужных сигналов состоялась с достаточной вероятностью, и при этом не было слишком большой задержки перед наступлением следующего типа ночей).

Эта задача имеет самое прямое отношение к теории информации — она демонстрирует, что даже самый узкий (всего 1 бит — ON/OFF) канал позволяет передать достаточно много информации.

Кто именно является автором «тюремной» формулировки, мне неизвестно, но именно эта забавная формулировка буквально покорила мир. Кроме того, несмотря на относительную молодость задачи, она уже успела обрасти кучей самых неожиданных вариаций и усложнений. Например:

Два переключателя. В комнате, куда приводят заключенных, не один, а целых два переключателя (следовательно, выйти на свободу можно быстрее. Вопрос: насколько?)

Две комнаты. Заключенных водят не в одну, а в две разных комнаты, выбирая их также случайным образом. В каждой комнате — свой переключатель.

Разделение передатчика и приемника. Каждую полночь начальник тюрьмы ставит переключатель в положение OFF. В час ночи он приводит туда первого заключенного, потом уводит, а в два часа ночи приводит туда же второго. Таким образом, первый из них должен «сработать» передатчиком информации, а второй — приемником.

Злобный начальник. Начальник тюрьмы знает стратегию узников и каждый день выбирает для посещения комнаты такого заключенного, чтобы максимально затруднить узникам их задачу.

Источник



Задача про хитрого электрика

Одна­жды в сек­рет­ном каби­не­те что-то слу­чи­лось с про­вод­кой, и охра­на вызва­ла элек­три­ка, что­бы он всё почи­нил. Ему ска­за­ли, что три выклю­ча­те­ля нахо­дят­ся сна­ру­жи, а три лам­поч­ки — внут­ри. Послед­ние сей­час не горят. Каж­дый выклю­ча­тель отве­ча­ет толь­ко за свою лам­поч­ку, но точ­ной схе­мы не зна­ет никто.

Элек­три­ку раз­ре­ши­ли как угод­но щёл­кать выклю­ча­те­ля­ми сна­ру­жи, но внутрь зай­ти раз­ре­ши­ли толь­ко один раз. Внут­ри с лам­поч­ка­ми тоже мож­но было делать что угод­но, но по сооб­ра­же­ни­ям сек­рет­но­сти воз­вра­щать­ся к выклю­ча­те­лям уже нель­зя. Элек­трик ухмыль­нул­ся, пощёл­кал выключателями,зашёл в ком­на­ту и сра­зу ска­зал, какой выклю­ча­тель отве­ча­ет за каж­дую лам­поч­ку. Как он это сделал?

Если решать зада­чу в лоб, то сра­зу напра­ши­ва­ет­ся такое реше­ние: вклю­чить одну лам­пу и выклю­чить дру­гую. В ито­ге, когда мы зай­дём в ком­на­ту, одна будет гореть, а дру­гая — нет, и мы пой­мём, какой выклю­ча­тель за что отвечает.

Но что делать с тре­тьей лам­пой? Если мы вклю­чим и её, то как отли­чим от такой же пер­вой? А если выклю­чим, то как отли­чим от нера­бо­та­ю­щей вто­рой? Нуж­но научить­ся раз­ли­чать две оди­на­ко­вые рабо­та­ю­щие или нера­бо­та­ю­щие лампы.

Самый про­стой спо­соб это сде­лать — раз­де­лить сами лам­пы допол­ни­тель­но на тёп­лые и холод­ные. Лам­па ста­но­вит­ся тёп­лой, когда пора­бо­та­ет, и даже если её выклю­чить, она всё рав­но какое-то вре­мя оста­нет­ся тёплой.

По усло­вию мы зна­ем, что все три лам­пы выклю­че­ны. Но вдруг они недав­но вклю­ча­лись и ещё не успе­ли остыть? Зна­чит, пер­вое, что мы дела­ем — ждём неко­то­рое вре­мя, что­бы все лам­пы сно­ва ста­ли холодными.

Теперь щёл­ка­ем любым выклю­ча­те­лем и нагре­ва­ем одну лам­пу. После того, как она пора­бо­та­ла доста­точ­но вре­ме­ни, что­бы нагреть­ся, мы её выклю­ча­ем. Полу­ча­ет­ся, что у нас все три лам­пы выклю­че­ны, но две из них холод­ные, а одна — тёплая.

Затем, что­бы раз­ли­чить две холод­ные лам­пы, щёл­ка­ем любым дру­гим выклю­ча­те­лем и захо­дим в ком­на­ту. В ито­ге мы увидим:

Читайте также:  Таблички 220 для выключателей

Источник

Задача про три лампочки

Это старая добрая задача, которую дают на различных собеседованиях в качестве разогрева. Она достаточно простая, но требует внимания, а также неплохого логического мышления.

Представим что вы стоите перед закрытой комнатой, в которой есть три лампочки и все они на данный момент выключены. Кроме того, перед вами есть три выключателя, которые отвечают за какую-либо из лампочек. Вы можете включать и выключать лампочки сколько угодно раз, а вот зайти в комнату вы можете всего один раз. Также вы не знаете какой выключатель к какой лампочке относиться.

Зайдя в комнату вы можете делать с лампочками все что угодно, вот только назад к выключателям вы уже вернуться не сможете. Теперь сам вопрос. Вам надо сказать какой выключатель относиться к какой-либо из лампочек. К примеру, второй выключатель работает с 3 лампочкой и так далее.

Решение

На самом деле здесь все очень просто. Если у нас нету никаких дополнительных возможностей, то мы можем поступить следующим образом. Включаем одну из лампочек и оставляем её гореть постоянно. Второй переключатель вообще не трогаем, а вот третий переключатель мы включаем, ждем несколько минут и потом выключаем его обратно. Теперь, когда мы зайдем в комнату мы обнаружим одну светящуюся лампочку, одну погасшую лампочку и при этом холодную на ощупь и одну также погасшую, но на ощупь теплую/горячую лампочку. На основе этого мы сможем понять какой выключатель относиться к той или иной лампочке.

Также, возможно ответить и по-другому. К примеру, если у нас есть возможность пользоваться дополнительными вещами, то мы можем подать больший ток на какой-либо переключатель. Теперь зайдя в комнату одна лампочка будет перегоревшей, одна включенной и одна выключенной. Опять-таки, определить какой выключатель к какой лампочке относиться не составит никакого труда.

Источник

Логические задачи и головоломки

Есть 2 комнаты. В одной висит обычная лампочка. Дверь туда закрыта. В другой комнате — 3 выключателя. Из них только один соединён с лампочкой. Можно сколько угодно вкл/выкл их. Потом нужно зайти в комнату с лампочкой, сколько угодно и что угодно там делать. А затем сказать, какой выключатель включает лампочку. Решение должно быть честным, т.е. из-за двери ничего не видно и не слышно, зайти в комнату можно только один раз, выключатели неразборные, не искрят, нельзя использовать какие-либо приборы, помощников, экстрасенсорные способности и пр.

Ответ: Решение основано на том, что включенная лампочка нагревается. Нужно включить первый из выключателей, подождать немного и выключить. Затем включить второй и идти в комнату. Если лампочка горит, то тут всё ясно -второй выключатель. Если не горит, то нужно потрогать лампочку. Если она горячая, то — первый выключатель, иначе — третий.

Комментарии

Оставлен Гость Ср, 05/26/2010 — 20:11

отредактируйте немного задачу, уточните что зайти можно только один раз

Оставлен admin Чт, 05/27/2010 — 04:09

Оставлен Гость Пнд, 01/17/2011 — 17:48

тестер-отвертка решит все быстрее без лишней бегатни в комнату и обратно. если у тебя нет тестера иди в Задачи со словами. Электричество и выключатели — не твоё

Оставлен Max Втр, 05/10/2011 — 10:43

а открыть дверь и пощелкать выключателями еще проще — остальные выключатели тоже идут к каким нибудь лампочкам, так что тестер отвертка тебе не поможет.
более грамотно резистор в один выключатель встроить:)

Оставлен Гость Чт, 11/17/2011 — 07:41

Эту задачу мне рассказал брат примерно год назад- я решил её через 1,5дня))))

Оставлен Ygrek Ср, 09/25/2013 — 00:33

1,5 выключателями щёлкал? Или ждал пока лампочка нагреется?

Источник