Сколькими монетами выплачивать штраф?

[Ktina]

(Минздравкультуры предупреждает: использование вычислительной техники при решении задач, легко решающихся в уму, опасно для вашего интеллектуального развития)

В городе Свирзинске только одна денежная единица - свирзик, причём имеют хождение те и только те монеты, достоинство которых выражается квадратом простого числа.
Ярдена перешла одну из свирзинских улиц на красный свет и ей выписали штраф в 1000 свирзиков.
Каким наименьшим числом монет Ярдена может выплатить этот штраф?

[kotenok gav]

За одну монету, очевидно, не выйдет.
2 монеты: легко проверяется.
3 монеты: должно быть ровно одно $2^2$. Легко проверяется, что 996 двумя монетами не выплатить.
4 монеты: дожно быть ровно 2 или 0 $2^2$.
Первый случай:
Легко проверяется, что 992 двумя монетами не выплатишь.
Второй случай пока не решил.
5 монет: $1000=29^2+11^2+5^2+3^2+2^2$

[Ktina]

kotenok gav
Нет необходимости проверять каждый случай в отдельности, там по остаткам легко видно, что монет не меньше 5.
Квадрат любого нечётного числа дарамдаш остаток 1 при делении на 8. А квадрат чётного простого числа - 4 при делении на 8.
Таким образом, если все монеты нечётные, то их не менее 8, а если все чётные, то не менее 250. Значит, есть как чётные, так и нечётные монеты. Берём любую чётную и откладываем в сторонку. В оставшейся кучке должно быть как минимум 4 нечётных монеты. Отсюда общее число монет не менее 5. Пример для 5 монет построить легче, если заметить, что одна из монет обязана равняться 9, иначе в сумме выйдет остаток 2 при делении на 3. То есть, мы уже знаем, что из наших 5 монет одна равна 4, а другая - 9. Остальное - уже дело техники.

[Legioner93]

kotenok gav в сообщении #1308503 писал(а):

$1000=29^2+11^2+5^2+3^2+2^2$

Ещё $1000=23^2+17^2+13^2+3^2+2^2$