МОШ 2021, 9 класс, задача 5
В ряд лежат бутербродов, каждый с колбасой и сыром. Дядя Фёдор и кот Матроскин играют в игру. Дядя Фёдор за одно действие съедает один бутерброд с одного из краёв. Кот Матроскин за одно действие может стянуть колбасу с одного бутерброда (а может ничего не делать). Дядя Фёдор каждый ход делает по действий подряд, а кот Матроскин делает только действие; дядя Фёдор ходит первым, кот Матроскин вторым, далее ходы чередуются до тех пор, пока дядя Фёдор не доест все бутерброды. Дядя Фёдор выигрывает, если последний съеденный им бутерброд был с колбасой. Верно ли, что при каждом натуральном он сможет выиграть независимо от ходов кота Матроскина?
(И. Митрофанов)
Ответ. нет.
Решение. Докажем, что при выиграет кот Матроскин. Для этого необходимо, чтобы на последнем шаге дяди Фёдора все оставшиеся бутербродов оказались без колбасы (иначе он сможет выбрать последовательность действий так, чтобы закончить на бутерброде с колбасой).
Пронумеруем бутерброды по порядку. Стратегию кота Матроскина разделим на несколько стадий. Сначала покажем, что он может действовать так, чтобы к моменту, когда останется треть от исходного количества бутербродов, все бутерброды, номер которых даёт остаток при делении на , были без колбасы.
Отметим в каждой сотне бутербродов тот бутерброд, номер которого даёт остаток при делении на . Пусть за первые ходов кот Матроскин стянет колбасу с каждого отмеченного бутерброда среди центральной трети бутербродов. Так как Дядя Фёдор за это время съедает бутербродов, никакие бутерброды среди центральной трети съедены не будут. Следующие ходов кот Матроскин будет забирать колбасу с произвольного отмеченного бутерброда, а если отмеченных бутербродов с колбасой не останется -- ничего не делать. Так как за один ход дядя Фёдор съедает не более одного отмеченного бутерброда (см. замечание 1), то ещё через ходов все оставшиеся отмеченные бутерброды будут без колбасы.
На следующей стадии своей стратегии кот Матроскин аналогичным образом добьётся того, чтобы все бутерброды, номер которых даёт остаток при делении на , оказались без колбасы; при этом количество бутербродов снова уменьшится в раза. На каждой следующей стадии он будет освобождать от колбасы очередной остаток от деления на ; через сто стадий, когда останется ровно бутербродов, они все будут без колбасы.
Замечание 1. Каждым ходом дядя Фёдор будет съедать бутерброды с номерами, дающими различные остатки от деления на , даже если съедает их с двух сторон. Это можно понять, заметив, что до его хода количества бутербродов для каждого остатка одинаковы, так как общее их количество кратно ; и после его хода ситуация такая же.
Замечание 2. Можно уточнить стратегию кота Матроскина, показав, что при он тоже выигрывает; на каждой стадии количество бутербродов при этом будет уменьшаться в два раза. Для этого колбасу ему нужно стягивать только с тех бутербродов (с номерами, дающими данный остаток от деления на ), до которых дядя Фёдор на данной стадии гарантированно не доберётся. Нетрудно понять, что такой бутерброд действительно всегда будет находиться.
А вот при уже выигрывает дядя Фёдор. Действительно, первыми ходами он съест любые сотен бутербродов; за это время усилиями соперника появится не более бутербродов без колбасы. Далее, если перед дядей Фёдором лежит сотен бутербродов, из которых не более без колбасы, то при он может съесть ту половину ряда (правую или левую), в которой бутербродов без колбасы больше. Тогда их в ряду останется не более плюс, благодаря коту Матроскину, не более новых -- всего не более . Продолжая так и далее, при дядя Фёдор получит сто бутербродов, из которых не более будут без колбасы.