|
|
 |
Условие
На доске написаны числа 2, 3, 4, ..., 29, 30. За рубль можно отметить любое число. Если какое-то число уже отмечено, можно бесплатно отмечать его делители и числа, кратные ему. За какое наименьшее число рублей можно отметить все числа на доске?
Решение
Отметим числа 17, 19, 23 и 29, потратив четыре рубля. Затем отметим число 2, потратив ещё рубль. После этого мы сможем бесплатно отметить все чётные числа (так как они делятся на 2), а после этого все нечётные числа, не превосходящие 15, – для любого из них (допустим, для числа 𝑛) чётное число 2𝑛 у нас отмечено, и мы можем отметить 𝑛 как его делитель. Осталось отметить 21, 25 и 27, и это тоже делается бесплатно: 25 делится на отмеченное число 5, а 21 и 27 – на отмеченное число 3. При любом способе решения задачи простые числа 17, 19, 23 и 29, превышающие 15, придётся отмечать за деньги – они не являются делителями или кратными каких-либо чисел на доске. Значит, 4 рубля мы потратим только на них. Чтобы отметить хотя бы что-то ещё, придётся тратить пятый рубль. Значит, дешевле чем за пять рублей условия задачи не выполнить.
Комментарий. На самом деле, отметив "большие" простые числа, мы могли бы вместо двойки отметить любое из оставшихся чисел на доске. В самом деле, потом мы бесплатно отметим его наименьший простой делитель 𝑝. Если 𝑝 = 2, действуем по алгоритму, описанному выше. Если нет, отмечаем 2𝑝 (это можно сделать, так как 𝑝 < 15), потом отмечаем двойку, а дальше всё остальное уже известным способом.
Аналогичное решение применимо и для произвольно длинного набора 2, 3, 4, ..., 𝑁 – мы вынуждены отметить за деньги
все "большие" простые числа (превышающие 𝑁/2), а потом отмечаем за рубль любое из оставшихся чисел. Далее бесплатно
отмечаем двойку способом, описанным выше, затем отмечаем
все чётные числа, потом все "малые" простые числа (не превышающие 𝑁/2), потому что любое "малое" 𝑝 будет делителем
2𝑝. Теперь можно отметить все остальные неотмеченные числа:
каждое из них будет делиться на свой минимальный простой
делитель – "малое" простое число.
