Фокусник расставил по кругу 12 шляп, под одну из которых он спрятал конфету. За один ход малыш Кирюша может проверить любые две шляпы, после чего фокусник перекладывает конфету под соседнюю шляпу с той, под которой конфета была, незаметно для Кирюши. Может ли Кирюша гарантированно найти конфету не более, чем за 12 ходов?
More Questions From This User See All
Answers & Comments
Стратегия:
Будем считать, что нам все время не везет, иначе мы нашли бы конфету раньше.
Пронумеруем шляпы от 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 ходов.