16 replies to this topic

[SyntaT]

Есть такая загадка. В интернетах есть, не подглядывать тока =)

есть тюрьма. в тюрьме 100 одиночных камер. в камерах 100 заключённых. Как-то раз охранник собирает всех заключённых в общем зале и предлагает им игру. Он даёт им 15 минут посовещаться, после чего разведёт всех заключённых по своим камерам. Потом будет водить всех зеков по одному в карцер, где есть только лампочка и выключатель. Лампочку видно только из этого карцера, стены антивандальные. Лампочку охранник трогать не будет, в самом начале она выключена. Водить будет не по порядку (на свой рандом), и этот рандомопорядок будет знать только он. После того, как он привёл заключённого в камеру, он даёт ему там посидеть с минутку, после чего выводит и спрашивает, побывали ли там все заключённые хотя бы по 1 разу? Если ответ нет/не знаю - всё продолжается, если ответ да (неверный) - всех поджарят, если ответ да (верный) - всех отпустят на свободу.
Как зекам спастись? Со 100% уверенностью.

С час себе голову ломал, потом с подсказки догадался.
Есть так же более усложнённый вариант этой задачки, но его после того, как разгадаете эту. (на сложный вариант сам ответа не знаю =)

[Beowulf]

Если задача не быть зажаренным - то просто всегда отвечать нет )

Spoiler

UPD: А если просто всем выбраться - то тогда назначают кого-то одного чтобы он выключил свет. Когда свет выключится второй раз - то все прошли по одному разу

[TyKaH]

я решил:

Spoiler

Зэки выбирают одного пахана, который принимает на себя всю работу. Лампочку выключает только он. Включают лампочку только в том случае, если она не горит и раньше этот заключённый её не включал. Пахан, выключив лампочку 100 раз, будет знать, что все побывали, и на следующий свой вывод об этом объявит.

[SyntaT]

Beowulf, поподробней распиши, может я тебя не понял.. Порядка, как в камеру водят заключённых нет. Это абсолютный рандом. Могут хоть первый день первых 10 водить, перемешивая. В начале лампочка выключена.

TyKaH правильно ответил, хотя и чуть наоборот, но это не имеет значения

ОТВЕТ

Spoiler

выбранный Вася лампочку мог включать. ну считать ему надо до 99, ибо он сам 100й =)

Заключённые выбирают 1го счётчика. Будем звать его Вася.
Только Вася имеет право включить лампочку.
Любой другой заключённый имеет право выключить лампочку только 1 раз.
Если простой зек попадает туда снова, а лампочка снова горит, он ничего не трогает.
Если лампочка не горит, простой зек тем более ничего не трогает.
В камеру попадает Вася. Вася включает свет и считает, что (1) - сам себя.
Когда Вася попадает туда в следующий раз, и лампочку кто-то выключил, он считает (2) и зажегает лампочку заново.
Если Вася попадает туда и лампочка горит, значит его просто привели туда 2 раза подрят и он ничего не делает.
Все заключённые кроме Васи отвечают не знаю/нет.. Только Вася, когда досчитает до 99 выключенных лампочек (100 включений, но просто уходя уже можно и не включать, к чему жечь свет зря), отвечает да.

Теперь усложнённая задачка про зэков-эльфов..

1-го сентября 100 бессмертных эльфийских магаданских зэков (далее — эльфов) постоили на торжественную линейку и предложили им ускорить процесс своего освобождения.

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

На столе стоит настольная лампа. Каждый день эльф с охранником заходят в комнату, эльф садится, включает лампу, рисует, либо читает книгу, либо думает, либо делает что-либо еще (неважно). Далее по протоколу эльф обязан выключить лампу (должен, но иногда этого может не делать) и уйти с охраной. Охранник иногда проверяет и, если эльф не выключил лампу, он делает это за него (потому что был както в магаданской тюрьме инцидент). Охранник неаккуратный, ленивый, но иногда лампу он выключает (пусть и редко). Также иногда в тюрьме бывают перебои с электричеством, и в этот день никого в комнату не водят. В таких случаях лампочку переводят в положение «выключено». Эльфов выбирают абсолютно случайно. Каждый день водят не более одного.

У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?». Если он ответит «не знаю» («нет»), то игра продолжается. Если он ответит «да», и это неправда — высшая мера наказания для всех. Если каждый из сотни эльфов сказал «да», и это всегда была правда, всех всех выпускают на волю в тундру.

Примечание. Если эльф сказал «да», и это правда, его, как остальных, продолжают водить в эту камеру на общих правах.

Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.

Задача вроде как тоже имеет решение, правда его я уже не знаю.. тоже щас голову ломаю..

[TyKaH]

прочёл. начал думать.
(но не забываем, что мы всё-таки в большинстве своём люди подневольные, офисные... ещё и работу делать должны)

UPD
первое, что пришло в голову:

Spoiler

в задаче сказано, что эльфы бессмертны, значит высшую меру им могут делать ноднократно Значит достаточно всем всегда говорить да — рано или поздно сводят туда всех, и «да» станет правдой

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

думаю дальше...

[Yra^l]

Spoiler

1)Каждый эльф придя в комнату один раз не выключает свет.
2)Придя в комнату где свет уже горит он выключает его.
3)Выключив свет 100 раз(99 если запретить выключения за собой)он говорит что все посетили комнату.
4)Если он уже сказал охраннику да, он больше не выключает свет
5)Каждые 300 дней эльфы могут заново один раз не выключить свет. И сбрасывают количество выключений света.

Так как они бессмертны, то когда-нить все скажут да и будут свободны.

[IVAnt]

Spoiler

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

[SyntaT]

а мне представляется так..

Spoiler

Эльфы должны пронумероваться от 1го до ста, и пронумеровать вперёд дни от 1го до ста (с повторением). Уходя эльф имеет право оставлять лампу зажжёной только в свой день, т.е. когда его номер соответствует его дню.. Допустим 5й эльф в 5й, 105й, 205й итд дни.. Приходящий на следующий день эльф будет знать, что 5й эльф тут уже бывал (ну и завести там себе где-нить таблицу в своей книжке, что читает..). Так постепенно у всех эта таблица и заполнится.

Протом порылся в интернетах, раз уж нашёл хоть какой-то алгоритм, и нашёл на хабре практически такой же, тока с ахуенной поправкой, которая сэкономит бедным эльфам пару сотен тысяч лет))
Если Приходящий на следующий день эльф увидит горящую лампу (допустим в 31й день), он будет знать, что 30й эльф тут бывал. И если он окажется в следующий раз в комнате в 130й день, то он может зажечь лампу и за 30го эльфа, ибо он всё равно уже знает, что 30й эльф там бывал.. Так эта система станет прогрессивной и алгоритм ускорится в разы..

[IVAnt]

ну и как они узнают, что все уже тут побывали?
чем не устраивает мой вариант? слишком просто?)

[SyntaT]

чем не устраивает мой вариант? слишком просто?)

лампочка деревянная, прибита к полу, не выкручивается =)
Стол, как уже упоминалось, вообще будут менять периодически, Как при твоём варианте как раз остальные узнают? Вандализм - не вариант. Надсмотрщик стоит в комнате. Горящую лампочку попробуй выкрути =)

Не, никто не говорил, что он негодный, твой варинт можно дополнить

Spoiler

циклом на подобии варианта Yra^l, что мол раз в 1000 дней счетоводом будет становиться следующий эльф..

Тогда он тоже будет полностью тру.. только оооочень долгий
У этой задачи множество решений.. Мне тут по скайпу ещё 2 высказали варианта, в одном из них лампочка так и вообще как прогресс-бар используется))

ну и как они узнают, что все уже тут побывали?

Spoiler

в моём варианте просто - они же все считают.. В начале сойдётся у одного, потом постепенно ещё у одного, потом и у всех.. То, что ответившие правильно продолжают ходить и могут и дальше сигналить лампой задачей разрешается

[underwoodoff]

Spoiler

А что им мешает просто 1-ого сентября спросить все ли были в камере? И никакой математики

[SyntaT]

будем считать, что оно только 1 раз было.. =) остальные не в счёт, иначе не интересно, хотя да, условием непонятно оговорено..

[TyKaH]

SyntaT, могу дополнить твой вариант:

Spoiler

когда какой-то эльф наконец узнает, что уже все побывали (по твоему алгоритму), то он начнёт зажигать лампу на первый день после отключения электричества. Таким образом из алгоритма выедается один день, то есть календарь придётся сдвигать каждый раз, когда было отключение электричества, но зато мы сообщаем факт намного более важный (Всем говорить "ДА"!), чем факт того, что какой-то эльф, чей номер совпал с днём, побывал тут. (ещё не раз совпадёт у него, им тут долго отдыхать)

UPD ыть =)

[Resistor]

TyKaH, спрятать текст забыл =)

[GUNman]

как я понял из условий второй задачи, заключенные об отключениях электричества не могут узнать из своих камер (как и о действиях охранника - забыл ли он отключить лампочку или она и была выключена), то есть мерить время отключениями нельзя. Отключение это просто вероятностный фактор, как и охранник - то есть зайдя в комнату и увидев, что в ней горит свет, эльф может сделать только следующие выводы:
1)кто-то из заключенных вчера оставил свет
2)охранник забыл его выключить
3)отключения света вчера не было, кто-то из заключенных побывал в комнате.
Заключенные в задаче эльфы (бессмертные), а не люди, то есть время на решение неограничено.
Да, совещание разумеется было всего 1 раз. Придумал решение исходя из этих условий:

Spoiler

во время совещания каждому эьфу должен быть присвоен номер. Далее они должны очень точно считать дни. В дни с 1 по 100 включать лампу имеет право только эльф №1. Он делает это каждый раз если его вызывают в комнату, а свет там не горит. Остальные эльфы оставляют свет включенным если он горит и не трогают его если он выключен. Видя включенный свет, все эльфы делают вывод, что эльф №1 с вероятностью 100% побывал в камере. Далее, в дни с 101 по 200 начинается время второго эльфа. Остальные соответственно если видят включенный свет, делают вывод, что эльф №2 100% побывал в камере. Аналогично в дни с 201 по 300 наступает время доложить о себе эльфу №3. Важная поправка: в дни 101, 201, 301 и т.д. если в камеру вызвали НЕ эльфа, у которого начинается "его время", и в камере горит свет, вошедшему необходимо его выключить! Разумеется в течение каждых 100 дней только несколько эльфов в лучшем случае увидят, что их товарищ с соответствующим номером побывал в камере (действия охранника и возможные отключения света, да и не факт, что эльфа хоть раз вызовут в камеру за "его" период) поэтому в дни с 10001 по 10100 снова начинает заявлять о себе включенным светом эльф №1, с 10101 по 10200 - эльф №2 и так далее, "цикл" продолжается. Таким образом каждый эльф будет постепенно накапливать информацию о том, кто из эльфов точно побывал в камере. Когда-нибудь кто-то из них наконец выяснит, что 100% все эльфы там побывали, он отвечает "да", но продолжает делать все то же самое (то есть когда наступает "его" время, он продолжает включать лампу если оказывается в камере и выключать если видит ее включенной. Таким образом, настанет день, когда последний эльф наконец скажет, что да - все 100 побывали в камере хоть 1 раз с вероятностью 100%.

UPD: поправил свое решение, для сильного сокращения суммарного времени, необходимого для получения свободы

[Gosha]

лампочка деревянная, прибита к полу, не выкручивается =)
Стол, как уже упоминалось, вообще будут менять периодически, Как при твоём варианте как раз остальные узнают? Вандализм - не вариант. Надсмотрщик стоит в комнате. Горящую лампочку попробуй выкрути =)

..............

Лампочки... горящие... перегорать имеют свойство. О - как!
Причём, совершенно неожиданно.

Народ, а где в условиях задачки - что страдальцам языки отрезанны?
.
Вполне могут свой номер посещения выкрикивать.

[SyntaT]

Народ, а где в условиях задачки - что страдальцам языки отрезанны?

они сидят в звуко-водо-свето-непроницаемых одиночках же, услышит его только охранник и анально накажет, эльф этого не хочет

Лампочки... горящие... перегорать имеют свойство. О - как!
Причём, совершенно неожиданно.

эльфийские деревянные лампочки не перегорают, но даже если под воздействием чёрной магии это случится, то эльф сможет пожаловаться на это тюремщику, и лампу заменят =)