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

    Заведующий концлагерем вызывает к себе 5 осужденных и говорит:

    «У вас будет время до вечера чтобы создать план действий, но уже завтра вы будете находиться в разных камерах и никогда не будете встречаться. У нас в лагере есть Ленинская комната, в которой на столе лежат 2 книги: „Капитал“ Маркса и „Анти-Дюринг“ Энгельса.

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

    Рано или поздно каждый из вас побывает в Ленинской комнате. Так вот, любой из вас в любое время может сказать „Мы все здесь уже были!“. Если окажется, что он прав, вы все будете освобождены. Если нет — расстреляны.»

    Что же делать осужденным, ведь время до вечера еще есть?

    UPD: Облегчаем задачу. Заключенных не 5, а 19.

    UPD: Ответ достаточно быстро и четко сформулировал товарищ tunelix, на основании почти правильного варианта by FloppyFormator:
    итак: у нас есть 1 счетчик и 4 исполнителя.
    задача исполнителя: если маркс лежит обложкой верх — переворачиваем энгельса, если обложкой вниз переворачиваем маркса мордой вверх. каждый испольнитель считает количество переворотов маркса — если он перевернул его 2 раза — больше он его на мордой вверх не переворачивает.
    счетчик: каждый раз когда он видит маркса перевернутого мордой вверх он увеличивает счетчик +1 и переворачивает маркса вниз лицом. если маркс лежите вниз лицом он циклически переворачивает энгельса.
    когда счетчик дойдет до 8 — он может сказать что все побывали в комнате.
    считать до 8 (а не до 4х) нужно чтоб обойти ситуацию когда 1м в комнату попадает счетчик, а там маркс лежит мордой вверх.


    Несколько соображений по поводу задачи и ее обсуждения:
    1. В оригинале (когда я о ней узнал) задача была про 2 выключателя и 23 заключенных. Пришлось переделать в патриотическом стиле, чтобы общественность не так быстро выгуглила ответ.
    2. Задача была намеренно усложнена. Так, например, 5 заключенных вкупе с 2 книгами наталкивают на мысли о двоичной системе счисления, хотя с 23 заключенными в этом (неправильном) направлении даже и не думаешь. Кроме того, если свести задачу к одной книге (убрав обязательное условие о перевороте хоть одной книги), то тоже задача решается намного проще. Но поиск правильного направления — это тоже задача, поэтому не стоит предъявлять претензии о некорректной формулировке.
    3. Условие о том, что каждый заключенный побывает в комнате несколько (да что там, много!) раз не было явно указано, т.к. если бы это было не так, у задачи очевидно не было бы решения.
    4. Поиск 'альтернативных' вариантов (поворачивать книги вокруг оси, делать пометки, закладки, ложить Маркса под ручку с Энгельсом и т.д.) был совсем не обоснованным. Условий задачи вполне достаточно для того, чтобы ее решить.
    5. Не всем было понятно, что собственно от них требовалось. Для меня правильное решение удовлетворяет следующим условиям: а) заключенные не будут расстреляны ни при каких обстоятельствах; б) заключенные имеют реальный шанс выйти. Даже при этих довольно общих критериях решение было найдено только одно.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 232

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

        Как только кто-то получает сигналы от всех по 2 раза (чтобы исключить ошибку из-за начального положения книг), тот и говорит что мы тут были все. Возможно я неправ...
          0
          Забыл добавить тыльной стороной или обложкой - пофигу.
            0
            Я уже один раз написал "Горячо", получил -1 :)
            Рациональное зерно в предложении есть, но со взаимным расположением книг это никак не связано. Данных в задаче хватает для решения, а стол может оказаться настолько маленьким, что книги на нем еле умещаются.
              +17
              "Маркс и Энгельс лежат рядом, почти касаясь друг друга."
              Новая поза?
                0
                Думаю, что в таком случае просто заранее пронумероваться и вырывать из какой-либо книги страницы со соответствующими номерами.
                0
                Похожую задачку задавали в Яндексе на собеседовании :)


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

                Это при условии, что в самом начале книжки лежат лицом вверх.
                  0
                  Книжки лежат лицом кто куда.
                    +1
                    Хорошо.
                    Перевёрнутый Маркс при первом посещении ленинской комнаты исполнителем - это либо сигнал от кого-то из ранее прибывших, либо случайно брошенная книжка в начале. Прибавим к "критической" величине счётчика единицу и всё ок )
                    В предыдущем решении забыл добавить, что после однократного переворачивания Маркса все кроме исполнителя в дальнейшем должны переворачивать только Энгельса.
                      0
                      Хм. А как же он узнает, это случайность или знак?

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

                      Может что-то в консерватории подправить?
                        0
                        Ориентироваться на 5.
                        Не дождаться можно и четырёх. В конце концов, начальник концлагеря волен всё время одного человека водить.
                          0
                          да, мне вот тоже не понятен момент начала отсчета...
                          а вариант с кручением вокруг оси дает больше вариаций - ведь кроме челов в комнату входить никто не будет, может и выравнивать тоже...
                            0
                            Повторю, вариант с кручением бесперспективный.
                            Единственное, на что нужно обращать внимание, - это лицом или спиной лежат книги.
                            • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Ну конечно, вы ничего не теряете, если ждете пятого.
                            Но потратить время до вечера можно с большей пользой. Думайте.
                          +1
                          у вас хорошее начало но решение не закончено.
                          итак: у нас есть 1 счетчик и 4 исполнителя.
                          задача исполнителя: если маркс лежит обложкой верх - переворачиваем энгельса, если обложкой вниз переворачиваем маркса мордой вверх. каждый испольнитель считает количество переворотов маркса - если он перевернул его 2 раза - больше он его на мордой вверх не переворачивает.
                          счетчик: каждый раз когда он видит маркса перевернутого мордой вверх он увеличивает счетчик +1 и переворачивает маркса вниз лицом. если маркс лежите вниз лицом он циклически переворачивает энгельса.
                          когда счетчик дойдет до 8 - он может сказать что все побывали в комнате.
                          считать до 8 (а не до 4х) нужно чтоб обойти ситуацию когда 1м в комнату попадает счетчик, а там маркс лежит мордой вверх.
                            0
                            Хм.

                            Рассмотрим случай:

                            # - номер зека
                            #* - счётчик
                            М - морда вверх
                            Ж - жопа вверх

                            # Мркс Эглс
                            Ж М
                            1 М М
                            2* Ж М +1
                            3 М М
                            4 М Ж
                            5 М Ж
                            1 М Ж
                            1 М М
                            1 М Ж
                            1 М М
                            ...

                            Т. е. если надзиратель будет водить только первого зека, то алгоритм зациклится, хотя все пятеро и побывали :(
                              0
                              В условии не сказано что они должны сказать немедленно как только это случится, а "..любой из вас в любое время..". мне видится что быстрее никак не получится.
                                0
                                Да, да. Просто если надзиратель станет водить только первого зека, то, боюсь, это не случиться никогда.
                                Или я не правильно понял Ваше решение?
                              0
                              Так у вас ещё дольше получается, аж до восьми нужно ждать.
                                0
                                Лично для меня это был самый сложный шаг в задаче.
                                Отлично.
                                  0
                                  Почему вы не написали в условии, что побывавший в комнате зек обязательно когда-нибудь туда снова попадёт? Если же это не так, то решение не верно!
                                    0
                                    Если это не так, то решения вообще нет, равно как и смысла ставить задачу.
                                      0
                                      Извините, но вы не правы. В таком случае могла, подразумеваться ещё какая-то деталь, которая делает решение возможным. Например, известное начальное положение книг. Спасибо за задачу, но прошу вас впредь внимательнее относиться к формулировке условия. Лучше перебдеть, чем недобдеть.

                                      ЗЫ. Кстати говоря, если бы условие было более формально сформулировано, не было бы бесконечных дискуссий на тему «а можно ли ещё как-то поворачивать книги?»
                                        0
                                        При формулировке задачи я старался включить все нетривиальные условия, достаточные для решения задачи. Внимательные и вдумчивые пользователи задачу решили. Если это не вышло у вас, проанализируйте лучше свои ошибки.
                                          0
                                          Не будем спорить. Давайте каждый из нас учтёт свои ошибки и чужие пожелания.
                                0
                                Согласен с решением.
                                Не имеет значения каким зашел счетчик, отсчет он начинает с момента маркс перевернут(либо другое заранее оговоренное значение). Далее "счетчик" считает до 4х изменений положения Маркса. Остальные четверо переворачивают Маркса в положение "счетчик+1", если они делают это впервые, при повторном заходе крутят Энгельса который счетчик не учитывает никак. Если Маркс находится в положении, которое нельзя изменить на значение "счетчик+1", крутят Энгельса и ждут следующего захода.
                                  0
                                  Можно считать, начиная со второго дня походов, а первый день как раз использовать для инициализации нужной "книги".
                                    0
                                    Не вижу смысла делать привязку к дням - надзиратель вправе выбирать любые дни и любые интервалы между заходами, эти условия не оговорены в задаче...
                                0
                                в таком случае я решения не вижу
                                0
                                А если исполнителя пустят туда только один раз?
                                0
                                Эх..похоже придется вспомнить молодость, да полистать учебник по прикладной математике..
                                  0
                                  у меня получается, что их выпустят только если случится так, что в один из дней в комнату пять раз введут кого-нибудь не повторяясь (то есть каждого по разу).
                                  Ну и мода же на ночь задачки загадывать )
                                    –1
                                    Меня все же озарило:

                                    Четверо — нападающие, один — квотербек =).
                                    Нападающий переворачивает всегда левую книгу, кроме того случая, если правая лежит обложкой вверх, и он ее еще не переворачивал.
                                    Квотербек также всегда переворачивает левую книгу, кроме тех случаев, когда правая лежит обложкой вниз, тогда он переворачивает ее обложкой вверх и записывает +1 к себе в карму.
                                    Когда карма достигнет +4, он плюсует еще полтора разка за себя, срёт в карму начальнику (имея карму >5) и говорит, что дело сделано.
                                      0
                                      О-ппа
                                      «Книжки лежат лицом кто куда.»
                                    0
                                    Имеет ли значение начальное положение книг? В условии не упоминается то, как они лежат изначально. Это надо понимать как то, что они обе лежат лицом вверх или как то что это не важно?
                                      0
                                      Неизвестно, как они лежат.
                                      0
                                      каждый из заключенных независимо от начального положения кладет книжки по-своему:
                                      1-й - лицом, лицом
                                      2-й - лицом, спиной
                                      3-й - спиной, лицом
                                      4-й - спиной, спиной
                                      5-й запоминает, какие комбинации уже были, и когда все пройдут - может говорить

                                      но это при условии, что водить их будут до бесконечности
                                        0
                                        это невозможно, так как перевернуть можно лишь одну книжку. А из положение спиной, спиной за раз в положение лицом, лицом не перевернешь
                                        0
                                        Давайте нам уже ответ белым! :)
                                          0
                                          Может им до вечера кого-нить из 5 в расход пустить?
                                          Или Хеппи Энд не минуем? =)
                                            0
                                            Кстати, переворачивать можно только со спины на обложку? Или можно ещё "вверх ногами" класть? Хм, хотя это ведь тоже переворачивать... Тогда можно ведь на каждой книге 4 комбинации - вверх обложкой и вверх ногами, вверх обложкой и вниз ногами и т.д....
                                              0
                                              Да, только со спины на обложку.
                                              0
                                              Я правильно понимаю, что как только мы скажем, что книжки можно по разному переворачивать в зависимости от того, куда смотрит переплёт, задачка решается очевидно.

                                              Я имею в виду, что каждая книжка получит по 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ый вошедший — кричит ура и все идут пить пиво
                                              ?
                                                0
                                                Имхо это и есть правильный вариант, я так и рассуждал. Но какой-то он не красивый. Давайте рассуждать.
                                                Есть 4 "исполнителя", и один "наблюдатель".
                                                "Наблюдатель" не всегда приходит после какого-то "исполнителя". Точно так же и исполнитель может ходить несколько раз подряд, и ему же тоже нужно что-то делать? - переворачивать что-то и как-то, выходит каждый "исполнитель" должен знать два положения своих книг. Даже не так! За каждым исполнителем закреплено 2 положения одной (!) книги, иначе что ему делать, если обе его книги лежат так, как ему положено их класть? Одна беда, исполнитель не сможет с уверенность и вообще как-нибудь :) сказать, что были все, пока не побывает в комнате после каждого.
                                                  0
                                                  Я думал над выделением ролей — исполнитель/наблюдатель, но эта идея не очень пошла, так как бойцы могут входить в комнату произвольно. Те если есть кто-то кто делает ключевое действие, то оно может не произойти или произойти слишком рано. Я понимаю, что это "махание руками", тем не менее верю, что действия не должны зависеть от человека — иначе, все зеки исполняют один и тот же алгоритм
                                                  0
                                                  5-й после второго увидит то же самое, что и после 4-го.
                                                    0
                                                    Не совсем — после второго:
                                                    Маркс - (1-3)
                                                    Энгельс - (1'-3')

                                                    после четвёртого:
                                                    Маркс - (2-4)
                                                    Энгельс - (2'-4')

                                                    Зеки про номера не договариваются заранее — каждый входит, смотрит на книги и понемает какой он по счёту
                                                      0
                                                      Сначала Вы написали "2ой вошедший — крутит Маркста в состояниях 2-4".

                                                      Потом :
                                                      "Не совсем — после второго:
                                                      Маркс - (1-3)
                                                      Энгельс - (1'-3')".

                                                      Так 1-3 или 2-4?
                                                      А езще никак не пойму каким образом первый зек поймет, что он первый.
                                                    0
                                                    Вы ничего не знаете про стол. Возможно он не позволяет крутить книжки по оси.
                                                    Сосредоточьтесь на том что точно можно - со спины на живот и наоборот. Этого вполне достаточно.
                                                    –1
                                                    Я так понимаю, заключённые понимают, что кто-то пошёл. Тогда можно использовать книги, как двоичный счетчик ;)
                                                      +1
                                                      и я так подумал, но проблема в том, что каждый раз надо обязательно книжку переворачивать (т.е. это счетчик хитов, а не хостов). Или я не так понял.
                                                      +2
                                                      тут ничего не сказано о расположении книг.. если это не важно, то
                                                      1) если каждый заключенный при посещении зала? он просто переворачивает книгу, с тыльной на лицевую, любую не важно какую
                                                      2) а суть подсчета заключается в том что 1 заключенный кладет крест-накрест книги сверху Энгельс снизу Ленин
                                                      2-й впервые посещающий видя такое условие кладет книги 1 на другую, параллельно( можно под 45градусов)), книгу Энгельса на книгу Ленина
                                                      3-й впервые посещающий кладет крест-накрест книги сверху Ленин снизу Энгельс
                                                      4-й впервые посещающий кладет 1 книгу на другую параллельно(можно под 45 градусов) книгу Ленина на книгу Энгельса
                                                      5-й впервые посещающий видит предыдущий знак и заявляет
                                                      причем если любой из заключенный заходит повторно, он просто переворачивает верхнюю книгу не меняя расположение знака
                                                      PS за отсутствие хайдов не минусуйте, не знаю как ставятся
                                                        –2
                                                        <font color="white"> текст под хайдом </font>. Нужна карма больше 0 для хайда..
                                                          0
                                                          А вот это ниче ответ, мне нравится. Мог бы, поставил бы +1!)
                                                          Действительно, самый быстрый способ освобождения, пока быстрее не читал.
                                                            0
                                                            Никаких крестов. Только с обложки на спину и наоборот.
                                                            0
                                                            чтобы их отпустили нужно доказать, что были оба, если предположить, что книги сразу лежат обложкой вверх, то все просто. Допустим они договариваются, что если один из них увидит перевернутую книгу, значит здесь уже один был. Допустим первого водят три раза подряд, он сначала переворачивает первую книгу, потом вторую, потом ворочает одну книгу.
                                                            для выхода на свободу:
                                                            1. увидел книжку тыльной стороной
                                                            2. изменилось расположение книг с твоего последнего, прибывания)
                                                            я вот так подумал
                                                              –1
                                                              А вы что здесь ожидали увидеть?
                                                                0
                                                                Вы забываете что с началом эксперимента они перестают общаться и получать информацию. Соотвественно передавать ее друг другу они могут только через книги. В условии не сказано про начальное положение книг, значит следует считать что рандомно лежат. Тоесть заключенные не смогут имееть одинаковые начальные данные и соответсвенно не смогут провести нужные расчеты с преворачиванием и четко сказать да я последний, или нет еще пара человек не ходило сюда.Чисто матиматически можно привести что через цать циклов походов с вероятностью такой то все заключенные прошли через эту комнату, в реальности всегда останется место ошибки и по сути задача решена небудет. Посему единственное что пришло в голову:заключенные пересчитываются, назначают каждому свои уникальный номер, а дальше при походе в комнату каждый вырывает из заранее оговоренной книги страницу соответствующую его номеру.
                                                                  0
                                                                  А в один прекрасный момент приходит кто-то, а там эти страницы уже выдраны в прошлый раз такими умниками :)
                                                                    0
                                                                    Условиям задачи не противоречит, и точка :)
                                                                0
                                                                Мне кажется решения с счетчиком не подходят, потому что заведующий концлагерем может провести счетчика в комнату только один раз. Тогда никто никогда не скажет что все были, потому что говорить должен счетчик, а его в комнату для того чтобы посчитать не пускают.
                                                                  0


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

                                                                  л0 - ленин обложкой вниз, л1- обложкой вверх, м0, м1 - аналогично.

                                                                  Первый ход:
                                                                  л0 м0
                                                                  Второй побывавший видит это, создает такую картину:
                                                                  ло м1
                                                                  Третий кто посещает комнату делает так:
                                                                  л1 м1
                                                                  Четвертый кто побывал в Ленинской комнате делает вот что:
                                                                  л1 м0
                                                                  Последний (только если видит л1 м0) - восстанавливает ситуацию.
                                                                  л0 м0.

                                                                  Для условия, в котором обе книги изначально обложкой вверх - 0 превратить в 1 и наоборот.
                                                                    0
                                                                    Не трогать вообще нельзя по условию
                                                                      0
                                                                      (но только одну) из книг
                                                                      –1
                                                                      Что делать, что делать - учиться считать в двоичной системе счисления.
                                                                        0
                                                                          0
                                                                          один программист точно есть =)
                                                                          у книги два состояния "обложка" и "тыл" - состояния 0 и 1
                                                                          книги две - максимальное количество комбинаций 4 те четверо разбирают себе по цифре, а пятый подводит черту - "все были"
                                                                            +1
                                                                            в условии говорится, что порядок посещения — произвольный. Так что пятого могут привести туда первым, и больше никогда не приводить :)
                                                                            0
                                                                            Не знал о Коде.. но сам о таком думал ;)
                                                                          0
                                                                          Хотя, моё решение имеет уязвимость и не может считаться решением. Буду думать.
                                                                            0
                                                                            хм... может им просто нужно всем до вечера зайти в библиотеку?
                                                                              +2
                                                                              Эта задача для Хабра уже в некотором роде боян: Новая задачка. Теперь про узников.
                                                                              +2
                                                                              http://habrahabr.ru/blog/zadachki/18955.…
                                                                              Разве не похоже?
                                                                                0
                                                                                Ну раз похоже - реши. Кто мешает? Условия разные, абсолютно, а формулировка просто похожая, чтобы не выдумывать что-то мудреное.
                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                    0
                                                                                    Вы до этого сначала додумайтесь (не зная более простой задачи).
                                                                                    Это целое искусство сводить задачи к более простым.
                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                        0
                                                                                        Я лишь хочу сказать, что если вы знаете решение хоть этой задачи, хоть подобной, то уже не интересно.
                                                                                        А если не знаете ни той, ни другой, то задачу свести к более простой будет тяжело.
                                                                                      0
                                                                                      Ага. Правда без второй книги тут не обойтись. Книгу переворачивать нужно)
                                                                                      +1
                                                                                      Тут тоже самое!
                                                                                      Лампочка - одна книга. Когда менять лампочку не надо переворачиваем другую книгу.
                                                                                      А опубликовал ту задачу я, так что ответ знаю.
                                                                                    0
                                                                                    Параметры:
                                                                                    0 - обложка вниз
                                                                                    1- обложка вверх

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

                                                                                    Вроде все учел, хотя могу и ошибаться :)
                                                                                      0
                                                                                      Интересно на сколько секунд я опоздал с ответом, :-)
                                                                                      Вроде тоже самое написал...
                                                                                        0
                                                                                        Не знаю даже как посмотреть, видно что в одну минуту запостили :)
                                                                                          0
                                                                                          Про четность забыл написать, хотя и имел ее ввиду ;)
                                                                                          0
                                                                                          счётчик Маркса и Энгельса переполнен и 11 превращается в 00 ? :)
                                                                                            +2
                                                                                            >обязательно взять любую (но только одну) из книг
                                                                                              0
                                                                                              Вот надо вам всю теорию порушить :-)
                                                                                              Держите +
                                                                                                +1
                                                                                                но можно иначе считать :)
                                                                                                00
                                                                                                01
                                                                                                11
                                                                                                10
                                                                                                  0
                                                                                                  пожалуй тогда все заработает...
                                                                                            +1
                                                                                            - Завели 1-го узника. Он увеличил счётчик на единицу.
                                                                                            - Опять завели 1-го узника. Он уменьшил счетчик на единицу.
                                                                                            - Опять завели 1-го узника. Он увидел, что счёчик равен изначальному и сказал, что все здесь были.
                                                                                            - Unhappy end.
                                                                                            +1
                                                                                            00=0
                                                                                            01=1
                                                                                            10=2
                                                                                            11=3

                                                                                            Каждый зашедший в свое нечетное посещение плюсует, в четное - минусует. Как только первый, зашедший в одно из посещений, увидит комбинацию, которую он оставил после первого своего посещения, то значит все были.
                                                                                              +2
                                                                                              Кстати, можно еще засечки на краю обложки ногтем ставить 8-)
                                                                                                0
                                                                                                1) нельзя перейти из состояния 01 в состояние 10 одним переворотом книжки
                                                                                                2) Предположим ситуацию: завели узника № 1, затем № 1. Тогда во второе посещение он увидит то же состояние, которое было после первого.
                                                                                                  0
                                                                                                  1) Ну и фиг с ним.
                                                                                                  00 - первый зек в первое посещение
                                                                                                  01 - второй зек в первое посещение
                                                                                                  11 - третий зек в первое посещение
                                                                                                  10 - четвертый зек в первое посещение
                                                                                                  и радостный вопль "мы все здесь были"
                                                                                                  вот только метод работать не будет из-за неопределенного начального состояния :)
                                                                                                    0
                                                                                                    каждое чётное посещение запоминает в каком положении были книги, как только увидит во всех положениях, то сможет радостно сообщить о том что все здесь побывали :)
                                                                                                0
                                                                                                Придумал.

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

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

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

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

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

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

                                                                                                      Читать ничего не надо, но нужно будет обязательно взять любую (но только одну) из книг и перевернуть ее (с тыльной стороны на обложку или наоборот).
                                                                                                        0
                                                                                                        Если ставить задачу в формулировке: "как им действовать, чтобы через некоторое время гарантированно выйти на свободу", то, можно показать, что задача решения не имеет (все, разумеется, ИМХО). Допустим, что это не так и существует гарантированный алгоритм. Далее представим, что ЗК водят в таком порядке: 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) Иначе если номер дня совпадает с порядковым номером заключенного, то он переворачивает Ленина, иначе переворачивает Маркса.

                                                                                                        Но похоже, что этот алгоритм можно еще оптимизировать...
                                                                                                          0
                                                                                                          Ну то есть, не Ленин, а Энгельс, разумеется...
                                                                                                          Как сильно совковые штампы-то въелись :-)
                                                                                                            0
                                                                                                            Уточнение к пункту 4) - разумеется Энгельса каждый сам переворачивает только один раз, а потом тупо крутит маркса.
                                                                                                            Этот образ действий гарантирует, что никого не расстреляют, не требует отдельного счетчика, но при увеличении количества зеков становится очень маловероятно скорое их освобождение...
                                                                                                            0
                                                                                                            О, сколько уже комментариев. Я не опоздал? :-)

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

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

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

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

                                                                                                            ВСЁ!
                                                                                                              0
                                                                                                              было почти вначале. Алгоритм сбивается если книги вначале лежат в случайном положении. «счетчик» примет начальное положение книги за посетителя, даже если он вошел первым
                                                                                                                0
                                                                                                                все в порядке если счетчиком будет тот, кто идет в первый день. он выставляет старший разряд в 0 (или меняет младший, если менять старший не нужно), все остальные ЗНАЮТ что они не ходили в первый день и действуют по заданому алгоритму. это работает.
                                                                                                                  +2
                                                                                                                  Остальные-то знают что они не ходили в первый день, а вот счетчик не знает. Не может быть ситуации в которой он скинет в ноль старший разряд и не засчитает посещение, для этого ему нужно знать что он первый, что невозможно.
                                                                                                                  А вот если считать до 6, то вроде как получается...
                                                                                                                    0
                                                                                                                    может испортить только одна мелочь, если одного из узников заведут в библиотеку, он перевернет книгу для счетчика. Счетчик зайдет первый раз и "скинет" значение, предполагая что это может быть ошибка. Но если первого узника больше никогда не поведут к книгам то его счетчик уже не дождется и будет все рвемя думать что его ждать, хотя на самом деле все уже были.
                                                                                                                    Итог - в библиотеке все побывали, счетчик заклинило :) Остается только надется что первого еще хотябы раз сводят в читальню
                                                                                                                      0
                                                                                                                      Мои функции не могут "предполагать", они просто работают :-)
                                                                                                                0
                                                                                                                Никак не пойму, а что будет если счетчик заходит первым и старший разряд уже 1? Он скидывает его в 0 и засчитывает посещение?
                                                                                                                  0
                                                                                                                  Именно так.
                                                                                                                  Начальное значение счетчика = 0
                                                                                                                  Счетчик считает до пяти.
                                                                                                                  Проверьте.
                                                                                                                    0
                                                                                                                    Так посещения-то не было, кого он посчитал?
                                                                                                                      0
                                                                                                                      Пронумеруем четырех гостей от 1 до 4, пятый - счетчик. Если начальное положение i=0, то после следующей последовательности посещений 1,5,2,5,3,5,4,5 функция счетчика будет равена четырем, а учитывая что "Выполнить эту операцию функция «гость» может только один раз", счетчик никогда уже не достигнет 5. То есть работать-то дальше будет, но завершения алгоритма уже гарантированно не получится при любой дальнейшей последовательности вызова функций.
                                                                                                                  +4
                                                                                                                  Немного расплывчатые условия задачи
                                                                                                                  Книги в начале лежат в случайном состоянии или строго обложками вверх?
                                                                                                                  Можно ли пользоваться "поворотами" книг и прочими условиями не связанными с переворотом?

                                                                                                                  Если можно, то задача решается забавно — каждый заключенный вырывает страницу из Энгельса и хавает ее! Тот кто зайдет и увидит 4 вырванных страницы говорит что я — последний :) Т.к. нигде не сказанно что этого делать нельзя, считаю выриант самым быстрым и простым :)
                                                                                                                    +1
                                                                                                                    Немного оптимизируем и ...можно отрывать и кушать только уголки, где написаны номера страниц. Хотя если кушать хочется, то можно и целиком...
                                                                                                                      +1
                                                                                                                      ага, а если еще ... заключенным выдать номера чтобы они хавали только свои страницы, то потом можно заведующего удивить фразой "Ну давайте уже Васю и Петю ведите, их нехватает!"
                                                                                                                      0
                                                                                                                      Можно я сам себя процитирую? «Начальное состояние может быть любым, и, к счастью, нас это не интересует.»
                                                                                                                      Пользоваться нужно именно переворотом. В этом соль задачи.
                                                                                                                      0
                                                                                                                      Перворачивать таким образом, чтобы книги были с перевернутой обложкой\лицевой стороной, и договорится о комбинациях, причем таким образом что каждая комбинация обозначает двух человек - того кто зашел, и предыдущего. Количества комбинаций вполне хватает для того чтобы всех "промаркировать"
                                                                                                                        0
                                                                                                                        А, и ещё забыл, первый входящий должен положить книги в опр. исходное положение)
                                                                                                                          0
                                                                                                                          А вообще их пятеро, и можно совершить каждому по одному действию в строгой последовательности,типо счетчик, и обозначить часть вариантов как "холостые", если их сразу поочереди поведут так вообще быстро выйдут.
                                                                                                                        0
                                                                                                                        Чёт намудрили народ. Всё же гораздо проще.


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

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

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

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

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

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

                                                                                                                          Вот невнимательность - вторая глупость.
                                                                                                                            0
                                                                                                                            Тоже не то во первых надо перернуть обязательно! во вторых можно перевернуть только 1 книгу.
                                                                                                                            0
                                                                                                                            Я посмотрел задачу про комнату с лампочкой.
                                                                                                                            Если добавить одно дополнительное условие: "Рано или поздно любой из вас пойдёт ещё раз", fl00r прекрасно решил задачу.

                                                                                                                            А так - непонятно.
                                                                                                                              –1
                                                                                                                              Во. Второй вариант.

                                                                                                                              При котором не учитывается начальное положение книг.


                                                                                                                              Определим за каждым заключённым одну из комбинаций: 00(1) 01(2) 11(3) 10(4) 00(5) — В скобках номера заключённых. Именно в такой последовательности.
                                                                                                                              После каждого вызова каждый заключённый пытается привести текущее положение книг в то положение которое назначено ему.
                                                                                                                              Если он не может этого сделать он пытается привести положенее книг к виду положение "слева от него". Т.е если я номер 3 пришёл и вижу: 00 я делаю 01.

                                                                                                                              Говорить что "мы побывали тут все" может заключённый под номером 5, но только в том случае если он перевернул книги из положения 4 в положение 5.

                                                                                                                                +1
                                                                                                                                первый зашёл 4 (сделал свою комбинацию) потом 5.
                                                                                                                                  0
                                                                                                                                  А. Я немного не доописал. Двигаем книги только тогда если они установлены в такое положение которое находится в спсике от меня слева. Если так не получается - двигаем книги так что бы получилась комбинация слева.
                                                                                                                                    0
                                                                                                                                    а если уже своя комбинация?
                                                                                                                                      0
                                                                                                                                      по условию изменять надо обязательно.
                                                                                                                                        0
                                                                                                                                        проверте свою теорию на любое начальное значение. что если 10 и заходит 5?
                                                                                                                                      0
                                                                                                                                      зашел 1 - сделал 00, второй сделал 01, заходит четвертый, сделать 10 не может, ок делает (левый вариант) 11, заходить опять четвертый - опа! делает свою 10, заходит пятый и глупо погибает :)
                                                                                                                                    0
                                                                                                                                    В сущности таким способом мы будем просто ждать того момента пока начальник конслагеря сам не проведёт всех заключённых поочереди в нужном нам порядке.
                                                                                                                                      0
                                                                                                                                      совсем не то, по вашему алгоритмы выжить — как в лотерею выиграть :)
                                                                                                                                        0
                                                                                                                                        ну там же не сказанно что количество проходов ограниченно?
                                                                                                                                        0
                                                                                                                                        Вопщем лучше наверно переописать. А то я уже запутался в своих же измышлениях.


                                                                                                                                        Итак имеем заранее определённый порядок положений книг:

                                                                                                                                        1 - 00
                                                                                                                                        2 - 01
                                                                                                                                        3 - 11
                                                                                                                                        4 - 10
                                                                                                                                        5 - 00

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

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

                                                                                                                                          0
                                                                                                                                          а если там 00 и заходит третий? ему надо сделать 11? Он не может.
                                                                                                                                          Если он сделает 01 то засчитают за второго, а если сделает 10 то потом зайдет пятый и радостно скажет что все были
                                                                                                                                            0
                                                                                                                                            Он должен сделать 01. Но нет ничего страшного в том что его засчитают за второго.
                                                                                                                                            Так как для успешного прохождения всего пути надо что бы каждый перевернул правильно.
                                                                                                                                            И тогда последний поймёт что всё было правильно до него и сделает вывод что все были.

                                                                                                                                            Идём от обратного.
                                                                                                                                            Если 5 увидит 10 - он поймёт что предыдущий был либо он либо 4. Если это был он сам - то возвращаемся в начало предложения. Если это был четвёртый - становимся на место четвёртого.

                                                                                                                                            Если четвёртый видит 11 - он поймёт что предыдущий были либо он сам либо 3. Ну и т.д..
                                                                                                                                            0
                                                                                                                                            А если осужденных не 5, а 50, тогда как? :-)
                                                                                                                                              0
                                                                                                                                              Вот я щас смотрю на "UPD:" в теле топика и начинаю нервно курить.
                                                                                                                                          0
                                                                                                                                          Вставлю свои пять копеек. Если начальное положение книг произвольно и заранее не известно, тогда решение вряд ли существует, поскольку заключённые не могут своими силами инициализировать книги (какой бы ни был выбран алгоритм, всегда можно подобрать контрпример). Если же начальное положение книг известно, то задача замечательно решается с помощью Кода Грея (как писали выше). Первые четыре уникальные заключённые увеличивают двоичный счётчик. Пятый, когда видит максимальное значение счётчика выдаёт результат.
                                                                                                                                            0
                                                                                                                                            чёрт, не заметил апдейта(
                                                                                                                                              0
                                                                                                                                              по условию задачи 5 тоже ДОЛЖЕН переворачивать.
                                                                                                                                                0
                                                                                                                                                он переворачивает книгу-не-счетчик
                                                                                                                                                ее же и переворачивают те кто уже ставили счетчик или если счетчик уже установленн но и ожидает сброса
                                                                                                                                                0

                                                                                                                                                есть четыре положения: 00 - 1, 01 - 2, 11 - 3, 10 - 4
                                                                                                                                                измениять положение можно либо на +1, либо на -1
                                                                                                                                                чётные посещения зэка +, нечётные -

                                                                                                                                                зэкам остаётся ждать, пока они не увидят:
                                                                                                                                                + - - - 1
                                                                                                                                                + + - - 2
                                                                                                                                                + + + - 3
                                                                                                                                                + + + + 4
                                                                                                                                                  0
                                                                                                                                                  Начальное положение книг неизвестно. Может оно было "01"?
                                                                                                                                                    0
                                                                                                                                                    с любым положением не работает такой подход :)
                                                                                                                                                +2
                                                                                                                                                Отставим в покое всякие биты и заморочки с дополнительными положениями книг, поскольку это не красиво и это хаки :)
                                                                                                                                                Значит так:
                                                                                                                                                Одного из зэков назначают счетчиком. В качестве флага мы выберем, например маркса. Если маркс лицом вверх - значит кто-то тут уже был. Счетчик, видя маркса лицом вверх, делает i++ и переворачивает его лицом вниз. Все остальные имеют право перевернуть маркса лицом вверх только один раз asap. Во всех остальных случаях переворачивают энгельса - нам плевать лицом куда он лежит. Как только у счетчика получится i=4 значит все тут были. Но! Так как мы не знаем изначальное состояние системы то может получиться что маркс изначально лежал лицом вверх и изначально i=1. Поэтому нам нужно чуть избыточности, ну, скажем переворачивать маркса лицом вверх каждый будет два раза. Тоесть как только i=8 - все были минимум один раз (если изначально i=1 то не_счетоводы были в комнате по два раза, кроме одного, который был всего один раз). Система рано или поздно сработает, при условии, что количество посещений каждого не лимитировано. Если заведующий лагерем знает решение, то в его силах либо позволить им выйти, либо сделать так чтобы они никогда не вышли.
                                                                                                                                                Таким образом получется что зэки выживут в любом случае и у них есть шанс ещё и оказаться на свободе.
                                                                                                                                                Но если зеки не придумают этого решения у них есть один простой способ - подождать ну, скажем, год, а потом рискнуть и сказать что все были, поскольку время играет им на руку - чем дальше, тем больше шансов на то, что они все уже были. :)
                                                                                                                                                  0
                                                                                                                                                  зачем 8? достаточно 5 (т.е. N раз)
                                                                                                                                                    0
                                                                                                                                                    не выйдет. если книга изначально была в подожении 0, а не_счетчики будут переворачивать маркса только один раз, то счетчик никогда не достигнет значения 5. Если они будут переворачивать маркса по два раза, то запросто может получиться что первый был 2 раза, второй тоже 2 раза, а третий и четвертый - ни разу. Всем кирдык.
                                                                                                                                                      0
                                                                                                                                                      Почему никогда? Приходит счетчик и переворачивает маркса. Далее все по разу ее переворачивают.
                                                                                                                                                        0
                                                                                                                                                        Прочитал комменты к своему варианту, да, все же 2*(N-1) раз =)
                                                                                                                                                    0
                                                                                                                                                    пожалуй это верно, нужно действительно минимум 8
                                                                                                                                                    +1
                                                                                                                                                    В общем, получается, что одну из книг исполнители используют вхолостую - чтобы "ход пропустить". А вторая книга - чтобы отметиться, что был. Если вторая книга лежит лицом книзу - исполнитель ее переворачивает. Все, он уже отметился и теперь будет только переворачить первую ("холостую") книгу. Счетчик переворачивает вторую книгу, если она лицом кверху (т.е. фиксирует отметку), либо крутит первую. Счетчик должен достичь числа N переворачиваний (по одному за каждого другого узника + 1 переворачивание для подстраховки, если вторая книга изначально лежала лицом кверху)
                                                                                                                                                      0
                                                                                                                                                      думаю это правильный ответ, причем для любого кол-ва заключенных
                                                                                                                                                      он уже был в разных вариациях выше, но это пожалуй самая простая и универсальная формулировка
                                                                                                                                                        0
                                                                                                                                                        нет, вру. Решение неверно.
                                                                                                                                                        Если изначально лежали книги ВВ (верх верх) то заключенные перевернут их для счетчика 4 раза, а вот счетчик будет ждать пятого (ведь первый он "не засчитал", вдруг книги изначально лежали неверно) — проблема в том что он никогда не дождется, ведь все уже перевернули книгу-счетчик и не имеют более права это делать
                                                                                                                                                          0
                                                                                                                                                          Ммм... согласен.
                                                                                                                                                        0
                                                                                                                                                        нет. количество срабатываний должно быть (N-1)*2, иначе не получится.
                                                                                                                                                          0
                                                                                                                                                          угу. по одному дополнительному перевороту для страховки. Т.е. каждый переворачивает не более двух раз.
                                                                                                                                                          PS. Значит, счетчики в данной задаче - все заключенные. А я-то сперва думал, именно пятый должен был быть самым умным (или просто грамотным) ... :)
                                                                                                                                                        0
                                                                                                                                                        уточняйте, попадет ли хоть один из зеков больше одного раза в комнату:
                                                                                                                                                        или возможен вариант, что всех в один день по одному разу отвели в комнату и дело с концом?
                                                                                                                                                        Вариант со счетчиками недееспособен, без повторяемости...
                                                                                                                                                          0
                                                                                                                                                          Вы меня опередили :)
                                                                                                                                                          0
                                                                                                                                                          Я так думаю что мы не используем одно очень важное условие. Это то что время таки дискретно и измерятеся в днях.

                                                                                                                                                          Щас подумаю и попробую придумать что то с днями.
                                                                                                                                                            0
                                                                                                                                                            Вообще-то, я в предложенной выше стратегии использовал это условие...
                                                                                                                                                              0
                                                                                                                                                              Выбирать заключенных я буду как мне хочется: например, сегодня первого три раза свожу, а завтра всех по очереди, а послезавтра обойдетесь.
                                                                                                                                                              0
                                                                                                                                                              Каждый заключённый когда первый раз туда попадает отрывает (загибает уголок и т.п.) по 1 странице с книги, когда в книгах не будет хватать 5 страниц - они все там побывали
                                                                                                                                                                0
                                                                                                                                                                я это предлагал уже
                                                                                                                                                                  0
                                                                                                                                                                  ага, значит можно решить поварачивая книги на определённую вечелену всякий раз когда ты первый раз касаешься книги, и когда она будет видно, что поворот сделало 5 человек, то кричать "ура я свободен"
                                                                                                                                                                0
                                                                                                                                                                В условии пропущен один важный момент, который делает правильную стратегию бесполезной:
                                                                                                                                                                >> Рано или поздно каждый из вас побывает в Ленинской комнате и не один раз.
                                                                                                                                                                Проще говоря, при времени стремящемся к бесконечности каждый побывает в комнате количество раз стремящееся к бесконечности.
                                                                                                                                                                  0
                                                                                                                                                                  Счетчики нафиг! Необходимо выделить следящего и обозначить протокол передачи ему информации о побывавших в камере.
                                                                                                                                                                  Каждый информатор старается сообщить о себе (оставив Маркса лицом), если перед ним это не сделал другой информатор и следящий не обозначил, что он это принял (Маркс жопой). Иначе он ждет своей очереди. Соответственно следящий считает, сколько там уже побывали. В первый день не учитывается никто и к началу второго дня Маркс должен лежать жопой, чтобы следящий, зайдя в комнату в первый день, не воспринял случайный сигнал за истинный.
                                                                                                                                                                    0
                                                                                                                                                                    >> Счетчики нафиг!
                                                                                                                                                                    >> Соответственно следящий считает, сколько там уже побывали

                                                                                                                                                                    Вы уж определитесь, чтоли :)
                                                                                                                                                                    +1
                                                                                                                                                                    Проблема счетчика

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

                                                                                                                                                                        --- Рано или поздно каждый из вас побывает в Ленинской комнате.---
                                                                                                                                                                        0
                                                                                                                                                                        Согласен, ваш пост забивает последний гвоздь в гроб идеи со счетчиком.
                                                                                                                                                                        Получается что всех могут сводить по разу подряд и больше не водить вообще и при этом задача должна иметь решение...
                                                                                                                                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                                                                          –1
                                                                                                                                                                          отстой
                                                                                                                                                                            –1
                                                                                                                                                                            Мое решение с PHP-кодом:


                                                                                                                                                                            Чем то мне это напоминает T-Триггер http://ru.wikipedia.org/wiki/%D0%A2%D1%8…(%D1%8D%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%B8%D0%BA%D0%B0)#T-.D1.82.D1.80.D0.B8.D0.B3.D0.B3.D0.B5.D1.80

                                                                                                                                                                            все основано на операции not и соблюдении четности,
                                                                                                                                                                            можно красиво сделать через операторы ~ и <<, но мне лень ;)



                                                                                                                                                                            $test = new test();
                                                                                                                                                                            $test->run();

                                                                                                                                                                            class test
                                                                                                                                                                            {
                                                                                                                                                                            public $currentBookState = '01'; // Расположение книг первоначальное
                                                                                                                                                                            public $order = array(1,2,1,1,3,4,5,1); // Очередность пускания Зеков к книгам

                                                                                                                                                                            function run()
                                                                                                                                                                            {
                                                                                                                                                                            $zekMemory = array(); // память зека, какую комбинацию он увидел при входе
                                                                                                                                                                            $zekBinMemory = array(); // сколько раз был у книг

                                                                                                                                                                            foreach ($this->order as $zek) {

                                                                                                                                                                            $zekBinMemory[$zek] = intval($zekBinMemory[$zek]) + 1;

                                                                                                                                                                            if (isset($zekMemory[$zek]) // Если зек здесь был
                                                                                                                                                                            && $this->invertor($this->currentBookState) == $zekMemory[$zek] // если он видел эту комбинацию
                                                                                                                                                                            && $zekBinMemory[$zek] % 2 == 0 // И если это не он снова пришел (N-раз подряд)
                                                                                                                                                                            ) {
                                                                                                                                                                            echo "Zek #{$zek}: We are free!!!\n";
                                                                                                                                                                            break;
                                                                                                                                                                            }

                                                                                                                                                                            // Если мы в первый раз, то запоминаем комбинацию книг
                                                                                                                                                                            if (!isset($zekMemory[$zek])) {
                                                                                                                                                                            echo "Zek #{$zek}: I'm here at first time; I see: {$this->currentBookState}, I made: " .$this->invertor($this->currentBookState). " \n";
                                                                                                                                                                            $zekMemory[$zek] = $this->currentBookState;
                                                                                                                                                                            $this->currentBookState = $this->invertor($this->currentBookState);
                                                                                                                                                                            } else {
                                                                                                                                                                            echo "Zek #{$zek}: I'm here was {$zekBinMemory[$zek]} times; I see: {$this->currentBookState}, I made: " .$this->invertor($this->currentBookState). " \n";
                                                                                                                                                                            $this->currentBookState = $this->invertor($this->currentBookState);
                                                                                                                                                                            }

                                                                                                                                                                            }
                                                                                                                                                                            }

                                                                                                                                                                            /**
                                                                                                                                                                            * Простеццкий инвертор
                                                                                                                                                                            */
                                                                                                                                                                            function invertor($val)
                                                                                                                                                                            {
                                                                                                                                                                            switch ($val) {
                                                                                                                                                                            case '00':
                                                                                                                                                                            return '01';
                                                                                                                                                                            case '01':
                                                                                                                                                                            return '11';
                                                                                                                                                                            case '11':
                                                                                                                                                                            return '10';
                                                                                                                                                                            case '10':
                                                                                                                                                                            return '00';
                                                                                                                                                                            }
                                                                                                                                                                            }
                                                                                                                                                                            }

                                                                                                                                                                            ?>


                                                                                                                                                                            Результат кода:

                                                                                                                                                                            bash-3.1#php test.php
                                                                                                                                                                            Zek #1: I'm here at first time; I see: 01, I made: 11
                                                                                                                                                                            Zek #2: I'm here at first time; I see: 11, I made: 10
                                                                                                                                                                            Zek #1: I'm here was 2 times; I see: 10, I made: 00
                                                                                                                                                                            Zek #1: I'm here was 3 times; I see: 00, I made: 01
                                                                                                                                                                            Zek #3: I'm here at first time; I see: 01, I made: 11
                                                                                                                                                                            Zek #4: I'm here at first time; I see: 11, I made: 10
                                                                                                                                                                            Zek #5: I'm here at first time; I see: 10, I made: 00
                                                                                                                                                                            We are free!!!

                                                                                                                                                                              0
                                                                                                                                                                              Zek #1: I'm here at first time; I see: 01, I made: 11
                                                                                                                                                                              Zek #1: I'm here was 2 times; I see: 11, I made: 10
                                                                                                                                                                              Zek #1: I'm here was 3 times; I see: 10, I made: 00
                                                                                                                                                                              Zek #1: We are free!!!
                                                                                                                                                                                0
                                                                                                                                                                                Zavedyshiy #0: No, you are dead!!! ha-ha-ha!
                                                                                                                                                                              0
                                                                                                                                                                              - час рабочего времени на рисование диаграмм переходов, в результате пришел к тому как в http://habrahabr.ru/blog/zadachki/42678.html#comment862945
                                                                                                                                                                                0
                                                                                                                                                                                Думается решение следующее...
                                                                                                                                                                                Зеки выбирают счетчика. Когда обычный зек заходит в комнату в первый раз - переворачивает маркса лицом вниз, если маркс уже лежит так - то ждет следующего раза, и крутит энгельса. Каждый зек должен перевернуть маркса лицов вниз ровно один раз. Счетчик переворачивает маркса лицом вверх и считает +1, когда насчитает N+1 - все свободны. По условиям задачи время отсидки неограничено - значит рано или поздно счетчик насчитает нужное количество
                                                                                                                                                                                  0
                                                                                                                                                                                  Время не ограничено, но начальник может больше не пускать счетчика никогда.
                                                                                                                                                                                    0
                                                                                                                                                                                    ну он не знает кто счетчик ))) так что шансы есть
                                                                                                                                                                                      0
                                                                                                                                                                                      Ему это и не нужно, он просто по условию может так сделать.
                                                                                                                                                                                    0
                                                                                                                                                                                    Читаем комменты сверху. Что будете делать, если Маркс УЖЕ лежит лицом вниз? Счетчик засчитает лишнюю попытку
                                                                                                                                                                                      0
                                                                                                                                                                                      И что? Ведь считаем до n+1
                                                                                                                                                                                        0
                                                                                                                                                                                        А если он лицом кверху? Каждый перевернет, получится N. Больше никто переворачивать не будет.
                                                                                                                                                                                    0
                                                                                                                                                                                    Гы, http://www.eruditor.ru/z/?29

                                                                                                                                                                                    И ответ: http://www.eruditor.ru/f/?z=29
                                                                                                                                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                                                                                        0
                                                                                                                                                                                        Самая большая проблема в том, что не известно начально положение книг. Если предположить, что обе книги лежат лицом вверх и корешком влево, тогда получается 16 состояний и известно 1-е.
                                                                                                                                                                                        Из каждого состояния можно сделать 4 перехода, 2 из которых оставляют состояние в той же 4-ке сотосяний, а одно позволяет перейти в следующую 4-ку. 1 вошедший переводит текущее состояние в состояние из 2-ой 2-ки (например в 4) и если он снова заходи в следующий раз он оставляет состояние из второй двойки, входит 2-й и переводит в состояние из 2-ой четверки, и так далее. Когда последний 5-й человек зайдет - он увидит что состояние из 4-ой 4-ки и, перевернув книгу как угодно, скажет: "Я 5-й и остальные 4-ро уже здесь побывали"

                                                                                                                                                                                        Таблица переходов http://konnikov.ru/temp/images/zeki.png
                                                                                                                                                                                          0
                                                                                                                                                                                          Вот наглядная таблица состояний
                                                                                                                                                                                          http://konnikov.ru/temp/images/zeki-state.png
                                                                                                                                                                                          0
                                                                                                                                                                                          Да, ребята. Зеки из вас — никакие!
                                                                                                                                                                                            0
                                                                                                                                                                                            Я вот лично не вижу в этом ничего страшного
                                                                                                                                                                                            0
                                                                                                                                                                                            К а п и т а л А н т и - Д ю р и н г
                                                                                                                                                                                            1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
                                                                                                                                                                                            Каждый приходящий знает отмечал он букву или нет. Если не отмечал, то просто переворачивает книгу и уголком этой книги отмечает ту следующую букву. Если отмечал - переворачивает и оставляет на том же месте.
                                                                                                                                                                                            При наличии имен авторов на титульной странице, можно больше человек спасти от фрика-начальника концлагеря :).
                                                                                                                                                                                            з.ы. от 0 до 1 людей понадобится, чтобы убедиться что, хотя бы одна книга лежит титульным листом вверх
                                                                                                                                                                                              0
                                                                                                                                                                                              Их блин 19 человек с целым вечером на составление плана. Составить план и бежать, бежать из этого концлагеря с маньяком-начальником! :)
                                                                                                                                                                                                0
                                                                                                                                                                                                Я понимаю, что задача на логику и т.п.
                                                                                                                                                                                                Но если подойти к задаче по другому.
                                                                                                                                                                                                возраст заключенных возьмем 20 лет.
                                                                                                                                                                                                вероятность того, что они проживут больше 50 лет = 0.01%, приравниваем 0
                                                                                                                                                                                                остаток жизни 30 лет.
                                                                                                                                                                                                Вероятность того, что начальник заведет всех в течении 10 лет = 100%
                                                                                                                                                                                                В противном случае теряется смысл.
                                                                                                                                                                                                Если решение не найдено и:
                                                                                                                                                                                                Если срок 10 лет, соглашаемся и через 10 лет говорим, что мы все были.

                                                                                                                                                                                                А теперь серьезно:
                                                                                                                                                                                                Автор задачи все время упирает на то, что переворота книг достаточно.
                                                                                                                                                                                                Из этого следует, что мы имеем, как уже многие говорили 4 состояния:
                                                                                                                                                                                                00, 01, 10, 11
                                                                                                                                                                                                00 и 01 – нулевой уровень (обнуляет только счетчик)
                                                                                                                                                                                                11 или 10 – я впервые отметился (все остальные поддерживают это состояние, до обнуления)

                                                                                                                                                                                                01 и 10 превращается только в 00 или 11
                                                                                                                                                                                                00 и 11 превращается только в 01 или 10

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

                                                                                                                                                                                                Короче говоря, все варианты уже тут перебрали и без меня.
                                                                                                                                                                                                Ждем ответа автора.
                                                                                                                                                                                                  0
                                                                                                                                                                                                  А почему состояний 4? Имхо их все же 16 - есть же еще корешок книжки, и он может быть как слева так и справа! Повторюсь, но все же http://konnikov.ru/temp/images/zeki-state.png
                                                                                                                                                                                                  0
                                                                                                                                                                                                  решение для любого(!) количества заключённых:

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

                                                                                                                                                                                                  * во всех остальных случаях переворачивается первая книга.

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

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

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

                                                                                                                                                                                                  если что непонятно - поясню.
                                                                                                                                                                                                    0
                                                                                                                                                                                                    Хм, а если в исходное позиции вторая книга уже была перевёрнута? тогда счётчик насчитает на единицу больше, следовательно он скажет, что все уже прошли, но на самом деле один человек ещё не прошёл. Как бороться с этим?
                                                                                                                                                                                                      0
                                                                                                                                                                                                      а я кажется додумался, как с этим бороться! =)

                                                                                                                                                                                                      По твоему решению заключённый должен ставить маркер только один раз. Если заставить их ставить маркер два раза, то когда счётчик сделает 2*X (X - колличество заключённых) обнуления маркера, он сможет с полной уверенностью сказать, что в комнате хотя бы по разу побывали все (или каждый "поставил маркер" по два раза, или в самом начале книга уже была перевёрнута, и один из заключённых поставил маркер один раз)