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

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

Условие

Докажите, что любое натуральное число можно представить в виде  3u12v1 + 3u22v2 + ... + 3uk2vk,  где  u1 > u2 > ... > uk ≥ 0  и  0 ≤ v1 < v2 < ... < vk  – целые числа.


Решение

  Индукция. База  (n = 1)  очевидна.
  Шаг индукции. Пусть  n = 2m.  Число m можно представить в указанном виде. Увеличив все vi на 1, получим представление числа n.
  Пусть n нечётно. Возьмём  v0 = 0.  Рассмотрим наибольшее u0, при котором  3u0n.  Если неравенство строгое, то представим число  l = n – 3u0  в указанном виде. При этом  v1 > 0,  поскольку l чётно, а  u1 < u0,  потому что  l < 3u0+1 – 3u0 = 2·3u0.

Замечания

4 балла

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

олимпиада
Название Турнир городов
Турнир
Номер 25
Дата 2003/2004
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 2

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

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