Задача про мудрецов и разноцветные шляпы

[gris]

Написал числовую интерпретацию, а оказывается, что её уже написали и всё уже решили. А я пропустил:-(

[EUgeneUS]

grizzly в сообщении #1317992 писал(а):

Неужели есть сомнения, что в такой формулировке задача не имеет решения?

Есть сомнения. Пусть у нас есть 50 мудрецов и шапки 50-и оттенков серого. (Одномерный непрерывный случай).
Причем, какие именно оттенки серого будут\могут быть использованы мудрецам неизвестны.

Первый из мудрецов называет среднее серости шапок, которые он видит.
Остальные решают линейное уравнение и называют серость своей шапки.

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

[kotenok gav]

gris в сообщении #1317996 писал(а):

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

Я эту задачу видел в Квантике, решение приблизительно помню, могу написать в ЛС.

[grizzly]

EUgeneUS в сообщении #1317998 писал(а):

Есть сомнения. Пусть у нас есть 50 мудрецов и шапки 50-и оттенков серого. (Одномерный непрерывный случай).
Причем, какие именно оттенки серого будут\могут быть использованы мудрецам неизвестны.

Представил. Есть 1М оттенков серого. Известно, что на мудрецах шапки 50-и оттенков. Какие именно могут быть использованы -- неизвестно. Дальше я Ваших уравнений не понял.

[EUgeneUS]

grizzly

(выше, в update своего поста)

я признал, что при одновременном объявлении результатов вычислений, что было явно указано в стартовом сообщении, задача очевидно решений не имеет.

-- 07.06.2018, 20:57 --

gris
А при такой формализации, чем не устраивает решение уважаемого Sender?

[gris]

Ой, а я и не увидел. И ТС, оказывается, появлялся. Пардон

[Unconnected]

Набор цветов известен заранее, и их N штук. Разве это не то же самое, что и "N мудрецов и N цветов шляп"? Цвета шляп могут повторяться (т.е. могут всем N мудрецам надеть шляпу 1-го цвета). Я правильно понял, что есть мнение, что решения не имеется?
Да, мудрецы называют свой цвет одновременно.

Ув. Sender, Ваше решение учитывает, что цвета надетых шляп могут повторяться? Если да, то почему это работает?..

[mihaild]

Unconnected в сообщении #1318063 писал(а):

Набор цветов известен заранее, и их N штук.

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

Unconnected в сообщении #1318063 писал(а):

Ув. Sender, Ваше решение учитывает, что цвета надетых шляп могут повторяться?

Отвечу за него: да, учитывает.
Работает потому что сумма цветов всех шляп по модулю $N$ может принимать только одно из $N$ значений.

Если цветов хотя бы $n+1$, то гарантированного решения нет: наденем каждому случайный цвет; т.к. цвет, называемый $i$-м мудрецом, не зависит от его настоящего цвета, то вероятность угадать у него $\frac{1}{n + 1}$, значит в среднем угадывает $\frac{n}{n+1} < 1$ человек - значит, с ненулевой вероятностью не угадывает ни один.

[kotenok gav]

Sender в сообщении #1317914 писал(а):

Сопоставим цветам числа от $0$ до $N-1$. Все вычисления ведутся в $\mathbb{Z}_N$. Пусть $S$ - сумма цветов всех шляп. Каждое из $N$ возможных значений $S$ берёт некоторый мудрец. Кто-нибудь да угадает.

Я не очень вас понял, но в Квантике решение было похожее.
Пусть первый мудрец посчитает сумму цветов шляп остальных по модулю $N$ и скажет это число (назовем его число-мудрец).
Пусть второй мудрец вычтет из числа-мудреца сумму цветов шляп всех остальных, кроме первого, по модулю $N$ и скажет это число.
Пусть третий мудрец вычтет из числа-мудреца сумму цветов шляп всех остальных, кроме первого, по модулю $N$ и скажет это число.
Пусть четвертый мудрец вычтет из числа-мудреца сумму цветов шляп всех остальных, кроме первого, по модулю $N$ и скажет это число.
...

[Dan B-Yallay]

kotenok gav в сообщении #1318130 писал(а):

Пусть первый мудрец посчитает сумму цветов шляп остальных по модулю $N$ и скажет это число (назовем его число-мудрец).
Пусть второй мудрец вычтет из числа-мудреца сумму цветов шляп всех остальных, кроме первого, по модулю $N$ и скажет это число.

Они не одновременно говорят что ли? Тогда задача решается намного проще: первый мудрец называет цвет шляпы второго мудреца, а второй просто повторяет этот цвет. Остальные $N-2$ мудрецов могут отдыхать.

[kotenok gav]

Dan B-Yallay в сообщении #1318133 писал(а):

Они не одновременно говорят что ли?

Да.
Только в Квантике требовалось чтобы правильно назвали не меньше $N-1$ мудреца.

[Sender]

kotenok gav, это другая задача. Там они выстроены в шеренгу так, что каждый видит цвета стоящих перед ним, и их опрашивают поочерёдно, начиная с последнего.

Квантик писал(а):

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


Отправляясь на третий тур, Квантик твёрдо решил самостоятельно найти ответ. И нашёл его. А потом Квантик задумался – а если бы хитрый су­дья предложил такое же испытание, но мудрецам на­ девали бы колпаки десяти разных цветов? Неужели они и тогда бы справились? Невероятно, но, оказыва­ется, да, и Квантик придумал, как могли бы действовать мудрецы. Попробуйте и вы это сделать. Удачи!

https://kvantik12.livejournal.com/34173.html

-- Пт июн 08, 2018 09:21:40 --

kotenok gav в сообщении #1318130 писал(а):

Я не очень вас понял, но в Квантике решение было похожее.

Эмм, какая часть вызывает затруднения?
$1$-й мудрец принимает сумму $S$ цветов всех шляп по модулю $N$ равной $0$,
$2$-й мудрец принимает сумму $S$ цветов всех шляп по модулю $N$ равной $1$,
...
$N$-й мудрец принимает сумму $S$ цветов всех шляп по модулю $N$ равной $N-1$.

Затем каждый из них вычисляет цвет своей шляпы, исходя из предполагаемого значения $S$.
Поскольку фактическое $S$ может принимать лишь одно из значений $0,\dots, N-1$, расчёты одного из мудрецов основываются на его истинном значении, его ответ и будет верным.

[Unconnected]

Я понял, спасибо большое!!

[Unconnected]

Sender
а Вы не могли бы описать ход мыслепоиска, который привёл к решению? Или это просто надо вспомнить что-то похожее и уже решённое?

[Sender]

Я сразу вспомнил задачу с мудрецами в шеренге, упомянутую kotenok gav, где использовался похожий приём. А как ту решал, не помню уже, это давно было.