Сдача в маршрутке

[Sirion]

Действие данной задачи происходит в мире, где для всякого натурального $p$ имеет хождение монета достоинством $p$ рублей.

Итак, маршрутка. Стоимость проезда - $k$ рублей. В маршрутке едет $n$ пассажиров. У первого пассажира при себе есть только монеты достоинством один рубль, у второго - только достоинством два рубля... у $i$-того - только достоинством $i$ рублей. Каждый пассажир взял с собой минимальное количество монет, которым можно оплатить проезд. Эти монеты они передают водителю. До того, как пассажиры начинают оплачивать проезд, у водителя денег нет.

Верно ли, что для любых $k, n$ водитель сможет дать сдачу каждому пассажиру, причём не более чем одной монетой?

[TOTAL]

Sirion в сообщении #868769 писал(а):

Верно ли, что для любых $k, n$ водитель сможет дать сдачу каждому пассажиру, причём ровно одной монетой?

Не верно. У них у всех "без сдачи"

[Sirion]

Спасибо, исправил "ровно одной" на "не более чем одной". Будем считать, что если пассажир заплатил точную сумму, то водитель даёт ему сдачу нулём монет

[TOTAL]

Свою $S$-ю монету предлагаю тем, кто пришел с $S$ монетами. Много желающих?

[Sirion]

Простите, не понял вопроса.

[TOTAL]

Sirion в сообщении #869056 писал(а):

Простите, не понял вопроса.

Это не вопрос, это полное решение.

[Sirion]

Хорошо. Значит, я не понял решение. Можете формализовать?

[TOTAL]

Sirion в сообщении #869078 писал(а):

Хорошо. Значит, я не понял решение. Можете формализовать?

Подсказка
1) люди с одинаковым числом монет нуждаются в разных сдачах
2) человек нуждается в сдаче монетой меньшего достоинства, чем у него, т.е. от человека, имеющего большее (или такое же) число монет

[Sirion]

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

2) человек нуждается в сдаче монетой меньшего достоинства, чем у него, т.е. от человека, имеющего большее число монет

Большее либо равное, если быть точным.

[Skeptic]

Пассажиру $i$ нужна сдача $i-k$. Такую монету сдал один из $(i-1)$ пассажиров.

[Shadow]

Skeptic в сообщении #869225 писал(а):

Пассажиру $i$ нужна сдача $i-k$.

Только если $i>k$

Сдачу $t$ рублей нужно дать тем и только тем пассажирам, которые дали $k+t$ рублей. Такую сумму дали пассажиры с номерами - делители числа $k+t$. Причем не все делители, а те, которые больше $t$. Или, надо доказать, что количество делителей числа $k+t$, больше $t$, не превосходит $\left\lceil\frac k t\right\rceil$ - число монет достоинством $t$ в наличии у водителя.
Если число таких делителей $x$, то наименьший из них не больше $\frac{k+t}{x}$ (в лучшем случае делители будут $k+t,(k+t)/2,(k+t)/3\cdots (k+t)/x$)
$\dfrac{k+t}{x}>t\Rightarrow x<\dfrac k t +1\Rightarrow x\le \left\lceil\dfrac k t\right\rceil$ что и требовалось доказать.

Следовательно, монет для сдачи у водителя всегда хватит. В некоторых случаях хватит без остатка. Например, стоимость перевозки 51 руб. Водитель получает шесть монет достоинством 9 руб. И всех их отдает пассажирам с номерами $60,30,20,15,12,10$.

[Sirion]

Да, похоже, моё решение с индукцией было слишком сложным.