HMMT 二月 2000 · POW 赛 · 第 18 题
HMMT February 2000 — POW Round — Problem 18
题目详情
英文原题
- Y ou have an in nite number of 1 en t, 2 en t, and 5 en t stamps. Y ou are trying top ost a letter that requires n en ts of p ostage stamps, where n > 8. Let a ( n ) be the number of sequen es of stamps that giv e exa tly the required p ostage of n en ts (i.e.
order matters). Find a ( n ) in terms of previous terms of the sequen e of a 's, using asfew previous terms as p ossible.
解析
英文解析
- a = a + a + a . Ev ery w a y to mak e n en ts ends in either a 1 en t, 2 en ts,
n n 1 n 2 n 5
or 5 en ts (sin e order matters, there is a distin t last stamp). There are a w a ys ton 1
mak e n en ts ending in a 1 en t stamp, sin e this is the number of w a ys to mak e n 1
en ts. Similarly , there are a w a ys to mak e n en ts ending in a 2 en ts stamp, andn 2
a w a ys to mak e n en ts ending in a 5 en ts stamp. Sin e ev ery w a y to mak e n en tsn 5
ends in one of these stamps, and there is no o v erlap, the total number of w a ys to mak en en ts is the sum of these, or a + a + a .
n 1 n 2 n 5