2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 19:53 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 20:00 


11/12/16
4537
grizzly в сообщении #1317992 писал(а):
Неужели есть сомнения, что в такой формулировке задача не имеет решения?


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

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

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 20:02 


21/05/16
2427
Аделаида
gris в сообщении #1317996 писал(а):
Какие должны быть алгоритмы, чтобы мудрецы остались целы?

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 20:17 
Заслуженный участник
Аватара пользователя


09/09/14
6091
EUgeneUS в сообщении #1317998 писал(а):
Есть сомнения. Пусть у нас есть 50 мудрецов и шапки 50-и оттенков серого. (Одномерный непрерывный случай).
Причем, какие именно оттенки серого будут\могут быть использованы мудрецам неизвестны.
Представил. Есть 1М оттенков серого. Известно, что на мудрецах шапки 50-и оттенков. Какие именно могут быть использованы -- неизвестно. Дальше я Ваших уравнений не понял.

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 20:29 


11/12/16
4537
grizzly

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

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


-- 07.06.2018, 20:57 --

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 21:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение07.06.2018, 22:53 


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

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 00:48 
Заслуженный участник
Аватара пользователя


16/07/14
2919
Москва
Unconnected в сообщении #1318063 писал(а):
Набор цветов известен заранее, и их N штук.
Если цвета заранее известны, то мудрецы могут заранее договориться о нумерации, и задача эквивалентна "на каждом пишут число от $1$ до $N$, каждый называет число". Так?
Unconnected в сообщении #1318063 писал(а):
Ув. Sender, Ваше решение учитывает, что цвета надетых шляп могут повторяться?
Отвечу за него: да, учитывает.
Работает потому что сумма цветов всех шляп по модулю $N$ может принимать только одно из $N$ значений.

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 07:33 


21/05/16
2427
Аделаида
Sender в сообщении #1317914 писал(а):
Сопоставим цветам числа от $0$ до $N-1$. Все вычисления ведутся в $\mathbb{Z}_N$. Пусть $S$ - сумма цветов всех шляп. Каждое из $N$ возможных значений $S$ берёт некоторый мудрец. Кто-нибудь да угадает. :-)

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 08:11 
Заслуженный участник
Аватара пользователя


11/12/05
7775
Diкий Запад
kotenok gav в сообщении #1318130 писал(а):
Пусть первый мудрец посчитает сумму цветов шляп остальных по модулю $N$ и скажет это число (назовем его число-мудрец).
Пусть второй мудрец вычтет из числа-мудреца сумму цветов шляп всех остальных, кроме первого, по модулю $N$ и скажет это число.

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 08:29 


21/05/16
2427
Аделаида
Dan B-Yallay в сообщении #1318133 писал(а):
Они не одновременно говорят что ли?

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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 08:37 
Заслуженный участник


14/01/11
2042
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$, расчёты одного из мудрецов основываются на его истинном значении, его ответ и будет верным.

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 16:06 


13/11/11
569
СПб
Я понял, спасибо большое!!

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 20:47 


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

 Профиль  
                  
 
 Re: Задача про мудрецов и разноцветные шляпы
Сообщение08.06.2018, 21:49 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group