Логические задачи → Злобные оккупанты 2

10 февраля 2008 | Добавил: Serge

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

задача взята с сайта braingames.ru

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку

Версия для печати.
RSS комментариев записи.

Метки → логические

Комментариев: 8

sas пишет:
1 марта 2008 в 09:32

перечисленные цвета - цвета полос радуги. Мегамозги договорились вставать друг за другом в соответствии смены цветов радуги.
SusAnna пишет:
7 марта 2008 в 16:12

они не могут переходить и переговариваться
Serafim пишет:
11 мая 2009 в 03:34

Стоящий последним должен сказать цвет колпака того ММ, который стоит следующим.
Тогда тот может услышать свой цвет, и назвать его.
Таким образом получаем 50% смертность, что, конечно, очень жаль, но лучше, чем ничего))
Slavic пишет:
4 июня 2009 в 15:12

С точки зрения информации, в первой задаче про оккупантов говорящий мог передать следующему только 1 бит информации (чёрный или белый). На основе этого следующий делал вывод о цвете своего колпака. Чтобы описать цвет каждого колпака нужно 7 вариантов, а это три бита информации. Однако 7 вариантов ответа не хватает для полноценной передачи 3 бит (нужно 8).
Потому вят ли есть способ спасти опять же всех кроме первого гарантированно. Вот такая теория. Мой вариант:
всем цветам для легкости рассказа можно присвоить числа от 0 до 6. Первый ММ видит колпаки двух следующих и вычисляет разность между первым и вторым по модулю. Цвет соответствующий этой цифре он и называет. У него есть 1/7 шанс выжить. Далее второй ММ отнимает переданное число от номера цвета следующего, т.о. угадывает свой цвет. Третий складывает сумму чисел первого и второго. Получает свой цвет. Таким обазом гарантированно спасены 2/3 и есть шансы, что угадают 1/21 ММ.
Чтобы исключить ошибку из-за отрицательных чисел они замыкают круг от 0 до 6, т.е. если ММ видит, что у соседа цвет 2, а ему сказали цвет 4, то у него на голове цвет 5 (2-4=-2; учитывая нулевой цвет, получаем -1; 6-1 = 5)
Большее количество ни как не удалось спасти,и это при том, что я против насилия:)
Slavic пишет:
10 июня 2009 в 20:54

Желание спасти ММ не давало мне спать.
Нашел я таки изъян в своем ответе. Действительно 7-ми сигналов не хватает для передачи полных трёх бит информации, но зачем использовать вообще двоичную систему? Ответ оказался куда проще и прозаичнее. Опять же рискует только тот, кто видит всех остальных. Присваиваем каждому цвету число от 1 до 7 и считаем их сумму. Замыкаем систему исчисления, т.е. убираем из суммы максимальное число делящееся на 7, получаем номер цвета от 1 до 7. Так делает каждый ММ, считая сумму цветов, которые он видит. Получается, что первый называет цвет, который у него получился, а следующий считает разность между своим числом и числом первого. Так каждый получит номер своего цвета, начинаяя круг с 7-ми до 1 каждый раз, когда разность меньше нуля. Таким образом можно расширить задачу на любое число цветов.
Ещё мысли о вероятности умереть. Вероятность угадать для первого 1/7. Для остальных 100%. Поэтому как и в первой задачке из ста МегаМозгов умирает только один - герой. Почтим его память друзья:)
Slavic пишет:
10 июня 2009 в 21:18

Почти неделю я не мог уснуть мысля о спасении ММ.
И нашел таки изъян в своих рассуждениях. Действительно нельзя передать семью сигналами 3 бита, но это и не надо. Незачем пользоваться двоичной системой исчисления, это же МегаМозги а не роботы-вычислители.
Делаем так. Каждому цвету даём номер от 1 до 7. Каждый МегаМозг высчитывает сумму впереди стоящих цветов. Превый убирает из суммы максимальное число делящееся на 7 и получает номер цвета. Его и называет, т. о. он выживет с вероятностью 1/7. Второй считает разность между своей суммой и суммой первого, которая явно больше суммы второго и выражена с учетом вычитания максимального числа делящегося на 7. Т. о. второй получает разность, которая и является номером его цвета. Так делают все МегаМозги, спасаясь с вероятностью 100% если никто не накосячил.
Как и в первой задаче шанс погибнуть есть только у пеервого в ряду, ему всё-равно нечего терять, потому он и называет любой цвет.
Задачу можно расширять до любого мыслимого количества цветов (считать быстро МегаМозги смогут, спасая свою жизнь) и разумного количества МегаМозгов, чтобы они слышали ответы предидущих. Вот тут интересная мысль. Все Мегамозги, стоящие между первым и последним делают выводы на основе того, что сказал предидущий и того, что они видят. А вот последний должен либо слышать всех и тогда вычислить свой цвет, либо гадать, азначит шансов у него столько же сколько и у первого в ряду.
Вот теперь всех упас, кого возможно:) Оставшихся безимянных героев помянем, светлой им памяти.
P.S. удалите предидущее сообщение сеть глючит
Virtus пишет:
16 мая 2011 в 02:06

Предыдущий комментарий относится конечно к предыдущей задаче (Злобные оккупанты 1)
Для данной
6/7что погибнет последний, остальные спасутся!!!
Решение.
Нумеруем цвета от 0 до 6
Каждый считает остаток от деления на суммы перед собой!!!
Последний называет цвет как договорятся (возможны любые вариантыб например чбы остаток от деления на 7 суммы был равен 0) 1/7 что он угадает. Остальные видя всех предыдущих и зная ответ стоящего за ним просто вычисляют цвет.
Virtus пишет:
16 мая 2011 в 02:07

Извиняюсь за пропуск цифры
Каждый считает остаток от деления на 7 суммы всех перед собой!!!