ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 78253
Тема:    [ Обратный ход ]
Сложность: 4
Классы: 10,11
В корзину
Прислать комментарий

Условие

k человек ехали в автобусе без кондуктора, и у всех них были монеты только достоинством в 10, 15, 20 копеек. Известно, что каждый уплатил за проезд и получил сдачу. Доказать, что наименьшее число монет, которое они могли иметь, равно k + $ \left[\vphantom{\frac{k+3}{4}}\right.$$ {\frac{k+3}{4}}$$ \left.\vphantom{\frac{k+3}{4}}\right]$, где значок [a] означает наибольшее целое число, не превосходящее a. Примечание. Проезд в автобусе стоит 5 копеек.

Решение

Для каждой использованной монеты нарисуем стрелку от того человека, у которого она была до выплат, к тому человеку, у которого она оказалась после выплаты (некоторые стрелки будут вести к автомату по оплате). Количество получившихся стрелок равно количеству использованных монет, а значит, достаточно доказать, что проведено не менее  k + $ \left[\vphantom{\dfrac{k+3}{4} }\right.$$ {\dfrac{k+3}{4}}$$ \left.\vphantom{\dfrac{k+3}{4} }\right]$ стрелок. Поскольку никто не мог заплатить за проезд без сдачи, к каждому человеку ведёт хотя бы одна стрелка (уже k стрелок). Так как одной монетой можно оплатить проезд не более четырёх человек, к автомату ведёт не менее  $ {\dfrac{k}{4}}$ стрелок. Но наименьшее целое число, не меньшее  $ {\dfrac{k}{4}}$, и есть  $ \left[\vphantom{\dfrac{k+3}{4} }\right.$$ {\dfrac{k+3}{4}}$$ \left.\vphantom{\dfrac{k+3}{4} }\right]$, а значит, всего проведено не менее  k + $ \left[\vphantom{\dfrac{k+3}{4} }\right.$$ {\dfrac{k+3}{4}}$$ \left.\vphantom{\dfrac{k+3}{4} }\right]$ стрелок. Замечание. На самом деле, при всех k > 1 эта оценка точная, т. е. указанного в условии количества монет достаточно. Докажем это индукцией по числу k. Сначала проверим базу индукции при  k = 2, 3, 4, 5. При k = 2 первый пассажир платит 10 копеек в кассу и 10 копеек второму пассажиру, а второй платит 15 копеек первому. При k = 3 первые двое расплачиваются как в предыдущем примере, но 10 копеек отдают не в кассу а третьему, который кладёт в кассу 15 копеек. При k = 4 первые трое расплачиваются как в предыдущем примере, но 15 копеек отдают четвёртому, который кладёт в кассу 20 копеек. При k = 5 первые двое и остальные трое расплачиваются по отдельности, как это описано в предыдущих примерах. Пусть теперь k$ \ge$6 и при всех меньших k утверждение доказано. Выделим четырёх пассажиров. Пусть все остальные расплачиваются как в соответствующем примере для k - 4, а выделенные четверо — как в примере для четырёх. Проверка того, что истраченное количество монет будет равно  k + $ \left[\vphantom{\dfrac{k+3}{4} }\right.$$ {\dfrac{k+3}{4}}$$ \left.\vphantom{\dfrac{k+3}{4} }\right]$, оставляется читателю в качестве упражнения.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 24
Год 1961
вариант
1
Класс 10
Тур 1
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .