Задачки

[Волод]

Рассмотрим мой оптимальный для мудрецов вариант.
Мудрецы хорошо подготовились распределили между собой шкатулки, так что бы в каждую заглянуло не меньше 50 мудрецов.
Все сходили на экскурсию в комнату со шкатулками и теперь каждый мудрец должен назвать фараону номер (или иные приметы шкатулки в которой лежит карточка с его именем).
Понятно, что около 50 мудрецов видели карточку со своим именем и знают в какой шкатулке она лежит.
Таким образом останется 50 шкатулок и 50 мудрецов.
В среднем по 25 "не осмотренных" лично шкатулок на мудреца.
Но это в среднем, у кого-то может оказаться что все 50 из 50 "не осмотрены", а у кого-то только одна.
Если найдётся такой мудрец или несколько, у которых из оставшихся 50 "не осмотрена" только одна, они сразу (мудрецы же соображают и считают мгновенно) идут к фараону и называют ему номер.
Остаются 49 мудрецов и 49 шкатулок или меньше, опять если находится мудрец ,у которого из оставшихся 49 "не осмотрена" лишь одна, он идут к фараону и т.д.
В итоге 100% спасение  всех.

Однако предположим на каком-то этапе такого везучего мудреца не находится.
Есть такой у которого из оставшихся шкатулок "не осмотрены" 2 шт.
Приходится ему идти к фараоны и играть в гусарскую рулетку сделав ставку на жизнь всех 100 мудрецов.
Предположим что он угадает, на это есть 50% шансов
................................................................
Какие-то шансы уцелеть у мудрецов есть.

[yurifromspb]

Ещё одна суперкрутая задача:

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

[yurifromspb]

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

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

[Волод]

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

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

Покажите документ с подписью и печатью фараона, настолько однозначно регламентирующий эту процедуру. 

Если дело будет обстоять так как Вы изложили, то ни о каких 30% шансов на спасение не может идти речи, цифра будет ближе к той, что называл Bhudh  0.5¹⁰⁰ хотя в этом отношении он был тоже не совсем точен, чуть-чуть более оптимистическая, но всё равно на уровне - шансов никаких   

[yurifromspb]

Покажите документ с подписью и печатью фараона, настолько однозначно регламентирующий эту процедуру. 

Если дело будет обстоять так как Вы изложили, то ни о каких 30% шансов на спасение не может идти речи, цифра будет ближе к той, что называл Bhudh  0.5¹⁰⁰ хотя в этом отношении он был тоже не совсем точен, чуть-чуть более оптимистическая, но всё равно на уровне - шансов никаких   

Так в условии:

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

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

Посмотрите по ссылке http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1165970704
Там участники поняли условие именно так и нашли, что решение с неоколонулевой вероятностью есть (это ошеломляет, но это так).

[Karakurt]

Кто-нибудь решал задачу Эйнштейна?

[Волод]

Покажите документ с подписью и печатью фараона, настолько однозначно регламентирующий эту процедуру. 

Если дело будет обстоять так как Вы изложили, то ни о каких 30% шансов на спасение не может идти речи, цифра будет ближе к той, что называл Bhudh  0.5¹⁰⁰ хотя в этом отношении он был тоже не совсем точен, чуть-чуть более оптимистическая, но всё равно на уровне - шансов никаких   

Так в условии:

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

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

Посмотрите по ссылке http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?num=1165970704
Там участники поняли условие именно так и нашли, что решение с неоколонулевой вероятностью есть (это ошеломляет, но это так).

В самом первом посте там ерунда написана, под которой может подписаться Bhudh

Например, если мудрецы будут открывать шкатулки наугад, то они выживут с вероятностью 2¹⁰⁰. Если каждый будет открывать первые 50 шкатулок, то их шансы снижаются до 0.

Но от того, что это там написано, оно ерундой не перестаёт быть.

[Волод]

Популярное изложение моей точки зрения:
Есть три напёрстка, под одним лежит шарик.
Сколько надо поднять напёрстков, что бы со 100% вероятностью определить тот, под которым лежит шарик?

[Солохин]

Сколько надо поднять напёрстков, что бы со 100% вероятностью определить тот, под которым лежит шарик?

Два. А если повезет (вероятность 1/3), то даже один.

И что?

[Волод]

А с какой вероятностью мудрец определил бы, в какой шкатулке лежит его карточка, если бы мог открыть 99 шкатулок из 100?

[Солохин]

Если дело будет обстоять так как Вы изложили, то ни о каких 30% шансов на спасение не может идти речи, цифра будет ближе к той, что называл Bhudh  0.5¹⁰⁰

Нет, существует стратегия, при которой они спасаются с неплохой вероятностью.

Чтобы её понять, представьте, что мудреца всего два. И каждому разрешается открыть лишь одну шкатулку.
Они могут заранее договориться о своих действиях, но после начала испытания ничего сообщить друг другу уже не могут.
В этом случае существует стратегия, при которой они выживают с вероятностью 1/2.

Хотя если они будут открывать наугад, без стратегии, то вероятность гибели 3/4.

[Солохин]

А с какой вероятностью мудрец определил бы, в какой шкатулке лежит его карточка, если бы мог открыть 99 шкатулок из 100?

Со 100% вероятностью. И что?

[Волод]

Если дело будет обстоять так как Вы изложили, то ни о каких 30% шансов на спасение не может идти речи, цифра будет ближе к той, что называл Bhudh  0.5¹⁰⁰

Нет, существует стратегия, при которой они спасаются в неплохой веротяностью.

Чтобы её понять, представьте, что мудреца всего два. И каждому разрешается открыть лишь одну шкатулку.
Они могут заранее договориться о своих действиях, но после начала испытания ничего сообщить друг другу уже не могут.
В этом случае существует стратегия, при которой они выживают с вероятностью 1/2.

Хотя если они будут открывать наугад, без стратегии, то вероятность гибели 3/4.

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

[Волод]

А с какой вероятностью мудрец определил бы, в какой шкатулке лежит его карточка, если бы мог открыть 99 шкатулок из 100?

Со 100% вероятностью. И что?

Почему при открытии 99 шкатулок из 100 вероятность 100%, а при открытии 50 шкатулок из 100 только 50%.
Или и при 99 открытых шкатулках вероятность 99 или при 50 открытых шкатулках вероятность выживания 51%.

Надо действительно как-то определиться с условиями задачи.

[Солохин]

Если всего две шкатулки , то вторую можно не открывать

Вы удивительным образом до сих пор не поняли условие задачи.
Чтобы спастись, каждый должен открыть шкатулку со своим именем.
"Не открывать" значит умереть.

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

[лад]

жив ли он ещё.

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

[Солохин]

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

Существует стратегия, придерживаясь которой все спасаются с вероятностью 5/12.
Ничего не зная о судьбе друг друга вплоть до вынесения окончательного приговора по его результатам!

жив ли он ещё.

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

Поскольку фараон - интеллектуальный садист, он будет изолировать их друг от друга и томить ожиданием, пока каждый покажет, на что он способен.
А потом казнит всех, если хоть один потерпел неудачу.

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

[лад]

жив ли он ещё.

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

Поскольку фараон - интеллектуальный садист, он будет изолировать их друг от друга и томить ожиданием, пока каждый покажет, на что он способен.
А потом казнит всех, если хоть один потерпел неудачу.

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

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

[Солохин]

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

Я восхищён! 

Вы нашли НОВОЕ решение этой задачи, не совпадающее с уже найденным!
Притом Ваше решение - гораздо проще и изящнее, чем известное.

[Солохин]

предполагаем что казнит сразу после первой ошибки, только из таких предположений можно решать задачу.

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

Но когда Вы найдёте решение, Вы увидите, что объективно это неважно.
Даже если мы уже обречены на смерть, можно все-таки действовать так, будто у нас ещё остаются шансы. И это оказывается единственным шансом все-таки избежать сети интеллектуального садиста на троне.
Верить в успех - и продолжать действовать!

На примере этой задачи можно видеть, как вера в победу увеличивает шансы на победу. Объективно увеличивает, заметьте! Строго математически.

[лад]

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

Я восхищён! 

Вы нашли НОВОЕ решение этой задачи, не совпадающее с уже найденным!
Притом Ваше решение - гораздо проще и изящнее, чем известное.

Да ошибка сразу. Можно перевернуть только одну монету, а магическая клетка любая, поэтому "Если на доске одни аверсы - значит заветная клетка "64"" ни о чем не говорит, кто сказал что магическая клетка 64? Одним реверсом нельзя сделать одни аверсы.

[Волод]

Немного о продолжении задачи о четырёх мудрецах.
Оптимальным для второго мудреца будет осмотр двух шкатулок которые не осмотрел первый мудрец ( эта стратегия конечно должна быть выработана ещё до визита в комнату первого мудреца), поскольку среди них точно не попадётся шкатулка с именем первого мудреца.
Итого получается что он осматривает две шкатулки из трёх в которых нет имени первого мудреца. Получаем 2/3.
Умножив на достижение первого мудреца получаем 2/3 *1/2=1/3 вероятность выживаемости мудрецов после визита в комнату первого и второго мудреца.


Конечно второй мудрец может осмотреть те же  шкатулки, что и первый, но тогда шансы найти свою карточку у него будут 1/3, что сразу приведёт общий счёт к 1/6.
Может быть промежуточный вариант он осмотрит одну из шкатулок первого мудреца и одну новую, тогда получаем 1/2, общий счёт 1/4

Поскольку оба последних варианта уже на втором мудреце проваливаются ниже 5/12 и даже ниже 30%, приходится возвращаться к первому варианту поведения второго мудреца.
Третьему мудрец может повторно осмотреть шкатулки, которые осмотрел первый тогда 1/2 и общий счёт 1/6
Может осмотреть повторно шкатулки, которые осмотрел второй  получиться тоже 1/2 и общий счёт 1/6
Может взять одну шкатулку от первого одну от второго с тем же результатом
То есть мы уже на третьем мудреце провалились до 1/6, а Вы говорите 5/12 

[Солохин]

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

Верно! Это первый шаг.
Если разрешается открыть только одну шкатулку, то так и надо сделать: распределить все шкатулки так, чтобы ни одна не осталась неоткрытой. При этом шанс на успех максимален (хотя все равно невелик при большом числе испытуемых).

А вот что делать дальше? если можно открывать вторую, третью и так далее. Какая стратегия оптимальна?

[лад]

На примере этой задачи можно видеть, как вера в победу увеличивает шансы на победу. Объективно увеличивает, заметьте! Строго математически.

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

[лад]

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

Верно! Это первый шаг.
Если разрешается открыть только одну шкатулку, то так и надо сделать: распределить все шкатулки так, чтобы ни одна не осталась неоткрытой. При этом шанс на успех максимален (хотя все равно невелик при большом числе испытуемых).

А вот что делать дальше? если можно открывать вторую, третью и так далее. Какая стратегия оптимальна?

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