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

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

Однако, есть стратегия, которая гарантирует гораздо лучший исход. Попробуйте её найти.

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

N>Однажды, когда начальнику тюрьмы стало скучно

Есть не менее занимательный способ развлечься — разрезать шар на несколько частей и составить из них пару копий исходного :)

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

W>Есть не менее занимательный способ развлечься — разрезать шар на несколько частей и составить из них пару копий исходного

Ну, искомая стратегия узников гораздо проще процесса разрезания шара. Хотя общая идея у них есть: декартово произведение любого количества непустых множеств непусто.

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

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

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

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

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

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

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

Переходим от шапок к двоичному числу.
Если оно рациональное — есть период, его по умолчанию можно продолжить и на себя, следовательно, погибнет конечное количество узников(до начала периода).
Если оно иррациональное, то
???
Profit.

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

N>декартово произведение любого количества непустых множеств непусто.
Ну, это весьма сомнительное утверждение. Будь оно верным, то спастись смогли бы все за исключением конечного числа неудачников. В конструктивной вселенной, где удвоение шара невозможно, к счастью, погибнет всё же бесконечное их число.

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

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

N>>декартово произведение любого количества непустых множеств непусто.
W>Ну, это весьма сомнительное утверждение. Будь оно верным, то спастись смогли бы все за исключением конечного числа неудачников. В конструктивной вселенной, где удвоение шара невозможно, к счастью, погибнет всё же бесконечное их число.

Я не вижу в удвоении шара ничего парадоксального. Во первых, очевидно, что это возможно при разбиении на бесконечное число частей — просто распылим шар на отдельные точки. То, что объём каждой точки нулевой, совершенно не мешает составить из них тело положительного объёма. При разбиении же шара на конечное число частей, не все из них должны являться линейно связными, то есть фактически могут состоять из бесконечного количества фрагментов, которые объедиенены только требованием инвариантности расстояний между всеми их точками. Построение Банаха — Тарского не выделяет какой-то конкретный способ такого разбиения, но просто доказывает, что есть бесконечное множество таких способов.
Наличие множеств, конкретные элементы которых мы не можем описать, не должно смущать — например, привычное нам множество действительных чисел несчётно, но очевидно, что при любой мыслимой системе нотации, которая использует формулы конечной длины, мы можем индивидуально описать только счётное количество действительных чисел, т.е. бо́льшая часть элементов останется без какой-либо конкретной нотации (т.е. способа назвать, идентифицировать данный конретный элемент). Если же добавить ещё и требование физической осуществимости, то к любому моменту мы можем индивидуально описать лишь конечное количество элементов любого множества, например, множества натуральных чисел. Невозможность рассуждать даже о счётных множествах существенно и необоснованно ограничила бы наши познавательные способности, и отбросила бы нас на много веков назад, к самому зарождению математики.

Кроме того, даже полностью конструктивные построения могут давать парадоксальные, как кому-то может показаться, результаты. Например, можно построить плотное подмножество окружности, которое конгруэнтно некоторому свому собственному подмножеству, даже без разбиения на части. Также, отрезок можно разбить на конечное число частей, и сложить их них некоторое собственное подмножество исходного отрезка.

Мне кажется, что надо иметь весьма необычную интуицию, чтобы допускать возможность существования непустых множеств с пустым декартовым произведением. На мой взгяд, это эквивалентно искусственному и необоснованному исключению всех элементов этого произведения из вселенной, которую описывает наша теория множеств. То есть, они как бы очевидно "есть", но теория искусственно ограничена так, чтобы их "не видеть" как множества (и как элементы других множеств). Это не делает её противоречивой, но делает её неадекватной тому, что мы хотим подразумевать под понятием множества. При этом она может оставаться интересным объектом исследования, как формальная теория (т.е. в качестве абстрактного математического объекта), но становится непригодной, если мы хотим в рамках неё рассуждать о множествах.

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

SO_>Посчитать энтропию последовательности, которую узник видит и выбрать такой цвет, который бы уменьшал ее?

И каким образом это повлияет на исход?

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

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

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

Уточню последовательность действия в условии:
Сначала все заключенные совещаются, вырабатывая стратегию
Потом их выстраивают и одевают шапки, одновременно
Все смотрят на доступную им информацию
Потом все пишут гипотезу
Потом одновременно гипотеза проверяется

Также не совсем понятные критерии успеха, речь идет о вероятности выживания заключенного или "Счетное число выжило" будет достаточно?

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

N>Уточню последовательность действия в условии:
N>Сначала все заключенные совещаются, вырабатывая стратегию (начальник может подслушивать)
N>Потом их выстраивают и одевают шапки, одновременно
N>Все смотрят на доступную им информацию
N>Потом все пишут гипотезу (каждый свою гипотезу, только про свою шапку)
N>Потом одновременно гипотеза проверяется (одновременно, но каждая гипотеза индивидуально)

Да. Уточнения в скобках.

N>Также не совсем понятные критерии успеха, речь идет о вероятности выживания заключенного или "Счетное число выжило" будет достаточно?

Бесконечное количество гарантированно выживает — это хорошо. Лишь конечное число погибает — ещё лучше (и тоже возможно).

Здравствуйте, nikov, Вы писали:
Кстати, тут физика встречается с математикой. Пусть тюремщик выбирает цвет шапки по следующему алгоритму.
X_n = 4*x_(n-1)*(1-x_(n-1)), X_n > 0.5 -- белая, иначе черная. Утверждение, что даже видя любую конечную предыстористорию, текущий узник хрен предскажет цвет своей шапки с вероятностью лучшей, чем 0.5. Поскольку бесконечное число узников физически не может получиться кроме как предел последовательности конечного числа узников, то судьбе узников не позавидуешь.

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

может я чего-то не понимаю в математике, но по моему при случайном назначении цвета шапок вероятность узника выжить составляет 1/2 независимо от используемой им стратегии угадывания

BZ>может я чего-то не понимаю в математике, но по моему при случайном назначении цвета шапок вероятность узника выжить составляет 1/2 независимо от используемой им стратегии угадывания

Мне навскидку тоже так кажется, получается видимая каждым узником информация никак не может повлиять на его личный выбор. А значение его личного выбора строго ровно 1/2. Правда я 100% не уверен, что как 1/2 счетные не группируй, то всегда останется 1/2, но пока кажется очень похожим на правду.

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

BZ>может я чего-то не понимаю в математике, но по моему при случайном назначении цвета шапок вероятность узника выжить составляет 1/2 независимо от используемой им стратегии угадывания

Дело не в вероятностях. Даже если бы вероятность для каждого узника выжить была бы равна 0, это бы само по себе не исключало возможность, что все они выживут по счастливому совпадению. Точно так же, вероятность выжить 1 для каждого не гарантирует, что хотя бы один узник выживет, так как простраство всевозможных комбинаций цветов шапок несчётно.

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

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

А>Кстати, тут физика встречается с математикой.

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

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

N>Дело не в вероятностях... позволяет им согласованно действовать таким образом, что при любом выборе цветов шапок, только конечное число узников могут ошибиться

видимо мы учили разные математики

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

BZ>видимо мы учили разные математики

Давай проверим. Докажем, что объединение счётного семейства попарно непересекающихся множеств, каждое из которых счётно, также является счётным.

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

	Доказательство
	Расположим элементы всех множеств данного семейства в виде бесконечной вправо и вниз таблицы: x₀₀ x₀₁ x₀₂ … x₁₀ x₁₁ x₁₂ … x₂₀ x₂₁ x₂₂ … ⋮ ⋮ ⋮ ⋱ Здесь каждая строка представляет собой некоторое множество семейства, а отдельные клетки строки — элементы этого множества. Данное расположение возможно, так как по предположению теоремы каждое из множеств счётно (т.е. его элементы можно пронумеровать натуральными числами), и само семейство также счётно (т.е. множества также можно пронумеровать натуральными числами). Теперь выпишем все элементы данной таблицы в один ряд, обходя ее по всем конечным диагоналям, идущим сверху-вниз и справа-налево (↙), в порядке возрастания длин этих диагоналей (т.е. первая диагональ будет состоять из одного элемента x₀₀, вторая — из двух элементов x₀₁, x₁₀, третья — из трёх x₀₂, x₁₁, x₂₀, и т.д.): x₀₀ x₀₁ x₁₀ x₀₂ x₁₁ x₂₀ … Так как каждая из диагоналей является конечной, ясно, что рано или поздно мы доберёмся до каждого элемента в этой таблице, и это произойдёт на некотором конечном шаге. Таким образом, мы получаем бесконечную последовательность, в которой каждый элемент таблицы встречается ровно по одному разу (и все они различны, по предположению теоремы), и его позиция в данной последовательности соответствует номеру шага, на котором мы его обнаружили при диагональном обходе таблицы. Порядок элементов в этой последовательности естественным образом определяет их взаимно-однозначное соответствие с натуральными числами, т.е. демонстрирует их счётность, что и требовалось доказать. (ясно, что требование попарного непересечения множеств семейства можно было бы убрать, но доказательство пришлось бы слегка видоизменить, чтобы не считать повторяющиеся элементы по несколько раз)

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

N>Давай проверим. Докажем, что объединение счётного семейства попарно непересекающихся множеств, каждое из которых счётно, также является счётным.

это какая-то базовая теорема — что n-мерные пространства также являются счётными. и даже док-во, не без твоей помощи, я вспомнил. но мне кажется что если с е помощью ты докажешь что какая-то стратегия даёт вероятность выживания при случайных шапках больше 50%, то ты что-то посчитал неправильно

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

BZ>это какая-то базовая теорема — что n-мерные пространства также являются счётными. и даже док-во, не без твоей помощи, я вспомнил. но мне кажется что если с е помощью ты докажешь что какая-то стратегия даёт вероятность выживания при случайных шапках больше 50%, то ты что-то посчитал неправильно

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

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

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

BZ>>видимо мы учили разные математики

N>Давай проверим. Докажем, что объединение счётного семейства попарно непересекающихся множеств, каждое из которых счётно, также является счётным.

N>Вот моё доказательство. Если у тебя похожее, то для целей данного этюда можно считать, что мы учили одинаковые разделы.

N>

	Доказательство
	N>Расположим элементы всех множеств данного семейства в виде бесконечной вправо и вниз таблицы: N> N> N> N> N> N> x₀₀ x₀₁ x₀₂ … x₁₀ x₁₁ x₁₂ … x₂₀ x₂₁ x₂₂ … ⋮ ⋮ ⋮ ⋱ N>Здесь каждая строка представляет собой некоторое множество семейства, а отдельные клетки строки — элементы этого множества. Данное расположение возможно, так как по предположению теоремы каждое из множеств счётно (т.е. его элементы можно пронумеровать натуральными числами), и само семейство также счётно (т.е. множества также можно пронумеровать натуральными числами). N>Теперь выпишем все элементы данной таблицы в один ряд, обходя ее по всем конечным диагоналям, идущим сверху-вниз и справа-налево (↙), в порядке возрастания длин этих диагоналей (т.е. первая диагональ будет состоять из одного элемента x₀₀, вторая — из двух элементов x₀₁, x₁₀, третья — из трёх x₀₂, x₁₁, x₂₀, и т.д.): N> N> N> x₀₀ x₀₁ x₁₀ x₀₂ x₁₁ x₂₀ … N>Так как каждая из диагоналей является конечной, ясно, что рано или поздно мы доберёмся до каждого элемента в этой таблице, и это произойдёт на некотором конечном шаге. Таким образом, мы получаем бесконечную последовательность, в которой каждый элемент таблицы встречается ровно по одному разу (и все они различны, по предположению теоремы), и его позиция в данной последовательности соответствует номеру шага, на котором мы его обнаружили при диагональном обходе таблицы. Порядок элементов в этой последовательности естественным образом определяет их взаимно-однозначное соответствие с натуральными числами, т.е. демонстрирует их счётность, что и требовалось доказать.

Есть проблема.. Ты ж типа отсортировал.. Так вот в любое место этой таблицы можно вставить еще одно множество не перечисленное в этой таблице..
http://sernam.ru/lect_math2.php?id=14
Т.е. все таки получится несчетное число таких множеств

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

BZ>>это какая-то базовая теорема — что n-мерные пространства также являются счётными. и даже док-во, не без твоей помощи, я вспомнил. но мне кажется что если с е помощью ты докажешь что какая-то стратегия даёт вероятность выживания при случайных шапках больше 50%, то ты что-то посчитал неправильно

N>Я же говорю, мы не гарантируем какую-либо вероятность выживания для какого-либо конкретного узника. Мы гарантируем, что при любом распределении шапок (будь оно случайным, или основанным на алгоритме, или ещё каким-то — не важно) погибнет лишь конечное число узников. Мы не гарантируем, что их будет меньше 100 или меньше 1000, но оно будет конечным.

т.е. в случайной последовательности бит ты их можешь предсказывать с вероятностью больше 50%?

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

BZ>т.е. в случайной последовательности бит ты их можешь предсказывать с вероятностью больше 50%?

я к тосму что такая формулировка выглядит гораздо интересней, если конечно я не ошибся и она эквивалентна исходной (точнее является её частным случаем когдла насяльник даже не интеерсуется этими вашими стратегиями)

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

Ох уж эти Гномики...

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

N>Давай проверим. Докажем, что объединение счётного семейства попарно непересекающихся множеств, каждое из которых счётно, также является счётным.


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

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

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

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

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

BZ>т.е. в случайной последовательности бит ты их можешь предсказывать с вероятностью больше 50%?

Зависит от того, что я знаю об этой последовательности.

Если есть случайная последовательность, и я не знаю ни один её элемент, и меня просят угадать элемент c индексом n, то не могу.

Если есть случайная последовательность, и я знаю её элементы с индексами от 0 до n-1, и меня просят угадать элемент c индексом n, то не могу.

Если есть случайная последовательность, и я знаю её элементы с индексами от 0 до 2n, и меня просят угадать элемент c индексом n, то могу с вероятностью 100%.

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

B>Есть проблема..
B>Ты ж типа отсортировал..
Я ничего не сортировал.

B>Так вот в любое место этой таблицы можно вставить еще одно множество не перечисленное в этой таблице..
Можно. Даже можно несколько вставить. Или имеющиеся убрать. И что из этого следует?

B>http://sernam.ru/lect_math2.php?id=14
Посмотрел. По ссылке написано "Счетное множество. Счетность множества рациональных чисел. Несчетность множества действительных чисел". Да, согласен, множество рациональных чисел счётно, а множество действительных — несчётно.

B>Т.е. все таки получится несчетное число таких множеств
Где получится и каких множеств? Я не совсем улавливаю ход твоей мысли.

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

BZ>>т.е. в случайной последовательности бит ты их можешь предсказывать с вероятностью больше 50%?

может будем говорить по существу? есть случ. последовательность, ты знаешь все её элементы с номером больше N. как это поможет тебе угадать N-й элемент с вероятностью больше 50%?

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

BZ>может будем говорить по существу? есть случ. последовательность, ты знаешь все её элементы с номером больше N.
BZ>как это поможет тебе угадать N-й элемент с вероятностью больше 50%?

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

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

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

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

M>Ох уж эти Гномики...

Это не те гномики

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

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

BZ>>может будем говорить по существу? есть случ. последовательность, ты знаешь все её элементы с номером больше N.
BZ>>как это поможет тебе угадать N-й элемент с вероятностью больше 50%?

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

Я, кажется, понял, какую вероятность ты имеешь в виду.

Если мы рассмотрим в качестве повторяющегося случайного процесса предъявление Предсказателю конечных отрезков (с указанными смещениями от начала) независимых бесконечных случайных последовательностей, где каждый бит выбран с помощью независимого случайного процесса, равновероятно дающего исходы 0 или 1, и он старается угадать для каждой из этих последовательностей бит, предыдущий по отношению к конечному отрезку, который он увидел, и мы оцениваем вероятность успешного предсказания в бесконечной серии таких испытаний, то эта вероятность равна 50%.

В условии задачи описана совершенно другая ситуация. Если мы хотим представить её в виде случайного процесса, то это можно сделать следующим образом. В начале Предсказатель выбирает стратегию. Затем фиксируется некоторая случайная последовательность (общая для всех последующих испытаний), где каждый бит выбран с помощью независимого случайного процесса, равновероятно дающего исходы 0 или 1. В качестве повторяющегося процесса рассматривается предъявление Предсказателю всевозможных конечных отрезков (с указанными смещениями от начала), и он старается угадать в каждом из этих случаев бит, предыдущий по отношению к наблюдаемому конечному отрезку одной и той же последовательности (не сохраняя память, приобретённую в результате каждого испытания — или, что то же самое, испытания проводятся независимо с счётным множеством копий Предсказателя, которые следуют одной и той же стратегии). Мы оцениваем вероятность успешного предсказания в бесконечной серии таких испытаний на одной и той же последовательности. В этом случае, как ни парадоксально, существует стратегия, которая обеспечивает вероятность правильного ответа 100% (это не означает достоверного события — конечное количество ответов из бесконечной серии испытаний могут оказаться ошибочными). Смысл этюда состоит в нахождении такой стратегии.

Ещё раз хочу подчеркнуть, что эти два случайных процесса совершенно не эквивалентны.

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

N>Если мы рассмотрим в качестве повторяющегося случайного процесса предъявление Предсказателю конечных отрезков (с указанными смещениями от начала) независимых бесконечных случайных последовательностей

Под "конечным отрезком" я подразумеваю подпоследовательность бесконечной последовательности, состоящую из всех её элементов с индексами, большими некоторого значения (т.е. результат отрезания от последовательности некоторого её начального отрезка из n элементов). Таким образом, конечный отрезок тоже является бесконечной последовательностью. Прошу прощения за неудачную терминологию.

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

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

А>>Кстати, тут физика встречается с математикой.

N>Сама постановка задачи — бесконечное число узников, видящих бесконечно далеко и способных договориться о несчётном числе возможных исходов — как бы намекает, что задача не совсем физическая.
Аноним (то есть, я) как бы намекает. Что ты ни при каких раскладах не получишь своего решения на конечной последовательности длины большей любого наперед заданного числа, что аноним (т.е. я) и подразумевает под бесконечной последовательностью.

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


N>Ещё раз хочу подчеркнуть, что эти два случайных процесса совершенно не эквивалентны.
Мне кажется, что твое "решение" явно или неявно опирается на один из следующих фактов.
1. Каждая бесконечная последовательность содержит саму себя и еще что-то (или две половинки самой себя и еще бесконечную последовательность).
2. Или всегда найдется предсказатель (если нашелся один, то нашлось и бесконечное число) который предсказывает любую подследовательность по предыдущей подпоследовательности с вероятностью больше 50%. Тогда сумма/произведение этих предсказателей будет ошибаться с вероятностью (0.5)^(inf), то есть 0.
Ошибка в 1. и 2. одна ни inf = exp(inf), ни inf == (inf)^n , N ->inf неверны никогда (не получаются из предела последовательности конечных последовательностей).

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

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

Гораздо лучший исход — это конечное количество убитых.
Это значит, что существует некоторая позиция z, начиная с которой нет ни одного убитого, все всё угадали.

Оставим закрытым вопрос, есть ли такая позиция, но допустим, что она есть.
Итак, известно, что color[z..∞) = guess[z..∞)

Узник номер i делает предположение guess[i] на основе (i, color[i+1..∞))
Поскольку палач знает функцию принятия решения, он спокойно может сделать color[i] = 1-guess[i], и так для всех, начиная с z-1 до 0.
То есть, количество жертв равно z.

Раз уж наши узники пишут ответы на бумажках, начиная с самого дальнего проективного конца ∞-1, то и палач может надевать шапки в том же порядке , отодвигая точку z сколь угодно далеко.
Поскольку распределение z — в руках палача, то он может подобрать его так, что матожидание будет бесконечным (?)

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

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


Есть одно решение подобных задач, основанное на аксиоме выбора:
http://ru.wikipedia.org/wiki/%D0%90%D0%BA%D1%81%D0%B8%D0%BE%D0%BC%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%B0#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D1.87.D0.B0.D0.BD.D0.B8.D1.8F )
Например, здесь: http://habrahabr.ru/post/190242/
Но, вопросы с неконструктивностью остаются.

Я тут попробовал набросать решение основанное на этой же аксиоме, но с попыткой держать призоньеров в рамках следующего набора неконструктивных 'мега-вычислительных' способностей:
1) Они умеют видеть и запоминать любые бесконечные счетные последовательности (написано в условии задачи).
2) 'Обьектом' для призоньеров может являтся бесконечное счетное множество чего-либо, а 'строить' его призоньеры могут за конечное время. Поэтому на 'строить' и 'обьект'
навешены кавычки. С несчетными множествами призоньеры работать не умеют.
3) Они умеют совершать обычные поэлементные действия над 'обьектами'. В частности, побитовый XOR над бесконечными двоичными последовательностями.
4) У них есть та самая f из первой формулировки аксиомы выбора: "Для всякого семейства X={A} непустых множеств существует функция f(X, _ ), которая каждому множеству A семейства X
сопоставляет один из элементов этого множества — f(X,A). Функция f называется функцией выбора для заданного семейства.".

Решение:

Призоньеры должны договориться так: когда их выстроят в колонну, то каждый призоньер I должен будет пристально вглядеться в даль, на
хвост колонны, и на основании открывшейся перед взором бесконечной последовательности цветов шапочек 'построить' некоторый 'обьект'.
( Что это за 'обьект' и как его 'строить' — об этом призоньеры должны как раз предварительно договориться между собой. )
Затем каждый призоньер на основании этого 'обьекта' должен вычислить предполагаемый цвет своей шапки. ( Как — оять же,
предварительно должны договориться между собой. ) И написать его на бумажке стражнику.

Вместо рядов призоньеров и цветов шапочек будем использовать бесконечные последовательности нулей и единиц. Т.е. на I-ом месте
последовательности 0 означает белую шапочку у I-ого призоньера, а 1 — черную.
Как известно, множество всех таких последовательностей B — несчетное.

Теперь определим одно интересное счетное подмножество M этого несчетного множества B. Пусть M состоит из двоичных записей справо на лево
всех натуральных чисел с дорисованными бесконечными хвостими из нулей. Т.е., M — это:
0000000....нули до бесконечности
1000000....нули до бесконечности
0100000....нули до бесконечности
1100000....нули до бесконечности
0010000....нули до бесконечности
1010000....нули до бесконечности
................

M обладает четырьмя полезными для призоньеров свойствами:

Свойство1: M — это множество всех элементов из множества B, которые содержат только конечное число единиц в своей записи. Т.е., например,
элемент 11000... содержит 2 единицы, 1011101000... — 5 единиц и т.д.
M не содержит элементов с бесконечным числом единиц. Хотя в множестве B такие элементы есть, например 1111111....единицы до бесконечности.

Свойство2: Если 'умножить по XOR' все элементы M на какой-либо элемент b из B, не принадлежащий M, то получится множество M(b) изоморфное M
и не пересекающееся с M. Под 'умножить по XOR' понимается побитовый XOR двух бесконечных двоичных последовательностей.
Доказательство: раз b не принадлежит M, то b содержит бесконечное число единиц. Т.к. любой элемент из M содержит конечное число единиц, то
его XOR с b будет содержать бесконечное число единиц. Т.к. умножение по XOR обратимо, M(b) изоморфно M.

Свойство3: Если 'умножить по XOR' все элементы M на какой-либо элемент m из M, то получится то же самое множество M. То же самое верно и
для всех множеств M(b), полученных XOR-умножением M на не принадлежащий ему элемент b.
Доказательство: возьмем произвольный m из M и будем его XOR-ить с остальными элементами из M. Новых элементов не получим. Никакие из
старых не пропадут. Для M(b) поступаем точно так же.
Вообще, M можно рассматривать как M(b0), где b0 == 0000000....нули до бесконечности.
Таким образом, учитывая Свойства 2 и 3, для двух разных b1 и b2 из B, соответственно M(b1) и M(b2) либо полностью совпадают либо полностью
не совпадают и изоморфны.

Свойство4: Пусть S — семейство всех несовпадающих и непересекающихся друг с другом множеств вида M(b). Это семейство, во-первых, покрывает
все множество B. Доказательство следует из свойств 2 и 3.
Во-вторых, S подходит в качестве аргумента X в формулировку аксиомы выбора.

Итак, призоньеры должны договориться, что каждый из них запомнит состояние колонны как бесконечную двоичную последовательность d. При этом те позиции, которые он не видит,
пусть заполнит 0-ями (или произвольным шумом, это не важно). А те позиции, которые ему видны — в соответствии с цветами шапочек.
Затем, каждый обязан построить 'обьект' M(d). Иными словами, каждый I-ый призоньер умножит маску M на свой элемент d(I). При этом он получит 'обьект' M(d(I)).
Т.к. хвост колонны все видят один и тот же, 'обьект' M(d(I)) получится одним и тем же для всех I.
Затем, каждый обязан воспользоваться функцией f из аксиомы выбора и получить двоичную последовательность h(I)=f(M(d(I))). Естесственно, h(I) получится одинаковой
для всех I.
В итоге, каждый I-ый призоньер пусть пишет на бумажке стражнику цвет, соответствующий I-ому биту в последовательности h(I), т.е Color(I)=h(I)[I] .

Таким образом, из-за Свойства 1, не угадают лишь конечное число участников викторины.

Подходит ? Или есть решение с меньшем количеством 'мега-способностей' ?

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

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

Узники строят все возможные последовательности и запоминают их. Каждый узник по хвосту однозначно определяет искомую последовательность и называет свой цвет. Начальник тюрьмы может изменить только конечное число шапок, поскольку изменение бесконечного числа дает другую последовательность и снова все узники выживают.

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

OK>Узники строят все возможные последовательности и запоминают их. Каждый узник по хвосту однозначно определяет искомую последовательность и называет свой цвет. Начальник тюрьмы может изменить только конечное число шапок, поскольку изменение бесконечного числа дает другую последовательность и снова все узники выживают.

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

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

A>Свойство2: Если 'умножить по XOR' все элементы M на какой-либо элемент b из B, не принадлежащий M, то получится множество M(b) изоморфное M

Изоморфизм — это биекция, сохраняющее какие-то операции (a ⋄ b = c ⇔ f(a) ⋄ f(b) = f(c)) или отношения (a ≺ b ⇔ f(a) ≺ f(b)) между элементами множества. Про изоморфизм имеет смысл говорить, если мы указали какие именно операции или отношения мы имеем в виду. В данном случае не хватает этого пояснения.

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

N>Здравствуйте, acmx, Вы писали:
A>>Свойство2: Если 'умножить по XOR' все элементы M на какой-либо элемент b из B, не принадлежащий M, то получится множество M(b) изоморфное M
N>Изоморфизм — это биекция, сохраняющее какие-то операции (a ⋄ b = c ⇔ f(a) ⋄ f(b) = f(c)) или отношения (a ≺ b ⇔ f(a) ≺ f(b)) между элементами множества. Про изоморфизм имеет смысл говорить, если мы указали какие именно операции или отношения мы имеем в виду. В данном случае не хватает этого пояснения.

Ну да, в принципе с замечанием согласен. Я использовал термин 'изоморфизм' в общем смысле, как его, впрочем, часто и используют: "Изоморфи́зм (от др.-греч. ἴσος — «равный, одинаковый, подобный» и μορφή — «форма») — это очень общее понятие ..." (отсюда: http://ru.wikipedia.org/wiki/%D0%98%D0%B7%D0%BE%D0%BC%D0%BE%D1%80%D1%84%D0%B8%D0%B7%D0%BC)
Чтобы быть корректным, скажу так: M(b) равномощно M, этим можно ограничиться.

Здравствуйте, 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 выживет независимо от стратегии. Ну а если рандом все же не идеален, то на тему анализа псевдослучайной последовательности чисел уже столько написано, что глупо было бы пытаться в этой ветке придумать чтото революционное.

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

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

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

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

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

Идём по ссылке и читаем.
Что непонятного-то?

Школяр "применил" теорему, смысл которой он не понимал.
Получилось смешно. Автор статьи показал это вполне убедительно.

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

A>Школяр "применил" теорему, смысл которой он не понимал.

А ты не объяснишь, в чём же истинный смысл этой теоремы?

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

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

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

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

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

A>>Школяр "применил" теорему, смысл которой он не понимал.

N>А ты не объяснишь, в чём же истинный смысл этой теоремы?

А какой смысл обьяснять это человеку, который не умеет читать?!
Теорема перед тобой.
Пост на хабре, который обьясняет все ошибки тоже перед тобой.
Чего ты от меня-то хочешь?

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

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

Пусть каждый белый колпак означает 0, каждый чёрный — 1, а порядковый номер означает позицию после запятой в бесконечной двоичной дроби. Тогда весь диапазон выбора заключён между нулём и двоичной бесконечной дробью 0.111(1). Множество таких дробей бесконечно и даже несчётно. Тогда задача сводится к тому, чтобы угадать начало этой дроби по её хвосту...
Обратная задача, угадать хвост дроби по её началу, точно не разрешима (см. доказательство несчётности множества рациональных чисел), а в этой задаче необходимо указать конечное количество разрядов при знании бесконечного ряда...

Я думаю, что не существует способа сделать равновероятный выбор случайного элемента из бесконечного множества. Т.е. мы не можем сделать равновероятный выбор какой-либо дроби из указанного диапазона. Из этого я делаю вывод, что должна существовать закономерность в выборе начальника тюрьмы. Т.е. интуитивно кажется, что решение должно существовать, но вот найти его —