Форум Tolkien.SU
Человек Играющий => Стол с зеленым сукном => Тема начата: Mrrl от 03/04/2008, 12:42:40
-
Задачка, в общем, известная.
У дверей пещеры разбойников стоит квадратный стол, в каждом углу - по дырке, под дыркой - кувшин, в кувшине - селедка. Селедка может быть повернута головой или хвостом вверх. Али-Баба может просунуть руки в два кувшина, ощупать селедки (установить, как они повернуты), и при желании перевернуть одну или обе. После этого стол начинает крутиться и останаливается в каком-то другом положении (установить, какие кувшины проверярилсь в прошлый раз, нельзя). Если все четыре селедки окажутся повернуты одинаково, то дверь откроется.
Может ли Али-Баба открыть дверь? Сколько действий ему потребуется?
У задачи есть продолжение. Рассматриваются столы различных форм, и во всех случаях задается вопрос - какое минимальное количество рук надо иметь Али-Бабе, чтобы открыть дверь?
- в случае p-угольного стола (p - простое)
- в случае 2*p-угольного стола (p - простое)
- в случае p*q-угольного стола (p,q - простые)
- в случае pn-угольного стола (p - простое)
- в произвольном случае
- в ситуации, когда стол может переворачиваться (вместе с селедками)
- для кубического стола (8 селедок в углах)
ну и так далее?
Задачка с подвохом, причем очень глубоким :) - когда найдете, можно будет его обсудить.
И чур, не подглядывать.
-
самое простое решение для начальной задачи, которое я вижу, занимает в 4/14 случаев 1 ход, а в остальных - 1+Y ходов, где Y в среднем 2 (точнее, равен количеству бросков монеты, необходимых, чтобы угадать результат).
Два вопроса, не очевидных из условия:
для Х рук он имеет право переворачивать от 1 до Х селёдок?
В такой задаче есть полностью надёжное решение, не зависящее от вероятности?
Для 1 руки нет определённо.
Интересно, сколько для одной руки требуется в среднем ходов?
-
Для Х рук - может проверить X селедок и перевернуть (в зависимости от результата проверки) от 0 до Х - но только из числа проверенных.
Задачка не на вероятности - для Али-Бабы принимается только полностью надежное решение. Однорукий Али-Баба, таким образом, может справиться только с 2-угольным столом.
Собственно, подвох где-то рядом: для начала, как сформулировать стратегию для треугольного стола при игре против однорукого Али-Бабы (ответ: поинтересоваться, какой угол собирается проверить Али-Баба в следующий раз, и подставить ему неправильную селедку).
В среднем для одной руки и N вершин - подсчитать несложно:
Sum({u,k},1<=u<=k<=N-1,Comb(N,k)/u)*N/(2^N-2).
Можно ли ее упростить и какова асимптотика, пока непонятно.
Но это если мы заранее выбрали желаемое направление. А вот если первую селедку не переворачивать, а остальные ориентировать в соответствии с ней, то число ходов может быть и меньше (начиная с какого-то N).
-
Похоже, что стол в форме 4-мерного гиперкуба выигрывает у 11-рукого Али-Бабы ;D
-
может перевернуть от 0 до Х
Вот это и было неочевидно - мог ли он НЕ переворачивать...
Собственно, подвох где-то рядом: для начала, как сформулировать стратегию для треугольного стола при игре против однорукого Али-Бабы (ответ: поинтересоваться, какой угол собирается проверить Али-Баба в следующий раз, и подставить ему неправильную селедку).
Да, в этом случае Али-Баба может полагаться только "на везение". Причём всегда остаётся возможность, что он "не попадёт". Кстати, а есть ли у треугольного стола такой же способ всегда выигрывать, если Али-Баба о двух руках? Впрочем, дошло - нет, тут Али-Бабе нужно максимум два хода на всё независимо от начального расположения.
Попарившись, нашёл для нач. задачи решение о пяти шести ходах. Меньше есть?
Вообще, подлый стол об 2Х+1 сторонах всегда найдёт чего подсунуть Х-рукому Али-Бабе. Это очевидно?
-
Есть решение за 5 ходов. А если бы Али-Баба знал хотя бы четность исходного числа селедок, повернутых головой вверх - уложился бы в 4.
В условии задачи есть слова "при желании". Значит, изначально предполагается, что может и не переворачивать :)
Неочевидно - существует ли неоптимизируемая стратегия с гарантированным выигрышем, в которой вообще может возникнуть ситуация, когда надо "не переворачивать". Казалось бы, если Али-Баба планирует ход, в котором возможно "пустое" действие, столу всегда выгодно повернуться так, чтобы именно такое действие и произошло - тогда Али-Баба зря потратит ход, а состояние стола не изменится. С другой стороны, Али-Баба за этот ход получит некоторую информацию, но вот достаточно ли этого?
Про 2*X+1 - да, очевидно. Выбираем сторону, селедки на которой ориентированы по-разному, и...
-
Неочевидно - существует ли неоптимизируемая стратегия с гарантированным выигрышем, в которой вообще может возникнуть ситуация, когда надо "не переворачивать".
Ну, я нашёл способ (в нач. задаче) на 5 ходов, при котором такая ситуация есть. Причём делать что-то явно хуже, чем не делать: у нас цель - уменьшать количество возможных вариантов, а не обязательно крутить что-то.
Ищу способ на 4 хода... но пока не получается.
-
Варианты стратегий однорукого Али-Бабы против случайно вращающегося стола:
- выбрать направление селедок и стремиться к нему;
- проверить первую селедку, не переворачивать, объявить ее направление целевым и стремиться к нему;
- первую селедку не переворачивать, вторую перевернуть, если она не совпадает с первой, но если и третья не сопадает с первой (а совпадает с исходным положением второй) - объявить ее направление целевым и не переворачивать;
- проверить первые 3 селедки (1-ю и 2-ю не переворачивать), объявить целевым направление тех, кого больше. 3-ю перевернуть только если 1-я и 2-я направлены одинаково, а 3-я - по-другому.
Для N=5 первая стратегия все еще лучше второй. Интересно, какая лучше при больших N.