Дядя Федор и кот Матроскин: игра с бутербродами

Докажем, что при $N = 3^{100}$ выиграет кот Матроскин. Для этого необходимо, чтобы на последнем шаге дяди Федора все оставшиеся $100$ бутербродов оказались без колбасы (иначе он сможет выбрать последовательность действий так, чтобы закончить на бутерброде с колбасой).

Пронумеруем бутерброды по порядку. Стратегию кота Матроскина разделим на несколько стадий. Сначала покажем, что он может действовать так, чтобы к моменту, когда останется треть от исходного количества бутербродов, все бутерброды, номер которых дает остаток $1$ при делении на $100$, были без колбасы.

Отметим в каждой сотне бутербродов тот бутерброд, номер которого дает остаток $1$ при делении на $100$. Пусть за первые $3^{99}$ ходов кот Матроскин стянет колбасу с каждого отмеченного бутерброда среди центральной трети бутербродов. Так как дядя Федор за это время съедает $3^{99}\cdot 100$ бутербродов, никакие бутерброды среди центральной трети съедены не будут. Следующие $3^{99}$ ходов кот Матроскин будет забирать колбасу с произвольного отмеченного бутерброда, а если отмеченных бутербродов с колбасой не останется – ничего не делать. Так как за один ход дядя Федор съедает не более одного отмеченного бутерброда (см. замечание 1), то еще через $3^{99}$ ходов все оставшиеся отмеченные бутерброды будут без колбасы.

На следующей стадии своей стратегии кот Матроскин аналогичным образом добьется того, чтобы все бутерброды, номер которых дает остаток $2$ при делении на $100$, оказались без колбасы; при этом количество бутербродов снова уменьшится в $3$ раза. На каждой следующей стадии он будет освобождать от колбасы очередной остаток от деления на $100$; через сто стадий, когда останется ровно $100$ бутербродов, они все будут без колбасы.