Решение 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  рубль.

Ответ задачи отсутствует