Олимпиадная задача: Деление 2k-значного числа на 9 — теория чисел и алгоритмы

  Пусть заданное число  N = a₁a₂...a_2k–1a_2k,  где a_i – одна из цифр 1, 2, 3, 4, 5, причём цифры с нечётными номерами выбирает первый игрок (А), а цифры с чётными номерами – второй (В). Обозначим  S_i = a₁ + a₂ + ... + a_i.  Число N делится на 9 тогда и только тогда, когда S_2k делится на 9.

  Пусть k делится на 3. Докажем, что в этом случае выигрывает игрок В. Для этого на любой ход a_2i–1 игрока А он должен отвечать ходом  a_2i = 6 − a_2i–1.  При этом  S_2i = 6i  при любом  i ≤ k,  в частности,  S_2k = 6k  делится на 9.

  Пусть теперь k не делится на 3. Покажем, что тогда выигрывает игрок А. Для этого ему достаточно выбрать  a₁ = 3,  а затем применить тактику В в первом случае, то есть на любой ход a_2i игрока В отвечать ходом  a_2i+1 = 6 − a_2i.  При этом  S_2k = 3 + 6(k − 1) + a_2k = 6k − 3 + a_2k.  Если  k = 3n + 1,  то

S_2k = 18n + 3 + a_2k  при делении на 9 дает остаток  3 + a_2k ≤ 8.  Если же  k = 3n + 2,  то остаток от деления  S_2k = 18n + 9 + a_2k  на 9 равен  a_2k ≠ 0.  В каждом из этих случаев число S_2k не делится на 9.

а) Может;  б) не может.