Здравствуйте, nikov, Вы писали:

N>С первого взгляда, перспективы узников весьма печальны: в худшем случае — все, а с вероятностью 1 — бесконечное количество узников погибнут. И, казалось бы, возможность выбрать стратегию никак не улучшает их положение: цвет шапок впереди стоящих узников не имеет причинной связи с цветом шапки узника, который их наблюдает, а других источников информации у него нет.

Тут еще надо учесть конечную скорость распространения света и звука...

Здравствуйте, nikov, Вы писали:

N>Для этого мне потребовалось бы рассказать решение. Я смогу это пояснить после того, как кто-нибудь запостит решение.

Да не будет никакого решения. Будет просто полная дурь. В лучшем случае софистика. ИМХО, разумеется.

Здравствуйте, alpha21264, Вы писали:

A>Здравствуйте, nikov, Вы писали:

N>>Для этого мне потребовалось бы рассказать решение. Я смогу это пояснить после того, как кто-нибудь запостит решение.

A>Да не будет никакого решения. Будет просто полная дурь. В лучшем случае софистика. ИМХО, разумеется.

Замечательное и простое решение ниже уже дали.
http://habrahabr.ru/post/190242/
Никакой софистики, всё корректно

Здравствуйте, <Аноним>, Вы писали:


А>Замечательное и простое решение ниже уже дали.
А>http://habrahabr.ru/post/190242/
А>Никакой софистики, всё корректно

По ссылке представлено опровержение решения

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, <Аноним>, Вы писали:


А>>Замечательное и простое решение ниже уже дали.
А>>http://habrahabr.ru/post/190242/
А>>Никакой софистики, всё корректно

Б>По ссылке представлено опровержение решения

Хм, тогда это вопрос обсуждения, ибо я там вижу следующее :

1) Формулировка задачи
2) Корректное её решение
3) Рассуждение автора о свойствах аксиомы выбора и о проблемах с ней связанных.

Из-за того, что он не смог решить задачу, потребовалось объяснить, почему решение "не совсем верное".
Объяснил, его эмоции понятны, свойства аксиомы выбора тоже. Решение по ссылке

А>Из-за того, что он не смог решить задачу, потребовалось объяснить, почему решение "не совсем верное".
А>Объяснил, его эмоции понятны, свойства аксиомы выбора тоже. Решение по ссылке

Может ли данная задача быть решена без использования аксиомы выбора — искусственный вопрос.
Аналогично, можно на каждую школьную задачку по геометрии спрашивать, может ли она быть решена без аксиомы Евклида и выдавать это за опровержение.
Смысла не вижу, в любом случае по ссылке никаких строгих рассуждений по этому вопросу нет, так что вопрос открытый и неинтересный.

Здравствуйте, <Аноним>, Вы писали:

А>Хм, тогда это вопрос обсуждения, ибо я там вижу следующее :

По ссылке ожидал увидеть чье-либо решение, и самое главное, доказательство правильности этого решения.

А>2) Корректное её решение

Хочу разобраться. Поэтому

Цитата

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

Вопрос 1:
Можно ли вообще разбить все возможные последовательности колпаков на классы эквивалентности с такой (выделенной) формулировкой. У меня почему-то получается единственный класс "эквивалентности", который включает в себя все последовательности (бесконечное число последовательностей). Выбора из этого класса вообще теряет смысл для решения задачи.

Здравствуйте, nikov, Вы писали:

N>В тюрьме находится бесконечное количество узников, пронумерованных всеми натуральными числами (номера написаны у них на одежде). Однажды, когда начальнику тюрьмы стало скучно, он объявил, что всех узников выведут во двор тюрьмы, выстроят в колонну по порядку номеров так, что каждый узник будет видеть всех узников с большими номерами, и каждому наденут на голову чёрную либо белую шапку, по усмотрению начальника тюрьмы (надо отметить, что у узников очень хорошее зрение и память, так что они могут увидеть и запомнить номера и цвет шапок всех впереди стоящих узников). После этого каждый узник должен написать на бумажке предполагаемый цвет своей шапки, и передать её стоящему рядом стражнику (другие узники не знают, что он написал). Те узники, которые напишут цвет своей шапки верно, выйдут на свободу, а остальных — казнят. У узников есть время посовещаться и решить, как они будут действовать (времени достаточно, даже чтобы установить индивидуальные правила для каждого узника и для каждой бесконечной последовательности шапок, которую он может увидеть).

N>С первого взгляда, перспективы узников весьма печальны: в худшем случае — все, а с вероятностью 1 — бесконечное количество узников погибнут. И, казалось бы, возможность выбрать стратегию никак не улучшает их положение: цвет шапок впереди стоящих узников не имеет причинной связи с цветом шапки узника, который их наблюдает, а других источников информации у него нет.
С вероятностью 1 — бесконечное количество узников погибнет и с такой же останется в живых.

N>Однако, есть стратегия, которая гарантирует гораздо лучший исход. Попробуйте её найти.
Никакой стратегии, потому как для нее нет информации ни спереди, ни сзади. Ну, разве что обнаружится период, и можно вычислить свое место..

Здравствуйте, Буравчик, Вы писали:

Б>Вопрос 1:
Б>Можно ли вообще разбить все возможные последовательности колпаков на классы эквивалентности с такой (выделенной) формулировкой. У меня почему-то получается единственный класс "эквивалентности", который включает в себя все последовательности (бесконечное число последовательностей).
это точно не правда. последовательность из всех нулей и из всех едениц различаются в бесконечном колличестве позиций. значит классов как минимум два (легко построить алгоритм строящий бесконечное множество таких последовательностей, но не все)
Б> Выбора из этого класса вообще теряет смысл для решения задачи.
отнють. мы изначально оперировали с бесконечными объектами, так что придется терпеть все тяготы и лишения сурового матана

Здравствуйте, cvetkov, Вы писали:

C>Здравствуйте, Буравчик, Вы писали:

C>это точно не правда. последовательность из всех нулей и из всех едениц различаются в бесконечном колличестве позиций. значит классов как минимум два (легко построить алгоритм строящий бесконечное множество таких последовательностей, но не все)

Да, все верно. Но также просто провести бесконечный "путь" от одной последовательности (состоящей из нулей) к другой (состоящий из единиц), в котором каждый "шаг" будет отличаться ровно на одну позицию. Значит все промежуточные шаги должны находиться в одном классе. И, как следствие, указанные две последовательности тоже. Противоречие, однако.

Здравствуйте, Буравчик, Вы писали:
Б>Хочу разобраться. Поэтому

Б>Цитата
Б>

Б>Рассмотрим все возможные последовательности колпаков. Назовем две последовательности эквивалентными, если они различаются лишь в конечном числе позиций. Это отношение, очевидно, транзитивно, рефлексивно и симметрично, поэтому можно с его помощью разбить все возможные последовательности на классы. По другому: две последовательности будут принадлежать одному классу, если они различаются лишь конечным числом колпаков.

Б>Вопрос 1:
Б>Можно ли вообще разбить все возможные последовательности колпаков на классы эквивалентности с такой (выделенной) формулировкой. У меня почему-то получается единственный класс "эквивалентности", который включает в себя все последовательности (бесконечное число последовательностей). Выбора из этого класса вообще теряет смысл для решения задачи.

1) Это отношение эквивалентности?
Судя по определению да.
2) Отношение эквивалентности всегда влечёт возможность разбить на классы?
В рамках наивной теории множеств — да. В рамках zfc, может быть тут какая-то тонкость? Это единственное место, где я вижу какую-то проблему, строго доказать на аксиомах не берусь, но каких-то упоминаний на эту тему нет.

3) Класс не один, так как 00000.. и 11111.. принадлежат разным классам.

По ссылке был дан классический аналогичный пример разбиения:
http://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8
Всё абсолютно аналогично.
Если мы представим наши последовательности как числа от нуля до 1, то, если две последовательности эквивалентны по нашему отношению, то их разница рациональна => любой наш класс эквивалентности является подмножеством класса эквивалентности Витали.
Всё чисто

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, cvetkov, Вы писали:

C>>Здравствуйте, Буравчик, Вы писали:

C>>это точно не правда. последовательность из всех нулей и из всех едениц различаются в бесконечном колличестве позиций. значит классов как минимум два (легко построить алгоритм строящий бесконечное множество таких последовательностей, но не все)

Б>Да, все верно. Но также просто провести бесконечный "путь" от одной последовательности (состоящей из нулей) к другой (состоящий из единиц), в котором каждый "шаг" будет отличаться ровно на одну позицию. Значит все промежуточные шаги должны находиться в одном классе. И, как следствие, указанные две последовательности тоже. Противоречие, однако.

Утверждение, которое поможет разрешить эту проблему, звучит следующим образом (далее слово последовательность означает последовательность элементов).
Если последовательность принадлежит множеству, то предел последовательности не обязательно принадлежит этому множеству.

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

0000000000000..
1000000000000..
1100000000000..
...

Элемента из всех 11111.. тут нет, и поэтому никаких противоречий нет.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, alpha21264, Вы писали:

A>>Да не будет никакого решения. Будет просто полная дурь. В лучшем случае софистика. ИМХО, разумеется.

А>Замечательное и простое решение ниже уже дали.
А>http://habrahabr.ru/post/190242/
А>Никакой софистики, всё корректно

Ну так я и знал.
Один школяр не понял умных слов, написанных в теореме.
И его уже и опровергли.

Здравствуйте, alpha21264, Вы писали:

А>>Замечательное и простое решение ниже уже дали.
А>>http://habrahabr.ru/post/190242/
А>>Никакой софистики, всё корректно

A>Ну так я и знал.
A>Один школяр не понял умных слов, написанных в теореме.
A>И его уже и опровергли.

поясните свою мысль, пожалуйсто.

Здравствуйте, <Аноним>, Вы писали:

А>2) Отношение эквивалентности всегда влечёт возможность разбить на классы?
А>В рамках наивной теории множеств — да. В рамках zfc, может быть тут какая-то тонкость? Это единственное место, где я вижу какую-то проблему, строго доказать на аксиомах не берусь, но каких-то упоминаний на эту тему нет.

Да уж, было бы круто доказать существование случаев, в которых невозможно разбить множество на классы

А>3) Класс не один, так как 00000.. и 11111.. принадлежат разным классам.

Вижу, вот и хочу понять как так. Вроде класс один, а вроде их бесконечное количество (ну или точно не один).

А>По ссылке был дан классический аналогичный пример разбиения:
А>http://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8
А>Всё абсолютно аналогично.
А>Если мы представим наши последовательности как числа от нуля до 1, то, если две последовательности эквивалентны по нашему отношению, то их разница рациональна => любой наш класс эквивалентности является подмножеством класса эквивалентности Витали.
А>Всё чисто

Меня интересовало количество классов эквивалентности, а не свойства конкретного класса.

И если пользуемся аналогией про числа, то вопрос:

Может ли бесконечная сумма рациональных чисел быть равна иррациональному числу. Почему?

Здравствуйте, <Аноним>, Вы писали:

А>Утверждение, которое поможет разрешить эту проблему, звучит следующим образом (далее слово последовательность означает последовательность элементов).
А>Если последовательность принадлежит множеству, то предел последовательности не обязательно принадлежит этому множеству.

Идея ясна. Но!

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

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

2. И вопрос. Рассмотрим другой элемент, не предел (обозначим LIM), а элемент перед этим пределом (обозначим LIM-1). Очевидно, что LIM и LIM-1 принадлежат к одному классу. Так что получается, и LIM-1 не достичь? Ведь если достигнем LIM-1, то и LIM сможем достичь? И далее не достичь LIM-2, LIM-3 и т.п.? Так мы и до исходного элемента дойдем (количество элементов-то в классе бесконечно).

А>Элемента из всех 11111.. тут нет, и поэтому никаких противоречий нет.

Пока что противоречие вижу. Поэтому и прошу объяснений, как "на пальцах", так и ссылками — на книги, работы, теоремы (и даже аксиомы!) А лучше так и так . Объясните.

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, <Аноним>, Вы писали:

А>>2) Отношение эквивалентности всегда влечёт возможность разбить на классы?
А>>В рамках наивной теории множеств — да. В рамках zfc, может быть тут какая-то тонкость? Это единственное место, где я вижу какую-то проблему, строго доказать на аксиомах не берусь, но каких-то упоминаний на эту тему нет.

Б>Да уж, было бы круто доказать существование случаев, в которых невозможно разбить множество на классы

А>>3) Класс не один, так как 00000.. и 11111.. принадлежат разным классам.

Б>Вижу, вот и хочу понять как так. Вроде класс один, а вроде их бесконечное количество (ну или точно не один).

А>>По ссылке был дан классический аналогичный пример разбиения:
А>>http://ru.wikipedia.org/wiki/%D0%9C%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE_%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8
А>>Всё абсолютно аналогично.
А>>Если мы представим наши последовательности как числа от нуля до 1, то, если две последовательности эквивалентны по нашему отношению, то их разница рациональна => любой наш класс эквивалентности является подмножеством класса эквивалентности Витали.
А>>Всё чисто

Б>Меня интересовало количество классов эквивалентности, а не свойства конкретного класса.
Б>И если пользуемся аналогией про числа, то вопрос:
Б>Может ли бесконечная сумма рациональных чисел быть равна иррациональному числу. Почему?

Все вопросы, которые вами задаются (и по посту выше), вполне имеют право на существование, и проблематика понятна;
но всё-таки они относятся к основам матанализа, а точнее к первым определениям в нём (понятие предела, рациональные/вещественные числа и т.д.), поэтому что-то тут на пальцах сложно объяснять, проще прочитать профессиональную литературу.

Мне кажется, можно поискать по следующим ключевым словам:
Основы матанализа. Предел последовательности. Вещественные числа.

Здравствуйте, <Аноним>, Вы писали:

Б>>Может ли бесконечная сумма рациональных чисел быть равна иррациональному числу. Почему?

А>Все вопросы, которые вами задаются (и по посту выше), вполне имеют право на существование, и проблематика понятна;
А>но всё-таки они относятся к основам матанализа, а точнее к первым определениям в нём (понятие предела, рациональные/вещественные числа и т.д.), поэтому что-то тут на пальцах сложно объяснять, проще прочитать профессиональную литературу.

Вроде задавал конкретный вопрос, а вместо ответа получил, извините, отписку.

А>Мне кажется, можно поискать по следующим ключевым словам:
А>Основы матанализа. Предел последовательности. Вещественные числа.

Основы я изучал. Иррациональное (как и любое вещественное) число может быть представлено в виде бесконечной десятичной дроби. Значит может быть представлено как бесконечная сумма рациональных чисел.

Но если так, то внутри одного класса эквивалентности должны оказаться все вещественные числа (в том числе иррациональные!), но это противоречит отношению эквивалентности. Ну и возвращаясь к задаче — все последовательности шапок окажутся в одном классе. Так где ошибка-то?

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, <Аноним>, Вы писали:

Б>>>Может ли бесконечная сумма рациональных чисел быть равна иррациональному числу. Почему?

А>>Все вопросы, которые вами задаются (и по посту выше), вполне имеют право на существование, и проблематика понятна;
А>>но всё-таки они относятся к основам матанализа, а точнее к первым определениям в нём (понятие предела, рациональные/вещественные числа и т.д.), поэтому что-то тут на пальцах сложно объяснять, проще прочитать профессиональную литературу.

Б>Вроде задавал конкретный вопрос, а вместо ответа получил, извините, отписку.

А>>Мне кажется, можно поискать по следующим ключевым словам:
А>>Основы матанализа. Предел последовательности. Вещественные числа.

Б>Основы я изучал. Иррациональное (как и любое вещественное) число может быть представлено в виде бесконечной десятичной дроби. Значит может быть представлено как бесконечная сумма рациональных чисел.

Б>Но если так, то внутри одного класса эквивалентности должны оказаться все вещественные числа (в том числе иррациональные!), но это противоречит отношению эквивалентности. Ну и возвращаясь к задаче — все последовательности шапок окажутся в одном классе. Так где ошибка-то?

Предлагаю, как джентльмен, просто поверьте на слово. Всё нормально. И рациональные числа не равны иррациональным, и последовательности куда надо принадлежат.

N>Однако, есть стратегия, которая гарантирует гораздо лучший исход. Попробуйте её найти.
Бесконечное количество узников могут при помощи шапок с вероятностью 1 навешать люлей конечному количеству охранников
А если охранникое тоже бесконечное количество, то баланс люлей определяется пределом отношения одной бесконечности на другую.
Но если серъезно то ИМХО тут вся надежда на неидеальность генератора случайных чисел. Если рандом совсем-совсем без закономерностей — то бесконечность/2 умрет, и бесконечность/2 выживет независимо от стратегии. Ну а если рандом все же не идеален, то на тему анализа псевдослучайной последовательности чисел уже столько написано, что глупо было бы пытаться в этой ветке придумать чтото революционное.