Логическая головоломка
Кстати, может кто-нибудь посчитает кол-во различных стратегий для n<=20? Я посчитал только кол-во ... стратегий для n=3, получилось 24 
(без учёта симметрий)
(без учёта симметрий)какая-то кривая постановка.
сколько различных цветов используется для шапок?
сколько различных цветов используется для шапок?
не я писал, а переписывать заломало. 100 цветов, что ж тут непонятного. Можно считать, что используются не цветные шапки, а шапки с номерами от 1 до 100. Различных наборов шапок 100^100.
! << 100^100
и если уж 100 различных цветов, то задача тривиальна: каждый говорит номер, который он не видит.
или цвета могут повторятся?!
слушай, перепиши условие внятно, а?
и если уж 100 различных цветов, то задача тривиальна: каждый говорит номер, который он не видит.
или цвета могут повторятся?!
слушай, перепиши условие внятно, а?
блин, 100^100 наборов. То есть для каждого цвет выбирается совершенно случайным образом от 1 до 100, независимо от предыдущих.
непонятно, что могут предпринимать мудрецы после того, как на них надели шапки.
Непонятно, каким инструментарием они обладают. Непонятно, какие ещё ограничения наложены на задачу.
Вопрос: больше ограничений нет?
Непонятно, каким инструментарием они обладают. Непонятно, какие ещё ограничения наложены на задачу.
Вопрос: больше ограничений нет?
мудрецы могут до этого договориться о некоторой стратегии. После этого их выстраивают в 100-угольник,
они смотрят друг на друга(каждый видит только 99 шапок и их цвета, и на ком они сидят и должны записать свои guess-ы на бумашках. При этом информацией они друг с другом ни в каком виде не могут обмениваться. Ну а потом смотрят, угадали они или нет.
Если хочешь, можешь сам мой пост поправить, а то уже у нас ночь уже, я спать пойду скоро, а сонный я нормально его всё равно не поправлю.
Если не получается, сначала решите когда 2 мудреца и 2 цвета.
они смотрят друг на друга(каждый видит только 99 шапок и их цвета, и на ком они сидят и должны записать свои guess-ы на бумашках. При этом информацией они друг с другом ни в каком виде не могут обмениваться. Ну а потом смотрят, угадали они или нет.
Если хочешь, можешь сам мой пост поправить, а то уже у нас ночь уже, я спать пойду скоро, а сонный я нормально его всё равно не поправлю.
Если не получается, сначала решите когда 2 мудреца и 2 цвета.
обмен информаций "я записал ответ" - обмен информацией?
считай, что они одновременно и независимо пишут ответы, но имхо это никак не влияет на решение.
Ты же не можешь сказать, ЧТО ты записал. Иначе тривиально было бы.
Ты же не можешь сказать, ЧТО ты записал. Иначе тривиально было бы.
правильно, но я могу ждать.... и это ожидание означает "я типа не могу написать ответа, пока ты не напишешь". второй думает "типа он пока не знает, значит думаем...". можно квантануть время и такты считать..
перечитал условие.
переформулируем так: "должен угадать хотя бы один"
я решал несколько другую задачу
переформулируем так: "должен угадать хотя бы один"
я решал несколько другую задачу
можно квантануть время и такты считать..
Кто решит, не постите решение, пусть дальше думает, как бы ему ещё читернуть
а чё там читерить?
для двух игроков:
первый называет то, что он видит
второй называт то, что он не видит
для двух игроков:
первый называет то, что он видит
второй называт то, что он не видит
я вот надумал тут такое:
все чуваки пронумерованы.
если чувак с номером k видит цвет k, то он записывает херню какую-нить на бумажку. все видят, что чувак k начал писать и все остальные шустро записывают одно число - k. хоть кто-нить из них точно имеет шапку цвета k, поэтому все будет "харашо"
update:
если все умники тупят уже 5 минут, то все пишут цвет 1 =)
update2: решение идет врозь с "считай, что они одновременно и независимо пишут ответы". так что надо думать о другом решении
все чуваки пронумерованы.
если чувак с номером k видит цвет k, то он записывает херню какую-нить на бумажку. все видят, что чувак k начал писать и все остальные шустро записывают одно число - k. хоть кто-нить из них точно имеет шапку цвета k, поэтому все будет "харашо"
update:
если все умники тупят уже 5 минут, то все пишут цвет 1 =)
update2: решение идет врозь с "считай, что они одновременно и независимо пишут ответы". так что надо думать о другом решении
то, что кто-то что-то записал и сам факт записи автором расценивается как обмен информацией.
класс!
тем более не рассмотрен случай, когда каждый чувак с номером К имеет цвет К
но при таком решении есть возможность "не отгадать", если шапки одеты соответственно 1-1, 2-2... k-k,... n-n, - хана.
ну ты меня понял 
вот рассматриваю: если все умники тупят уже 5 минут, то все пишут цвет 1 =)
постановка кривая. автор хотел другого, а именно:
их привели в комнату, показали друг-дружке (всех разом развели по камерам и сказали: пишите.
их привели в комнату, показали друг-дружке (всех разом развели по камерам и сказали: пишите.
в этой постановке никто не выживет
задача: угадать хотя бы одному.
я показал как так сделать для двоих
я показал как так сделать для двоих
Когда постить-то решение можно будет
Кто решит, не постите решение, пусть дальше думает, как бы ему ещё читернуть
?мне в приват напиши, я скажу, правильно или нет.
update : вот и есть один решивший без квантований и суперструн
update2 : 2 решили. Без суперструн.
Да, считайте, что им показали на ком какие шапки и увели в камеры. И там они пишут свои ответы. Нету обмена информацией !
update : вот и есть один решивший без квантований и суперструн
update2 : 2 решили. Без суперструн.
Да, считайте, что им показали на ком какие шапки и увели в камеры. И там они пишут свои ответы. Нету обмена информацией !
посчитал ко-во стратегий, для n=3 >= 24(нашёл 24 для n=4 >= 1536(они все особого вида).
Дальше, думаю, моя тупая прога сдохнет. Если её оптимизировать, может быть для n=5, 6, 7 посчитает, а потом всё равно подохнет.
Дальше, думаю, моя тупая прога сдохнет. Если её оптимизировать, может быть для n=5, 6, 7 посчитает, а потом всё равно подохнет.
Очень подозрительно твои числа делятся на n!. Есть ощущение, что часть из творих стратегий - это просто перестановка местами мудрецов в других стратегиях )
посчитал ко-во стратегий, для n=3 >= 24(нашёл 24 для n=4 >= 1536(они все особого вида).
да, так и есть. Я считал только линейные стратегии и тупо в лоб, без учёта перестановок.
Как их учесть, чтобы сократить счёт в проге — не знаю, ибо тупой и не думал.
Но меня совершенно убило, что есть решения отличные от того, которое очень простое.
Как их учесть, чтобы сократить счёт в проге — не знаю, ибо тупой и не думал.
Но меня совершенно убило, что есть решения отличные от того, которое очень простое.
Впрочем очень похоже на
n! * 2^n-2n-1
n! * 2^n-2n-1
up!
решение все же интересно.
напишите его.
решение все же интересно.
напишите его.
Всё делается в кольце Z_n,
i-й мудрец говорит f_i=i-(x_1+x_2+...+x_{i-1}+x_{i+1}+x_n (-1)=n-1 если быть совсем точным.
Тогда x_i-f_i=s-i, где s — сумма всех шапок. s-i пробегает все значения, значет где-то есть 0, то есть угадали.
i-й мудрец говорит f_i=i-(x_1+x_2+...+x_{i-1}+x_{i+1}+x_n (-1)=n-1 если быть совсем точным.
Тогда x_i-f_i=s-i, где s — сумма всех шапок. s-i пробегает все значения, значет где-то есть 0, то есть угадали.
Народ, а они о стратегии могут договариваться зарание?
У Вас 3 часа на раздумье ... Вот Вам бумага, карандаши ... . Завтра каждому наденут ...
все пишут один цвет
i-й мудрец говорит f_i=i-(x_1+x_2+...+x_{i-1}+x_{i+1}+x_n (-1)=n-1 если быть совсем точным.
Тогда x_i-f_i=s-i, где s — сумма всех шапок. s-i пробегает все значения, значет где-то есть 0, то есть угадали.
не понимаю
f_i - это цвет шапки у данного мудреца или что?
что значит (-1)=n-1?
Если 2 человека, у каждого по 2 колпака: черный и белый. Вот стою я в черном, а человек напротив в белом, как глядя на него я могу сделать вывод, что у меня черный? Ведь цвет моего колпака никак не зависит от цвета его колпака? Я наверное что-то кардинально не понимаю, можешь объяснить на примере 2 человек на пальцах, а не формулами?
Про двух писали. Один говорит цвет, который видит на втором. Второй говорит цвет, обратный к тому, что видит. Тогда если у них одинакового цвета колпаки - первый угадает свой, если разного - второй.
на примере 2 человек на пальцах
Аналогично, когда народу больше, всегда (по стратегии Avova) ровно один "угадает" свой цвет.
f_i это его догадка. x_i это цвета шапок. По условию f_i можно брать любую функцию, которая не зависит от x_i.
да клевая задачка)
люблю такие
люблю такие
vitamin8808
Фараон решил проверить, стоит ли ему кормить своих 100 мудрецов, или пришло время заменить. Он заказал шапки ста цветов, по 100 шапок на мудреца(про запас собрал мудрецов и сказал:У Вас 3 часа на раздумье и договор. Вот Вам бумага, карандаши (фараон, естественно, был новохронологический, продвинутый). Завтра каждому наденут на голову шапку - какого цвета - Вы знать каждый про себя не будете. Для одного мудреца 100 вариантов, для всех ста — 100^100 вариантов различных шапкований. И покажут каждому всех других(то есть они будут стоять не как в известной задаче в линию, а в 100-угольнике, каждый видит все 99 шапок, кроме своей). И каждый должен написать - какого цвета шапка на нём(любой обмен информацией между мудрецами запрещён, их попросту разводят по камерам и там они пишут свои догадки ). Если хоть один напишет правильно - будете жить и продолжать служить. Нет - всем отрубят головы.
Вопрос - могут ли мудрецы гарантированно сохранить свои головы и содержание?
Чтобы вас окончательно запутать, скажу что возможных стратегий, по видимому, очень много Ж)
Но есть одна очень простая.