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

С первого взгляда, перспективы узников весьма печальны: в худшем случае — все, а с вероятностью 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
Т.е. все таки получится несчетное число таких множеств