Про Али-Бабу

[ptil]

Али-Баба пытается проникнуть в пещеру с сокровищем. У входа в пещеру стоит барабан с четырьмя отверстиями по бокам. Около каждого отверстия внутри поставлен переключатель, имеющий два положения: <вверх> и <вниз>. Разрешается засунуть руки в любые два отверстия, пощупать, как стоят переключатели и переключить их произвольным образом (в частности, можно не переключать). После этого барабан вращается и после остановки нельзя установить, какие именно переключатели переключали в прошлый раз. Разрешается проделать эту операцию до 10 раз. Дверь в пещеру открывается, когда все переключатели в одном положении.
Как Али-Бабе попасть в пещеру?

[jtrefd]

  Мысль, не существует решения: есть вероятность, что все 10 раз будем попадать в одну и ту же пару отверстий.
Правильно рассуждаю?

[jtrefd]

Наверное, фраза

после остановки нельзя установить, какие именно переключатели переключали в прошлый раз

нуждается в уточнении.

[ptil]

есть вероятность, что все 10 раз будем попадать в одну и ту же пару отверстий.

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

Наверное, фраза

после остановки нельзя установить, какие именно переключатели переключали в прошлый раз

нуждается в уточнении.

Имеется ввиду, что нельзя запомнить, в какие именно отверстия засовывали руки в прошлый раз

[jtrefd]

Спасибо.
Не уяснил взаимное расположение отверстий. Надо быть повнимательнее.

[devnull]

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

[hripunov]

За первых два хода мы запросто можем три рычага привести в одно, например верхнее положение.
-Сначало два диаметрально противоположных приводим в верхнее положение
- затем суем руки в два соседних и если надо один приводим в верхнее положение...
Затем посложнее. Обозначим вехнее положение как В, нижнее как H.
Перед третьим ходом имеем 3 В  и один неизвестный. Но если пещера не открылась, то ясно, что он Н

-Суем руки в два соседних отверстия. В худшем случае они оба в положении В. Переключаем один в положение Н. Теперь там сложились варианты: 1)ВНВН или  2) ВННВ.
-Потом опять суем руки в  диаметральные . Если они в одинаковом положении то это вариант 1; переключаем оба, и пещера открывается. Если же их положение различно (вариант 2), то вынимаем руки, и ...
-Суем руки в два соседних отверстия. Если там одинаково, то переключаем оба и пещера открывается. Если там не одинаково, то все равно переключаем оба и складывается вариант 1.
 

[ptil]

hripunov, все верно

[Смекалистый]

Я решил в точности как hripunov, но я подошел к решению более формально и расписал подробный алгоритм для Али-Бабы, чтобы ему не пришлось долго думать. 

Обозначим положения переключателей: Н - нижнее, В - верхнее.
Текущее состояние обозначим (n,v), n - кол-во нижних переключателей, v - кол-во верхних.
Например, (1,3) - это 1 Н и 3В и изобразим так:
НВ
ВВ


Сначала переведем из неопределенного состояния (?,?) -> (1,3) за 2 хода.

1)  (?,?) -> (1,3) или (2,2)
Суем руки по диагонали и меняем на
НН -> ВВ
ВВ -> ВВ
ВН -> ВВ
НВ -> ВВ

Получаем:

В*
*В

* - неизвестные значения
Получили состояние (2,2) или (1,3).

2) (1,3) или (2,2) -> (1,3)
Суем руки в соседние и меняем:
НН - не может быть
НВ -> ВВ
ВН -> ВВ
ВВ оставляем
Таким образом получаем состояние (1,3).

3) (1,3)->(2,2)
Суем руки в соседние и меняем:
НВ -> ВВ - открылось
ВН -> ВВ - открылось
ВВ -> НВ - количество Н увеличилось на 1
НН - не может быть

4) (2,2) -> (2,2) не диагональное
(2,2) не диагональное - это:
ВВ    НВ    НН    ВН
НН    НВ    ВВ    ВН

Суем руки по диагонали и заменяем:
ВВ -> НН - открылось
НН -> ВВ - открылось
ВН, НВ оставляем

5) (2,2) не диагональное -> (2,2) диагональное
т.е. в такие
ВН    НВ
НВ    ВН

Суем руки в соседние и меняем:
ВВ -> НН - открылось
НН -> ВВ - открылось
ВН -> НВ
НВ -> ВН

6) (2,2) диагональное -> открытое
Суем руки по диагонали, там возможно только 2 варианта:
ВВ -> НН - открылось
НН -> ВВ - открылось



Таким образом требуется максимум 6 ходов.

[лучник]

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

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

[школьник]

 есть решение 2 задачи 7 ходов максимум
1) переворачиваем диагональные
2)переворачиваем соседнии
3)переворачиваем диагональные
4)переворачиваем 1
5)переворачиваем диагональные
6)переворачиваем соседнии
7)переворачиваем диагональные
Двери открыты при любой начальной комбинации