HMMT 十一月 2018 · 冲刺赛 · 第 30 题
HMMT November 2018 — Guts Round — Problem 30
题目详情
英文原题
- [ 15 ] Let n be a positive integer. Let there be P ways for Pretty Penny to make exactly n dollars outnof quarters, dimes, nickels, and pennies. Also, let there be B ways for Beautiful Bill to make exactlynn dollars out of one dollar bills, quarters, dimes, and nickels. As n goes to infinity, the sequence offractions approaches a real number c . Find c .n p
Note: Assume both Pretty Penny and Beautiful Bill each have an unlimited number of each type ofn bcoin. Pennies, nickels, dimes, quarters, and dollar bills are worth 1, 5, 10, 25, 100 cents respectively.
HMMT November 2018, November 10, 2018 — GUTS ROUND
Organization Team Team ID#
解析
英文解析
- [ 15 ] Let n be a positive integer. Let there be P ways for Pretty Penny to make exactly n dollars outnof quarters, dimes, nickels, and pennies. Also, let there be B ways for Beautiful Bill to make exactlynn dollars out of one dollar bills, quarters, dimes, and nickels. As n goes to infinity, the sequence offractions approaches a real number c . Find c .n p
Note: Assume both Pretty Penny and Beautiful Bill each have an unlimited number of each type ofn bcoin. Pennies, nickels, dimes, quarters, and dollar bills are worth 1, 5, 10, 25, 100 cents respectively.
Proposed by: James Lin
Answer: 20
Let d be the number ways to make exactly x cents using only dimes and nickels. It is easy to see thatxwhen x is a multiple of 5,
j kxd = + 1 .
10 x
Now, let c be the number of ways to make exactly x cents using only quarters, dimes and nickels.
Again, it is easy to see that when x is a multiple of 5,xc = c + d .
x x 25 x
(We can either use 1 or more quarters, which corresponds to the c term, or we can use 0 quarters,
x 25
which corresponds to the d term.) Combining these two equations, we see that c can be approximatedx xby a polynomial of degree 2. (In fact, we get five di ↵ erent approximations of c , depending on thexvalue of x (mod 25), but they all only di ↵ er by a constant, which will not a ↵ ect the limit case.) Wealso see that
B = c + c + . . . + cn 100 n 0
100( n 1)
P = c + c + . . . + c .andn 100 n 100 n 5 0
Suppose a is the value such that lim = 1 . Thenncn !1 2
b n/ 100 c pann n n
400 · ( + 1)(2 · + 1)2
B a (100 k )
k =0 100 100 100 nlim = lim = lim = 20 .
n n n pb n/ 5 cn !1 n !1 n !1
P ( + 1)(2 · + 1)2
a (5 k )n
5 5 5
k =0