Маркс и Энгельс

может им всегда молчать? никого тогда не расстреляют...

Ну никто не запрещает как я понимаю перемещать книги относительно друг друга.
К примеру сигналы каждого человека:
1. Маркс и Энгельс лежат рядом, почти касаясь друг друга.
2. Маркс лежит правее Энгельса, на дистанции к примеру больше чем ширина книги.
3. Маркс левее Энгельса ...
4. Маркс выше Энгельса ...
5. Маркс ниже Энгельса ...

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

Похожую задачку задавали в Яндексе на собеседовании :)


Назначить одного человека "исполнителем".
Далее следующий алгоритм: всем кроме исполнителя переворачивать Маркса на спину, если он уже не перевёрнут. Если перевёрнут - переворачивать Энгельса.
Исполнителю, если Маркс перевёрнут, перевернуть назад и прибавить к счётчику единицу. Если не перевёрнут, перевернуть Энгельса.
Если счётчик достиг величины (количество заключённых-1), т. е. в нашем случае 4, значит, в Ленинской комнате все были.

Это при условии, что в самом начале книжки лежат лицом вверх.

Эх..похоже придется вспомнить молодость, да полистать учебник по прикладной математике..

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

Имеет ли значение начальное положение книг? В условии не упоминается то, как они лежат изначально. Это надо понимать как то, что они обе лежат лицом вверх или как то что это не важно?

каждый из заключенных независимо от начального положения кладет книжки по-своему:
1-й - лицом, лицом
2-й - лицом, спиной
3-й - спиной, лицом
4-й - спиной, спиной
5-й запоминает, какие комбинации уже были, и когда все пройдут - может говорить

но это при условии, что водить их будут до бесконечности

Давайте нам уже ответ белым! :)

Может им до вечера кого-нить из 5 в расход пустить?
Или Хеппи Энд не минуем? =)

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

Я имею в виду, что каждая книжка получит по 4 состояния:
# - [лицо, переплёт]
1 - (вверх, вправо)
2 - (вверх, влево)
3 - (вниз, вправо)
4 - (вниз, влево)

Более того, состояния 1-3 и 2-4 взаимозаменяемые — те можно переходить из одного в другое. Также можно переходить из 1 в 4 и из 2 в 3.
Таким образом:
1ый вошедший — крутит Маркса в состояниях 1-3
2ой вошедший — крутит Маркста в состояниях 2-4
3ий вошедший — крутит Энгельса в состояниях 1'-3'
4ый вошедший — крутит Энгельса в состояниях 2'-4'
5ый вошедший — кричит ура и все идут пить пиво
?

тут ничего не сказано о расположении книг.. если это не важно, то
1) если каждый заключенный при посещении зала? он просто переворачивает книгу, с тыльной на лицевую, любую не важно какую
2) а суть подсчета заключается в том что 1 заключенный кладет крест-накрест книги сверху Энгельс снизу Ленин
2-й впервые посещающий видя такое условие кладет книги 1 на другую, параллельно( можно под 45градусов)), книгу Энгельса на книгу Ленина
3-й впервые посещающий кладет крест-накрест книги сверху Ленин снизу Энгельс
4-й впервые посещающий кладет 1 книгу на другую параллельно(можно под 45 градусов) книгу Ленина на книгу Энгельса
5-й впервые посещающий видит предыдущий знак и заявляет
причем если любой из заключенный заходит повторно, он просто переворачивает верхнюю книгу не меняя расположение знака
PS за отсутствие хайдов не минусуйте, не знаю как ставятся

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

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

Хотя, моё решение имеет уязвимость и не может считаться решением. Буду думать.

хм... может им просто нужно всем до вечера зайти в библиотеку?

Эта задача для Хабра уже в некотором роде боян: Новая задачка. Теперь про узников.

http://habrahabr.ru/blog/zadachki/18955.…
Разве не похоже?

Параметры:
0 - обложка вниз
1- обложка вверх

Условия:
1. Каждый человек должен запомнить состояние книг при первом своем заходе в комнату.
2. Идет цикличность.
3. Если первый раз заходишь прибавляешь на 1 (т.е если было 01 то будет 10... если 11 то соотвественно 00)
4. Если второй раз заходишь то убавляешь на единицу(т.е. думаю что все понятно)
5. как только число книг при входе больше или равно твоему изначальному то значит все побывали уже

Вроде все учел, хотя могу и ошибаться :)

00=0
01=1
10=2
11=3

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

Придумал.

Выбирают одного счетчика.

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

Пишите ответы белым.

Основная проблема при решении этой задачи, на мой взгляд, кроется в том, что книги надо обязательно переворачивать, иными словами 2мя битами нам не обойтись. Но можно ли увеличить разрядность? Можно, это же книги Ж)

Во-первых можно определять какая книжка лежит выше, это даст 1 дополнительный бит. Во-вторых, можно определить, как книги будут лежать относительно друг-друга, т.е. переплеты в разные стороны или в одну: это даст еще 2 бита.

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

Итого имеем 5 бит, с которыми уже много проще решить, к примеру:
0) Заключенные назначают значения 5ти бит положениям книг и выбирают среди себя счетчика
1) Каждому из 4х оставшихся назначаются биты, если заключенный входит и видит, что его бит установлен не им, значит надо инициализировать и установить все биты на 00000.
2) Если заключенный видит, что его бит не установлен, он его устанавливает и если это не вызывает переворота, то использует запасной.
3) Счетчик всегда смотрит и использует запасной переворот. Как только он видит, что первые 4 биту установлены, он радостно бежит к начальнику и просится на свободу.

При этом:
1) Если заключенному надо просто сменить ориентацию переплета, а его книжка лежит сверху и на ней не определен резервный поворот, то он берет книжку снизу, переворчивает её и кладет снова вниз, при этой операции он может повернуть свою, не переворачивая. Ж)
2) Если наоборот: ему надо повернуть, а книга лежит снизу, значит он должен использовать резервный переворот и ждать, пока книги поменяются местами(бит какого-нибудь заключенного).

Тут все время проскакивают варианты с обеими книгами но в условии черным по белому сказано :)

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

Если ставить задачу в формулировке: "как им действовать, чтобы через некоторое время гарантированно выйти на свободу", то, можно показать, что задача решения не имеет (все, разумеется, ИМХО). Допустим, что это не так и существует гарантированный алгоритм. Далее представим, что ЗК водят в таком порядке: 1-й, 2-й, 3-й, 4-й, 5-й, 5-й, 5-й, 5-й... и т. д. до бесконечности. Тогда пятый должен в одно из своих посещений сказать "опа! пора...". Но поскольку с момента его первого посещения никакой информации его политзаключенные товарищи ему передать не могут, то он может определить, что все были до него в первое-же посещение. Но так как начальное расположение книг не известно, то любое расположение книг в его первое посещение может получиться в случае, если никого до него и не водили.

Предлагаю вариант поведения группы товарищей, в предположении, что заведующий этим пионерлагерем действует достаточно рандомно, и периодически все зеки посещают ленинскую комнату:

Заключенные расчитываются на номера с 1 по 5. Все дни, начиная со следующей недели циклически нумеруются с 1 до 5, т е 1,2,3,4,5,1,2,3,4,5,1,2,3,4,5 и т д. Каждый заключенный, когда его приводят, действует следующим образом:
1) Смотрит и запоминает, как лежит Ленин.
2) Если это первое посещение, то распрямляет все пальцы на левой руке (инициализирует счетчик).
2) Если посещение не первое и ленин лежит не так, как в прошлый раз, то загибает себе палец на левой руке и держит так до следующего посещения :-)
3) Если видит что все пальцы загнуты, то радостно кричит "Мы тут все уже были!".
4) Иначе если номер дня совпадает с порядковым номером заключенного, то он переворачивает Ленина, иначе переворачивает Маркса.

Но похоже, что этот алгоритм можно еще оптимизировать...

О, сколько уже комментариев. Я не опоздал? :-)

Итак, мы имеем дело с цифрами — нулем и единицей. Пусть ноль — состояние, когда книга лежит обложкой вниз.
Начальное состояние может быть любым, и, к счастью, нас это не интересует.
Давайте произвольно выберем:
i j
1 1

Опишем наши функции:

Одна из пяти функций(осужденных, ага) будет, как правильно говорилось выше, «счетчиком».
Опишем функцию «счетчик»:
1) «Счетчик» всегда устанавливает старший разряд (i) в «0». Всегда. И увеличивает свое значение на единицу.
2) Если старший разряд уже «0», когда «счетчик» пришел — просто меняет значение младшего разряда (j). Его значение нам вообще не интересно.

Опишем остальные функции. Назовем их «гости».
Целью «гостя» является установка старшего разряда в единицу. Это не обязательно произойдет в его первый визит.
1) Если i=0, он меняет его на единицу. Выполнить эту операцию функция «гость» может только один раз. При следующих «срабатываниях» функция будет тупо вертеть младший разряд j, значение которого никого не интересует.
1) Если i=1 и «гость» его еще ни разу не менял, вертит «j» и уходит, до следующего раза.

ВСЁ!

Немного расплывчатые условия задачи
Книги в начале лежат в случайном состоянии или строго обложками вверх?
Можно ли пользоваться "поворотами" книг и прочими условиями не связанными с переворотом?

Если можно, то задача решается забавно — каждый заключенный вырывает страницу из Энгельса и хавает ее! Тот кто зайдет и увидит 4 вырванных страницы говорит что я — последний :) Т.к. нигде не сказанно что этого делать нельзя, считаю выриант самым быстрым и простым :)

Перворачивать таким образом, чтобы книги были с перевернутой обложкой\лицевой стороной, и договорится о комбинациях, причем таким образом что каждая комбинация обозначает двух человек - того кто зашел, и предыдущего. Количества комбинаций вполне хватает для того чтобы всех "промаркировать"

Чёт намудрили народ. Всё же гораздо проще.


Есть 4 комбинации книг которые можно получить:

Верх1 Верх2
Верх1 Тыл2
Тыл1 Верх2
Тыл1 Тыл2

Закрепляем каждую комбинацию за одним человеком.
5 ничего не делает и при входе в команту не переворацичвает книги.

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

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

Ну и ещё: если один из четвёрки не может привести комбюинацию к своей - он не трогает книги вообще.

Я посмотрел задачу про комнату с лампочкой.
Если добавить одно дополнительное условие: "Рано или поздно любой из вас пойдёт ещё раз", fl00r прекрасно решил задачу.

А так - непонятно.

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

Отставим в покое всякие биты и заморочки с дополнительными положениями книг, поскольку это не красиво и это хаки :)
Значит так:
Одного из зэков назначают счетчиком. В качестве флага мы выберем, например маркса. Если маркс лицом вверх - значит кто-то тут уже был. Счетчик, видя маркса лицом вверх, делает i++ и переворачивает его лицом вниз. Все остальные имеют право перевернуть маркса лицом вверх только один раз asap. Во всех остальных случаях переворачивают энгельса - нам плевать лицом куда он лежит. Как только у счетчика получится i=4 значит все тут были. Но! Так как мы не знаем изначальное состояние системы то может получиться что маркс изначально лежал лицом вверх и изначально i=1. Поэтому нам нужно чуть избыточности, ну, скажем переворачивать маркса лицом вверх каждый будет два раза. Тоесть как только i=8 - все были минимум один раз (если изначально i=1 то не_счетоводы были в комнате по два раза, кроме одного, который был всего один раз). Система рано или поздно сработает, при условии, что количество посещений каждого не лимитировано. Если заведующий лагерем знает решение, то в его силах либо позволить им выйти, либо сделать так чтобы они никогда не вышли.
Таким образом получется что зэки выживут в любом случае и у них есть шанс ещё и оказаться на свободе.
Но если зеки не придумают этого решения у них есть один простой способ - подождать ну, скажем, год, а потом рискнуть и сказать что все были, поскольку время играет им на руку - чем дальше, тем больше шансов на то, что они все уже были. :)

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

Я так думаю что мы не используем одно очень важное условие. Это то что время таки дискретно и измерятеся в днях.

Щас подумаю и попробую придумать что то с днями.

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

В условии пропущен один важный момент, который делает правильную стратегию бесполезной:
>> Рано или поздно каждый из вас побывает в Ленинской комнате и не один раз.
Проще говоря, при времени стремящемся к бесконечности каждый побывает в комнате количество раз стремящееся к бесконечности.

Счетчики нафиг! Необходимо выделить следящего и обозначить протокол передачи ему информации о побывавших в камере.
Каждый информатор старается сообщить о себе (оставив Маркса лицом), если перед ним это не сделал другой информатор и следящий не обозначил, что он это принял (Маркс жопой). Иначе он ждет своей очереди. Соответственно следящий считает, сколько там уже побывали. В первый день не учитывается никто и к началу второго дня Маркс должен лежать жопой, чтобы следящий, зайдя в комнату в первый день, не воспринял случайный сигнал за истинный.

Проблема счетчика

Выше, предлагается использовать одного товарища как счетчика. Кажется, что счетчик это тупиковая идея.
Что если счетчик побывает в комнате не много раз, а N-1?
Или он будет в комнате много больше N, но в самом начале игры, до того как в комнату поведут остальных заключенных, и больше в комнату его водить не будут?
В таких случаях он просто физически не сможет сосчитать всех.

- час рабочего времени на рисование диаграмм переходов, в результате пришел к тому как в http://habrahabr.ru/blog/zadachki/42678.html#comment862945

Думается решение следующее...
Зеки выбирают счетчика. Когда обычный зек заходит в комнату в первый раз - переворачивает маркса лицом вниз, если маркс уже лежит так - то ждет следующего раза, и крутит энгельса. Каждый зек должен перевернуть маркса лицов вниз ровно один раз. Счетчик переворачивает маркса лицом вверх и считает +1, когда насчитает N+1 - все свободны. По условиям задачи время отсидки неограничено - значит рано или поздно счетчик насчитает нужное количество