|
|
 |
Условие
У продавца и покупателя в сумме 1999 рублей монетами и купюрами в 1, 5, 10, 50, 100, 500 и 1000 рублей. Кот в мешке стоит целое число рублей, причём денег у покупателя достаточно. Докажите, что покупатель сможет купить кота, получив причитающуюся сдачу.
Решение 1
Пусть покупатель отдаст продавцу все свои деньги. Тогда у продавца станет 1999 рублей. Покажем, что он сможет выплатить любую сдачу меньше 1999 рублей. Поскольку сумма кончается на 9, должно найтись 9 рублей (либо 9 рублёвок, либо пятерка и 4 рублевки – в каждом случае ими можно набрать любую сумму от 1 до 9 рублей). Отложим эти 9 рублей в кучку "единиц". Сумма оставшихся рублёвок и пятерок кратна 10, поэтому их можно связать в "десятки" – пачки по 10 рублей. Теперь сумма за вычетом отложенных денег равна 1990 и набрана купюрами и пачками с нулем в конце. Аналогично предыдущему найдём и отложим в сторону 9 "десяток" или полсотни и 4 "десятки" в кучку "десятков", затем 9 "сотен" или 500-рублёвку и 4 "сотни" – в кучку "сотен". Останется одна тысяча рублей – кучка "тысяч". Посмотрим на цифры сдачи и наберём из соответствующих кучек нужное число единиц, десятков, сотен и тысяч.
Решение 2
Заметим, что каждая из стоимостей купюр (монет) делится на все меньшие, а 1999 при делении на 5, 10 50, 100, 500 и 1000 дает максимально возможные остатки: 4, 9, 49, 99, 499 и 999 соответственно.
Достаточно доказать, что покупатель у которого ещё есть деньги, может передать продавцу 1 рубль (так постепенно он выплатит всю стоимость кота). Пусть в некоторый момент наименьшая купюра у покупателя – n рублей. Если n = 1, то покупатель отдаёт этот рубль продавцу. В противном случае сумма 1999 – n денег продавца при делении на n даёт остаток n – 1. Это значит, что продавец может выдать сдачу в n – 1 рубль.
Замечания
5 баллов
