Тема: Али-Баба и спиритический сеанс.

[Mrrl›]

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

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

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

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

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

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

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

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

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

[Мёнин›]

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

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

[Mrrl›]

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

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

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

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

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

[Mrrl›]

Похоже, что стол в форме 4-мерного гиперкуба выигрывает у 11-рукого Али-Бабы 

[Мёнин›]

может перевернуть от 0 до Х

Вот это и было неочевидно - мог ли он НЕ переворачивать...

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

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

Попарившись, нашёл для нач. задачи решение о пяти шести ходах. Меньше есть?
Вообще, подлый стол об 2Х+1 сторонах всегда найдёт чего подсунуть Х-рукому Али-Бабе. Это очевидно?

[Mrrl›]

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

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

Про 2*X+1 - да, очевидно. Выбираем сторону, селедки на которой ориентированы по-разному, и...

[Мёнин›]

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

Ну, я нашёл способ (в нач. задаче) на 5 ходов, при котором такая ситуация есть. Причём делать что-то явно хуже, чем не делать: у нас цель - уменьшать количество возможных вариантов, а не обязательно крутить что-то.
Ищу способ на 4 хода... но пока не получается.

[Mrrl›]

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

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

Для N=5 первая стратегия все еще лучше второй. Интересно, какая лучше при больших N.