Старинная загадка олимпиадного типа

[Xenia1996]

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

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

[TOTAL]

Xenia1996 в сообщении #441574 писал(а):

В одной далёкой стране в обращении были только монеты в 1, 2, 3, 4 и 5 шмыльзиков.
Ответ обосновать.

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

[Xenia1996]

Опять я дурой вышла, у меня ооочень длинное решение.

Прежде всего, цена башмаков должна делиться на 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 однокопеечных.

[TOTAL]

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

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

[Xenia1996]

TOTAL в сообщении #442164 писал(а):

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

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

Согласна.

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

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

[TOTAL]

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

[Xenia1996]

(Оффтоп)

Супер!