ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116396
Темы:    [ Арифметика остатков (прочее) ]
[ Индукция (прочее) ]
Сложность: 4+
Классы: 10,11
В корзину
Прислать комментарий

Условие

Докажите, что при  n > 1  число   11 + 3³ + ... + (2n – 1)2n – 1   делится на 2n, но не делится на 2n+1.


Решение

  Лемма 1.   k2n ≡ 1  (mod 2n+2)   для каждого нечётного числа k.
  Доказательство.   k2n – 1 = (k – 1)(k + 1)(k² + 1)(k4 + 1)...(k2n–1 + 1)   – произведение  n + 1  чётных множителей. Вдобавок один из первых двух множителей делится на 4.

  Лемма 2.   (k + 2n)kkk(1 + 2n)  (mod 2n+2)   при  n > 1.
  Доказательство.     а все слагаемые, кроме двух первых, делятся на 2n+2.

  Вернёмся к решению задачи. Обозначим сумму из условия через Sn, а разность  Sn+1Sn  через Rn. Будем вести индукцию по n.
  База  (n = 2)  очевидна.
  Шаг индукции.  Sn+1 = Sn + RnRn есть сумма 2n–1 слагаемых вида mm, где  m = 2n + k,  k – нечётное число, меньшее 2n. По лемме 1
mmmk  (mod 2n+2).  Поэтому   Rn ≡ (1 + 2n) + (3 + 2n)³ + (5 + 2n)5 + ...  (mod 2n+2).
  По лемме 2   Rn ≡ Sn(1 + 2n) (mod 2n+2).   Значит,   Sn+1 ≡ 2Sn(1 + 2n–1)  (mod 2n+2).
  По предположению индукции Sn делится на 2n (значит, Sn+1 делится на 2n+1) и не делится на 2n+1 (значит, Sn+1 не делится на 2n+2).

Замечания

1. См. также задачу М2252 из Задачника "Кванта" ("Квант", 2012, №1).
2. 7 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 2011/2012
Номер 33
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
Задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .