|
|
 |
Условие
В ряд лежат $100N$ бутербродов, каждый с колбасой и сыром. Дядя Федор и кот Матроскин играют в игру. Дядя Федор за одно действие съедает один бутерброд с одного из краев. Кот Матроскин за одно действие может стянуть колбасу с одного бутерброда (а может ничего не делать). Дядя Федор каждый ход делает по $100$ действий подряд, а кот Матроскин делает только $1$ действие; дядя Федор ходит первым, кот Матроскин вторым, далее ходы чередуются до тех пор, пока дядя Федор не доест все бутерброды. Дядя Федор выигрывает, если последний съеденный им бутерброд был с колбасой. Верно ли, что при каждом натуральном $N$ он сможет выиграть независимо от ходов кота Матроскина?Решение
Докажем, что при $N = 3^{100}$ выиграет кот Матроскин. Для этого необходимо, чтобы на последнем шаге дяди Федора все оставшиеся $100$ бутербродов оказались без колбасы (иначе он сможет выбрать последовательность действий так, чтобы закончить на бутерброде с колбасой).
Пронумеруем бутерброды по порядку. Стратегию кота Матроскина разделим на несколько стадий. Сначала покажем, что он может действовать так, чтобы к моменту, когда останется треть от исходного количества бутербродов, все бутерброды, номер которых дает остаток $1$ при делении на $100$, были без колбасы.
Отметим в каждой сотне бутербродов тот бутерброд, номер которого дает остаток $1$ при делении на $100$. Пусть за первые $3^{99}$ ходов кот Матроскин стянет колбасу с каждого отмеченного бутерброда среди центральной трети бутербродов. Так как дядя Федор за это время съедает $3^{99}\cdot 100$ бутербродов, никакие бутерброды среди центральной трети съедены не будут. Следующие $3^{99}$ ходов кот Матроскин будет забирать колбасу с произвольного отмеченного бутерброда, а если отмеченных бутербродов с колбасой не останется – ничего не делать. Так как за один ход дядя Федор съедает не более одного отмеченного бутерброда (см. замечание 1), то еще через $3^{99}$ ходов все оставшиеся отмеченные бутерброды будут без колбасы.
На следующей стадии своей стратегии кот Матроскин аналогичным образом добьется того, чтобы все бутерброды, номер которых дает остаток $2$ при делении на $100$, оказались без колбасы; при этом количество бутербродов снова уменьшится в $3$ раза. На каждой следующей стадии он будет освобождать от колбасы очередной остаток от деления на $100$; через сто стадий, когда останется ровно $100$ бутербродов, они все будут без колбасы.
Ответ
Нет.Замечания
1. Каждым ходом дядя Федор будет съедать бутерброды с номерами, дающими различные остатки от деления на $100$, даже если съедает их с двух сторон. Это можно понять, заметив, что до его хода количества бутербродов для каждого остатка одинаковы, так как общее их количество кратно $100$; и после его хода ситуация такая же.
2. Можно уточнить стратегию кота Матроскина, показав, что при $N = 2^{100}$ он тоже выигрывает; на каждой стадии количество бутербродов при этом будет уменьшаться в два раза. Для этого колбасу ему нужно стягивать только с тех бутербродов (с номерами, дающими данный остаток от деления на $100$), до которых дядя Федор на данной стадии гарантированно не доберется. Нетрудно понять, что такой бутерброд действительно всегда будет находиться.
А вот при $N = 2^{100} - 1$ уже выигрывает дядя Федор. Действительно, первыми $2^{99} - 1$ ходами он съест любые $2^{99} - 1$ сотен бутербродов; за это время усилиями соперника появится не более $2^{99} - 1$ бутербродов без колбасы. Далее, если перед дядей Федором лежит $2^{k}$ сотен бутербродов, из которых не более $(100 - k) \cdot 2^{k} - 1$ без колбасы, то при $k > 0$ он может съесть ту половину ряда (правую или левую), в которой бутербродов без колбасы больше. Тогда их в ряду останется не более $(100 - k) \cdot 2^{k-1} - 1$ плюс, благодаря коту Матроскину, не более $2^{k-1}$ новых – всего не более $(100 - k + 1) \dot 2^{k-1} - 1$. Продолжая так и далее, при $k = 0$ дядя Федор получит сто бутербродов, из которых не более $99$ будут без колбасы.
