100 узников

[venco]

Руст в сообщении #429794 писал(а):

Конечно вместо упорядочивания можно использовать и другие действия типа поворотов ящиков на месте на соответствующий угол. Правда для квадратных ящиков углы поворотов по 0.9 градусов почти не отличимы. Однако, 30 процентный результат можно получить даже с гораздо меньшей информацией. Например, если в открытом ящике номер выше 50 (узники пронумеруем от 1 до 100) поворачиваем ящик на бок направо, иначе налево. Уже такая не полная информация обеспечивает вероятность порядка $\prod_k (1-\frac{1}{2^k})>0.3$.

Это чисто математическая задача, без подвохов. Если в условии сказано, что информацию передавать нельзя, значит никак нельзя.

[TOTAL]

VAL в сообщении #429845 писал(а):

Хотя равные интервалы не не гарантированы. Гарантировано отсутствие возможности передачи информации.

За счет длины интервалов узники могут передавать информацию.

[--mS--]

(Оффтоп)

TOTAL в сообщении #429870 писал(а):

VAL в сообщении #429845 писал(а):

Хотя равные интервалы не не гарантированы. Гарантировано отсутствие возможности передачи информации.

За счет длины интервалов узники могут передавать информацию.

Да нет никаких длин интервалов. Ну, например, в день по человеку заводят. В 9-00. Сто дней, и вуаля.

[Null]

А как первым 2ум узникам открыть свои имена с вероятностью >30%?
Или я условие не понял?

[TOTAL]

Null в сообщении #429875 писал(а):

А как первым 2ум узникам открыть свои имена с вероятностью >30%?
Или я условие не понял?

Да никак, враньё всё это, всех повесят.

[venco]

Вероятность найти своё имя для каждого узника - 50%. Но можно сделать ненулевой корреляцию.

[TOTAL]

venco в сообщении #429915 писал(а):

Вероятность найти своё имя для каждого узника - 50%. Но можно сделать ненулевой корреляцию.

Пусть узников всего два. Как им выжить с вероятностью больше 0.3?

[venco]

Для начала рассмотрите случай с двумя узниками и двумя ящиками, каждый открывает ровно один ящик. Догадаетесь, как им выжить с вероятностью 50%?

[TOTAL]

venco в сообщении #429928 писал(а):

Для начала рассмотрите случай с двумя узниками и двумя ящиками, каждый открывает ровно один ящик. Догадаетесь, как им выжить с вероятностью 50%?

Нет, сто узников и сто ящиков. После первых двух порывшихся в ящиках узников - как выжить с вероятностью больше 0.3?

[venco]

TOTAL в сообщении #429929 писал(а):

venco в сообщении #429928 писал(а):

Для начала рассмотрите случай с двумя узниками и двумя ящиками, каждый открывает ровно один ящик. Догадаетесь, как им выжить с вероятностью 50%?

Нет, сто узников и сто ящиков. После первых двух порывшихся в ящиках узников - как выжить с вероятностью больше 0.3?

Я не хочу сразу говорить решение. Поэтому для начала предлагаю рассмотреть случай с двумя узниками и двумя ящиками, каждый открывает ровно один ящик. Как и в исходной задаче вероятность найти своё имя у каждого узника 50%. Казалось бы, если нет возможности передавать информацию, то общая вероятность должна быть 25%. Тем не менее, есть достаточно простая стратегия, при которой они выживают с вероятностью 50%.

[Equinoxe]

venco, думаю, это как-то связано с тактикой первого: например, если он вдруг встречает имя второго, начинает идти с другого конца, для него 0.5 останется 0.5, но для второго что-то уже поменяется…

[TOTAL]

venco в сообщении #429933 писал(а):

Казалось бы, если нет возможности передавать информацию, то общая вероятность должна быть 25%. Тем не менее, есть достаточно простая стратегия, при которой они выживают с вероятностью 50%.

Да ничего не казалось бы, очевидно, они должны вскрыть разные ящики. Вернёмся всё-таки к 100 ящикам.

[arseniiv]

venco в сообщении #429928 писал(а):

Для начала рассмотрите случай с двумя узниками и двумя ящиками, каждый открывает ровно один ящик. Догадаетесь, как им выжить с вероятностью 50%?

Имеем 4 возможности (а-г): оба выбирают первый ящик, в соответствии с номером, наоборот и оба выбирают второй. Имена узников могут распределиться только двумя способами: 12 и 21.
В случаях 12б и 21в узникам не повезёт, а в остальных повезёт. Получается вероятность $0{,}75$. Что делаю не так?

[Null]

2 ящика - 2 ученых понятно.
Но когда ученых и ящиков по 100 первые два ученых могут найти свои имена с вероятностью около 25% ну остальные ученые вероятность не увеличат. Как больше 30% можно получить?

[venco]

TOTAL в сообщении #429935 писал(а):

venco в сообщении #429933 писал(а):

Казалось бы, если нет возможности передавать информацию, то общая вероятность должна быть 25%. Тем не менее, есть достаточно простая стратегия, при которой они выживают с вероятностью 50%.

Да ничего не казалось бы, очевидно, они должны вскрыть разные ящики. Вернёмся всё-таки к 100 ящикам.

Ок, для двух узников Вам удалось получить вероятность лучше, чем $2^{-n}$. Осталось обобщить это решение на произвольное $n$.

-- Пт апр 01, 2011 08:13:05 --

Null в сообщении #429938 писал(а):

2 ящика - 2 ученых понятно.
Но когда ученых и ящиков по 100 первые два ученых могут найти свои имена с вероятностью около 25% ну остальные ученые вероятность не увеличат. Как больше 30% можно получить?

25% у первых двух только, пока Вы не нашли правильную стратегию. Щас подумаю, как бы ещё намекнуть...