Информация о задаче

Задача 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