Задача 110134

Темы:    [ Признаки делимости на 11 ] [ Выигрышные и проигрышные позиции ] [ Деление с остатком ] [ Периодичность и непериодичность ]

Сложность: 4 Классы: 8,9,10

Условие

Автор: Емельянов Л.А.

Два игрока по очереди выписывают на доске в ряд слева направо произвольные цифры. Проигрывает игрок, после хода которого одна или несколько цифр, записанных подряд, образуют число, кратное 11. Кто из игроков победит при правильной игре?

Решение

  Обозначим цифры, выписываемые игроками, последовательно через a₁, a₂, ..., цифры с нечётными номерами выписывает первый, а с чётными – второй. Рассмотрим остатки r_i от деления на 11 знакопеременных сумм S₀ = 0,  S₁ = a₁, S₂ = a₁ – a₂,  ...,  S_k = a₁ – a₂ + a₃ – ... + (–1)^k–1a_k.
  Согласно признаку делимости на 11, после k-го хода на доске возникнет число, кратное 11, тогда и только тогда, когда  r_k совпадает с одним из r₀, ..., r_k–1. Расположим эти остатки по кругу по часовой стрелке от 0 до 10 и изобразим последовательность ходов как процесс перемещения по кругу по неповторяющимся остаткам r_i. При этом первый игрок i-м ходом "прибавляет" к r_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, k. Тогда второй может занять один из них и после хода первого, второй может занять последний свободный остаток и выиграть.

Ответ

Второй игрок.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2003
Этап
Вариант	4
Класс
Класс	9
задача
Номер	03.4.9.4