Натуральные числа - в пищу! (задача о числоядных подружках)

[Ktina]

Ксюша, Кацечка Катенька и несколько их числоядных подружек скушали все натуральные числа от 2 до 2012 включительно. Известно, что если девочка А съела число Б, то она съела и все его делители (кроме единички).
Какое наибольшее число девочек могло быть в этой стукнутой компании?

*каждое число может быть съедено не более, чем одной девочкой и не более одного раза

[gris]

Взял на себя благородный труд: посчитал количество простяшек от 1009 до 2011. Их 137. То есть уж по крайней мере 137 девочек скушали по одному числу без всяких там возможных пересечений.
Подозреваю, что решение вообще связано со всеми простыми от 2 до 2011. То есть 305 девиц. Уж в эту компанию нельзя ни одной девочки добавить.. Ведь они все числа съели

Максимальна ли она?
Подскажите же, Ktina!

[Mathusic]

Если девочки решили скушать числа на отрезке $[2, n]$, то ответ будет $\displaystyle g(n)=\pi(n)-\pi(\frac{n}{2})+1.$
То есть в случае $2012$ будет $g(2012)=138$, немножечко меньше чем у gris

[gris]

У меня девочек в два раза больше
137 это те, которые при любом раскладе будут присутствовать.
Мой вариант — все простые от и до. Девочки кушают по одному простому числу.
Забыл, что они съели всё.

[Mathusic]

gris в сообщении #597139 писал(а):

У меня девочек в два раза больше

(Оффтоп)

Неудачная шутка

gris в сообщении #597139 писал(а):

137 это те, которые при любом раскладе будут присутствовать.

Но ведь может быть, например, и всего две девочки: одна съедает всё, кроме $2011$, другая - его.

[gris]

Так надо же максимизировать число девочек.
Я имел в виду, что при любом раскладе 137 можно безболезненно отделить.

[Профессор Снэйп]

Ну, я согласен с gris. На каждое простое число от $n/2$ до $n$ можно выделить по отдельной девочке. Но это, конечно же, лишь оценка снизу.

А точный ответ получается так. Если посмотреть на числа от $2$ до $n$, упорядоченные по делимости, то там будет конечное частично упорядоченное множество. Надо этот ЧУМ аккуратненько нарисовать, потом выделить максимальные элементы, ввести на них отношение $a \mathbin{R} b \Leftrightarrow \exists c(c \leqslant a \mathop{\&} c \leqslant b)$, рассмотреть содержащую это отношение минимальную эквивалентность и посчитать число классов этой эквивалентности. Оно и будет точным ответом.

Число $n = 2012$ дюже большое, так что ручками эту процедуру проделать нереально. Но прогу наваять легко, и она всё сделает в мгновение ока. Все шаги описанного алгоритма полиномиальны

-- Пт июл 20, 2012 12:16:15 --

Mathusic в сообщении #597136 писал(а):

Если девочки решили скушать числа на отрезке $[2, n]$, то ответ будет $\displaystyle g(n)=\pi(n)-\pi(\frac{n}{2})+1.$
То есть в случае $2012$ будет $g(2012)=138$, немножечко меньше чем у gris

А как он у Вас получился, такое ответ?

-- Пт июл 20, 2012 12:19:11 --

Хотя в принципе, понятно. Девочка, которая съела $2$, скушает также все чётные числа, в частности $6$, в частности все числа, кратные трём и т. д... Получается, при произвольном $n$ ответ будет на единичку больше, чем количество простых от $n/2$ до $n$.

[gris]

Я, конечно, ошибся с числом 305. Ведь девочки съели все числа.
Но если не требовать съедения всех чисел, то ответ будет $\pi (n)$. Но это, конечно, сильное упрощение.
Задача неполиткорректна. Почему только девочки? Да и надо ли акцентировать? Предлагаю заменить на амёб или просто разбивать на подмножества. А то сбивает с толку. Начинаешь всё это представлять, и такой кавардак в голове начинается

[Профессор Снэйп]

gris в сообщении #597152 писал(а):

А нельзя ли так показать, что максимальное число девочек это количество всех простых чисел от 1 до $n$

Нельзя так. Девочка, которая скушает $6$, обязана кушать $2$ и $3$. Так что всё же от $n/2$ до $n$. Ну и ещё одна девочка, которая скушает остальное

[TOTAL]

(Оффтоп)

gris в сообщении #597152 писал(а):

Почему только девочки? Да и надо ли акцентировать? Предлагаю заменить на амёб

Сползлись девочки-амёбы, чтобы полакомиться целыми числами. Неужели так лучше?