Тема Заключительный этап ВсОШ

Закл (финал) 11 класс → .04 Закл 2017

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела заключительный этап всош

Разделы подтемы Закл (финал) 11 класс

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#107146Максимум баллов за задание: 7

В ряд выписаны $n$ положительных чисел $a,a ,...,a . 1 2 n$ Вася хочет выписать под каждым числом $a i$ число $b >a i i$ так, чтобы для любых двух из чисел $b1,b2,...,bn$ отношение одного из них к другому было целым. Докажите, что Вася может выписать требуемые числа так, чтобы выполнялось неравенство $(n−1)∕2 b1b2...bn ≤ 2 a1a2...an.$

Источники: Всеросс., 2017, ЗЭ, 11.3(см. olympiads.mccme.ru)

Подсказки к задаче

Подсказка 1:

Условие слишком общее, не совсем понятно, как с ним работать. Попробуйте задать какие-то ограничения на отношения бэшек, чтобы получилось более сильное условие, из справедливости которого будет следовать справедливость изначального.

Подсказка 2:

Степень двойки в неравенстве намекает, что можно попробовать доказать, что отношения бэшек будут степенями двойки.

Подсказка 3:

Для удобства можно, не умаляя общности, сделать так, чтобы все ашки были в отрезке [1; 2). Почему и как это сделать? А главное, зачем?

Подсказка 4:

Ответ на последний вопрос - так проще придумывать нужные бэшки. Попробуйте придумать n последовательностей, для которых бэшка не меньшее соответствующей ашки, отношение бэшек - степень двойки, а произведение всех их членов равно n-й степени правой части неравенства из условия. Тогда какая-то одна будет подходить.

Показать доказательство

Мы докажем, что существуют даже числа $b ,b, 1 2$ $...,b , n$ удовлетворяющие следующим (более сильным) условиям:

$(1)$ $bi ≥ ai$ при всех $i≤n;$

$(2)$ $(n−1)∕2 b1b2...bn ≤2 a1a2...an;$

$(3)$ отношение любых двух из чисел $bi$ является степенью двойки (с целым показателем).

Заметим, что доказываемое утверждение не изменится, если какое-то из чисел $ak$ (а с ним и соответствующее $bk)$ умножить на некоторую степень двойки. Умножим каждое из чисел $ak$ на степень двойки так, чтобы все полученные числа лежали в промежутке $[1,2).$

Не умаляя общности можно считать, что $1≤ a1 ≤a2 ≤ ...≤ 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;

a , a , a , a ,...,a , a n n n n n n

Поскольку для любых $k$ и $ℓ$ выполнено неравенство $2aℓ ≥ 2> ak,$ каждая из последовательностей удовлетворяет $(1).$ Кроме того, каждая из последовательностей, очевидно, удовлетворяет $(3).$ Осталось показать, что хотя бы одна из них удовлетворяет $(2).$

Для этого заметим, что произведение всех $n2$ чисел во всех $n$ последовательностях равно

2(n−1)+(n−2)+...+0⋅anan...an= (2(n−1)∕2a1a2...an)n 1 2 n

Следовательно, произведение чисел хотя бы в одной из последовательностей не превосходит $2(n−1)∕2a1a2...an,$ что и требовалось.

Предыдущая подтема

Следующая подтема