|
|
 |
Условие
У входа в пещеру стоит барабан, на нём по кругу через равные промежутки расположены N одинаковых с виду бочонков. Внутри каждого бочонка лежит селёдка – либо головой вверх, либо головой вниз, но где как – не видно (бочонки закрыты). За один ход Али-Баба выбирает любой набор бочонков (от 1 до N штук) и переворачивает их все. После этого барабан приходит во вращение, а когда останавливается, Али-Баба не может определить, какие бочонки перевёрнуты. Пещера откроется, если во время вращения барабана все N селёдок будут расположены головами в одну сторону. При каких N Али-Баба сможет открыть пещеру?Решение
Заменим бочонки на нули и единицы, стоящие по кругу.
Пусть N ≠ 2k. Покажем, что при невезении Али-Баба никогда не откроет пещеру. Можно считать, что мы играем против Али-Бабы, вращая круг, и что он заранее говорит нам, на каких местах он будет менять цифры на каждом (в том числе и на первом) ходу.
Рассмотрим сначала случай, когда N нечётно. Расставим на круге нули и единицы так, чтобы Али-Баба не выиграл первым своим (известным нам) ходом (то есть чтобы после его хода на круге были как нули, так и единицы).
Пусть Али-Баба на очередном ходу выбрал для замены определённые k мест. Он выиграет только если эти k мест совпадут либо со множеством всех нулей, либо со множеством всех единиц. Но число нулей не равно числу единиц (сумма чисел нечётна!). Значит, каких-то цифр – не k штук. Загнав поворотом такую цифру на одно из выбранных k мест, мы не дадим Али-Бабе выиграть следующим ходом.
Случай, когда N чётно, но имеет нечётный делитель m, сводится к разобранному: отметим на большом круге m равноотстоящих мест и забудем про остальные; действуя, как описано выше, мы сможем помешать Али-Бабе уравнять все цифры на отмеченных местах.
Алгоритм выигрыша Али-Бабы для 2k бочонков будем строить индуктивно. База (k = 1) очевидна.
Шаг индукции. Пусть у нас есть алгоритм Am для m бочонков. Построим A2m. Начнём с частных случаев. Разобьём круг на m пар противоположных бочонков и установим соответствие между этими парами и и m бочонками на другом круге.
1) Пусть мы знаем, что в каждой паре цифры равны. Применим алгоритм Am, заменяя бочонки соответствующими парами. Ясно, что когда пещера открылась там, она откроется и здесь.
2) Пусть мы знаем, что чётность суммы в каждой паре одинакова. Применим Am для пар. Если пещера не открылась, то все суммы были нечётны. Но меняя оба числа пары, мы не меняем чётности. Значит, все суммы остались нечётными. Изменим m цифр подряд (назовём эту операцию D). Теперь все суммы чётны. Еще раз применив Am для пар, откроем пещеру. Назовём алгоритм для этого случая B.
3) Применим теперь Am для пар другим способом: цель – сделать суммы в парах одной чётности. По-прежнему на каждом шагу мы выбираем набор пар согласно Am, но меняем в каждой выбранной паре только по одной цифре. Назовём этот алгоритм C. Он гарантирует, что на каком-то шаге (мы не знаем, на каком) чётности сумм совпадут. Пещеру это, понятно, не откроет. Но мы схитрим: после каждого шага C применим B, а затем D. При совпадении сумм чётностей B откроет пещеру, а иначе BD не изменит чётностей сумм.
Ответ
При N = 2k, k = 0, 1, 2, ...
Замечания
1. 14 баллов.
2. Существует алгоритм, при котором селёдки принимают все 2N возможных положений.
