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

Как я понимаю, тут нужно использовать формулы сочетаний из комбинаторики, но я не понимаю как :\

задан 11 Янв '15 13:57

(11 Янв '15 14:27) EdwardTurJ
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Повтор вопроса". Закрывший - EdwardTurJ 11 Янв '15 14:27

1

Нужно подсчитать число решений уравнения $%x+2y+5z=110000$% в целых неотрицательных числах. Здесь $%x$% -- число рублёвых монет, $%y$% -- число двухрублёвых, $%z$% -- пятирублевых.

Придавая $%z$% различные значения от $%0$% до $%22000$%, будем получать уравнения вида $%x+2y=5(22000-z)$%. Для фиксированного $%N$% уравнение $%x+2y=N$% имеет $%[N/2]+1$% решение, где квадратные скобки означают целую часть. Действительно, $%y$% может принимать любое значение от $%0$% до $%[N/2]$% включительно, и $%x$% далее однозначно выражается из равенства $%x=N-2y$%.

Число $%N=5(22000-z)$% в правой части уравнения принимает значения $%0$%, $%5$%, $%10$%, $%15$%, ... , $%110000$%. Значения $%[N/2]+1$% при этом получаются равными $%1$%, $%3$%, $%6$%, $%8$%, ... , $%55001$%. Все эти числа надо сложить между собой. Закономерность тут достаточно простая: после первой 1 происходит увеличение то на 2, то на 3 -- с чередованием. Если сложить числа попарно, не считая самого последнего, то получится арифметическая прогрессия $%4+14+24+\cdots+109994$%, в которой ровно 11000 членов. Применяя формулу для суммы членов прогрессии, имеем $%(4+109994)\cdot11000/2$%, к которой надо прибавить самое последнее слагаемое $%55001$%. Получится $%605044001$%, и это конечный ответ.

ссылка

отвечен 11 Янв '15 14:43

10|600 символов нужно символов осталось
Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×869

задан
11 Янв '15 13:57

показан
2149 раз

обновлен
11 Янв '15 14:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru