Здравствуйте! Помогите, пожалуйста.
Сколькими способами можно наклеить марки на 50 коп., используя марки достоинством в 3, 5, 10, 20 копеек, расположенные в одну линию (расположения, отличающиеся порядком марок, рассматриваются как различные, число марок не ограничено).

задан 23 Май '14 0:49

изменен 23 Май '14 19:55

Deleted's gravatar image


126

@Александр_777, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(23 Май '14 19:56) Deleted
10|600 символов нужно символов осталось
2

Один из способов подсчёта может быть таков. Обозначим через $%a_n$% количество способов наклеить марки общей стоимостью $%n$% копеек. Нам требуется найти $%a_{50}$%. Очевидно, что $%a_0=1$% (если стоимость равна нулю, то имеется всего один способ наклеить марки, оставив чистый лист). Также удобно считать, что члены с отрицательными индексами равны нулю. Тогда имеет место следующая рекуррентная формула: $%a_n=a_{n-3}+a_{n-5}+a_{n-10}+a_{n-20}$%, справедливая для всех $%n\ge1$%. В соответствии с этой формулой находим последовательно все нужные значения. Они таковы: 0, 0, 1, 0, 1, 1, 0, 2, 1, 2, 3, 1, 5, 4, 4, 9, 5, 11, 14, 12, 23, 20, 29, 41, 37, 62, 66, 79, 118, 117, 167, 205, 230, 330, 363, 468, 606, 683, 930, 1098, 1341, 1761, 2040, 2642, 3259, 3911, 5075, 6061, 7601, 9549. Последнее значение будет ответом.

Общее описание здесь таково: если мы разложим в степенной ряд рациональную функцию $$f(t)=\frac1{1-t^3-t^5-t^{10}-t^{20}},$$ то коэффициент при $%t^n$% будет равен $%z_n$%.

Возможны и другие принципы подсчёта, но они тоже требуют вычислений. Например, можно заметить, что число трёхкопеечных марок кратно пяти. Оно может принимать значения 0, 5, 10, 15. Каждый из этих случаев отдельно разбираем, а получаемые величины суммируем. Для примера: если количество марок по 3 коп. равно, скажем, 10, то далее надо набрать сумму 20 коп. через 5, 10 и 20. Это эквивалентно тому, что мы набираем 4 коп. через 1, 2 и 4 (после сокращения на 5 все величины сильно уменьшаются). Здесь все способы можно перечислить, а затем понять, сколькими способами мы можем вставить трёхкопеечные марки между остальными. Например, если 4 записано как 2+1+1, то сама расстановка этого типа может быть осуществлена 3 способами, так как порядок важен. Добавить же 10 марок к трём имеющимся можно $%C_{10+3}^3$% способами.

ссылка

отвечен 23 Май '14 5:22

Спасибо большое!

(23 Май '14 22:32) Александр_777
1

@falcao, а как будет выглядеть рекуррентная формула, если порядок не важен?

(8 Июн '16 1:03) Isaev
1

@Isaev: в такой версии получится число решений уравнения 3x+5y+10z+20t=50 в целых неотрицательных числах. Здесь ответ можно вычислить почти устно. Ясно, что x кратно 5; полагаем x=5a. Тогда уравнение имеет вид 3a+y+2z+4t=10. При этом t=0,1,2. Тогда надо просуммировать число решений уравнения y+2z+3a=N при N=2,6,10. Нетрудно доказать, что уравнение y+2z=M имеет ровно [M/2]+1 решений. Тогда перебор значений a даёт в итоге ответ 23.

(8 Июн '16 2:15) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

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

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

отмечен:

×3,926
×1,402

задан
23 Май '14 0:49

показан
1843 раза

обновлен
8 Июн '16 2:15

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

по почте:

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

по RSS:

Ответы

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

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