Как много чисел можно выбрать?

[Ktina]

Какое наибольшее количество чисел можно выбрать из натуральных чисел от 1 до 1000000 так, чтобы среди выбранных не было трёх (попарно -- прим. ред.) различных чисел $a, b, c$, для которых $a$ делится на $b$, а $b$ делится на $c$?
(ВДЦ “Орлёнок”)

[Ontt]

750000? Ушел думать, почему.

[Ktina]

Ontt в сообщении #682902 писал(а):

750000? Ушел думать, почему.

Ваш ответ верен.
Существует красивое решение.

[Aritaborian]

Раз уж верный ответ дан, Ktina, не тяните, выкладывайте решение ;-) И желательно для произвольного количества чисел, а не только миллиона.

[Ontt]

(Оффтоп)

Aritaborian в сообщении #682931 писал(а):

не тяните, выкладывайте решение

Подождите чуть-чуть, если можно, я уже близок (как мне кажется) к разгадке.

-- 12.02.2013, 16:46 --

Ktina в сообщении #682909 писал(а):

Существует красивое решение.

Мои рассуждения были такими.
Возьмем три натуральных числа $a_n, b_n$ и $c_n$, которые удовлетворяют следующим условиям (соответствующим условиям задачи): $a_n\ne b_n, b_n\ne c_n, a_n\ne c_n$, при этом $a_n$ делится на $b_n$, а $b_n$ делится на $c_n$.
Таким образом:
$a_n/b_n=x$,
$b_n/c_n=y$,
где $x, y \in \mathbb{N}$, и (так как $a_n\ne b_n, b_n\ne c_n$) $x, y > 1$. Очевидно, что $a_n>b_n>c_n$.
Из $a_n=b_n x$ и $b_n=c_n y$ следует, что $a_n=c_n x y$.
Поскольку у нас $x, y \in \mathbb{N}$ и $x, y > 1$ (то есть минимальные значения, которые могут принимать $x$ и $y$ - это $2$, или другими словами $x, y \geqslant 2$), можно утверждать, что для любого $c_n>\frac 1 4 N$, где $N \in \mathbb{N}$ - некое пороговое значение, выполняется неравенство $a_n>N$.
Кроме того, для любого $c_n\leqslant\frac 1 4 N$ существует как минимум одно натуральное $a_n\leqslant N$ (например, $a_n=c_n \cdot 2 \cdot 2$).

Применительно к условиям задачи можно сделать вывод, что для любого $c$, превышающего 250000, между 1 и 1000000 включительно не существует ни одного $a$, которое бы делилось на $b$, а $b$ делилось на $c$. А для любого $c$, не превышающего 250000, между 1 и 1000000 включительно существует как минимум одно $a$, которое бы делилось на $b$, а $b$ делилось на $c$.
Соответственно, из всех чисел от 1 до 1000000 мы должны исключить все $c$, для которых существует соответствующее $a$. То есть условию задачи будет соответствовать выборка всех чисел от 250001 до 1000000, и ответ: 750000.

В моих рассуждениях есть, как мне кажется, пробел. Например, для любого $N$, кратного 4, можно исключить $a=N$ и оставить $c=\frac 1 4 N$, хотя при этом ответ не изменится.

[Ktina]

Aritaborian в сообщении #682931 писал(а):

Раз уж верный ответ дан, Ktina, не тяните, выкладывайте решение И желательно для произвольного количества чисел, а не только миллиона.

Разобьём все числа на цепочки:
1, 2, 4, ... ,
3, 6, 12, ...
5, 10, 20, ...
7, 14, 28, ...
....................
В каждой цепочке, начинающейся с числа, меньшего 500000, можно выбрать не более двух чисел, а в каждой из остальных -- не более одного, отсюда и ответ.

[Руст]

Ktina в сообщении #682954 писал(а):

1, 2, 4, ... ,
3, 6, 12, ...
5, 10, 20, ...
7, 14, 28, ...
....................
В каждой цепочке, начинающейся с числа, меньшего 500000, можно выбрать не более двух чисел, а в каждой из остальных -- не более одного, отсюда и ответ.

Это не решение. Возьмем тройки $1,2,4$, $8,16,32$, $64,128,256$. Если взять с каждой тройки хотя бы по одному числу, уже образуется такая тройка.
Поэтому, в рассуждении должны были участвовать не тройки, а все числа начинающиеся с нечетного числа и множители со всеми степенями двойки. И это не поможет, так как не исключаются другие множители не являющиеся степенями двойки.

[Ktina]

Руст в сообщении #683019 писал(а):

Это не решение. Возьмем тройки $1,2,4$, $8,16,32$, $64,128,256$. Если взять с каждой тройки хотя бы по одному числу, уже образуется такая тройка.
Поэтому, в рассуждении должны были участвовать не тройки, а все числа начинающиеся с нечетного числа и множители со всеми степенями двойки. И это не поможет, так как не исключаются другие множители не являющиеся степенями двойки.

Я плохо сформулировала.
Не тройки, а цепочки.
Начиная с каждого нечётного $n$.
Вот так: $n, 2n, 4n, 8n, \dots$ пока не превзойдёт 1000000.
Это да поможет, потому что мы ищем оценку сверху.
А пример для 750000 очевиден -- все числа, большие 250000.

[Руст]

Я имел ввиду, что это не поможет найти решение, большее чем было указано 750000.
Я согласен, что это рассуждение доказывает, что нельзя больше. Только надо немного уточнить.
Берутся цепочки чисел, начинающиеся с нечетного меньше 250000 (всего 125000)
и с нечетного больше 250000 меньшего 500000 и с нечетного больше 500000.
Из первых можно взять не больше двух (всего 250000), с пар можно взять каждую - это 250000 тысяч
и с одиночек по одному - 250000. И так оценка сверху 750000. Решение дано раньше (все числа больше 250000).

[Ktina]

Руст, спасибо! Вам удалось сформулировать чётче, чем мне.