IPB

Добро пожаловать, гость ( Вход | Регистрация )

> Правила раздела

Публикующим:
     1. Задачу можно опубликовать двумя способами:
          - создав для нее отдельную тему с информативным названием;
          - добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
     2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
     1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
     2. Правильность решения можно проверить, написав личное сообщение автору.

 
Тема закрытаОткрыть новую тему
> Бесконечная колонна мегамозгов
Swordelf
8.5.2020, 10:48
Сообщение #1


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 26.10.2010
Пользователь №: 21 424



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

Пояснения:
1. ММы выстраиваются так: 1 -> 2 -> 3 -> 4 -> ... -> n -> ... (стрелкой показано, куда они смотрят, например, 2-ой видит колпаки 3-го, 4-го, т.д.). Число мегамозгов счетно, каждый знает свой (натуральный) номер в последовательности.
2. ММы как всегда бесконечно умны, бесконечно далеко видят и могут договориться заранее о стратегии.
3. ММы не могут обмениваться никакой дополнительной информацией. Вся информация, что у них есть, - цвета колпаков впереди стоящих ММов. Называют свой цвет они абсолютно одновременно.

P.S. Задача очень сложная, но очень крутая.

Сообщение было отредактировано Swordelf: 8.5.2020, 10:50
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Owen
8.5.2020, 12:59
Сообщение #2


Kорифей
****

Группа: Администраторы Braingames
Сообщений: 2 471
Регистрация: 6.3.2013
Пользователь №: 43 989



Эта задача, если не изменяет память, есть в закрытой части форума, не исключена ее публикация, поэтому лучше бы ее тут не обсуждать.

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

P.S. Эта задача, кстати, есть в отборе: https://www.braingames.ru/index.php?path=co...683&drafts=true. Если вы хотите провериться и вообще узнать, какие задачи лежат в отборе (там есть и круче этой на мой субъективный взгляд), надо стать VIP-ом.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Swordelf
8.5.2020, 15:31
Сообщение #3


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 26.10.2010
Пользователь №: 21 424



Действительно, спасибо, что указали на нее smile.gif Еще не успел пройтись по всем задачам из отбора.
QUOTE(Owen @ 8.5.2020, 12:59) *
P.S. Эта задача, кстати, есть в отборе: https://www.braingames.ru/index.php?path=co...683&drafts=true.

Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
SlvBuz
8.5.2020, 20:04
Сообщение #4


Участник
**

Группа: Пользователи Braingames
Сообщений: 272
Регистрация: 16.7.2012
Пользователь №: 38 054



Что такое счетное число? Я тупой. Их захватили от 1 до Х? или для любого ММ есть номер который можно на него надеть?
Я правильно понял, что каждый мм видит бесконечное число остальных?
Колпаки никогда не могут быть все одного цвета?
Что такое конечное число? Мы должны сказать N=100, или что?

Сообщение было отредактировано SlvBuz: 8.5.2020, 20:10


--------------------
____________________________________________________________________
Вчера нашел бумажник с 10000$. Как любой честный и благородный человек...
... я поступать не стал.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Зеркало
9.5.2020, 14:10
Сообщение #5


Участник
**

Группа: Отбор задач
Сообщений: 150
Регистрация: 1.6.2015
Пользователь №: 54 010



QUOTE(SlvBuz @ 8.5.2020, 20:04) *
Что такое счетное число? Я тупой. Их захватили от 1 до Х? или для любого ММ есть номер который можно на него надеть?
Я правильно понял, что каждый мм видит бесконечное число остальных?
Колпаки никогда не могут быть все одного цвета?
Что такое конечное число? Мы должны сказать N=100, или что?

Счётное число - это, насколько я понимаю, мощность счётного множества ℵ0, грубо говоря, наименьшее бесконечное число (бесконечности в математике тоже бывают разными). Счётное число мегамозгов означает, что всех их можно выстроить в одну, хоть и бесконечную, колонну. Можно сказать и так, что для любого мегамозга есть номер (натуральное число), который можно на него надеть. Каждый видит бесконечное число стоящих впереди себя. Колпаки могут быть любого цвета, надо придумать алгоритм для общего случая. Конечное число - любое натуральное число (как я понимаю, оно ничем не ограничено).


--------------------
И уже говорю я не маме,
А в чужой и хохочущий сброд:
"Ничего! Я споткнулся о камень,
Это к завтраму всё заживет!"


Сергей Есенин
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
SlvBuz
9.5.2020, 17:37
Сообщение #6


Участник
**

Группа: Пользователи Braingames
Сообщений: 272
Регистрация: 16.7.2012
Пользователь №: 38 054



QUOTE(Зеркало @ 9.5.2020, 14:10) *
Счётное число - это, насколько я понимаю, мощность счётного множества ℵ0, грубо говоря, наименьшее бесконечное число (бесконечности в математике тоже бывают разными). Счётное число мегамозгов означает, что всех их можно выстроить в одну, хоть и бесконечную, колонну. Можно сказать и так, что для любого мегамозга есть номер (натуральное число), который можно на него надеть. Каждый видит бесконечное число стоящих впереди себя. Колпаки могут быть любого цвета, надо придумать алгоритм для общего случая. Конечное число - любое натуральное число (как я понимаю, оно ничем не ограничено).

Спасибо, только не понятен один момент, если на всех наденут черный колпак, тогда все ММ скажут "белый" и ошибутся. Я так понимаю, с цветами надо аккуратно условие ставить.


--------------------
____________________________________________________________________
Вчера нашел бумажник с 10000$. Как любой честный и благородный человек...
... я поступать не стал.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
0
9.5.2020, 18:57
Сообщение #7


Охгдеж
****

Группа: Пользователи Braingames
Сообщений: 1 328
Регистрация: 26.3.2009
Пользователь №: 13 618



QUOTE(Зеркало @ 9.5.2020, 14:10) *
Можно сказать и так, что для любого мегамозга есть номер (натуральное число), который можно на него надеть. Каждый видит бесконечное число стоящих впереди себя. Колпаки могут быть любого цвета, надо придумать алгоритм для общего случая. Конечное число - любое натуральное число (как я понимаю, оно ничем не ограничено).

Зря вы сказали "алгоритм". Я помню эту задачу еще из прошлого века из фидо.
Нет там алгоритма, чистая схоластика. То есть нужно не придумать алгоритм а доказать что он существует основываясь на аксиоме которая и многим математикам не нравится

Ой
Комментарий оказывается написал не тот кто начал тему. Но это не так важно
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Зеркало
9.5.2020, 19:45
Сообщение #8


Участник
**

Группа: Отбор задач
Сообщений: 150
Регистрация: 1.6.2015
Пользователь №: 54 010



QUOTE(SlvBuz @ 9.5.2020, 17:37) *
Спасибо, только не понятен один момент, если на всех наденут черный колпак, тогда все ММ скажут "белый" и ошибутся. Я так понимаю, с цветами надо аккуратно условие ставить.

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

QUOTE( @ 9.5.2020, 18:57) *
Ой
Комментарий оказывается написал не тот кто начал тему. Но это не так важно

Вы правы, не я автор темы и даже не знаю, как решается эта задача. Написал просто, как понял её условия. Если что-то понял неправильно, пусть автор поправит.


--------------------
И уже говорю я не маме,
А в чужой и хохочущий сброд:
"Ничего! Я споткнулся о камень,
Это к завтраму всё заживет!"


Сергей Есенин
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Swordelf
9.5.2020, 20:21
Сообщение #9


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 26.10.2010
Пользователь №: 21 424



QUOTE( @ 9.5.2020, 18:57) *
Нет там алгоритма, чистая схоластика. То есть нужно не придумать алгоритм а доказать что он существует основываясь на аксиоме которая и многим математикам не нравится.

Вы правы, это не совсем алгоритм, однако лично для меня это не делает решение менее красивым. А аксиома выбора, нравится она математикам или нет, используется в 99% всего матана.
QUOTE
Если что-то понял неправильно, пусть автор поправит.

Вы все верно поняли.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
UNDEFEAT
9.5.2020, 21:17
Сообщение #10


Avorthoren
****

Группа: Модераторы BrainGames
Сообщений: 3 607
Регистрация: 13.11.2010
Из: Kиев
Пользователь №: 21 696



QUOTE(Swordelf @ 9.5.2020, 20:21) *
А аксиома выбора, нравится она математикам или нет, используется в 99% всего матана.


Вы так написали, будто используют её не математики smile.gif

Как вы вообще 99% получили? Что на что делили? smile.gif
Везде, где её можно не использовать, её не используют.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Swordelf
9.5.2020, 21:44
Сообщение #11


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 26.10.2010
Пользователь №: 21 424



QUOTE(UNDEFEAT @ 9.5.2020, 21:17) *
Везде, где её можно не использовать, её не используют.

Под "использованием" я понимаю использование либо ее напрямую, либо любого утверждения, доказательство которого ее использует. Кроме того, в большинстве учебников матана она не упоминается там, где на самом деле неявно используется (напрямую).
QUOTE(UNDEFEAT @ 9.5.2020, 21:17) *
Как вы вообще 99% получили? Что на что делили? smile.gif

Справедливо, 99% - это скорее всего преувеличение. Хотел защитить свое субъективное мнение, не прав smile.gif
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
0
10.5.2020, 1:09
Сообщение #12


Охгдеж
****

Группа: Пользователи Braingames
Сообщений: 1 328
Регистрация: 26.3.2009
Пользователь №: 13 618



QUOTE(Swordelf @ 9.5.2020, 21:44) *
Под "использованием" я понимаю использование либо ее напрямую, либо любого утверждения, доказательство которого ее использует. Кроме того, в большинстве учебников матана она не упоминается там, где на самом деле неявно используется (напрямую).

Просто так получилось что телега оказалась впереди лошади.
Сначала построили теорию, потом обнаружили проблему и чтобы не ломать теорию придумали костыль.
Костыль приводит к странным побочным эффектам и именно это не нравится.
Есть альтернативы (например аксиома счетного выбора) - да они выглядят как костыль для костыля, да часть утверждений с их помощью не доказать, но может эти утверждения и не должны быть доказаны, главное что они убирают парадоксы. И эту задачу с такой аксиомой не решить, а значит красота в еще одном парадоксе вызванной этой аксиомой.
И да для учебника матана достаточно урезанной аксиомы. А не упоминается потому как практически не упоминается вся остальная теория множеств. Студентам только про построение действительных чисел рассказывают зачем им влезать в дебри несчетных семейств несчетных множеств.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
WitP
10.5.2020, 3:24
Сообщение #13


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 13.12.2015
Пользователь №: 55 547



Если число мм-в конечно, то задача не решаема, для k-го мм-а стоит функция выбора колпака fk, тогда ему вешается колпак 1-fk и все мм-и дают не верный ответ. А вот если счетно, то уже игра с бесконечностью), можно положить что таких k-ых мм-в уже множество и тогда череда колпаков на них едина, например все черные колпаки или смена белый, черный...
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Swordelf
10.5.2020, 3:42
Сообщение #14


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 26.10.2010
Пользователь №: 21 424



QUOTE( @ 10.5.2020, 1:09) *
Просто так получилось что телега оказалась впереди лошади.

Да, соглашусь.
QUOTE( @ 10.5.2020, 1:09) *
Студентам только про построение действительных чисел рассказывают зачем им влезать в дебри несчетных семейств несчетных множеств.

Я думаю, студентам хотя бы должны указывать на нее, чтобы те, кому интересно (а не только те, кто общается с самыми умными людьми), смогли сами почитать.
QUOTE
Если число мм-в конечно, то задача не решаема

Задача-то решаема: даже если все умрут, умрет конечное число ММ-ов smile.gif
Вы, наверное, имеете в виду, что максимальное кол-во гарантированно выживших равно нулю, и тут вы правы.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
WitP
10.5.2020, 4:31
Сообщение #15


Новичок
*

Группа: Пользователи Braingames
Сообщений: 5
Регистрация: 13.12.2015
Пользователь №: 55 547



Вы, наверное, имеете в виду, что максимальное кол-во гарантированно выживших равно нулю, и тут вы правы.
[/quote]
Да, если переформулировать задачу, найдутся и те мм-ги, которые угадают свой колпак в счетном множестве таких счетно и не угадавших уже конечное число. Но это парадокс))
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Owen
10.5.2020, 11:32
Сообщение #16


Kорифей
****

Группа: Администраторы Braingames
Сообщений: 2 471
Регистрация: 6.3.2013
Пользователь №: 43 989



Эх, что же я написал неясного во втором посте? На форуме не надо обсуждать решения задач, выложенных на сайте! Вы наполняете тему спойлерами (и неважно, понимаете вы это или нет), единственное, что вы получите на выходе - что задача из отбора гарантированно не пройдет на главную.

Остановитесь, блин, уже. Хотите обсудить свои мысли по задаче - станьте VIP-ами (или модераторами), решите в отборе, после чего обсуждайте и с ведущим модератором, и в комментариях для решивших...
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
alan
11.5.2020, 2:04
Сообщение #17


zzz...
*****

Группа: Администраторы Braingames
Сообщений: 12 296
Регистрация: 23.2.2009
Из: Симферополь
Пользователь №: 13 114



Закрыл тему.
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Тема закрытаОткрыть новую тему
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 27.10.2020, 13:28