Мне задачу рассказала Лена Бунина, которой в свою очередь её рассказал П.Е. Пушкарь. Мне понадобилось несколько дней, чтобы решить. Особенно интересно, сможет ли её решить кто-нибудь не с мехмата.
Итак задача:
Есть бесконечно много узников (счётное число), пронумерованных натуральными числами. Каждый узник знает все номера, в том числе свой. Узники умеют бесконечно быстро думать, и у них бесконечно много памяти. Сначала у них есть время на обсуждение алгоритма.
Их выстраивают по порядку, так что первый смотрит в спину второго, второй в спину третьего и т.д. На них одновременно надевают колпаки двух цветов. Каждый узник видит, какие колпаки надеты на узниках с большими номерами (первый видит все колпаки, кроме своего, второй — все, кроме своего и первого и т.д.). Никакой информацией они уже не обмениваются. Дальше каждый из них должен одновременно со всеми сказать, какой на нём колпак. Кто не угадает — того расстреливают. Как сделать так, чтобы лишь конечное число узников расстреляли?
8 comments:
пока что у меня есть стойкое ощущение, что где-то ошибка в условиях.
Знание инфы о колпаках остальных не дает никакой инфы о своем колпаке по условию. Больше никакой инфы не поступает.
Да, поэтому никакой отдельный узник не может узнать, какой колпак на нём. Но в задаче спрашивается о всей последовательности в целом (ВСЕГО ошибок должны быть конечное число).
В условии ошибки нет.
Юлька, представляйся :)
Нет никакой ошибки, хотя решения я ещё не нашёл :)
Так и что в итоге то ?
У меня в блоге недавно обсуждали эту задачу. В твоем варианте они знают свои номера?
Да, знают. Собственно, и решение у меня такое же.
Я эту задачку не решал, но у знакомый четверокур физтеха часов за 5 в поезде ее раскрутил
Post a Comment