2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Сколькими монетами выплачивать штраф?
Сообщение29.04.2018, 00:28 
Аватара пользователя


01/12/11

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

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

 Профиль  
                  
 
 Re: Сколькими монетами выплачивать штраф?
Сообщение29.04.2018, 07:55 


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

 Профиль  
                  
 
 Re: Сколькими монетами выплачивать штраф?
Сообщение29.04.2018, 09:17 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Сколькими монетами выплачивать штраф?
Сообщение29.04.2018, 11:42 
Заслуженный участник
Аватара пользователя


28/07/09
1178
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$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group