Раскраска с ограничением

[Ktina]

В какое наименьшее число цветов (в зависимости от $n$) нужно раскрасить все натуральные числа от 1 до $n$ (включительно), если два различных числа, одно из которых кратно другому, должны быть покрашены в разные цвета?

[cool.phenon]

Предполагаю, что это - количество простых чисел,которые не превышают $n$.

[TOTAL]

$[\log_2n]+1$ или около того

[hippie]

Точно!

Покрасим в один цвет числа, которые имеют одинаковое число простых делителей (с учётом кратности, т.е. $4=2\cdot 2$ имеет 2 простых делителя, а $8=2\cdot 2\cdot 2,\ 12=2\cdot 2\cdot 3$ и $50=2\cdot 5\cdot 5$ по 3 простых делителя).

[Ktina]

hippie в сообщении #677718 писал(а):

Точно!

Покрасим в один цвет числа, которые имеют одинаковое число простых делителей (с учётом кратности, т.е. $4=2\cdot 2$ имеет 2 простых делителя, а $8=2\cdot 2\cdot 2,\ 12=2\cdot 2\cdot 3$ и $50=2\cdot 5\cdot 5$ по 3 простых делителя).

Зачем так усложнять?

Необходимость:
Рассмотрим все степени двойки в искомом диапазоне. Их как раз столько, сколько указали Вы и TOTAL. Все они должны быть разного цвета.

Достаточность:

Покрасим 1 в первый цвет, 2 и 3 -- во второй, с 4 по 7 -- в третий и т. д.
Если одно число кратно другому, то оно как минимум вдвое больше. Значит, уже другого цвета.

Разве не так?

[TOTAL]

hippie в сообщении #677718 писал(а):

Покрасим в один цвет числа, которые имеют одинаковое число простых делителей

Я решал так же.

-- Вт янв 29, 2013 21:56:19 --

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

Зачем так усложнять?
Разве не так?

Ага, всякому свое и не мыто бело.

[Ktina]

TOTAL в сообщении #677731 писал(а):

hippie в сообщении #677718 писал(а):

Покрасим в один цвет числа, которые имеют одинаковое число простых делителей

Я решал так же.

Ваше и hippie решение сложнее тем, что нужно доказывать, что среди чисел от 1 до $n$ наибольшее количество простых делителей будет у наибольшей степени двойки, не превосходящей $n$. Мелочь, но на неё тратятся минуты, которые на олимпиаде могут определять разницу между победой и неудачей.

[TOTAL]

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

Мелочь, но на неё тратятся минуты, которые на олимпиаде могут определять разницу между победой и неудачей.

В поисках решения, которое короче на минуту, чем то, что первым пришло в голову, можно провести все оставшееся до конца олимпиады время.