Скольким способами можно разменять 90 000 рублей монетами в 1, 2 и 5 рублей?

Сначала разменяем 10 монет, разложим по 5, 2 и 1 ой монетам:

5,5

5,5,2,2,1

И так далее, каждый раз заменяя пятёрки двойками, а двойки единицами. В итоге запишем:

5 * 2 - 1 способ

5 * 1; 2 * n, n = 0, 1,2 (при n = 0 заменяем 1 рублём) - 3 способа

5 * 0; 2 * n, n = 0, 1,2, ... 5 - 6 способов

Получим 10 способов.

Аналогично, разложим 20 монет:

5 * 4 - 1 способ

5 * 3; 2 * n, n = 0, 1,2 - 3 способа

5 * 2; 2 * n, n = 0, 1,2, ... 5 - 6 способов

5 * 1; 2 * n, n = 0, 1,2, ... 7 - 8 способов

5 * 0; 2 * n, n = 0, 1,2, ... 10 - 11 способов

Получим 1 + (3+6) + (8+11) = 1 + 9 + 19 = 29 способов.

Теперь разложим 90 000 монет:

5 * 18000 - 1 способ

5 * 17999; 2 * n, n = 0, 1,2 - 3 способа

5 * 17998; 2 * n, n = 0, 1,2, ... 5 - 6 способов

Продолжим

5 * 1; 2 * n, n = 0, 1,2, ... 44997 - 44998 способов

5 * 0; 2 * n, n = 0, 1,2, ... 45000 - 45001 способов

Получим ряд 1 + (3+6) + ... + (44998 + 45001)

Ряд а = 9 + 19 + 29 + ... + 89999 - арифметический ряд

а = 10000 (9 + 89999) / 2 = 450040000

Итак, а + 1 = 450040001 можно разменять 90000 рублей.