Разделы 
Дополнительно
Задача по математике - 1675
2019-01-20 
Два игрока по очереди выписывают на доске в ряд слева направо произвольные цифры. Проигрывает игрок, после хода которого одна или несколько цифр, записанных подряд, образуют число, делящееся на 11. Кто из игроков победит при правильной игре?
Решение:
Обозначим цифры, выписываемые игроками, последовательно через $a_1, a_2,\cdots$, цифры с нечетными номерами выписывает первый, а с четными - второй. Рассмотрим остатки от деления на 11 знакопеременных сумм $S_0 = 0, S_1 - a_1, S_2 - a_1 - a_2, \cdots, S_k - a_1 - a_2 + a_3 + \cdots + ( -1)^{k-1} a_k$. Согласно признаку делимости на 11, после $k$-го хода на доске возникнет число, делящееся на 11, тогда и только тогда, когда $S_k$ совпадает с одним из $S_0,\cdots, S_{k-1}$. Расположим остатки отделения на 11 по кругу по часовой стрелке от 0 до 10 и изобразим последовательность ходов как процесс перемещения по кругу по неповторяющимся остаткам отделения на 11 сумм $0 = S_0, S_1, S_2, S_3, \cdots$. При этом первый игрок $i$-м ходом прибавляет к $S_{i-1}$ любое число $a_i$ от 1 до 9, а второй - любое число от -1 до -9. Таким образом, кроме повтора уже встречавшегося остатка, первому игроку запрещен ход против часовой стрелки на 1, а второму - ход по часовой стрелке на 1. После $i$-го хода свободными останутся $10 - i$ остатков. Игрок гарантированно может сделать ход, если есть хотя бы два свободных остатка, значит, первые восемь ходов игроки сделать смогут, а 11-й ход сделать нельзя никогда.
Рассмотрим ситуацию после седьмого хода (это ход первого), когда свободны 3 остатка.
1) Свободные остатки расположены подряд: $i - 1, i, i + 1$. Тогда второй выписывает число с остатком $i$ (занимает остаток $i$), первый - $i + 1$, а второй $i - 1$ и выигрывает.
2) Остатки расположены так: два рядом - $i, i + 1$ и один отдельно - $j$. Тогда второй занимает один из остатков $i, i + 1$, далее либо первый занимает остаток $i + 1$, второй $j$ и выигрывает, либо первый занимает $j$, а второй - один из оставшихся $i, i + 1$ и выигрывает.
3) Никакие два остатка не стоят рядом: $i, j, к$. Тогда второй может занять один из них и после хода первого, второй может занять последний свободный остаток и выиграть.
Ответ. Победит второй игрок.
Два игрока по очереди выписывают на доске в ряд слева направо произвольные цифры. Проигрывает игрок, после хода которого одна или несколько цифр, записанных подряд, образуют число, делящееся на 11. Кто из игроков победит при правильной игре?
Решение:
Обозначим цифры, выписываемые игроками, последовательно через $a_1, a_2,\cdots$, цифры с нечетными номерами выписывает первый, а с четными - второй. Рассмотрим остатки от деления на 11 знакопеременных сумм $S_0 = 0, S_1 - a_1, S_2 - a_1 - a_2, \cdots, S_k - a_1 - a_2 + a_3 + \cdots + ( -1)^{k-1} a_k$. Согласно признаку делимости на 11, после $k$-го хода на доске возникнет число, делящееся на 11, тогда и только тогда, когда $S_k$ совпадает с одним из $S_0,\cdots, S_{k-1}$. Расположим остатки отделения на 11 по кругу по часовой стрелке от 0 до 10 и изобразим последовательность ходов как процесс перемещения по кругу по неповторяющимся остаткам отделения на 11 сумм $0 = S_0, S_1, S_2, S_3, \cdots$. При этом первый игрок $i$-м ходом прибавляет к $S_{i-1}$ любое число $a_i$ от 1 до 9, а второй - любое число от -1 до -9. Таким образом, кроме повтора уже встречавшегося остатка, первому игроку запрещен ход против часовой стрелки на 1, а второму - ход по часовой стрелке на 1. После $i$-го хода свободными останутся $10 - i$ остатков. Игрок гарантированно может сделать ход, если есть хотя бы два свободных остатка, значит, первые восемь ходов игроки сделать смогут, а 11-й ход сделать нельзя никогда.
Рассмотрим ситуацию после седьмого хода (это ход первого), когда свободны 3 остатка.
1) Свободные остатки расположены подряд: $i - 1, i, i + 1$. Тогда второй выписывает число с остатком $i$ (занимает остаток $i$), первый - $i + 1$, а второй $i - 1$ и выигрывает.
2) Остатки расположены так: два рядом - $i, i + 1$ и один отдельно - $j$. Тогда второй занимает один из остатков $i, i + 1$, далее либо первый занимает остаток $i + 1$, второй $j$ и выигрывает, либо первый занимает $j$, а второй - один из оставшихся $i, i + 1$ и выигрывает.
3) Никакие два остатка не стоят рядом: $i, j, к$. Тогда второй может занять один из них и после хода первого, второй может занять последний свободный остаток и выиграть.
Ответ. Победит второй игрок.
