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