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

Сначала разменяем 10 монет, разложим по 5, 2 и 1ой монетам:5,55,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 рублей.