Головоломка Кармелита

"Прыткий" Кармелит (Кармелиты - члены ордена нищенствующих монахов. - Примеч. пер.) был веселым малым со сладкой речью и блестящими глазками. "Брат-сборщик был он - важная особа. Такою лестью вкрадчивою кто бы Из братьи столько в кружку мог добыть?.. С приятностью монах исповедал, Охотно прегрешенья отпускал. Епитимья его была легка, Коль не скупилась грешника рука". "Звался он Губертом". Однажды, достав четыре мешочка с деньгами, он сказал:


- Если кармелит-сборщик получит пятьсот серебряных пенни, то скажите, сколькими способами он может разложить их по этим четырем мешочкам?
Славный человек объяснил, что порядок не играет роли (так что размещение 50, 100, 150, 200 считается таким же, как и размещение 200, 50, 100, 150) и что один, два или даже три мешочка могут оставаться пустыми.

Ответ

Пятьсот серебряных пенни можно разместить по четырем мешкам при заданных условиях ровно 894 348 различными способами. Если бы монет было 1000, то число способов возросло бы до 7 049 112. Это трудная задача на разбиение чисел. У меня есть единая формула, позволяющая решить задачу при любом числе монет для случая четырех мешков, но ее крайне трудно получить, и лучший метод состоит в том, чтобы найти 12 отдельных формул для различных сравнений по модулю 12.