Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 143
У меня в голове почему-то такие рассуждения.
Будем рассматривать очередь не с конца, а с начала, то есть каждый гном видит конечное число колпаков. Предположим, что решение задачи существует, то есть для i+1-того гномика существует функция fi (i — индекс) от i аргументов, возвращающая Синий или Красный. Более того, эти функции «независимы» = гномики не умеют общаться = функция i аргументов.
Кажется, этого для отсутствия решения достаточно.
Будем рассматривать очередь не с конца, а с начала, то есть каждый гном видит конечное число колпаков. Предположим, что решение задачи существует, то есть для i+1-того гномика существует функция fi (i — индекс) от i аргументов, возвращающая Синий или Красный. Более того, эти функции «независимы» = гномики не умеют общаться = функция i аргументов.
Я утверждаю, что для любого набора таких функций найдется такая раскраска гномиков, что все гномы умрут.
Действительно, вставим гномам в уши затычки, чтобы они не слышали друг друга, снимем шапки и начнем опрашивать гномов по одному спереди. При этом каждому гному мы будем надевать шапку противоположного цвета.
Теперь вынем затычки и спросим гномов одновременно. Каждый гном в обоих случаях видит одно и то же, значит и скажет то же самое, а, значит, умретк радости эльфов.
В итоге мы получим для данной последовательности гномов последовательность шапок смертников.
Теперь вынем затычки и спросим гномов одновременно. Каждый гном в обоих случаях видит одно и то же, значит и скажет то же самое, а, значит, умрет
В итоге мы получим для данной последовательности гномов последовательность шапок смертников.
Кажется, этого для отсутствия решения достаточно.
Честно говоря, я не понял про рассматривание очереди с другой стороны. Она бесконечная, у нее нет начала.
Там в авторском решении (2 пункт) подразумевалось, что у очереди есть конец.
В общем-то, для моего доказательства можно бесконечную с обеих сторон последовательность сделать конечной с одной стороны. Назовем какого-то гнома первым, а на всех перед ним забьем. У нас и так останется бесконечное количество ошибок, даже если все выброшенные угадают.
Назовем две последовательности эквивалентными, если они различаются лишь в конечном числе позиций. (...) Дело за малым: стоя в очереди, любой гномик может определить, в каком классе лежит текущая (та, которая имеет место быть) последовательность. В самом деле, каждый гномик НЕ видит лишь конечное число колпаков, а следовательно они никак не влияют на принадлежность последовательности какому-то классу.
В общем-то, для моего доказательства можно бесконечную с обеих сторон последовательность сделать конечной с одной стороны. Назовем какого-то гнома первым, а на всех перед ним забьем. У нас и так останется бесконечное количество ошибок, даже если все выброшенные угадают.
Я подумал над вашей идеей. Продлить ее на бесконечность, к сожалению, не выходит.
У вас искажены условия задачи.
Во-первых, очередь не бесконечная, а с произвольным конечным количеством человек (соотношение цветов тоже произвольное).
Во-вторых, участники называют цвета не одновременно, а по очереди, начиная с того участника, который видит всех остальных, и далее по порядку.
Такая задача имеет очень элегантное решение в математико-программистком ключе, причём, и это в-третьих, все участники, кроме первого, должны угадать цвет безошибочно.
Во-первых, очередь не бесконечная, а с произвольным конечным количеством человек (соотношение цветов тоже произвольное).
Во-вторых, участники называют цвета не одновременно, а по очереди, начиная с того участника, который видит всех остальных, и далее по порядку.
Такая задача имеет очень элегантное решение в математико-программистком ключе, причём, и это в-третьих, все участники, кроме первого, должны угадать цвет безошибочно.
Тогда у вас тоже искажены условия задачи. Потому что там вообще не про гномов, а про спички. И нужно переложить одну спичку так, чтобы получилось равенство.
Это уже другая, более тривиальная задача.
В статье поинтересней и посложнее будет.
В статье поинтересней и посложнее будет.
Ничего интересного и сложного я в ней не вижу. Видимо, потому что я не математик. :/
Если колпак на вас выбран случайно, то его цвет по определению слова «случайно» не имеет ни с чем взаимосвязи. Определить цвет колпака, глядя на окружающие предметы, в том числе на другие колпаки, невозможно просто по условию задачи.
Всё. Говорить тут больше не о чем.
Четвертый раздел поста напомнил Корчевателя. Нет, я, конечно, верю, что текст взят из головы автора, а не с vesna.yandex.ru, но благодаря отсутствию задачи в данной задаче на этот пост можно ловить «математиков» в кавычках (по аналогии с «фотографами»).
Бесконечность очереди тут явно добавлена, чтобы запудрить «математику» мозги. Потому что если сделать очередь конечной (например, четыре человека), невозможность определять цвет колпака становится очевидной даже ребенку.
Если колпак на вас выбран случайно, то его цвет по определению слова «случайно» не имеет ни с чем взаимосвязи. Определить цвет колпака, глядя на окружающие предметы, в том числе на другие колпаки, невозможно просто по условию задачи.
Всё. Говорить тут больше не о чем.
Четвертый раздел поста напомнил Корчевателя. Нет, я, конечно, верю, что текст взят из головы автора, а не с vesna.yandex.ru, но благодаря отсутствию задачи в данной задаче на этот пост можно ловить «математиков» в кавычках (по аналогии с «фотографами»).
Бесконечность очереди тут явно добавлена, чтобы запудрить «математику» мозги. Потому что если сделать очередь конечной (например, четыре человека), невозможность определять цвет колпака становится очевидной даже ребенку.
Тут вся фишка именно в бесконечности очереди и необходимости конечного количества ошибок.
Вполне очевиден факт, что для любого n найдется такое расположение шапок, что ошибок будет не меньше, чем n. Но это не решает задачу, ошибок может быть всё еще конечное число.
Вполне очевиден факт, что для любого n найдется такое расположение шапок, что ошибок будет не меньше, чем n. Но это не решает задачу, ошибок может быть всё еще конечное число.
Не нужно быть математиком, чтобы понимать, что это изначально тупиковый путь рассуждений.
Вот вам ниже объяснили в ваших терминах. С тем же успехом можно бы делить этих ваших бесконечных гномиков по сексуальной ориентации. В отличие от цвета шапки, свою-то ориентацию вы знаете!
Вот вам ниже объяснили в ваших терминах. С тем же успехом можно бы делить этих ваших бесконечных гномиков по сексуальной ориентации. В отличие от цвета шапки, свою-то ориентацию вы знаете!
Ну, вообще-то, для конечного количества гномов есть решение, которое с гарантией спасает всех, кроме одного.
Определить цвет, только разглядывая других, конечно, нельзя. Но ведь есть и ещё один канал информации. Каждый гном слышит, всё, что сказано теми, кто видит его. И этим уже можно воспользоваться.
Если хотите, кину в личку решение для конечного количества. Здесь, кажется, избегают его публикации. 8)
Определить цвет, только разглядывая других, конечно, нельзя. Но ведь есть и ещё один канал информации. Каждый гном слышит, всё, что сказано теми, кто видит его. И этим уже можно воспользоваться.
Если хотите, кину в личку решение для конечного количества. Здесь, кажется, избегают его публикации. 8)
Всё-таки скорее очередь бесконечная, но всё же гномики называют цвета по очереди. И тогда действительно имеют смысл все эти размышления о последовательностях.
думал щас будет известная и красивая задачка:
Сидели 3 мудреца, и спорили кто из них мудрее всех. Царь дал им такую задачку. У меня в сумке лежат 5 шляп, 3 белых и 2 черных. Сейчас вы закроете глаза, и я надену какие-то 3 из них. Он усадил их в 3 разных угла, так что каждый мог видеть какие надеты шляпы на 2-х других мудрецах.Тот из вас кто первым скажет, какая у него шляпа – тот и есть наимудрейший.
Сидели 3 мудреца, и спорили кто из них мудрее всех. Царь дал им такую задачку. У меня в сумке лежат 5 шляп, 3 белых и 2 черных. Сейчас вы закроете глаза, и я надену какие-то 3 из них. Он усадил их в 3 разных угла, так что каждый мог видеть какие надеты шляпы на 2-х других мудрецах.Тот из вас кто первым скажет, какая у него шляпа – тот и есть наимудрейший.
Интересная задача!
Правильно? :)
Попробую рассуждать вслух.
Если перед вами две черные шапки — остаются только белые, сразу называем белый.
Если в первый момент никто другой не поступил так, значит, никто из них не видит перед собой две черные шапки.
Значит, если вы видите хотя бы одну черную шапку, то на вас белая. Называем белый.
А вот если перед вами две белых шапки, на вас может быть либо черная, либо белая. Если другие мудрецы молчат, значит, они тоже столкнулись с этой неопределенностью. А она имеет место, если каждый из них видит две белые шапки, и одна из них — ваша. Называем белый.
В итоге получается, что при любом раскладе надо называть белый цвет. Это не беспроигрышный вариант, но если вы ошибетесь, значит, вы и так были в ситуации, когда один из других мудрецов имеет над вами преимущество.
Если в первый момент никто другой не поступил так, значит, никто из них не видит перед собой две черные шапки.
Значит, если вы видите хотя бы одну черную шапку, то на вас белая. Называем белый.
А вот если перед вами две белых шапки, на вас может быть либо черная, либо белая. Если другие мудрецы молчат, значит, они тоже столкнулись с этой неопределенностью. А она имеет место, если каждый из них видит две белые шапки, и одна из них — ваша. Называем белый.
В итоге получается, что при любом раскладе надо называть белый цвет. Это не беспроигрышный вариант, но если вы ошибетесь, значит, вы и так были в ситуации, когда один из других мудрецов имеет над вами преимущество.
Правильно? :)
Тоже мыслил так.
Задача заметно усложнится, а то и станет совсем не решаемой, если изменить в условиях «Сидели 2 мудреца и 1 тролль (который не мыслил как описано выше, и даже видя перед собой 2 черные шляпы говорил-бы, что на нем — черная), и спорили кто из них мудрее всех».
Задача заметно усложнится, а то и станет совсем не решаемой, если изменить в условиях «Сидели 2 мудреца и 1 тролль (который не мыслил как описано выше, и даже видя перед собой 2 черные шляпы говорил-бы, что на нем — черная), и спорили кто из них мудрее всех».
да, правильно)
Это задачи не просто на логику, а на рефлексию.
Подробнее о рефлексии — см. работы Владимира Лефевра по теории игр.
Суть в том, что у каждого мудреца есть не только объектная модель (видимые и невидимая шапки), но и субъектная (представление о том, как думает он сам и как думают его коллеги).
А также у него есть модель царя (который может быть добрым или злым, а то и подлым, — наденет три чёрных шапки из заявленных двух, и будет ловить лулзы).
Пример короткого решения.
с закрытыми глазами
«Царь-батюшка справедливый. Следовательно, он всех поставит в равные условия. Следовательно, на всех белые шапки».
приоткрывет глаз, видит одну белую и одну чёрную шапку Чорт!!!
У царя тоже, кстати, есть модели мудрецов…
Подробнее о рефлексии — см. работы Владимира Лефевра по теории игр.
Суть в том, что у каждого мудреца есть не только объектная модель (видимые и невидимая шапки), но и субъектная (представление о том, как думает он сам и как думают его коллеги).
А также у него есть модель царя (который может быть добрым или злым, а то и подлым, — наденет три чёрных шапки из заявленных двух, и будет ловить лулзы).
Пример короткого решения.
с закрытыми глазами
«Царь-батюшка справедливый. Следовательно, он всех поставит в равные условия. Следовательно, на всех белые шапки».
приоткрывет глаз, видит одну белую и одну чёрную шапку Чорт!!!
У царя тоже, кстати, есть модели мудрецов…
Кстати, задачки на хабре были и раньше. Например, не менее известная задачка про зеков и лампочку. habrahabr.ru/post/69558/
До множества Витали удаётся додуматься быстро, но я пока не смог понять, а корректно ли это решение вообще. Вроде бы, ошибок не видно.
Без аксиомы выбора — можно попробовать что-нибудь сделать с помощью аксиомы детерминированности (там все множества измеримы, так что трюк с множеством Витали не пройдёт), но пользоваться ей очень уж сложно.
Без аксиомы выбора — можно попробовать что-нибудь сделать с помощью аксиомы детерминированности (там все множества измеримы, так что трюк с множеством Витали не пройдёт), но пользоваться ей очень уж сложно.
За исключением неконструктивности авторское решение 100% корректно, поскольку жутко старое и проверенное кучу раз. Кстати, я задачу чуток упростил, дав гномам знание о месте, занимаемом в очереди. В оригинале этого, естественно, нет. Но тогда никто вообще ничего бы не понял.
UPD. Я думаю, не стоит пользоваться аксиомой детерминированности вообще, она какая-то совсем уж непризнанная =)
UPD. Я думаю, не стоит пользоваться аксиомой детерминированности вообще, она какая-то совсем уж непризнанная =)
Делить на классы можно. Одна проблема — принадлежность к классу не несет информации о цвете шапки на тех участках, на которых классы друг от друга отличаются. А это как раз те участки на которых содержится информация о цвете собственной шапки. Тоесть каждый раз, выбирая цвет шапки и зная класс, гномик все равно имеет вероятность угадать в 50% и так бесконечное число раз.
«на которых классы друг от друга отличаются» следует читать «на которых последовательности входящие в класс друг от друга отличаются»
Но поскольку все гномики выберут один и тот же класс, ошибётся всё равно лишь конечное число. На самом деле, говорить о «вероятности ошибиться» здесь нельзя: для понятия «вероятности» необходима измеримость в вероятностном пространстве множества, в котором событие реализуется.
Еще раз — вероятность ошибиться НЕ зависит от выбранного класса.
При этом первый гномик, глядя на последовательность, может совершенно точно перечислить всех гномиков, которые ответят неправильно (и их окажется конечное число). Не знает он только свою судьбу.
Действительно, для конкретного гномика вероятность ошибиться равна 1/2. Матожидание числа казнённых гномиков (если о нём вообще можно говорить) больше любого наперёд заданного числа. Но для каждой конкретной последовательности это число конечно.
Действительно, для конкретного гномика вероятность ошибиться равна 1/2. Матожидание числа казнённых гномиков (если о нём вообще можно говорить) больше любого наперёд заданного числа. Но для каждой конкретной последовательности это число конечно.
Задача ставилась найти способ совершить конечное число ошибок для любой(!) последовательности.
А то, если так рассуждать — для каждой конкретной последовательности число ошибок конечно, и ограничено длиной этой последовательности, и для этого гномикам совершенно не нужно о чем либо договариваться.
Но в любом случае от их договоренностей ничего не меняется.
А то, если так рассуждать — для каждой конкретной последовательности число ошибок конечно, и ограничено длиной этой последовательности, и для этого гномикам совершенно не нужно о чем либо договариваться.
Но в любом случае от их договоренностей ничего не меняется.
Это решение для любой (именно бесконечной) последовательности. И договориться им нужно о том, чтобы из каждого класса эквивалентности выбрать именно общую для всех последовательность. Иначе есть риск, что каждый из гномиков выберет последовательность, которая даёт неверный результат именно на нём.
Каким образом выбранная последовательность на что-то влияет?
Она гарантирует, что в ней только конечное число ошибок (по построению). Можно выбрать любую из класса эквивалентности — главное, чтобы она была одинакова для всех.
Для последнего гномика (с номером бесконечность) это «конечное число ошибок» равно бесконечности.
Нет такого гномика. И такого номера нет. Перед каждым гномиком стоит бесконечно много других гномиков. И, начиная с какого-то места, они образуют именно ту последовательность, которая содержится в множестве Витали. Так что ни один из этих гномиков уже не ошибётся (хотя сам он знать об этом не будет).
Для последнего гномика возможное количество ошибок в классе равно длине последовательности.
Какую «именно ту последовательность»? Вот он последний гномик с не важно каким номером. Он не видит ничего. Какую последовательность он выберет и на что это повлияет?
Какую «именно ту последовательность»? Вот он последний гномик с не важно каким номером. Он не видит ничего. Какую последовательность он выберет и на что это повлияет?
По условию задачи, гномиков бесконечно много: «На каждого гнома из бесконечной очереди...» Так что говорить о «последнем гномике» — это то же самое, что говорить о последнем натуральном числе. У каждого гномика номер в очереди конечен (N). За каждым стоит конечное число гномиков. А перед каждым — бесконечное число, так что каждый имеет бесконечно много информации. У этой очереди нет не только конца, но и середины — каждый её элемент находится где-то в начале.
Тогда о каком конечном числе ошибок идет речь? Берите любое сколь угодно большое конечное число N, берите гномика N+1 — возможное число ошибок для выбранной им последовательности будет N+1. Это не конечное число.
Для любой последовательности найдётся такой гномик, что после него ошибок не будет. Поскольку они выбирают из множества Витали ту единственную последовательность, которая отличается от последовательности их цветов в конечном числе мест. А значит, есть последнее место, в котором они различаются, а после этого места — совпадают.
Для бесконечных последовательностей этот гномик бесконечно далеко. Это место есть, но для разных последовательностей оно разное. «последнее место» не равно «конечное».
Вы считаете, что существует последняя цифра числа «пи»? Или хотя бы числа 1/7? И чему же она равна?
Можно надеть шапки так, что их цвета будут соответствовать чётности цифр того же числа 1/7. Какого цвета будет шапка у «последнего гномика»?
Можно надеть шапки так, что их цвета будут соответствовать чётности цифр того же числа 1/7. Какого цвета будет шапка у «последнего гномика»?
Последней цифры чила «пи» не существует. Какая связь с гномиками?
Гномики не выбирают как надевать шапки и ничего не знают про этот алгоритм по условию задачи.
Гномики не выбирают как надевать шапки и ничего не знают про этот алгоритм по условию задачи.
Точно так же и последнего гномика в бесконечной последовательности не существует. Гномики цветов не выбирают — их выбирает экспериментатор. И для последовательности цветов шапок он может использовать цифры любого вещественного числа, в том числе и «пи». Так какого цвета в этом случае будет шапка у последнего гномика?
Вы сами только что сказали, что гномик не определен, а теперь спрашиваете его цвет — вопрос не имеет смысла и соответственно ответа.
Как все то, что Вы только что сказали помогает определить конечность числа ошибок?
Как все то, что Вы только что сказали помогает определить конечность числа ошибок?
Значит, я неправильно понял фразу «Для бесконечных последовательностей этот гномик бесконечно далеко». Да, для каждой последовательности цветов шапок место последней ошибки своё — но для каждой последовательности это место есть, и для каждой последовательности оно конечно (поскольку элементов с бесконечными номерами не существует). Да, оно может быть сколь угодно далеко (в том смысле, что для любого N найдётся последовательность с более, чем N ошибками), но для каждой последовательности число ошибок остаётся конечным.
Уже было — так рассуждать нельзя.
Там было «для каждой конкретной последовательности число ошибок конечно, и ограничено длиной этой последовательности» Какое это отношение имеет к бесконечным последовательностям, я не понимаю — у них длины (как натурального числа) нет. И требования, чтобы максимум числа ошибок по всем последовательностям был конечным, в задаче нет.
Если у них нет длины, как вы их сравнили и создали класс? Вдруг на бесконечном элементе они снова начнут отличаться? Только не надо про возможность создания такой бесконечной последовательности, для которой это будет возможно исходя из способа ее формирования. Тогда задачу можно выродить в одеть всем синюю шапку и всем называть цвет который видят.
Требование есть: по условию задачи способ раскраски неизвестен — поэтому придется рассмотреть все возможные последовательности и заключить для них конечность ошибок, не для каждой в отдельности, а для любой.
Требование есть: по условию задачи способ раскраски неизвестен — поэтому придется рассмотреть все возможные последовательности и заключить для них конечность ошибок, не для каждой в отдельности, а для любой.
поэтому придется рассмотреть все возможные последовательности и заключить для них конечность ошибок, не для каждой в отдельности, а для любой.
Правильно, именно так она и решается. Берутся все возможные последовательности, делятся на классы эквивалентности по отношению «различаются не более, чем в конечном числе элементов» (то, что это отношение эквивалентности, т.е. рефлексивно, симметрично и транзитивно — проверяется элементарно), далее в каждом классе выбирается какая-нибудь последовательность (по аксиоме выбора), и именно её гномики используют в качестве опорной после того, как разобрались, в каком классе их последовательность находится (а это может сделать любой гномик).
Число классов континуально, число элементов в каждом классе счётно. Но из ZFC следует, что решение есть (хоть оно и неконструктивно).
А теперь просуммируйте ошибки бесконечного количества классов так, чтобы получилось конечное число ошибок.
А зачем? У нас одна последовательность цветов (неизвестно какая), складывать её ошибки ни с чем больше не надо.
Чтобы оценить сколько ошибок приходится на одну бесконечную последовательность. В среднем, а не для какой-то заранее известной.
Это и так понятно. В среднем — бесконечно много. Но матожидание случайной величины, принимающей конечные значения, вполне может быть бесконечным — в этом нет никакой трагедии.
«В среднем — бесконечно много.» — это ответ на задачу и все остальное в принципе не важно.
«матожидание случайной величины, принимающей конечные значения, вполне может быть бесконечным» — с каких пор среднее конечных чисел бесконечно?
«матожидание случайной величины, принимающей конечные значения, вполне может быть бесконечным» — с каких пор среднее конечных чисел бесконечно?
Гномики с конечным номером ничем друг от друга не отличаются. Поэтому если ошибку сделали конечное число гномиков, они должны иметь бесконечный номер в очереди.
Не может быть бесконечного номера. Номера — это числа. Сколь угодно большие номера — да. Это значит, что какое число N ни взять, злодей сможешь надеть на гномов колпаки так, чтобы неугадали какие-то гномики с номерами больше N.
Значит этих гномиков не существует. Значит либо все гномики угадают свой цвет, либо количество не угадавших — бесконечно.
Не могли бы вы пояснить, почему «значит»?
Ещё раз: чтобы количество казнённых гномиков было конечно, необходимо, чтобы гномики на бесконечном отрезке гарантированно угадали свой цвет. Но так как для первого гномика ситуация ничем не отличается от гномика №N. Поэтому если есть решение, при котором начиная с N-го гномика все гномики угадывают свои шапки, то это же решение применимо для гномика № N-1, и для гномика №1. Разве что если среди гномиков попадётся гномик-эмо, который захочет таким образом избавиться ото всех этих мучений с угадыванием шапок раз и навсегда.
Это неправда. Давайте я вам приведу пример. Задача: дается вещественное число Х. Каждое натуральное число сравнивает себя с Х и убивается, если Х оказывается больше. Убьется, вне зависимости от Х, конечное число нат. чисел. Однако нельзя сказать, что раз на бесконечном отрезке числа выживут, то можно применять стратегию к меньшим числам, и выживут все.
Ситуации для гномиков различаются: они видят разные хвосты последовательности, их положения в очереди различаются, и поэтому они по-разному делают вывод о своем цвете.
Ситуации для гномиков различаются: они видят разные хвосты последовательности, их положения в очереди различаются, и поэтому они по-разному делают вывод о своем цвете.
Вы меня путаете. Я конечно же имел ввиду гномиков, бесконечно удалённых от начала очереди.
По такой логике гномики могут вообще ни о чём не договариваться, а просто называть случайный цвет.
Почему нельзя? Каждый конкретный гномик ошибается или не ошибается, гномиков много, чем не пространство?
Не совсем. Все гномики определят принадлежность к классу абсолютно одинаково, поскольку каждый не видит лишь конечное число колпаков, что никак не мешает ему определить верный класс текущей последовательности. Затем все абсолютно одинаково выберут представителя класса (о том, как это сделать, они договариваются заранее). Теперь текущая последовательность и выбраный гномиками представитель, по причине принадлежности одному классу, различаются лишь конечным числом колпаков. Пусть они считают, что представитель и есть текущая последовательность (хоть и видят, что это не так). Ошибется лишь конечное число гномов. Сколь угодно большое, но конечное.
В математике правда существует понятие «Сколь угодно большое конечное число»? Можно ссылку?
Такого конкретного объекта не существует. Давайте я вам приведу пример. Можно начать щелкать пальцами и считать количество щелчков. Вы можете щелкнуть столько раз, сколько захотите, — больше любого наперед заданного числа. Тем не менее это будет конечное число щелчков.
Обычно это понятие встречается в контексте «для сколь угодно большого натурального числа N выполняется такое-то условие».
Ряд натуральных чисел бесконечен.
Вот для всех их оно и выполняется. Например, «для сколь угодно большого натурального числа N существует простое число, большее N» — вполне типичная формулировка теоремы.
Другой вариант — «число элементов в каком-то множестве (например, делителей числа) может быть сколь угодно большим». Это синоним утверждения «для любого N найдётся множество из указанного семейства, число элементов которого будет больше N».
Другой вариант — «число элементов в каком-то множестве (например, делителей числа) может быть сколь угодно большим». Это синоним утверждения «для любого N найдётся множество из указанного семейства, число элементов которого будет больше N».
Решение — гномы должны договориться называть синий цвет, если видят перед собой синие и красные шапки, или только синие, в случае если перед гномом все шапки красные — он должен назвать красный цвет
Кстати, можно упростить задачу — пусть известно, что цвета шапок гномиков образуют биты рационального числа, т.е. последовательность, начиная с какого-то места, периодическая. Тогда алгоритм становится полностью конструктивным — находим период, продолжаем его до себя и называем соответствующий цвет. И всё равно для каждого конкретного гномика вероятность ошибиться будет 1/2 :)
о чем они все вместе договорились перед тем, как получить колпаки
Раз у них была возможность договариваться, то ошибку можно снизить ровно до одного гнома. Перед раздачей колпаков договориться, что если гном сзади видит красный колпак перед собой, то пинает гнома по правой ноге, а если синий- то по левой. Таким образом ничего не узнает только первый гном и большая часть их племени спасена :)
Наименьшую последовательность в классе, содержащем последовательность из одних синих колпаков найти можно. Все последовательности этого класса содержат конечное количество красных колпаков, то есть число последовательностей в нем счетно:
Можно представить каждый бесконечный бинарный вектор с конечным числом единиц как два числа: количество ведущих нулей и число, представленное бинарной записью от первой единицы до последней. То есть это множество равносильно множеству рациональных чисел. (Ничего не напутал?)
Можно ли сказать, что в любом классе, на которые заданным отношением эквивалентности делится множество любых бесконечных бинарных векторов будет счетное число членов?
Можно представить каждый бесконечный бинарный вектор с конечным числом единиц как два числа: количество ведущих нулей и число, представленное бинарной записью от первой единицы до последней. То есть это множество равносильно множеству рациональных чисел. (Ничего не напутал?)
Можно ли сказать, что в любом классе, на которые заданным отношением эквивалентности делится множество любых бесконечных бинарных векторов будет счетное число членов?
То, что число членов в любом классе счётно — верно: возьмём «исключающее или» двух последовательностей из одного класса — получим число с конечным числом единиц, т.е. двоично-рациональное. То есть, каждый элемент класса, в котором уже выбран канонический представитель, кодируется одним двоично-рациональным числом.
А вот найти наименьший элемент в счётном множестве можно не всегда: попробуйте, например, множество 1/(2^n), n — натуральные.
Вполне упорядочить континуум без аксиомы выбора мы, к сожалению, не можем…
А вот найти наименьший элемент в счётном множестве можно не всегда: попробуйте, например, множество 1/(2^n), n — натуральные.
Вполне упорядочить континуум без аксиомы выбора мы, к сожалению, не можем…
Эх, если бы так просто можно было сказать. Я вот тоже всё пытался свести к вполне упорядоченному континууму, но как назло все классы счётные, упорядочивать нужно только внутри них, а друг к другу они отношения не имеют.
В чём проблема? Если бы у нас был вполне упорядоченный континуум, то в любом его подмножестве был бы наименьший (в смысле этого порядка) элемент. Существование функции выбора на P(S), насколько я понимаю, эквивалентно возможности вполне упорядочить S.
Упс, а я и не знаю, что такое P(S).
То же, что и 2^S — множество всех подмножеств.
Да, из упорядоченного континуума следует, конечно же, существование фукнции выбора. Однако нужно было наоборот: предположим, что гномики умеют выбирать представителей, следует ли отсюда, что они могут вполне упорядочить [0; 1]? Если да, то необходимость аксиомы подтверждена. Однако не факт, что следует, так как описанные классы — это далеко не 2^[0; 1].
В рамках псевдонаучных спекуляций:
Если у нас нет аксиомы выбора, то можно предположить существование двух экзотических объектов:
1) аморфное множество — бесконечное множество, которое нельзя разбить на два непересекающихся бесконечных подмножества.
2) Объединение M счётного числа двухэлементных множеств S_i, для которых нет функции выбора, т.е. для любого подмножества X множества M пересечение X с S_i содержит либо 0, либо 2 элемента для всех i, кроме конечного их числа.
Предположим, что эта экзотика водится среди подмножеств континуума. Что из этого можно извлечь?
Если у нас нет аксиомы выбора, то можно предположить существование двух экзотических объектов:
1) аморфное множество — бесконечное множество, которое нельзя разбить на два непересекающихся бесконечных подмножества.
2) Объединение M счётного числа двухэлементных множеств S_i, для которых нет функции выбора, т.е. для любого подмножества X множества M пересечение X с S_i содержит либо 0, либо 2 элемента для всех i, кроме конечного их числа.
Предположим, что эта экзотика водится среди подмножеств континуума. Что из этого можно извлечь?
В рамках данной задачи — не представляю. А если просто так, то
1) Аморфное множество мощнее континуума, так что его нельзя даже представить. И что говорить о нем? =)
1) Аморфное множество мощнее континуума, так что его нельзя даже представить. И что говорить о нем? =)
Аморфное множество несравнимо по мощности ни с каким бесконечным вполне упорядоченным множеством, и не мощнее никакого бесконечного множества (кроме совсем небольшого класса). Оно даже не содержит в себе ни одного счётного подмножества. Так что, в каком-то смысле оно совсем небольшое.
Да, я ошибся. Даже представляю себе что-то такое, но что с ним делать, пусть оно и было бы, ума не приложу.
Ещё можно попробовать разобраться в доказательстве отсутствия неизмеримых множеств при выполнении аксиомы детерминированности: seminariomatematico.dm.unito.it/rendiconti/61-4/393.pdf. Может быть, она и «функцию гномиков» отменит?
Увы, вашего аморфного множества не существует, что доказывается тривиально. Любое бесконечное множество содержит счетное подмножество, которое биективно, например, натуральным числам. Если количество оставшихся элементов бесконечно — разбиение уже построено. Если же конечно, возьмем две биекции из четных и нечетных чисел в испытуемое множество, а конечный остаток припишем к любой из частей.
В модели ZFC. Если же отказаться от аксиомы выбора (весьма спорной аксиомы), то всё становится совсем иначе.
Где у меня используется аксиома выбора?
В утверждении «любое бесконечное множество содержит счетное подмножество»
Математика без аксиомы выбора превращается в странную вещь… Погуглил — и в самом деле. Но не следует ли отсюда, что существуют множества, мощностью меньше счетной? И если это не так, как тогда доказать минимальность счетной мощности?
Например, аморфное множество, менее мощно, чем счетное.
Про аморфное множество нельзя сказать, что оно «менее мощно, чем счетное». Их мощности несравнимы, ни одно из них не содержит подмножества, эквивалентного другому. Оно является частным случаем более широкого класса — множеств, «конечных по Дедекинду» (тех, мощность которых изменяется при добавлении к ним ещё одного элемента).
«Минимальность счётной мощности» означает, что каждое подмножество натурального ряда либо счётно, либо конечно. Можно воспользоваться тем, что у любого подмножества есть минимальный элемент, и просто пересчитать все элементы подмножества по возрастанию. Либо номера закончатся — тогда подмножество конечно, либо нет — тогда каждому натуральному числу будет соответствовать какой-то элемент подмножества, а значит, оно эквивалентно натуральному ряду, т.е. счётно.
Это классическое доказательство. Выходит, в нем используется аксиома выбора. Никогда не задумывался над этим.
Не используется. «Выбрать наименьший элемент из подмножества» — конструктивная операция, для неё аксиома выбора не нужна. Как и вообще для построения натурального ряда.
Если мы возьмём классическое построение: 0={}, N+1=N U {N}, то наименьшим элементом множества натуральных чисел будет пересечение всех его элементов.
Если мы возьмём классическое построение: 0={}, N+1=N U {N}, то наименьшим элементом множества натуральных чисел будет пересечение всех его элементов.
Нет, так сказать нельзя. Пусть мое отношение эквивалентности будет константа true. Тогда класс будет один и он будет той же размерности, что и пространство. Или же пусть отношение будет «совпадает первая координата». Классов два, оба континуальные.
Я имею в виду множество и отношение эквивалентности, указанные в задаче.
Для того, чтобы избавиться от аксиомы выбора в решении, надо даже не упорядочивать подмножества, а иметь способ находить в каждом из них первый вектор (по какому-нибудь общему для всех подмножеств признаку).
Для того, чтобы избавиться от аксиомы выбора в решении, надо даже не упорядочивать подмножества, а иметь способ находить в каждом из них первый вектор (по какому-нибудь общему для всех подмножеств признаку).
Прошу прощения, не правильно понял вас из-за «любых бинарных векторов». Да, последовательностей в каждом классе счетно. Но первый вектор во всех классах выбрать не получится. Введение в ответ на вопрос «почему?» написано в четвертом разделе статьи.
Это если искать именно минимум. По такому же обоснованию нельзя найти минимум в множестве рациональных чисел исключая ноль. Но их можно упорядочить так, что первое число в последовательности будет четко определено. Емнип, это делается, например, так:
1/1 1/2 1/3…
2/1 2/2 2/3…
3/1 3/2 3/3…
.
.
.
А считаем сначала элемент на месте 0,0, потом 0,1 потом 1,0 и так далее, по диагоналям.
1/1 1/2 1/3…
2/1 2/2 2/3…
3/1 3/2 3/3…
.
.
.
А считаем сначала элемент на месте 0,0, потом 0,1 потом 1,0 и так далее, по диагоналям.
Нет, необходимость аксиомы выбора говорит о том, что найти принцип, по которому можно было бы выбирать элемент из каждого класса, нельзя =) Можно взять какой-то конкретный класс, как-то упорядочить его и найти особенный вектор в нем. Но сделать это во всем разом не выйдет.
В третьей части я написал, почему легчикографический минимум не подходит. А четвертая часть про то, почему ничего не подойдет. Вот невозможно придумать такой способ выбора особого представителя, чтобы он сработал сразу для всех классов.
В третьей части я написал, почему легчикографический минимум не подходит. А четвертая часть про то, почему ничего не подойдет. Вот невозможно придумать такой способ выбора особого представителя, чтобы он сработал сразу для всех классов.
Чтобы избавиться от аксиомы выбора, надо решить задачу выбора для данного множества :) Верно… Но, по-моему, перспективнее встречный подход — сначала показать, что без аксиомы выбора такой функции в данном случае может и не быть, а потом — что гномики в такой ситуации вообще проиграют. Но это очень сложно, там почти не за что зацепиться.
Предположим, что у гномиков есть выигрышная стратегия, причём детерминированная. Вопрос: можем ли мы с её помощью получить функцию выбора на классах эквивалентности?
Ответ: да.
Возьмём любой класс. Наденем на гномиков шапки в соответствии с любой последовательностью из этого класса (без АС мы этого сделать не сможем, поэтому будем проводить счётное число экспериментов параллельно). Зададим гномикам Вопрос, возьмём последнего не угадавшего свой цвет, и поменяем его шапку на другую. Его точка зрения не изменится (он видит то же, что и раньше), у гномиков, стоящих перед ним — тем более. Гномики, находящиеся ближе к началу очереди, могут изменить свой ответ, но нам это неважно — главное, что в следующий раз гномик, шапку которого мы поменяли, не ошибётся, и «зона ошибки» уменьшится.
За конечное число таких шагов мы получим последовательность из нашего класса, в которой ни один гномик не ошибся. Очевидно, что для любых двух стартовых последовательностей из одного класса итоговая последовательность получится одной и той же, таким образом, мы получили функцию выбора.
Таким образом, задача полностью сводится к поиску модели, в которой функции выбора для наших классов нет. Если мы такую модель найдём — гномики проиграют.
Ответ: да.
Возьмём любой класс. Наденем на гномиков шапки в соответствии с любой последовательностью из этого класса (без АС мы этого сделать не сможем, поэтому будем проводить счётное число экспериментов параллельно). Зададим гномикам Вопрос, возьмём последнего не угадавшего свой цвет, и поменяем его шапку на другую. Его точка зрения не изменится (он видит то же, что и раньше), у гномиков, стоящих перед ним — тем более. Гномики, находящиеся ближе к началу очереди, могут изменить свой ответ, но нам это неважно — главное, что в следующий раз гномик, шапку которого мы поменяли, не ошибётся, и «зона ошибки» уменьшится.
За конечное число таких шагов мы получим последовательность из нашего класса, в которой ни один гномик не ошибся. Очевидно, что для любых двух стартовых последовательностей из одного класса итоговая последовательность получится одной и той же, таким образом, мы получили функцию выбора.
Таким образом, задача полностью сводится к поиску модели, в которой функции выбора для наших классов нет. Если мы такую модель найдём — гномики проиграют.
Я не понял, честно говоря. Какую злодей последовательность ни выберет, после конечного числа шагов все гномики назовут ее (0 ошибок). Каким это образом тут задается функция выбора?
Гномики не могут использовать результаты предыдущего эксперимента, их стратегия всегда одинакова. Последовательность меняет злодей, а гномики только подсказывают ему, как её менять (например, он каждый раз может надевать на гномиков шапки тех цветов, которые они назвали). Утверждается, что (1) при любой стратегии гномиков и любой исходной последовательности этот процесс стабилизируется за конечное число шагов, (2) что результат стабилизации лежит в том же классе, что и исходная последовательность, и (3) что для всех последовательностей из одного класса результат стабилизации одинаков. А значит, в каждом классе появился канонический (при данной стратегии гномиков) элемент.
Если применять коценпции теории алгоритмов, то вот статья, в которой доказывается, что невозможно найти минимальный алгоритм, выполняющий заданную задачу =)
Если конечно сами гномики — машины Тьюринга.
Если конечно сами гномики — машины Тьюринга.
Спасибо за прекрасную задачу. Действительно заставляет задуматься.
Есть две разные «математики» — с аксиомой выбора и без нее. Обе математики (пока) имеют право на существование, так как никто не доказал, что они противоречивы. И вопрос верно ли авторское решение теряет смысл в этом контексте. Решение верно в математике с аксиомой выбора и неверно в математике без аксиомы выбора. Вот и все.
Есть две разные «математики» — с аксиомой выбора и без нее. Обе математики (пока) имеют право на существование, так как никто не доказал, что они противоречивы. И вопрос верно ли авторское решение теряет смысл в этом контексте. Решение верно в математике с аксиомой выбора и неверно в математике без аксиомы выбора. Вот и все.
Моей целью было показать, что и с аксиомой выбора авторское решение неверно. Двумя комментариями выше человек, вроде бы, поставил точку, доказав, что решения и вовсе нет.
Как ни странно, нельзя даже сказать, что «без аксиомы выбора решения нет». Ведь может быть такая ситуация, что аксиома выбора в полном объёме не действует (например, для подмножеств гиперконтинуума), но, несмотря на это, континуум можно вполне упорядочить. Тогда и функция выбора для гномиков будет существовать. Всё, что пока удалось доказать — что решение есть тогда и только тогда, когда есть функция выбора на классах эквивалентности. И что существует модель (ZF+AD), в которой этой функции нет.
Хм, в статье я даже не упомянал об возможности невыполнения АС. Пост как раз о том, что пусть даже она и есть, решения всё равно нет — так и так нет. И вы это более-менее подтвердили чуть выше =)
Я как раз считаю, что при наличии АС решение есть. Правда, для нас оно неконструктивно, а гномики, чтобы им пользоваться, должны иметь быстродействие не менее континуума операций в секунду (или знать порядок элементов вполне упорядоченного континуума наизусть, тогда им хватит счетного числа операций).
Понимаете, если вы докажете, что решения у задачи нет (с аксиомой выбора), то тем самым решите фундаментальную проблему человечества и докажете противоречивость ZFC. Потому что все рассуждения в авторском решении следуют из аксиом ZFC.
Пытаясь поставить задачу в интуитивные русла, вы забываете, что в ней речь идет о бесконечном наборе гномиков, и вы не можете бесплатно оперировать такими интуитивные понятиями типа: «как гномикам договориться» или «гномик видит шапки на всех гномиках перед ним». Вся проблема в том, что задача не реализуема на практике (принимай ты аксиому выбора или не принимай), так как гномиков бесконечно. Единственное, что мы можем сделать в такой ситуации — это признать, что задача про гномиков чисто формальная и не реализуема в реальной жизни. И теперь, приняв это, мы спокойно можем решать эту формальную задачу в разных аксиоматических системах (с аксиомой выбора и без нее). В разных системах наша формальная задача может иметь разный ответ. И ничего страшного в этом нет. Грубо говоря, на практике все равно не проверить, поэтому наша интуиция нам не друг.
Пытаясь поставить задачу в интуитивные русла, вы забываете, что в ней речь идет о бесконечном наборе гномиков, и вы не можете бесплатно оперировать такими интуитивные понятиями типа: «как гномикам договориться» или «гномик видит шапки на всех гномиках перед ним». Вся проблема в том, что задача не реализуема на практике (принимай ты аксиому выбора или не принимай), так как гномиков бесконечно. Единственное, что мы можем сделать в такой ситуации — это признать, что задача про гномиков чисто формальная и не реализуема в реальной жизни. И теперь, приняв это, мы спокойно можем решать эту формальную задачу в разных аксиоматических системах (с аксиомой выбора и без нее). В разных системах наша формальная задача может иметь разный ответ. И ничего страшного в этом нет. Грубо говоря, на практике все равно не проверить, поэтому наша интуиция нам не друг.
Но не буду вас слишком запутывать, и так уже нагородил. Дело в том, что я вас только что обманул. Кто попался? Нельзя выбрать наименьший в лексикографическом порядке элемент класса.
Подлый, коварный автор! Я прошерстил все комменты, прежде чем догадался прочитать псто дальше. Никак не мог поверить, что такую лажу никто не заметил)
deleted
О чем этот пост вообще?
А мне показалось, что разговор все-таки ни о чем. Нет, конечно о чем-то говорят, но это все равно ни о чем. Выращенные в физтехах, верящие в существование абсолютной истины, фанатики симметрии пытаются найти смысл и стройность в загадочном мире. И все только ради того, чтобы не меняться и заставить других верить в подобную инерцию. Сколько открытий же им принесет новый мир, который наступает и никого не спрашивает.
Минусующие, объясните мне, что такое бесконечность?
Какая абсолютная истина? Какой-такой мир? Половина разговора шла о том, что в разных математиках ответ на задачу различен — так что ни о какой абсолютной истине никто и не думает. И ни одна из этих математик ни к какому миру отношения не имеет. Какой бы новый мир не наступил, для него найдётся какая-нибудь модель где-нибудь на задворках математики (частный случай, например, фрактальная размерность 9+2/3 с трансфинитным временем… кого этим можно удивить?)
фрактальная размерность 9+2/3 с трансфинитным временем
1: 0 в вашу пользу.
Но я не считаю, что математика была или будет неприменима. Я считаю, что математики и теор. физики уже вынуждены крошить фундамент на котором стоит их последовательное описание мира, чтобы двигаться дальше (тупо, чтобы получать зарплаты). И эта задача именно об этом. О том, что само понятие модели подвергается деконструкции. А обсуждение пустое, потому что его участники находятся либо со стороны одной математики — одной абсолютной истины, либо со стороны другой. И никто даже не пытается отойти от модели модели. Куда удобнее и мягче конструировать урода дальше.
1: 0 в вашу пользу.
Но я не считаю, что математика была или будет неприменима. Я считаю, что математики и теор. физики уже вынуждены крошить фундамент на котором стоит их последовательное описание мира, чтобы двигаться дальше (тупо, чтобы получать зарплаты). И эта задача именно об этом. О том, что само понятие модели подвергается деконструкции. А обсуждение пустое, потому что его участники находятся либо со стороны одной математики — одной абсолютной истины, либо со стороны другой. И никто даже не пытается отойти от модели модели. Куда удобнее и мягче конструировать урода дальше.
Доказал ли я неверность авторского решения? Думаю, что да. Формулировка задачи — как гномикам договориться. Необходимость аксиомы выбора однозначно говорит, что ответа на «как» в решении нет и быть не может.
Думаю что нет, не доказали. По формулировке задачи гномики таковы, что как-то способны воспринимать и оперировать любыми бесконечными последовательностями шапок сразу и целиком. Поэтому, думаю, и «говорить» и «сравнивать» такие последовательности они умеют. Значит как-то договорятся.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача про гномов и разноцветные шапки