Question

Фокусник расставил по кругу 12 шляп, под одну из которых он спрятал конфету. За один ход малыш Кирюша может проверить любые две шляпы, после чего фокусник перекладывает конфету под соседнюю шляпу с той, под которой конфета была, незаметно для Кирюши. Может ли Кирюша гарантированно найти конфету не более, чем за 12 ходов?

Answer 1

Ответ: да.

Стратегия:

Будем считать, что нам все время не везет, иначе мы нашли бы конфету раньше.

Пронумеруем шляпы от 1 да 12.

Тут есть инвариант: шляпа каждым своим ходом меняет четность.

1) Сначала допустим, что она под четным номером.

Проверим шляпы 2 и 4. На следующем ходу, исходя из допущения, конфета не может быть под номерами 2, 3, 4.

Она будет под нечетным номером (инвариант). Проверим 1 и 5. На следующем ходу, конфета не может быть под номерами: 1, 2, 3, 4, 5.

Аналогично проверяем 12 и 6, 11 и 7, 10 и 8.

На 5 проверке: 10 и 8: конфета была под четным номером, но т. к. в 10 и 8 конфеты не оказалось, то изначально конфета лежала под нечетным номером, а значит на 5 ходу она была под нечетным номером, а на следующем ходу она будет лежать под четным номером.

2) Далее мы уже знаем, что конфета лежит под четным номером.

Повторяем в точности 1), т. к. мы уже точно знаем, что конфета под четным номером.

Итого у нас 5+5=10 ходов.

Answer 2

Да, Кирюша может гарантированно найти конфету не более, чем за 12 ходов. Пусть каждая шляпа будет представлена номером от 1 до 12. В начале Кирюша выбирает любые две шляпы и проверяет их. Пусть он выбрал шляпы с номерами 1 и 2. Если конфета оказалась под шляпой 1, то фокусник перекладывает ее под шляпу 2. Если конфета оказалась под шляпой 2, то фокусник перекладывает ее под шляпу 1. Если конфета оказалась под другой шляпой, то фокусник перекладывает ее под одну из выбранных шляп, например, под шляпу 1. Таким образом, после первого хода Кирюша знает, что конфета находится либо под шляпой 1, либо под шляпой 2. На следующем ходу Кирюша выбирает любые две другие шляпы, например, с номерами 3 и 4, и повторяет процесс проверки и перекладывания конфеты. Если конфета оказалась под одной из первых двух шляп (1 или 2), то Кирюша уже знает, где она находится. Если конфета оказалась под другой шляпой, то фокусник перекладывает ее под одну из выбранных шляп, например, под шляпу 3. Таким образом, после второго хода Кирюша знает, что конфета находится либо под шляпой 1 или 2, либо под шляпой 3 или 4. На каждом последующем ходу Кирюша выбирает две новые шляпы и повторяет процесс проверки и перекладывания конфеты. После 12-го хода Кирюша будет знать, что конфета находится либо под одной из первых двух шляп, либо под одной из последних двух шляп. Таким образом, Кирюша гарантированно найдет конфету не более, чем за 12 ходов.