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

Проект МЦНМО
при участии
школы 57
Задача 66158
Темы:    [ Числовые неравенства. Сравнения чисел. ]
[ Теория алгоритмов (прочее) ]
[ Принцип Дирихле (прочее) ]
Сложность: 5-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Петров Ф.

На доске выписаны в ряд n положительных чисел a1, a2, ..., an. Вася хочет выписать под каждым числом ai число  bi ≥ ai  так, чтобы для каждых двух из чисел b1, b2, ..., bn отношение одного из них к другому было целым. Докажите, что Вася может выписать требуемые числа так, чтобы выполнялось неравенство  b1b2...bn ≤ 2(n–1)/2a1a2...an.


Решение

Мы докажем, что существуют даже числа b1, b1, ..., bn, удовлетворяющие следующим (более сильным) условиям:
    1)  bibi  при всех  i ≤ n;
    2)  b1b2bn ≤ 2(n–1)/2a1a2...an;
    3) отношение любых двух из чисел bi является степенью двойки (с целым показателем).   Заметим, что доказываемое утверждение не изменится, если какое-то из чисел ak (а с ним и соответствующее bk) умножить на некоторую степень двойки. Умножим каждое из чисел bk на степень двойки так, чтобы все полученные числа лежали в промежутке  [1, 2).
  Не умаляя общности можно считать, что  1 ≤ a1a2 ≤ ... ≤ an < 2.  Покажем, что всем трём условиям удовлетворяет одна из следующих n последовательностей:
    a1, 2a1, 2a1, 2a1, ..., 2a1, 2a1;
    a2, a2, 2a2, 2a2, ..., 2a2, 2a2;
    a3, a3, a3, 2a3, ..., 2a3, 2a3;
      ...
    an–1, an–1, an–1, an–1, ..., an–1, 2an–1;
    an, an, an, an, ..., an, an.
  Поскольку  2al ≥ 2 > ak  для любых k и l, каждая из последовательностей удовлетворяет 1). Кроме того, каждая из последовательностей, очевидно, удовлетворяет 3). Осталось показать, что хотя бы одна из них удовлетворяет 2).
  Для этого заметим, что произведение всех n² чисел во всех n последовательностях равно    Следовательно, произведение чисел хотя бы в одной из последовательностей не превосходит  2(n–1)/2a1a2...an.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 5
класс
Класс 10
задача
Номер 10.4
олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2016/2017
этап
Вариант 5
класс
Класс 11
задача
Номер 11.3

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

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