Головоломка. Числа на доске

Разбор

1. Отметим числа 17, 19, 23 и 29. Это уже 4 рубля.
2. Затем отметим число 2. Это уже 5 рублей.
3. Теперь мы сможем бесплатно отметить все чётные числа, так как они делятся на 2.
4. Далее - все нечётные числа меньше 16. Для любого из них чётное число у нас уже отмечено, и мы можем отметить его как делитель.
5. Осталось отметить 21, 25 и 27:
   25 делится на отмеченное число 5, а 21 и 27 — на отмеченное число 3.

Замечание: при любом варианте решения простые числа 17, 19, 23 и 29, превышающие 15, придётся отмечать за деньги, т.к. они не являются делителями или кратными каких-либо чисел на доске. То есть 4 рубля мы потратим только на них. Чтобы отметить еще что-то, придётся тратить пятый рубль. Получаем, что дешевле чем за пять рублей условия задачи не выполнить.