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 out n of quarters, dimes, nickels, and pennies. Also, let there be B ways for Beautiful Bill to make exactly n n dollars out of one dollar bills, quarters, dimes, and nickels. As n goes to infinity, the sequence of P n fractions approaches a real number c . Find c . B n Note: Assume both Pretty Penny and Beautiful Bill each have an unlimited number of each type of coin. 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 out n of quarters, dimes, nickels, and pennies. Also, let there be B ways for Beautiful Bill to make exactly n n dollars out of one dollar bills, quarters, dimes, and nickels. As n goes to infinity, the sequence of P n fractions approaches a real number c . Find c . B n Note: Assume both Pretty Penny and Beautiful Bill each have an unlimited number of each type of coin. 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 that x when x is a multiple of 5, j k x d = + 1 . x 10 Now, let c be the number of ways to make exactly x cents using only quarters, dimes and nickels. x Again, it is easy to see that when x is a multiple of 5, c = 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 approximated x x by a polynomial of degree 2. (In fact, we get five di ↵ erent approximations of c , depending on the x value of x (mod 25), but they all only di ↵ er by a constant, which will not a ↵ ect the limit case.) We also see that B = c + c + . . . + c n 100 n 0 100( n 1) and P = c + c + . . . + c . n 100 n 100 n 5 0 c n Suppose a is the value such that lim = 1 . Then n !1 2 an P b n/ 100 c n n n 2 400 · ( + 1)(2 · + 1) B a (100 k ) n k =0 100 100 100 lim = lim = lim = 20 . P n n n b n/ 5 c n !1 n !1 n !1 2 P ( + 1)(2 · + 1) n a (5 k ) 5 5 5 k =0