Любопытная задачка по математике
Итак, счётное количество мудрецов выстроены в шеренгу в затылок друг другу.Есть ли первый мудрец, и если да, то он видит всех или наоборот, никого?
знаю 2 способа решения, чтобы 99 узников выжили со 100% вероятностью, а 1 - с 50% 
Но как применить это для модифицированной задачи, пока затрудняюсь.
Но как применить это для модифицированной задачи, пока затрудняюсь.
Есть ли первый мудрец, и если да, то он видит всех или наоборот, никого?Да, первый (скорее последний) мудрец есть. Он видит всех, кроме себя.
А другие мудрецы-то узнают убили первого или нет?
А другие мудрецы-то узнают убили первого или нет?Можно считать, что в обеих задачах стражники сначала проводят опрос общественного мнения, а уж потом берутся за сокращение поголовья узников.
Т.е. нет, мудрецы не знают, правильно ли отвечали их коллеги.
А свой номер каждый мудрец знает в момент ответа (т.е. сколько позади него) ?
А свой номер каждый мудрец знает в момент ответа (т.е. сколько позади него) ?Да, знает.
Правда, я эту задачку помнил, и ответ знал. А решение придумывал.
Я тоже считаю, что ответ совершенно противоречит "здравому смыслу".
Просто еще раз убеждаемся, что бесконечность - непривычна
Конечно, это дело обобщается легко на любое конечное число цветов.
А вот для континуума мудрецов ты сначала укажи алгоритм, как стражники будут их опрашивать ;-)
Я тоже считаю, что ответ совершенно противоречит "здравому смыслу".
Просто еще раз убеждаемся, что бесконечность - непривычна
Конечно, это дело обобщается легко на любое конечное число цветов.
А вот для континуума мудрецов ты сначала укажи алгоритм, как стражники будут их опрашивать ;-)
А вот для континуума мудрецов ты сначала укажи алгоритм, как стражники будут их опрашивать ;-)
Ответ правильный, решение неправильное. Ошибка начинается вот тут:
Тем более, если уже сталкивался с задачей.
Всех последовательностей из нулей и единиц счетное число.Может удалишь пока спойлер? Дай другим порешать.
Тем более, если уже сталкивался с задачей.
Всех последовательностей из нулей и единиц счетное число.тьфу, да. тоже мне математик
Может удалишь пока спойлер?Белым цветом же вроде запостил?..
Белым цветом же вроде запостил?..Мало ли. У меня, например, фон не белый. Отлично читается.
Ну и в любом случае предложенное решение неправильное.
p.s. Спасиб
Да, знает.это первый подвох
мудрецы не знают, правильно ли отвечали их коллегии во второй тоже? тогда во второй они вообще ничего полезного не знают
знают, и немало.
Давай говори, правильно или нет, и сотру.Да, годится. Стирай :-)
Fj уже постил этот парадокс
Может быть, оттуда я его и помню
этот парадоксну а это второй самый главный подвох
зы: решение откопал в архиве
Fj уже постил этот парадоксЧёрт, .
Даже мудрецы те же, только постановка более гуманистическая.
Про Деда-Мороза, который обманывал маленьких детей (давая конфеты и отбирая их) веселее.
Где-то здесь эта задача была уже. Свой номер знать не нужно, решается так же. И для континуума мудрецов так же. Сначала их упорядочиваем частичным порядком порядком и так и опрашиваем. Для континуума ответ вроде тот же, но я не проверял
upd. Не, для континуума не получится так
upd. Не, для континуума не получится так
Свой номер знать не нужно, решается так жея прочитал решение, в котором порядковый номер используется. как можно без порядкового номера решить?
Ну, я чота уже не так уверен, что работает. В общем, отношение эквивалентности выбираем таким образом, что 2 последовательности эквивалентны, если существует сдвиг, при котором они совпадают по всем элементам, кроме конечного числа. В этом случае, если образованный класс непериодичен, то все работает также, если периодичен, то если мудрец видит перед собой последовательность без предпериода, то он выбирает цвет, продолжающий период в его сторону, иначе также как и в обычной задаче. Вроде такое проходит и порядковый номер не нужен
В общем, отношение эквивалентности выбираем таким образом, что 2 последовательности эквивалентны, если существует сдвиг, при котором они совпадают по всем элементам, кроме конечного числаесли не ошибаюсь, то это можно переформулировать так: две последовательности эквивалентны, если начиная с некоторой позиции (разной для двух последовательностей они совпадают. то есть можно отрезать префиксы и останутся одинаковые хвосты.
рассмотрим некий класс, содержащий последовательность Y
в нем будут элементы
Y
1Y
0Y
10Y
00Y
или общая формула:
{0,1}*Y
(это, возможно, лишь часть элементов этого класса)
что надо сказать мудрецу, который видит перед собой Y ?
Если выбранный представитель не содержит этого номера (то есть выбрали Y то неважно, что скажет этот мудрец. Таких мудрецов конечное число.
А если содержит, то говорит элемент по этому номеру.
А если содержит, то говорит элемент по этому номеру.
Таких мудрецов конечное число.не понимаю почему конечное число
ведь формула {0, 1}* Y
Мудрецы представляют собой последовательность {0,1}*N+Y, выбранный представитель - {0,1}*M+Y, то есть без номера будут только первые
N-M мудрецов.
N-M мудрецов.
Если выбранный представитель не содержит этого номера (то есть выбрали Y то неважно, что скажет этот мудрец. Таких мудрецов конечное число.я, кажется, допетрил
таким образом, мудрецы начиная с некоторой позиции будут видеть хвост Представителя.
они делают поиск подстроки (хвоста) и называют число, предшествующее этому хвосту в Представителе
только поиск, вообще говоря, может вернуть несколько результатов, но это в случае периодов только, а с ними более-менее все очевидно
> в классе эквивалентности есть минимальный элемент - он является хвостом всех остальных элементов
Это не так. Минимального элемента нет.
> мудрецы начиная с некоторой позиции будут видеть хвост Представителя.
А вот это так, потому что Пердставитель и реальная последовательность, начиная с некоторого индекса (разного для них) совпадают
по определению эквивалентности. И с этого момента мудрецы уже не ошибаются, ну, с оговоркой на возможную периодичность, когда
соотвествие индексов неоднозначно.
> они делают поиск подстроки (хвоста) и называют число, предшествуещее этому хвосту в Представителе
Да, так сработает.
Это не так. Минимального элемента нет.
> мудрецы начиная с некоторой позиции будут видеть хвост Представителя.
А вот это так, потому что Пердставитель и реальная последовательность, начиная с некоторого индекса (разного для них) совпадают
по определению эквивалентности. И с этого момента мудрецы уже не ошибаются, ну, с оговоркой на возможную периодичность, когда
соотвествие индексов неоднозначно.
> они делают поиск подстроки (хвоста) и называют число, предшествуещее этому хвосту в Представителе
Да, так сработает.
Это не так. Минимального элемента нет.да, что-то в сторону дернуло меня=)
И мудрецы всего мира, вздрагивая, просыпаются по ночам в холодном поту и с учащенным сердцебиением: им приснилось, что они попали в произвольно большое конечное подмножество...
Ну, я чота уже не так уверен, что работает. В общем, отношение эквивалентности выбираем таким образом, что 2 последовательности эквивалентны, если существует сдвиг, при котором они совпадают по всем элементам, кроме конечного числа. В этом случае, если образованный класс непериодичен, то все работает также, если периодичен, то если мудрец видит перед собой последовательность без предпериода, то он выбирает цвет, продолжающий период в его сторону, иначе также как и в обычной задаче. Вроде такое проходит и порядковый номер не нуженСогласен, свой номер не нужен. Круто, чё...
Остаётся, правда, нераскрытой тема оптимальности выбранной стратегии мудрецов, ну да бог с ней.
Объясните мне, я, наверное, тупой и не понимаю.
Вот есть классическая задачка про апельсины в вазе - за минуту до 12-00 в вазу кладут 10 апельсинов (с 1-го по 10-й) и 1 апельсин (первый) вынимают. Когда проходит половина времени, оставшегося до 12, в вазу кладут еще 10 апельсинов (с 11-го по 20-й а 1 (теперь номер два) апельсин вынимают. И так далее. Вопрос - сколько апельсинов будет в вазе в 12-00.
Далее произносятся слова, мол, какой бы номер апельсина мы ни взяли, в вазе его нет: его убрали на соответствующем шаге, и делается парадоксальный вывод: в 12-00 в вазе пусто.
Чем отличается ситуация с мудрецами? Если, скажем, количество возможных цветов имеет мощность континуума, то для любого мудреца, какого бы мы ни взяли, вероятность угадать цвет будет нулевой, а вероятность пойти на плаху - единичной, ведь он лишь угадывает экземпляр (которых, кстати, даже при бинарной раскладке континуум). Т.е. на плаху пойдет бесконечное число мудрецов.
Что я делаю не так?
Вот есть классическая задачка про апельсины в вазе - за минуту до 12-00 в вазу кладут 10 апельсинов (с 1-го по 10-й) и 1 апельсин (первый) вынимают. Когда проходит половина времени, оставшегося до 12, в вазу кладут еще 10 апельсинов (с 11-го по 20-й а 1 (теперь номер два) апельсин вынимают. И так далее. Вопрос - сколько апельсинов будет в вазе в 12-00.
Далее произносятся слова, мол, какой бы номер апельсина мы ни взяли, в вазе его нет: его убрали на соответствующем шаге, и делается парадоксальный вывод: в 12-00 в вазе пусто.
Чем отличается ситуация с мудрецами? Если, скажем, количество возможных цветов имеет мощность континуума, то для любого мудреца, какого бы мы ни взяли, вероятность угадать цвет будет нулевой, а вероятность пойти на плаху - единичной, ведь он лишь угадывает экземпляр (которых, кстати, даже при бинарной раскладке континуум). Т.е. на плаху пойдет бесконечное число мудрецов.
Что я делаю не так?
Я что-то не понял задачи. Ну пусть мудрецы гадают с вероятностью 1\2.
Тогда с вероятностью 1 выживет счетное число мудрецов.
Больше чем счетное, очевидно, нельзя.
О каком алгоритме идет речь?
Или вы хотите именно мощность погибших минимизировать?
Получается глупо довольно, потому что в любом случае потерь по мощности нет
Тогда с вероятностью 1 выживет счетное число мудрецов.
Больше чем счетное, очевидно, нельзя.
О каком алгоритме идет речь?
Или вы хотите именно мощность погибших минимизировать?
Получается глупо довольно, потому что в любом случае потерь по мощности нет
А если цветов континуум? То могут быть потери мощности. Более того матождиание количества выживших
0 (если они гадают с равномерной вероятностью). И да, конечное число умерших тоже удивляет
0 (если они гадают с равномерной вероятностью). И да, конечное число умерших тоже удивляет
Если цветов континуум, а мудрецов - счетное число, то я могу просто выбрать случайно равномерно счетное число цветов и раздать мудрецам.
Тогда вероятность того, что хоть один мудрец угадает свой цвет равна 0 очевидно.
Тогда вероятность того, что хоть один мудрец угадает свой цвет равна 0 очевидно.
А при данной стратегии угадают почти все (за исключением конечного числа)
Причем тут стратегия вообще?
Я объявляю - я разыграл![[math]$X_i$[/math]](mathimg.php?math=%24X_i%24)
- н.о.р. равномерные на [0,1] цвета.
Вероятность того, что кто-то что-то угадает меньше чем сумма вероятностей того, что определенный мудрец что-то угадает, то есть 0.
Я объявляю - я разыграл
Вероятность того, что кто-то что-то угадает меньше чем сумма вероятностей того, что определенный мудрец что-то угадает, то есть 0.
> Причем тут стратегия вообще?
Ну я не знаю. Ты пришёл и объявил, что если просто случайно выбирать, то будет то же самое.
Я тебе привёл пример, что нет. К чему ты хочешь найти контрпример, не очень понятно.
Ну я не знаю. Ты пришёл и объявил, что если просто случайно выбирать, то будет то же самое.
Я тебе привёл пример, что нет. К чему ты хочешь найти контрпример, не очень понятно.
Вот есть классическая задачка про апельсины в вазе - за минуту до 12-00 в вазу кладут 10 апельсинов (с 1-го по 10-й) и 1 апельсин (первый) вынимают. Когда проходит половина времени, оставшегося до 12, в вазу кладут еще 10 апельсинов (с 11-го по 20-й а 1 (теперь номер два) апельсин вынимают. И так далее. Вопрос - сколько апельсинов будет в вазе в 12-00.Омеговый-то апельсин останется, поди.
Далее произносятся слова, мол, какой бы номер апельсина мы ни взяли, в вазе его нет: его убрали на соответствующем шаге, и делается парадоксальный вывод: в 12-00 в вазе пусто.
Причем тут стратегия вообще?Задача не по теории вероятностей, а мудрецы не гадают.
Есть функция F(k, {x_i} которая по k и хвосту последовательности x_i, i>k выдает однозначно цвет.
Указана такая функция, что для любой последовательности {x_i} количество {k: F(k, {x_i}) != x_k} конечно.
Задача не по теории вероятностей, а мудрецы не гадают.
Вы точно про континууум цветов шляп и счетное число мудрецов в шляпах говорите?
Зафиксируем все увиденное одним мудрецом. Оно независимо с цветом его шляпы. Тогда его ответ есть случайная величина независящая от цвета его шляпы. Разыграем ее, а теперь будем разыгрывать цвет его шляпы. Вероятность, что он попадает в это число равна 0. Значит фиксированный мудрец угадывает цвет своей шляпы с вероятностью 0.
Отсюда и все мудрецы - с вероятностью 0.
Я говорил про конечное число цветов.
С континуальным числом цветов и счетным число мудрецов я утверждаю, что все мудрецы умрут вне зависимости от вашей стратегии.
С континуальным числом цветов и счетным число мудрецов я утверждаю, что все мудрецы умрут вне зависимости от вашей стратегии.
Я могу понять что если мудрецы смотрят назад и слышат все ответы - тогда ок.
А если вперед и спрашивают спреди назад, то да.
А если вперед и спрашивают спреди назад, то да.
Для начала определи вероятностное пространство.
Затем пойми, что вероятность того, что мудрец угадает свой цвет может не существовать.
После чего нужно понять, что ответы мудрецов не являются независимыми и переход к бесконечному их числу выполнить нельзя.
Или можно просто прочитать решение и убедится, что оно правильное.
Затем пойми, что вероятность того, что мудрец угадает свой цвет может не существовать.
После чего нужно понять, что ответы мудрецов не являются независимыми и переход к бесконечному их числу выполнить нельзя.
Или можно просто прочитать решение и убедится, что оно правильное.
Для начала определи вероятностное пространство.
Чего тут определять.
У нас есть последовательность случайных величины, равномерно распределенные на [0,1]. Это потому что я из как угодно заданных цветов захотел увидеть такую подборку цветов.
Ответ n-ого мудреца есть функция от начальных n-1 элемента последовательности. Если угодно - случайная функция, где эта случайная функция суть случайная среда, независящая от величин. Иначе говоря, есть какое-то вероятностное пространство, на котором мудрецы выбирают себе случайную функцию для ответа на свой вопрос. Функцию, зависящую от ответов предыдущих, то есть от i-1 переменной. Есть другое вероятностной пространство, на котором я выбираю цвета. Они независимы, поэтому я рассматриваю их декартово произведение с произведением мер и произведением сигма-алгебр. Все же стандартно до ужаса.
Мы рассматриваем следующую вероятность:
В чем вопрос здесь? В том, что под знаком вероятности событие? Эм, ну это вопрос равенства двух случайных величин, разумеется событие.
После чего нужно понять, что ответы мудрецов не являются независимыми и переход к бесконечному их числу выполнить нельзя.
Андрей, ты ли это? У нас объединение счетного числа событий, вероятность объединения не больше суммы вероятностей, какая нафиг независимость?
Или можно просто прочитать решение и убедится, что оно правильное.
А где решение для континуума цветов? Можно ссылку? Я не понял, когда всплыл континуум цветов...
upd: Нашел сообщение Fj. Читаю.
Тонкое место в измеримости функции, используемой мудрецами...
Ответ ![[math]$n$[/math]](mathimg.php?math=%24n%24)
мудреца - функция от всех с ![[math]$i>n$[/math]](mathimg.php?math=%24i%26gt%3Bn%24)
.
Ответ мудреца может не быть случайной величиной. После чего нельзя так просто говорить о вероятности.
Решение для континуума цветов в точности такое же, как и для двух цветов.
Ответ мудреца может не быть случайной величиной. После чего нельзя так просто говорить о вероятности.
Решение для континуума цветов в точности такое же, как и для двух цветов.
> С континуальным числом цветов и счетным число мудрецов я утверждаю, что все мудрецы умрут вне зависимости от вашей стратегии.
Можешь повторить это после прочтения решения?
А на самом деле тонкое место там - аксиома выбора.
Эта задача показывает, что она не так уж и интуитивно понятна, поскольку при ее наличии возникают странные вещи, которые, кажется,
противоречат здравому смыслу.
Можешь повторить это после прочтения решения?
А на самом деле тонкое место там - аксиома выбора.
Эта задача показывает, что она не так уж и интуитивно понятна, поскольку при ее наличии возникают странные вещи, которые, кажется,
противоречат здравому смыслу.
Да, я почитал и вроде понял концепт.
Да, тонкое место в том, что я слишком узко представляю себе возможности мудрецов
Они используют неизмеримую функцию от своих данных
Я просто не понял к чему ты независимость вдруг приплел
Да, тонкое место в том, что я слишком узко представляю себе возможности мудрецов
Они используют неизмеримую функцию от своих данных
Я просто не понял к чему ты независимость вдруг приплел
Ну для меня тонкое место там - неизмеримая функция, которую используют мудрецы А она да, проистекает из аксиомы выбора.
А она да, проистекает из аксиомы выбора.все равно, интересный взгляд. Мне вот никогда не нравилось, когда в якобы детерминированную задачу (или задачу на "наихудший случай" как здесь) приводят вероятностные рассуждения, а здесь пример как их корректно привести. И заодно хороший пример облома с неизмеримой функцией, тоже стоит запомнить
Наконец-то докзал задачу про 3х мудрецов. Потом решение прочитал. Немного по-другому доказал, без функционала, но тоже с аксиомой выбора. Хорошая задачка. Есть еще подобные?
Наконец-то докзал задачу про 3х мудрецов. Потом решение прочитал. Немного по-другому доказал, без функционала, но тоже с аксиомой выбора. Хорошая задачка. Есть еще подобные?Не, других таких задач не знаю. Правда специально не искал, хотя интересно. Наткнёшься - пиши.
А как доказал? Напиши сюда или в приват, если не трудно.
Вводим частичный порядок на последовательности из 0 и 1.
A >= B, если существуют такие i и j, что A[i:] мажорирует B[j:] (A[i:] - подпоследовательность A, начиная с i-го элемента).
Рассмотрим так же отношение эквивалентности, порождённое этим порядком, то есть A = B, если существуют такие i и j, что A[i:] = B[j:].
Выберем по представителю, далее будем рассматривать их.
Через ~A обозначем инвертирование A.
Рассмотрим подмножество V последовательностей, для которых A != ~A.
На V можно ввести такую двузначную функцию f : V -> {0, 1}, что для всякого A f(A)!= f(~A) и если A >= B, то f(A) >= f(B).
Это эквивалентно разбиению V на 2 множества V_0 и V_1 cо свойствами:
Для всякого A, A и ~A лежат в разных множествах, ну, и неравенство (если A >= B и A лежит в V_0, то B тоже лежит в V_0).
Будем строить эти множества трансфинитной индукцией, добавляя пары A и ~A, с сохранением этих 2х свойств.
Допустим, есть уже множества S_0 и S_1 (множества удовлетворяют свойствам). Добавляем туда A и ~A.
Рассмотрим множество, куда можно добавить A c сохранением 2го свойства. Если в S_i нет элементов, сравнимых с A, то нет и сравнимых с ~A,
и их можно добавить любым образом (только по одному в каждое).
A нельзя добавить в S_0, если существует такое B из S_1, что A > B.
A нельзя добавить в S_1, если существует такое С из S_0, что A < C.
Одновременно эти 2 условия не могут быть выполнены, так как иначе элементы C и B, уже лежащие в S_0 и S_1, нарушают второе свойство.
Таким образом, A можно добавить либо в S_0, либо в S_1. Тогда несложно показать, что ~A можно добавить в другое множество (используя, что ~S_0 = S_1 и инверт пары меняет неравенство). Индукция доказана.
Отдельно надо рассмотреть случай, когда A и ~A сравнимы. Он тоже простой.
В итоге мы получаем искомую функцию f.
Считаем, что на элементах A, для которых A = ~A, f(A) = A'[0], где A' = A и A' периодична.
Мудрец выбирает своего представителя A и говорит "f(A)" (ну, "f(A) + 1", так как у нас 1-й тип и 2-й, а не 0-й и 1-й).
Почему это работает.
Допустим, один из мудрецов ошибся (A - представитель 1-го мудреца, B - 2-го, C - 3-го).
Рассмотрим 2 случая.
1. A != ~A
Допустим, f(A) = 0, а тюрьма была второго типа.
Тогда везде, кроме конечного числа элементов, где у него 0, у остальных 1. Это значит, что
B >= ~A и С >= ~A.
Но тогда f(B) >= f(~A) = 1 и f(C) >= f(~A) = 1.
То есть в этом случае 2й и 3й мудрецы угадают.
Аналогично, если f(A) = 1, а тюрьма оказалась 1го типа, то
B <= ~A, С <= ~A.
Тогда f(B) <= f(~A) = 0 и f(C) <= f(~A) = 0,
и другие 2 мудреца угадывают.
2. A = ~A
Тогда f(A) = f(~A) = 1 и тюрьма 1го типа.
B <= ~A = A <= ~B, C <= ~A = A <= ~C.
При этом очевидно, что B = ~B тогда и только тогда, когда B = ~A и С = 0.
В этом случае f(A) != f(B) (то есть f(B) = 0 а f(C) = 0, то есть опять 2е угадали.
Если же B != ~B и С != ~C, то снова f(B) = f(C) = 0.
A >= B, если существуют такие i и j, что A[i:] мажорирует B[j:] (A[i:] - подпоследовательность A, начиная с i-го элемента).
Рассмотрим так же отношение эквивалентности, порождённое этим порядком, то есть A = B, если существуют такие i и j, что A[i:] = B[j:].
Выберем по представителю, далее будем рассматривать их.
Через ~A обозначем инвертирование A.
Рассмотрим подмножество V последовательностей, для которых A != ~A.
На V можно ввести такую двузначную функцию f : V -> {0, 1}, что для всякого A f(A)!= f(~A) и если A >= B, то f(A) >= f(B).
Это эквивалентно разбиению V на 2 множества V_0 и V_1 cо свойствами:
Для всякого A, A и ~A лежат в разных множествах, ну, и неравенство (если A >= B и A лежит в V_0, то B тоже лежит в V_0).
Будем строить эти множества трансфинитной индукцией, добавляя пары A и ~A, с сохранением этих 2х свойств.
Допустим, есть уже множества S_0 и S_1 (множества удовлетворяют свойствам). Добавляем туда A и ~A.
Рассмотрим множество, куда можно добавить A c сохранением 2го свойства. Если в S_i нет элементов, сравнимых с A, то нет и сравнимых с ~A,
и их можно добавить любым образом (только по одному в каждое).
A нельзя добавить в S_0, если существует такое B из S_1, что A > B.
A нельзя добавить в S_1, если существует такое С из S_0, что A < C.
Одновременно эти 2 условия не могут быть выполнены, так как иначе элементы C и B, уже лежащие в S_0 и S_1, нарушают второе свойство.
Таким образом, A можно добавить либо в S_0, либо в S_1. Тогда несложно показать, что ~A можно добавить в другое множество (используя, что ~S_0 = S_1 и инверт пары меняет неравенство). Индукция доказана.
Отдельно надо рассмотреть случай, когда A и ~A сравнимы. Он тоже простой.
В итоге мы получаем искомую функцию f.
Считаем, что на элементах A, для которых A = ~A, f(A) = A'[0], где A' = A и A' периодична.
Мудрец выбирает своего представителя A и говорит "f(A)" (ну, "f(A) + 1", так как у нас 1-й тип и 2-й, а не 0-й и 1-й).
Почему это работает.
Допустим, один из мудрецов ошибся (A - представитель 1-го мудреца, B - 2-го, C - 3-го).
Рассмотрим 2 случая.
1. A != ~A
Допустим, f(A) = 0, а тюрьма была второго типа.
Тогда везде, кроме конечного числа элементов, где у него 0, у остальных 1. Это значит, что
B >= ~A и С >= ~A.
Но тогда f(B) >= f(~A) = 1 и f(C) >= f(~A) = 1.
То есть в этом случае 2й и 3й мудрецы угадают.
Аналогично, если f(A) = 1, а тюрьма оказалась 1го типа, то
B <= ~A, С <= ~A.
Тогда f(B) <= f(~A) = 0 и f(C) <= f(~A) = 0,
и другие 2 мудреца угадывают.
2. A = ~A
Тогда f(A) = f(~A) = 1 и тюрьма 1го типа.
B <= ~A = A <= ~B, C <= ~A = A <= ~C.
При этом очевидно, что B = ~B тогда и только тогда, когда B = ~A и С = 0.
В этом случае f(A) != f(B) (то есть f(B) = 0 а f(C) = 0, то есть опять 2е угадали.
Если же B != ~B и С != ~C, то снова f(B) = f(C) = 0.
100 узников выстроены в шеренгу в затылок друг другу. На каждом надета шапка одного из двух возможных цветов. Узники видят только шапки стоящих перед ними узников. Свою не видят. Шапки узников, стоящих сзади, тоже не видят.я так понимаю, что в любом случае у самого первого шанс выжить 50х50, а остальные выживают точно.
Стражники устраивают такую игру. Начиная с хвоста колонны они задают каждому узнику по очереди вопрос о цвете его шапки. Если тот не угадывает - секир-башка. При этом узники слышат ответы друг друга.
До начала экзекуции узники могут договориться, как они будут отвечать.
Вопрос: как должны отвечать бедолаги, чтобы выжило максимальное количество из них?
самый первый просто складывает номера цветов шапок (0 или 1, или сколько там всего цветов) по модулю два и называет получившийся цвет. соответственно, все остальные, зная ответ последнего (и всех остальных предыдущих) и цвета стоящих перед ними, могут с уверенностью назвать цвет шапки на себе.
расширенную задачку как решить пока не знаю - тут моих пяти лет мехмата не хватает. во всяком случае, слабо верится, что процент выживших будет больше 50.
Ну процент выживших здесь считать не получится, т.к. всего мудрецов счетное число.
Но, начиная с некоторого номера, выживут все, т.е. в пределе - 100%.
Вообще решения озвучивались в треде уже.
Но, начиная с некоторого номера, выживут все, т.е. в пределе - 100%.
Вообще решения озвучивались в треде уже.
Vano
Сиквел нашумевшего в своё время поста :-)Наткнувшись на просторах интернета, никак не мог не запостить. Уж больно перекликается с первой частью про мудрецов в счётной тюрьме.
Формулировку я слегка изменил, но найти ответ в сети всё равно легко. Со всеми вытекающими.
Для разминки классическая лайт-версия задачки.
100 узников выстроены в шеренгу в затылок друг другу. На каждом надета шапка одного из двух возможных цветов. Узники видят только шапки стоящих перед ними узников. Свою не видят. Шапки узников, стоящих сзади, тоже не видят.
Стражники устраивают такую игру. Начиная с хвоста колонны они задают каждому узнику по очереди вопрос о цвете его шапки. Если тот не угадывает - секир-башка. При этом узники слышат ответы друг друга.
До начала экзекуции узники могут договориться, как они будут отвечать.
Вопрос: как должны отвечать бедолаги, чтобы выжило максимальное количество из них?
Размявшись, переходим к обобщённой версии задачи.
Тут нам в качестве узников уже потребуются "мудрецы" из первой части, причём в счётном количестве... :-)
DISCLAIMER. Отсюда начинается "для математиков". Кто не спрятался, я не виноват.
Итак, счётное количество мудрецов выстроены в шеренгу в затылок друг другу. На каждом шапка. Для простоты пусть шапки будут двух возможных цветов (желающие могут попробовать решить задачу для произвольного заданного заранее - непустого, ясен пень, - множества цветов). Свою шапку мудрецы не видят. Шапки стоящих позади - тоже не видят. Зато видят шапки всех стоящих впереди коллег по несчастью.
Стражники начинают играть в знакомую игру. Они задают каждому мудрецу вопрос о цвете его шапки. Не угадал - голова с плеч. А чтобы мудрецам совсем жизнь мёдом не казалась, еще и не дают слушать ответы других. Т.е. каждый мудрец отвечает независимо от остальных.
До начала стражницкой забавы мудрецы могут обменяться любой информацией.
Вопрос: как мудрецам следует действовать, чтобы минимизировать потери в личном составе?
Задача математическая, никаких подвохов нет.
p.s. Сиквел, как ему и положено, получился имхо попроще, чем первая часть. Страждущие могут попробовать решить аналогичную задачу ну хотя бы для континуума мудрецов, каждый из которых видит всех остальных, но не себя.