Задача 5. Подмножество без утроенных чисел

Цепочки чисел

Сначала поймём, какие числа вообще могут мешать друг другу. Любое натуральное число однозначно записывается как $3^k \cdot m$, где $m$ не делится на $3$: делим число на $3$, пока делится. Например, $45 = 3^2 \cdot 5$, $14 = 3^0 \cdot 14$.

Если одно число ровно в $3$ раза больше другого, то у них одно и то же $m$, а показатели $k$ отличаются на $1$. Поэтому числа от $1$ до $1500$ распадаются на цепочки — в каждой следующее число втрое больше предыдущего, пока числа не больше $1500$:

по одной на каждое $m$, не делящееся на $3$. Запрещены только пары соседей одной цепочки, а числа из разных цепочек друг другу не мешают. Например, цепочка $m = 1$: $1, 3, 9, 27, 81, 243, 729$ (семь чисел); $m = 5$: $5, 15, 45, 135, 405, 1215$ (шесть); $m = 1000$: только $1000$.

Значит, задача распадается на отдельные цепочки: в каждой надо выбрать как можно больше чисел без двух соседей подряд.

Оценка сверху для одной цепочки

Пусть в цепочке $L$ чисел. Разобьём её на пары соседей: (1-е, 2-е), (3-е, 4-е), … При нечётном $L$ последнее число останется без пары. Числа одной пары отличаются ровно в $3$ раза, поэтому из каждой пары в $S$ попадает не больше одного числа. Отсюда из цепочки можно взять не больше

то есть половину длины, округлённую вверх. Складывая по всем цепочкам, получаем: в $S$ не больше суммы этих половин.

Пример: берём 1-е, 3-е, 5-е числа

Оценка достигается: в каждой цепочке возьмём 1-е, 3-е, 5-е, … числа. Между двумя взятыми всегда стоит невзятое, поэтому конфликтов нет, а взято ровно столько, сколько в оценке. Нечётные места цепочки — это числа $3^k \cdot m$ с чётным $k$: $k = 0, 2, 4, 6, \ldots$ Посчитаем их по слоям (запись $\left[\dfrac{N}{d}\right]$ — сколько чисел от $1$ до $N$ делятся на $d$):

• $k = 0$, не делятся на $3$: $1500 - \left[\dfrac{1500}{3}\right] = 1500 - 500 = 1000$;
• $k = 2$, делятся на $9$, но не на $27$: $\left[\dfrac{1500}{9}\right] - \left[\dfrac{1500}{27}\right] = 166 - 55 = 111$;
• $k = 4$, делятся на $81$, но не на $243$: $\left[\dfrac{1500}{81}\right] - \left[\dfrac{1500}{243}\right] = 18 - 6 = 12$;
• $k = 6$, делятся на $729$, но не на $2187$: $2 - 0 = 2$ (это $729$ и $1458$);
• $k = 8$: $3^8 = 6561 > 1500$ — таких чисел нет.

Ответ

Оценка сверху (шаг 2) и пример (шаг 3) дают одно и то же число, поэтому наибольшее количество элементов $S$ равно $1125$. Для любого $N$ ответ записывается так же: