2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Старинная загадка олимпиадного типа
Сообщение04.05.2011, 12:19 


01/10/10

2116
Израиль (племянница БизиБивера)
В одной далёкой стране в обращении были только монеты в 1, 2, 3, 4 и 5 шмыльзиков.
Как-то раз к местному сапожнику пришёл маленький Кай и заказал башмаки.
На вопрос сапожника, сколько у Кая денег, Кай ответил, что в его кармане ровно 100 монет, но он не помнит, каких именно и все ли из них одинаковые. Сапожник улыбнулся и сказал: "в таком случае у тебя уж точно найдется ровно столько, сколько стоит пара башмаков".

Сколько стоит пара башмаков и как именно сапожник догадался, что у Кая найдётся точная сумма?
Ответ обосновать.

 Профиль  
                  
 
 Re: Старинная загадка олимпиадного типа
Сообщение04.05.2011, 12:52 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
Xenia1996 в сообщении #441574 писал(а):
В одной далёкой стране в обращении были только монеты в 1, 2, 3, 4 и 5 шмыльзиков.
Ответ обосновать.

Если 60 копеек невозможно набрать двушками, то двушек не более 29.
Если 60 копеек невозможно набрать трояками, то трояков не более 19.
...
Тогда имеем по крайней мере 27 монет в 1 копейку. (А достаточно было бы иметь 4 копеешных монеты.)

 Профиль  
                  
 
 Re: Старинная загадка олимпиадного типа
Сообщение04.05.2011, 13:42 


01/10/10

2116
Израиль (племянница БизиБивера)
Опять я дурой вышла, у меня ооочень длинное решение.

Прежде всего, цена башмаков должна делиться на 5. В противном случае, если у Кая только пятикопеечные монеты, точную сумму он уплатить не сможет. Аналогично, цена должна делиться на 4, 3, 2, 1. НОК этих чисел равен 60, значить цена кратна 60. 120 и выше она быть не может (а вдруг у Кая 100 однокопеечных монет?).
Значит, ровно 60.

Теперь покажем, что 60 можно набрать всегда.
Если есть 12 пятёрок, задача решена, так что предположим, что пятёрок не более 11. Если двушек более 11 и трёшек тоже более 11, можно сгруппировать 12 двушек и 12 трёшек, и задача снова решена, так что либо двушек, либо трёшек - не более 11. А налогично, либо четвёрок, либо единичек также не более 11. Оставшиеся как минимум 100-3*11=100-33=67 монет - либо только 1 и 2, либо только 1 и 3, либо только 4 и 2, либо только 4 и 3. По Дирихле, какого-то из двух видов будет не менее 34. Если этот вид - не единичка, задача решена.
Предположим, что это 34 единички. Среди оставшихся 66 монет, по Дирихле, найдутся 14 одного вида. Если это не единички, задача решена, так что пусть будет ещё 14 единичек. Итак, у нас уже 48 единичек. Из 52 оставшихся монет как минимум 11 одного вида, а нам нужно добрать всего 12 копеек. Значит, опять рассматриваем наихудший случай - 11 единичек. Теперь у нас 59 единичек. Если больше единичек нет, то берём любую некопеечную монету, а из нашей кучки выбрасываем на одну копейку меньше, чем эта монета.
И теперь у нас ровно 60.

Теперь уже задним умом понимаю, что намного быстрее решить можно было бы :-(

-- Ср май 04, 2011 13:51:03 --

TOTAL в сообщении #441582 писал(а):
Xenia1996 в сообщении #441574 писал(а):
В одной далёкой стране в обращении были только монеты в 1, 2, 3, 4 и 5 шмыльзиков.
Ответ обосновать.

Если 60 копеек невозможно набрать двушками, то двушек не более 29.
Если 60 копеек невозможно набрать трояками, то трояков не более 19.
...
Тогда имеем по крайней мере 27 монет в 1 копейку. (А достаточно было бы иметь 4 копеешных монеты.)

Ваше решение я понимаю так:

Среди сумм 56, 57, 58, 59, 60 какую-то одну обязательно можно набрать, в противном случае будет "перескок" через более, чем 5 монет.
Следовательно, и вправду достаточно 4 однокопеечных.

 Профиль  
                  
 
 Re: Старинная загадка олимпиадного типа
Сообщение05.05.2011, 08:50 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
На вопрос сапожника, сколько у Кая денег, Кай ответил, что в его кармане ровно 60 монет

Каю и этого хватит.

 Профиль  
                  
 
 Re: Старинная загадка олимпиадного типа
Сообщение05.05.2011, 09:04 


01/10/10

2116
Израиль (племянница БизиБивера)
TOTAL в сообщении #442164 писал(а):
На вопрос сапожника, сколько у Кая денег, Кай ответил, что в его кармане ровно 60 монет

Каю и этого хватит.

Согласна.

Опять же, среди сумм 56, 57, 58, 59, 60 какую-то одну обязательно можно набрать, в противном случае будет "перескок" через более, чем 5 монет.

Предположим, что можно набрать 56, а 60 - нельзя. Тогда четвёрок быть не должно, двоек будет не более одной, а единичек - не более трёх. Но тогда из оставшихся 56 монет могут быть только пятаки и трёхи, а по Дирихле, каких-то из них будет не менее 28. Но 20 трёх или 12 пятаков дарамдаш 60.
Случаи с 57, 58, 59 рассматриваются аналогично.

 Профиль  
                  
 
 Re: Старинная загадка олимпиадного типа
Сообщение05.05.2011, 09:12 
Заслуженный участник
Аватара пользователя


23/08/07
4780
Нов-ск
Если 60 копеек невозможно набрать двушками и трояками, то двушек и трояков в сумме не более 30.
Если 60 копеек невозможно набрать четвериками, то четвериков не более 14.
Если 60 копеек невозможно набрать пятаками, то пятаков не более 11.
Тогда имеем по крайней мере 5 монет в 1 копейку. (А достаточно было бы иметь 4 копеешных монеты.)

 Профиль  
                  
 
 Re: Старинная загадка олимпиадного типа
Сообщение05.05.2011, 09:27 


01/10/10

2116
Израиль (племянница БизиБивера)

(Оффтоп)

Супер!

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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