HMMT 二月 2000 · POW 赛 · 第 18 题

HMMT February 2000 — POW Round — Problem 18

Y ou ha v e an in nite n um b er of 1 en t, 2 en t, and 5 en t stamps. Y ou are trying to p ost a letter that requires n en ts of p ostage stamps, where n > 8. Let a ( n ) b e the n um b er 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 as few 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 to n 1 mak e n en ts ending in a 1 en t stamp, sin e this is the n um b er 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, and n 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 ts n 5 ends in one of these stamps, and there is no o v erlap, the total n um b er of w a ys to mak e n en ts is the sum of these, or a + a + a . n 1 n 2 n 5