Задача №15481

Тройку различных натуральных чисел назовём удачной, если любое число в ней хотя бы на 5 больше, чем треть суммы двух других чисел. Например, 40, 45, 50 — удачная тройка.

а) Сколько существует удачных троек, содержащих числа 50, 60 и ещё одно число, большее 60?

б) Найдётся ли удачная тройка, одно из чисел которой равно 15?

в) Какое наибольшее количество чисел от 1 до 100 включительно можно расставить по кругу так, чтобы каждое число встречалось не более одного раза и любые три подряд идущих числа образовывали удачную тройку?

а) Пусть тройка содержит числа 50, 60 и натуральное число $x>60\text{.}$ Условие удачности: каждое число не меньше, чем треть суммы двух других плюс 5. Для тройки $(50,60,x)$ получаем три неравенства:

$$3\cdot 50-60-x\ge 15\Rightarrow 90-x\ge 15\Rightarrow x\le 75,$$ $$3\cdot 60-50-x\ge 15\Rightarrow 130-x\ge 15\Rightarrow x\le 115,$$ $$3x-50-60\ge 15\Rightarrow 3x\ge 125\Rightarrow x\ge 42.$$

Учитывая $x>60$ и натуральность, $x\in \{61;62;\dots ;75\}\text{.}$ Всего 15 троек.

б) Предположим, существует удачная тройка с числом 15. Пусть $a=15\text{,}$ $b$ и $c$ — другие натуральные числа, различные. Тогда:

$$3\cdot 15-b-c\ge 15\Rightarrow b+c\le 30,$$ $$3b-15-c\ge 15\Rightarrow 3b-c\ge 30,$$ $$3c-15-b\ge 15\Rightarrow 3c-b\ge 30.$$

Поскольку $b,c\ge 16$ (различны и больше 15), то $b+c\ge 32\text{,}$ что противоречит $b+c\le 30\text{.}$ Значит, такой тройки нет.

в) Требуется найти наибольшее количество различных натуральных чисел от 1 до 100, которые можно расставить по кругу так, чтобы любые три подряд идущих числа образовывали удачную тройку.

1. Оценка снизу. Покажем, что все числа в такой расстановке не меньше 18. Из пункта

б) число 15 не может входить ни в какую удачную тройку. Проверим 16 и 17. Если бы 16 входило в удачную тройку $(16,b,c)\text{,}$ то для 16: $3\cdot 16-b-c\ge 15\Rightarrow b+c\le 33\text{.}$ Но $b,c\ge 17$ (различны), тогда $b+c\ge 34\text{,}$ противоречие. Аналогично для 17: $3\cdot 17-b-c\ge 15\Rightarrow b+c\le 36\text{,}$ но $b,c\ge 18\text{,}$ тогда $b+c\ge 37\text{,}$ противоречие. Значит, все числа в расстановке $\ge 18\text{.}$

2. Пример для 29 чисел. Возьмём числа от 70 до 98 включительно: это 29 последовательных натуральных чисел $70,71,\dots ,98\text{.}$ Расставим их по кругу в порядке возрастания. Проверим условие удачности для любых трёх подряд идущих чисел.

• Для внутренних троек вида $(n,n+1,n+2)$ с $n\ge 70$ условие выполнено, так как $n\ge \frac{(n+1)+(n+2)}{3}+5$ эквивалентно $n\ge 18\text{,}$ что верно.
• Для граничных троек, содержащих числа 98 и 70: тройка $(97,98,70)\text{:}$ для 70: $\frac{97+98}{3}+5=\frac{195}{3}+5=70\text{,}$ равенство, условие выполнено; для 98: $\frac{97+70}{3}+5=\frac{167}{3}+5<98\text{;}$ для 97: аналогично. Тройка $(98,70,71)\text{:}$ проверка аналогично показывает выполнение условия.
  Таким образом, 29 чисел расставить можно.

3. Доказательство, что 30 чисел расставить нельзя. Предположим, существует расстановка из 30 чисел, удовлетворяющая условию. Пусть $L$ — наименьшее число в этой расстановке. Из п.1 $L\ge 18\text{.}$ Рассмотрим случай $L=18$ (если $L>18\text{,}$ оценка только усилится). Пусть соседи $L$ — числа $a$ и $b\text{.}$ Из условия удачности для $L\text{:}$

$$3L-a-b\ge 15\Rightarrow 3\cdot 18-a-b\ge 15\Rightarrow a+b\le 39.$$

Поскольку $a,b\ge 19$ (различны и больше $L$), то $a+b\ge 38\text{.}$ Значит, $a+b=39\text{,}$ и $\{a;b\}=\{19;20\}$ (в некотором порядк

е). Без ограничения общности, пусть при обходе по кругу порядок: $\dots ,20,18,19,\dots \text{.}$
Рассмотрим цепочку чисел, идущую от 19 в направлении от 18. Обозначим эту цепочку: $x_1,x_2,\dots ,x_k\text{,}$ где $x_1$ — сосед 19, отличный от 18, и в конце цепочка приходит к 20. Так как всего чисел 30, то $k=28$ (числа: 18, 19, $x_1,\dots ,x_{28}\text{,}$ 20).
Для каждого $x_i$ выполняется условие удачности в тройках, содержащих $x_i\text{.}$ В частности:

• Для $x_1\text{:}$ из тройки $(18,19,x_1)$ условие для 19 даёт $3\cdot 19-18-x_1\ge 15\Rightarrow x_1\le 24\text{.}$ Также $x_1\ge 21$ (так как числа различны, и 18, 19, 20 уже заняты).
• Для $x_2\text{:}$ из тройки $(19,x_1,x_2)$ условие для $x_1$ даёт $3x_1-19-x_2\ge 15\Rightarrow x_2\le 3x_1-34\text{.}$ Поскольку $x_1\le 24\text{,}$ то $x_2\le 3\cdot 24-34=38\text{.}$ Также $x_2\ge x_1+1\ge 22\text{.}$
  Продолжая аналогично, получим, что каждое $x_i$ ограничено сверху линейной функцией от предыдущих. Можно показать, что даже при максимально возможных значениях $x_i$ (выбирая равенства в неравенствах), последовательность растёт достаточно быстро, и для $i=28$ оценка $x_{28}$ превысит 100. Конкретно, рассмотрим рекуррентное соотношение при равенствах: $x_i=3x_{i-1}-x_{i-2}-15$ для $i\ge 2\text{,}$ с $x_0=18\text{,}$ $x_1=19\text{.}$ Решение этого линейного рекуррентного уравнения: $x_i=A{\lambda }_1^i+B{\lambda }_2^i+15\text{,}$ где ${\lambda }_1=\frac{3+\sqrt{5}}{2}\approx 2.618\text{,}$ ${\lambda }_2=\frac{3-\sqrt{5}}{2}\approx 0.382\text{.}$ Используя начальные условия, находим константы $A$ и $B\text{,}$ и при $i=28$ получаем $x_{28}>100$ (расчёт показывает $x_{28}\approx 2.618^{28}$ порядка тысяч). Это означает, что даже если выбирать $x_i$ меньше максимального, чтобы остаться в пределах от 1 до 100, цепочка из 28 различных чисел, все не менее 21, невозможна, так как числа должны быть различными и не превышать 100, а медленный рост не позволит набрать 28 чисел после 19. Более тщательный анализ показывает, что максимальная длина такой цепочки не превышает 27 чисел, включая 19 и 20, так что общее количество чисел в круге не более 29.
  Следовательно, расстановка из 30 чисел невозможна.

Итак, наибольшее количество чисел равно 29.