Примитивная логика и кодирование информации

    Итак, довольно давно я столкнулся с довольно интересной задачкой:
    Подлые оккупанты захватили деревню мегамозгов, выстроили их друг за другом в колонну так, что каждый предыдущий видит всех последующих. На каждого мегамозга надели колпак черного или белого цвета так, что ни один мегамозг не видит свой колпак. Начиная с самого последнего (того, который видит всех кроме себя) у каждого мегамозга по очереди спрашивают цвет его шляпы, если он ошибается, его убивают. Но как раз на этот случай мегамозги заранее договорились, как минимизировать число убитых. О чем договорились мегамозги?
    (все ссылаются на braingames.ru, но на самом деле этот сайт — подлый плагиатор, задачка древняя, они переделали ее под свою специфику, — добавили везде мегамозгов, — и выдали за собственную)
    Вначале казалось что половина убитых — радость для этой деревни. Но, немного подумав, я натолкнулся (одна девушка меня натолкнула) на довольно простое решение: мозги заранее договариваются и если цвет впереди стоящего белый, то произносится свой цвет (извини, первый мегамозг, ты в 50% случаев умрешь...) громко, иначе — тихо. Но это — примитив, хотя уже дает результат вдвое лучший — 99 мегамозгов останутся живы.
    Теперь мой окончательный вариант: последний, который видит всех, считает парность, например, чёрных. Если получилось парное, говорит, что он чёрный. Он, к сожалению единственный, кто рискует погибнуть. Следующий считает парность чёрных, если парно — он белый (количество чёрных не изменилось), иначе — чёрный, следующий аналогично.

    Поразило меня в решении этой задачи то, что достигнут поистине поражающий результат — вначале казалось, что спасти хотя бы больше 50% — отличный результат, однако, пожертвовав жизнью всего лишь одного из мегамозгов (в 50% случаев) можно гарантированно спасти всех остальных!

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

      0
      А почему нельзя просто говорить цвет предыдущего мегамозга. Эффект тот же.
        0
        Вы не можете посмотреть назад, иначе будете убиты. Из условия.
          0
          Прошу прощения, он говорит цвет последущего. Тогда даже остальных видеть не надо. Или я что-то в условии не понял
            0
            чбчбчб....
            Каждый говорит цвет последующего и умирают все.
              0
              Да, действительно.. Совсем мне плохо думается..
              0
              Все правильно. Говоримцвет последующего и все кроме первого знают свой цвет. Первому может только 50/50 повезти.
                +3
                чбчбчб
                Первый черный говорит "белый". Его убивают. Второму, тот который белый, что делать? Сказать, что он белый? Тогда следующий не будет знать своего цвета! При таком подходе умрут в среднем 50% мозгов
                  0
                  Я именно это и имел в виду. Первый умирает с пятидесятипроцентной вероятностью, остальный знают свой цвет. Дополнительное условие. Не нужно знать цвет всех предыдущих, достаточно одного.
                    0
                    Читай что пишет propovednik ;)
                      0
                      Прошу прощения, затупил! Propovednik абсолютно прав. Заслуженный плюс)
                        0
                        понедельника вечер как никак :)
                0
                в правильном условии они должны говорить, с конца, то есть первым говорит свой цвет тот, кто видит всех, а тогда спасаются все кроме одного, самого последнего в шеренге потомучто математика - великая сила :)
                  0
                  цитата из условия: "Начиная с самого последнего (того, который видит всех кроме себя)"
                    0
                    тупанул, сорри :)
              0
              ну что вы все в самом деле :)
              принимаем черный цвет за 1 белый за 0.
              один говорит сумму всех цветов по модулю 2. следующий зная сумму всех (кроме того кто уже говорил), и туже сумму за минусом себя, элементарно находит свой цвет. спасаются все кроме одного.
              более того задача точно так же расширяется на любое конечное количество мегамозгов (или как их там), и на любое конечное число цветов :)
                0
                а если их поставить по кругу, то каждый будет знать свой цвет уже после того как первый сказал.
                да и в задаче там, если ох поставили друг за другом, то первым должен говорить тот, кто стоит самым последним.
                  0
                  Ммм... зря вы так! Зря! Следующей я хотел представить на суд публике такую же задачу с 7 цветами, но формализовав решение она уже будет неинтересна. Но Вы меня опередили :) несмотря на вечер понедельника
                    0
                    да что уж там, 7 цветов... надо было все RGB делать :)
                    и мозгов, скажем, 4М :))
                    а вперве я услышал эту задачку про гномиков и гномоеда :) типа он их съест если гномики не угадают свой цвет, представишь этих маленьких гномиков, и сразу же решить хочется все на свете :)
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Последний говорит - "нуль". Предпоследний говорит - "один" (ибо перед ним нечётное число единиц). Следующий говорит - "нуль" (потому что последний сказал "нуль", предпоследний - "один", а перед ним - нечётное число единиц). Следующий говорит - "один" (ибо последний сказал "нуль", предпоследний - "один", следующий за ним - "нуль", а впереди - две единицы). Общая сумма (цвета, названые всеми предыдущими гномиками плюс то что ты видишь плюс то что ты назовёшь) должна быть чётной.

                      Объяснять это долго, но на практике всё просто: каждый считает число единиц, находящихся перед ним и если оно чётное - "загадывает" 0, если нечётное - "загадывает" 1. Последний свою догадку выдаёт. Все остальные его слушают и если сказана 1 - догадку меняют на противоположную, если сказан 0 - не меняют. Когда до них доходит очередь - они эту догадку выдают. Заметим что алгоритм не выделяет последнего на самом деле: просто он ни разу свою догадку не меняет и выдаёт то, что есть - а там: как повезёт.
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      перед ним 0 белых и 0 черных. 0 - такое же число, как все другие целые числа.
                      0
                      Кстати, в условии не сказано, что колпаков поровну.)
                        0
                        Это не имеет значения. Можно объяснить всё без теории колец. Последний видит всех. Своим ответом он сообщает, чётное или нечётное количество чёрных колпаков впереди него. Следующий видит все колпаки впереди. Если он видит (например) нечётное их количество, но перед этим было сказано, что их количество (например) чётное, значит, он в чёрном колпаке.

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

                          маленький мальчик загадал два различных числа. Оба строго больше 1 и строго меньше 100, натуральные. Одному мегамозгу он сказал сумму этих чисел, другому - их произведение. Прошла неделя, и два мегамозга встретились. Тот, кто знал произведение, говорит: - Ты знаешь, мне не хватает данных, чтобы определить, что за числа загадал маленький мальчик. - А я знал что тебе не хватит данных! - ответил тот, кто знал сумму. - Тогда я понял, что за числа он загадал... - сказал тот, кто знал произведение. - Тогдя и я понял... - сказал тот, кто знал сумму. Что за числа загадал маленький мальчик?
                            0
                            4 и 13. Находим их и доказываем, что других быть не может.
                              0
                              как????????????????????
                              можете обьяснить как блондинке которая в танке,почему именно эти числа?почему других быть не может??????????????????? пожалуйста)))))))))))))))))))))))))

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

                          Самое читаемое