У барона Мюнхгаузена есть 50 гирь. Веса этих гирь – различные натуральные числа, не превосходящие 100, а суммарный вес гирь – чётное число. Барон утверждает, что нельзя часть этих гирь положить на одну чашу весов, а остальные – на другую чашу так, чтобы весы оказались в равновесии. Могут ли эти слова барона быть правдой?

   Решение

Темы:    [ Признаки делимости на 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. Тогда второй может занять один из них и после хода первого, второй может занять последний свободный остаток и выиграть.

Ответ

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

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