Здесь больше нет рекламы. Но могла бы быть, могла.


Ответ

Имя:
E-mail:
Тема:
Иконка сообщения:

подсказка: нажмите alt+s для отправки или alt+p для предварительного просмотра сообщения


Сообщения в этой теме

Автор: Mrrl›
« : 03/04/2008, 23:29:16 »

Варианты стратегий однорукого Али-Бабы против случайно вращающегося стола:

- выбрать направление селедок и стремиться к нему;
- проверить первую селедку, не переворачивать, объявить ее направление целевым и стремиться к нему;
- первую селедку не переворачивать, вторую перевернуть, если она не совпадает с первой, но если и третья не сопадает с первой (а совпадает с исходным положением второй) - объявить ее направление целевым и не переворачивать;
- проверить первые 3 селедки (1-ю и 2-ю не переворачивать), объявить целевым направление тех, кого больше. 3-ю перевернуть только если 1-я и 2-я направлены одинаково, а 3-я - по-другому.

Для N=5 первая стратегия все еще лучше второй. Интересно, какая лучше при больших N.
Автор: Мёнин›
« : 03/04/2008, 21:43:57 »

Цитировать
Неочевидно - существует ли неоптимизируемая стратегия с гарантированным выигрышем, в которой вообще может возникнуть ситуация, когда надо "не переворачивать".
Ну, я нашёл способ (в нач. задаче) на 5 ходов, при котором такая ситуация есть. Причём делать что-то явно хуже, чем не делать: у нас цель - уменьшать количество возможных вариантов, а не обязательно крутить что-то.
Ищу способ на 4 хода... но пока не получается.
Автор: Mrrl›
« : 03/04/2008, 21:11:19 »

Есть решение за 5 ходов. А если бы Али-Баба знал хотя бы четность исходного числа селедок, повернутых головой вверх - уложился бы в 4.

В условии задачи есть слова "при желании". Значит, изначально предполагается, что может и не переворачивать :)
Неочевидно - существует ли неоптимизируемая стратегия с гарантированным выигрышем, в которой вообще может возникнуть ситуация, когда надо "не переворачивать". Казалось бы, если Али-Баба планирует ход, в котором возможно "пустое" действие, столу всегда выгодно повернуться так, чтобы именно такое действие и произошло - тогда Али-Баба зря потратит ход, а состояние стола не изменится. С другой стороны, Али-Баба за этот ход получит некоторую информацию, но вот достаточно ли этого?

Про 2*X+1 - да, очевидно. Выбираем сторону, селедки на которой ориентированы по-разному, и...
Автор: Мёнин›
« : 03/04/2008, 20:02:50 »

Цитата: Mrrl от 03/04/2008, 14:19:18
может перевернуть от 0 до Х
Вот это и было неочевидно - мог ли он НЕ переворачивать...

Цитировать
Собственно, подвох где-то рядом: для начала, как сформулировать стратегию для треугольного стола при игре против однорукого Али-Бабы (ответ: поинтересоваться, какой угол собирается проверить Али-Баба в следующий раз, и подставить ему неправильную селедку).
Да, в этом случае Али-Баба может полагаться только "на везение". Причём всегда остаётся возможность, что он "не попадёт". Кстати, а есть ли у треугольного стола такой же способ всегда выигрывать, если Али-Баба о двух руках? Впрочем, дошло - нет, тут Али-Бабе нужно максимум два хода на всё независимо от начального расположения.

Попарившись, нашёл для нач. задачи решение о пяти шести ходах. Меньше есть?
Вообще, подлый стол об 2Х+1 сторонах всегда найдёт чего подсунуть Х-рукому Али-Бабе. Это очевидно?
Автор: Mrrl›
« : 03/04/2008, 18:07:32 »

Похоже, что стол в форме 4-мерного гиперкуба выигрывает у 11-рукого Али-Бабы  ;D
Автор: Mrrl›
« : 03/04/2008, 14:19:18 »

Для Х рук - может проверить X селедок и перевернуть (в зависимости от результата проверки) от 0 до Х - но только из числа проверенных.
Задачка не на вероятности - для Али-Бабы принимается только полностью надежное решение. Однорукий Али-Баба, таким образом, может справиться только с 2-угольным столом.

Собственно, подвох где-то рядом: для начала, как сформулировать стратегию для треугольного стола при игре против однорукого Али-Бабы (ответ: поинтересоваться, какой угол собирается проверить Али-Баба в следующий раз, и подставить ему неправильную селедку).

В среднем для одной руки и N вершин - подсчитать несложно:

Sum({u,k},1<=u<=k<=N-1,Comb(N,k)/u)*N/(2^N-2).

Можно ли ее упростить и какова асимптотика, пока непонятно.
Но это если мы заранее выбрали желаемое направление. А вот если первую селедку не переворачивать, а остальные ориентировать в соответствии с ней, то число ходов может быть и меньше (начиная с какого-то N).


Автор: Мёнин›
« : 03/04/2008, 13:33:00 »

самое простое решение для начальной задачи, которое я вижу, занимает в 4/14 случаев 1 ход, а в остальных - 1+Y ходов, где Y в среднем 2 (точнее, равен количеству бросков монеты, необходимых, чтобы угадать результат).

Два вопроса, не очевидных из условия:
для Х рук он имеет право переворачивать от 1 до Х селёдок?
В такой задаче есть полностью надёжное решение, не зависящее от вероятности?
Для 1 руки нет определённо.
Интересно, сколько для одной руки требуется в среднем ходов?
Автор: Mrrl›
« : 03/04/2008, 12:42:40 »

Задачка, в общем, известная.

  У дверей пещеры разбойников стоит квадратный стол, в каждом углу - по дырке, под дыркой - кувшин, в кувшине - селедка. Селедка может быть повернута головой или хвостом вверх. Али-Баба может просунуть руки в два кувшина, ощупать селедки (установить, как они повернуты), и при желании перевернуть одну или обе. После этого стол начинает крутиться и останаливается в каком-то другом положении (установить, какие кувшины проверярилсь в прошлый раз, нельзя). Если все четыре селедки окажутся повернуты одинаково, то дверь откроется.
  Может ли Али-Баба открыть дверь? Сколько действий ему потребуется?

У задачи есть продолжение. Рассматриваются столы различных форм, и во всех случаях задается вопрос - какое минимальное количество рук надо иметь Али-Бабе, чтобы открыть дверь?

- в случае p-угольного стола (p - простое)
- в случае 2*p-угольного стола (p - простое)
- в случае p*q-угольного стола (p,q - простые)
- в случае pn-угольного стола (p - простое)
- в произвольном случае

- в ситуации, когда стол может переворачиваться (вместе с селедками)

- для кубического стола (8 селедок в углах)

ну и так далее?

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

И чур, не подглядывать.