Здравствуйте, nikov, Вы писали:
BZ>>это какая-то базовая теорема — что n-мерные пространства также являются счётными. и даже док-во, не без твоей помощи, я вспомнил. но мне кажется что если с е помощью ты докажешь что какая-то стратегия даёт вероятность выживания при случайных шапках больше 50%, то ты что-то посчитал неправильно
N>Я же говорю, мы не гарантируем какую-либо вероятность выживания для какого-либо конкретного узника. Мы гарантируем, что при любом распределении шапок (будь оно случайным, или основанным на алгоритме, или ещё каким-то — не важно) погибнет лишь конечное число узников. Мы не гарантируем, что их будет меньше 100 или меньше 1000, но оно будет конечным.
т.е. в случайной последовательности бит ты их можешь предсказывать с вероятностью больше 50%?
Здравствуйте, BulatZiganshin, Вы писали:
BZ>т.е. в случайной последовательности бит ты их можешь предсказывать с вероятностью больше 50%?
я к тосму что такая формулировка выглядит гораздо интересней, если конечно я не ошибся и она эквивалентна исходной (точнее является её частным случаем когдла насяльник даже не интеерсуется этими вашими стратегиями)
Здравствуйте, 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%?
Если это вопрос про меня, то я не способен знать бесконечное число элементов. Поэтому, будем считать, что это вопрос про некоторое идеализированное существо, которое способно. Разумеется, мы уже не подразумеваем физическую осуществимость данного процесса, и не можем говорить о физических вероятностях (которыми, например, оперирует статистическая или квантовая физика, и которые имеют отношение к объективной реальности).
Так как мы рассуждаем о несчётном множестве возможных последовательностей, где интуитивные представления могут подводить, надо перейти на формальное основание. Чтобы говорить о вероятностях, нужно определить вероятностное пространство, т.е. указать некоторое пространство элементарных событий, определить на нём сигма-алгебру, и ввести некоторую сигма-аддитивную меру. Может оказаться, что это возможно сделать различными способами, и только какой-то из них может соответствовать тому, что ты интуитивно подразумеваешь под вероятностью в данном конкретном вопросе. Если ты определишь вероятностное пространство, котрое ты имеешь в виду, то, я думаю, будет нетрудно дать ответ на твой вопрос.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>может будем говорить по существу? есть случ. последовательность, ты знаешь все её элементы с номером больше N. BZ>>как это поможет тебе угадать N-й элемент с вероятностью больше 50%?
N>Если это вопрос про меня, то я не способен знать бесконечное число элементов. Поэтому, будем считать, что это вопрос про некоторое идеализированное существо, которое способно. Разумеется, мы уже не подразумеваем физическую осуществимость данного процесса, и не можем говорить о физических вероятностях (которыми, например, оперирует статистическая или квантовая физика, и которые имеют отношение к объективной реальности).
Я, кажется, понял, какую вероятность ты имеешь в виду.
Если мы рассмотрим в качестве повторяющегося случайного процесса предъявление Предсказателю конечных отрезков (с указанными смещениями от начала) независимых бесконечных случайных последовательностей, где каждый бит выбран с помощью независимого случайного процесса, равновероятно дающего исходы 0 или 1, и он старается угадать для каждой из этих последовательностей бит, предыдущий по отношению к конечному отрезку, который он увидел, и мы оцениваем вероятность успешного предсказания в бесконечной серии таких испытаний, то эта вероятность равна 50%.
В условии задачи описана совершенно другая ситуация. Если мы хотим представить её в виде случайного процесса, то это можно сделать следующим образом. В начале Предсказатель выбирает стратегию. Затем фиксируется некоторая случайная последовательность (общая для всех последующих испытаний), где каждый бит выбран с помощью независимого случайного процесса, равновероятно дающего исходы 0 или 1. В качестве повторяющегося процесса рассматривается предъявление Предсказателю всевозможных конечных отрезков (с указанными смещениями от начала), и он старается угадать в каждом из этих случаев бит, предыдущий по отношению к наблюдаемому конечному отрезку одной и той же последовательности (не сохраняя память, приобретённую в результате каждого испытания — или, что то же самое, испытания проводятся независимо с счётным множеством копий Предсказателя, которые следуют одной и той же стратегии). Мы оцениваем вероятность успешного предсказания в бесконечной серии таких испытаний на одной и той же последовательности. В этом случае, как ни парадоксально, существует стратегия, которая обеспечивает вероятность правильного ответа 100% (это не означает достоверного события — конечное количество ответов из бесконечной серии испытаний могут оказаться ошибочными). Смысл этюда состоит в нахождении такой стратегии.
Ещё раз хочу подчеркнуть, что эти два случайных процесса совершенно не эквивалентны.
Здравствуйте, nikov, Вы писали:
N>Если мы рассмотрим в качестве повторяющегося случайного процесса предъявление Предсказателю конечных отрезков (с указанными смещениями от начала) независимых бесконечных случайных последовательностей
Под "конечным отрезком" я подразумеваю подпоследовательность бесконечной последовательности, состоящую из всех её элементов с индексами, большими некоторого значения (т.е. результат отрезания от последовательности некоторого её начального отрезка из n элементов). Таким образом, конечный отрезок тоже является бесконечной последовательностью. Прошу прощения за неудачную терминологию.
Re[3]: Узники и шапки
От:
Аноним
Дата:
04.06.14 06:30
Оценка:
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, Аноним, Вы писали:
А>>Кстати, тут физика встречается с математикой.
N>Сама постановка задачи — бесконечное число узников, видящих бесконечно далеко и способных договориться о несчётном числе возможных исходов — как бы намекает, что задача не совсем физическая.
Аноним (то есть, я) как бы намекает. Что ты ни при каких раскладах не получишь своего решения на конечной последовательности длины большей любого наперед заданного числа, что аноним (т.е. я) и подразумевает под бесконечной последовательностью.
Re[12]: Узники и шапки
От:
Аноним
Дата:
04.06.14 06:37
Оценка:
Здравствуйте, 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>Однако, есть стратегия, которая гарантирует гораздо лучший исход. Попробуйте её найти.
Я тут попробовал набросать решение основанное на этой же аксиоме, но с попыткой держать призоньеров в рамках следующего набора неконструктивных 'мега-вычислительных' способностей:
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, этим можно ограничиться.
, отодвигая точку z сколь угодно далеко.
Перекуём баги на фичи!
