Задача
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]$, оставляется читателю в качестве упражнения.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь