Двое играют на шахматной доске 8×8. Начинающий игру делает первый ход – ставит на доску коня. Затем они по очереди его передвигают (по обычным правилам), при этом нельзя ставить коня на поле, где он уже побывал. Проигравшим считается тот, кому некуда ходить. Кто выигрывает при правильной игре – начинающий или его партнёр?

   Решение

Темы:    [ Периодичность и непериодичность ] [ Деление с остатком ]

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

Прислать комментарий

Условие

Пусть  a₀, a₁, ..., a_n, ... – периодическая последовательность, то есть для некоторого натурального T   a_n+T = a_n  (n ≥ 0).  Докажите, что
  а) среди всех периодов этой последовательности существует период наименьшей длины t;
  б) T делится на t.

Решение

а) В любом множестве натуральных чисел есть наименьший элемент.

б) Пусть t – наименьший период и  T = tq + r,  где  0 < r < t.  Тогда  a_n+r = a_n+T–tq = a_n+T = a_n  для любого n, то есть r – тоже период. Противоречие.

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