В футбольном чемпионате участвуют 18 команд. На сегодняшний день проведено 8 туров (в каждом туре все команды разбиваются на пары и в каждой паре команды играют друг с другом, причём пары не повторяются). Верно ли, что найдутся три команды, которые не сыграли ни одного матча между собой?

   Решение

Темы:    [ Индукция (прочее) ] [ Принцип Дирихле (прочее) ] [ Правило произведения ] [ Десятичная система счисления ]

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

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

Условие

Для любого натурального числа n существует составленное из цифр 1 и 2 число, делящееся на 2ⁿ. Докажите это.
(Например, на 2 делится 2, на 4 делится 12, на 8 делится 112, на 16 делится 2112...)

Решение 1

  Докажем, что разные n-значные числа, составленные из цифр 1 и 2, дают разные остатки при делении на 2ⁿ.
  Действительно, разность d таких чисел можно представить в виде   a_n·10^n–1 + a_n–1·10^n–2 + ... + a₂·10 + a₁,   где каждое из чисел a_i равно 0 или ±1. Рассмотрим наименьший номер k, для которого  a_k ≠ 0.  Очевидно, что d делится на 2^k–1, но не делится на 2^k. Таким образом, d делится на 2ⁿ только тогда, когда  d = 0.
  Но и таких n-значных чисел, и различных остатков ровно 2ⁿ, поэтому одно из этих чисел дает остаток нуль, то есть делится на 2ⁿ.

Решение 2

  Докажем по индукции более сильное утверждение:
    для любого натурального n существует составленное из цифр 1 и 2  n-значное число, кратное 2ⁿ.
  База: 2 делится на 2.
  Шаг индукции. Пусть n-значное число A из единиц и двоек делится на 2ⁿ. Число 10ⁿ делится на 2ⁿ, но не делится на 2ⁿ⁺¹. Следовательно, ровно одно из чисел  10ⁿ + A,   2·10ⁿ + A  кратно 2ⁿ⁺¹.

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