2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Задача про бесконечное количество мудрецов
Сообщение09.03.2020, 22:25 
Мудрецы в черных и белых шляпах стоят в точках натурального ряда и видят всех мудрецов с большими номерами. Докажите, что у мудрецов имеется стратегия, позволяющая каждому из них назвать цвет своей шляпы так, что лишь конечно много мудрецов будут неправы. (Стратегия — это функция, отображающая известную мудрецу информацию в его ответ; такая функция должна быть одна для всех мудрецов.)

Я смог решить эту задачу для случая, когда все мудрецы знают свой номер. Я решал так: пусть две последовательности совпадающие начиная с некоторого n совпадают, тогда отнесем их к одному классу эквивалентности. По аксиоме выбора я могу сопоставить каждому классу сопоставить "представителя" этого класса. Очевидно, что каждый мудрец может определить класс следующей за ним последовательности, а значит он может сказать свой цвет, в зависимости от того, что стоит в последовательности - "представителе". Значит всего конечное количество мудрецов будет не право. Мне не понятно как обобщить на случай, если мудрецу не известен его номер.

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение09.03.2020, 22:51 
Аватара пользователя
Кто из мудрецов слышит ответ конкретного мудреца?

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение09.03.2020, 22:57 
Аватара пользователя
del

 
 
 
 Posted automatically
Сообщение09.03.2020, 23:02 
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:
- отсутствуют собственные содержательные попытки решения задачи;
- текст стоит отформатировать нормально.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 
 
 
 Posted automatically
Сообщение09.03.2020, 23:47 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение09.03.2020, 23:56 
KappaGolden в сообщении #1443942 писал(а):
Мне не понятно как обобщить на случай, если мудрецу не известен его номер.
Посмотрите сначала на периодические последовательности и потом ещё на те из остальных, которые финально периодические (сначала какой-то кусок, а потом пошла периодическая). Останется самое страшное.

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 00:10 
Аватара пользователя
В общем случае имеем абсолютно нормальное невычислимое число в двоичной записи. Никакой закономерной Seq она не образует.
Задача не имеет решения.

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 00:15 
Аватара пользователя
Нужно сказать, что две последовательности эквивалентны, если после сдвига они совпадают, начиная с некоторого элемента. Дальше вопрос - как может быть устроено множество таких сдвигов?

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 00:46 
gabber
Глупости пишете, имеет, но при одном часто принимаемом условии.

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 13:11 
Не имеющая отношения к делу часть здесь: «Задача про бесконечное количество мудрецов для gabber»

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 19:56 
arseniiv в сообщении #1443966 писал(а):
KappaGolden в сообщении #1443942 писал(а):
Мне не понятно как обобщить на случай, если мудрецу не известен его номер.
Посмотрите сначала на периодические последовательности и потом ещё на те из остальных, которые финально периодические (сначала какой-то кусок, а потом пошла периодическая). Останется самое страшное.


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

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 19:58 
Аватара пользователя
Допустим что мудрец перед собой видит последовательность $011001\ 011001\ 011001\ 011001\ 011001 \ldots$ (пробелы расставлены для удобства, их не видно). Пусть заведомо известно, что последовательность периодическая. Какой цвет надо называть мудрецу?

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 20:07 
mihaild в сообщении #1444101 писал(а):
(пробелы расставлены для удобства, их не видно)
Кстати было бы хорошо, если бы их было видно, а то приходится смотреть в код, чтобы убедиться в периодичности. :D

-- Вт мар 10, 2020 22:08:35 --

KappaGolden в сообщении #1444099 писал(а):
Не совсем ясно, как решать даже для периодической последовательности. Можете подсказать, как именно решать для этого случая?
Альтернативный совет: начните с последовательности одних нулей (или одних единиц). Я так сам и начинал.

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 21:17 
mihaild в сообщении #1444101 писал(а):
Допустим что мудрец перед собой видит последовательность $011001\ 011001\ 011001\ 011001\ 011001 \ldots$ (пробелы расставлены для удобства, их не видно). Пусть заведомо известно, что последовательность периодическая. Какой цвет надо называть мудрецу?


Скорее всего, ему нужно ответить: 1, т.к. если он видит перед собой повторяющуюся последовательность 011001, то значит он стоит в самом её конце.

 
 
 
 Re: Задача про бесконечное количество мудрецов
Сообщение10.03.2020, 22:31 
Да, именно так. Если он ответит 0, то бесконечное количество мудрецов вместе с ним на этой последовательности ошибутся, а нам этого не надо.

 
 
 [ Сообщений: 21 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group