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