Логическая головоломка

vitamin8808

Фараон решил проверить, стоит ли ему кормить своих 100 мудрецов, или пришло время заменить. Он заказал шапки ста цветов, по 100 шапок на мудреца(про запас собрал мудрецов и сказал:
У Вас 3 часа на раздумье и договор. Вот Вам бумага, карандаши (фараон, естественно, был новохронологический, продвинутый). Завтра каждому наденут на голову шапку - какого цвета - Вы знать каждый про себя не будете. Для одного мудреца 100 вариантов, для всех ста — 100^100 вариантов различных шапкований. И покажут каждому всех других(то есть они будут стоять не как в известной задаче в линию, а в 100-угольнике, каждый видит все 99 шапок, кроме своей). И каждый должен написать - какого цвета шапка на нём(любой обмен информацией между мудрецами запрещён, их попросту разводят по камерам и там они пишут свои догадки ). Если хоть один напишет правильно - будете жить и продолжать служить. Нет - всем отрубят головы.
Вопрос - могут ли мудрецы гарантированно сохранить свои головы и содержание?
Чтобы вас окончательно запутать, скажу что возможных стратегий, по видимому, очень много Ж)
Но есть одна очень простая.

vitamin8808

Кстати, может кто-нибудь посчитает кол-во различных стратегий для n<=20? Я посчитал только кол-во ... стратегий для n=3, получилось 24 (без учёта симметрий)

kachokslava

какая-то кривая постановка.
сколько различных цветов используется для шапок?

vitamin8808

не я писал, а переписывать заломало. 100 цветов, что ж тут непонятного. Можно считать, что используются не цветные шапки, а шапки с номерами от 1 до 100. Различных наборов шапок 100^100.

kachokslava

! << 100^100
и если уж 100 различных цветов, то задача тривиальна: каждый говорит номер, который он не видит.
или цвета могут повторятся?!
слушай, перепиши условие внятно, а?

vitamin8808

блин, 100^100 наборов. То есть для каждого цвет выбирается совершенно случайным образом от 1 до 100, независимо от предыдущих.

kachokslava

непонятно, что могут предпринимать мудрецы после того, как на них надели шапки.
Непонятно, каким инструментарием они обладают. Непонятно, какие ещё ограничения наложены на задачу.
Вопрос: больше ограничений нет?

vitamin8808

мудрецы могут до этого договориться о некоторой стратегии. После этого их выстраивают в 100-угольник,
они смотрят друг на друга(каждый видит только 99 шапок и их цвета, и на ком они сидят и должны записать свои guess-ы на бумашках. При этом информацией они друг с другом ни в каком виде не могут обмениваться. Ну а потом смотрят, угадали они или нет.
Если хочешь, можешь сам мой пост поправить, а то уже у нас ночь уже, я спать пойду скоро, а сонный я нормально его всё равно не поправлю.
Если не получается, сначала решите когда 2 мудреца и 2 цвета.

kachokslava

обмен информаций "я записал ответ" - обмен информацией?

vitamin8808

считай, что они одновременно и независимо пишут ответы, но имхо это никак не влияет на решение.
Ты же не можешь сказать, ЧТО ты записал. Иначе тривиально было бы.

kachokslava

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

kachokslava

перечитал условие.
переформулируем так: "должен угадать хотя бы один"
я решал несколько другую задачу

vitamin8808

можно квантануть время и такты считать..

Кто решит, не постите решение, пусть дальше думает, как бы ему ещё читернуть

kachokslava

а чё там читерить?
для двух игроков:
первый называет то, что он видит
второй называт то, что он не видит

incwizitor

я вот надумал тут такое:
все чуваки пронумерованы.
если чувак с номером k видит цвет k, то он записывает херню какую-нить на бумажку. все видят, что чувак k начал писать и все остальные шустро записывают одно число - k. хоть кто-нить из них точно имеет шапку цвета k, поэтому все будет "харашо"
update:
если все умники тупят уже 5 минут, то все пишут цвет 1 =)
update2: решение идет врозь с "считай, что они одновременно и независимо пишут ответы". так что надо думать о другом решении

kachokslava

то, что кто-то что-то записал и сам факт записи автором расценивается как обмен информацией.

chel_1992

класс!

kachokslava

тем более не рассмотрен случай, когда каждый чувак с номером К имеет цвет К

chel_1992

но при таком решении есть возможность "не отгадать", если шапки одеты соответственно 1-1, 2-2... k-k,... n-n, - хана.

chel_1992

ну ты меня понял

incwizitor

вот рассматриваю: если все умники тупят уже 5 минут, то все пишут цвет 1 =)

kachokslava

постановка кривая. автор хотел другого, а именно:
их привели в комнату, показали друг-дружке (всех разом развели по камерам и сказали: пишите.

ARTi

в этой постановке никто не выживет

kachokslava

задача: угадать хотя бы одному.
я показал как так сделать для двоих

a101



Кто решит, не постите решение, пусть дальше думает, как бы ему ещё читернуть
Когда постить-то решение можно будет ?

vitamin8808

мне в приват напиши, я скажу, правильно или нет.
update : вот и есть один решивший без квантований и суперструн
update2 : 2 решили. Без суперструн.
Да, считайте, что им показали на ком какие шапки и увели в камеры. И там они пишут свои ответы. Нету обмена информацией !

vitamin8808

посчитал ко-во стратегий, для n=3 >= 24(нашёл 24 для n=4 >= 1536(они все особого вида).
Дальше, думаю, моя тупая прога сдохнет. Если её оптимизировать, может быть для n=5, 6, 7 посчитает, а потом всё равно подохнет.

a101



посчитал ко-во стратегий, для n=3 >= 24(нашёл 24 для n=4 >= 1536(они все особого вида).
Очень подозрительно твои числа делятся на n!. Есть ощущение, что часть из творих стратегий - это просто перестановка местами мудрецов в других стратегиях )

vitamin8808

да, так и есть. Я считал только линейные стратегии и тупо в лоб, без учёта перестановок.
Как их учесть, чтобы сократить счёт в проге — не знаю, ибо тупой и не думал.
Но меня совершенно убило, что есть решения отличные от того, которое очень простое.

a101

Впрочем очень похоже на
 
n! * 2^n-2n-1

incwizitor

up!
решение все же интересно.
напишите его.

vitamin8808

Всё делается в кольце 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, то есть угадали.

baa4504

Народ, а они о стратегии могут договариваться зарание?

vitamin8808

У Вас 3 часа на раздумье ... Вот Вам бумага, карандаши ... . Завтра каждому наденут ...

sashachist

все пишут один цвет

Lena64


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 человек на пальцах, а не формулами?

a101



на примере 2 человек на пальцах
Про двух писали. Один говорит цвет, который видит на втором. Второй говорит цвет, обратный к тому, что видит. Тогда если у них одинакового цвета колпаки - первый угадает свой, если разного - второй.

Аналогично, когда народу больше, всегда (по стратегии Avova) ровно один "угадает" свой цвет.

vitamin8808

f_i это его догадка. x_i это цвета шапок. По условию f_i можно брать любую функцию, которая не зависит от x_i.

incwizitor

да клевая задачка)
люблю такие
Оставить комментарий
Имя или ник:
Комментарий: