HMMT 二月 2015 · 团队赛 · 第 6 题
HMMT February 2015 — Team Round — Problem 6
题目详情
- [ 30 ] 100 in pennies (worth 0 . 05 each), dimes (worth $0 . 10 each), and quarters (worth $0 . 25 each). Prove that she can split her coins into two piles, each with total value exactly $50.
解析
- [ 30 ] 100 in pennies (worth 0 . 05 each), dimes (worth $0 . 10 each), and quarters (worth $0 . 25 each). Prove that she can split her coins into two piles, each with total value exactly $50. Answer: N/A Solution 1. First, observe that if there are pennies in the mix, there must be a multiple of 5 pennies (since 5 , 10 , 25 ≡ 0 (mod 5)), so we can treat each group of 5 pennies as nickels and reduce the problem to the case of no pennies, treated below. Indeed, suppose there are no pennies and that we are solving the problem with only quarters, dimes, and nickels. So we have 25 q + 10 d + 5 n = 10000 (or equivalently, 5 q + 2 d + n = 2000), where q is the number of quarters, d is the number of dimes, and n is the number of nickels. Notice that if q ≥ 200, d ≥ 500, or n ≥ 1000, then we can just take a subset of 200 quarters, 500 dimes, or 1000 nickels, respectively, and make that our first pile and the remaining coins our second pile. Thus, we can assume that q ≤ 199, d ≤ 499, n ≤ 999. Now if there are only quarters and dimes, we have 5 q + 2 d < 1000 + 1000 = 2000, so there must be nickels in the mix. By similar reasoning, there must be dimes and quarters in the mix. So to make our first pile, we throw all the quarters in that pile. The total money in the pile is at most $49 . 75, so now, • if possible, we keep adding in dimes until we get an amount equal to or greater than 50, then we are done. Otherwise, it must be $50 . 05 since the total money value before the last dime is either 49 . 95. In that case, we take out the last dime and replace it with a nickel, giving us $50. • if not possible (i.e. we run out of dimes before reaching $50 ) , then all the quarters and dimes have been used up, so we only have nickels left. Of course, our money value now has a hundredth’s place of 5 or 0 and is less than $50, so we simply keep adding nickels until we are done. Solution 2. First, observe that if there are pennies in the mix, there must be a multiple of 5 pennies (since 5 , 10 , 25 ≡ 0 (mod 5)), so we can treat each group of 5 pennies as nickels and reduce the problem to the case of no pennies, treated below. Similarly, we can treat each group of 2 nickels as dimes, and reduce the problem to the case of at most one nickel. We have two cases: Case 1 . There are no nickels. Then, either the dimes alone total to at least indy can form a pile with $50 worth of dimes and a pile with the rest of the money, or the quarters alone total to at least indy can form a pile with $50 worth of quarters and a pile with the rest of the money. Case 2 . There is exactly one nickel. By examining the value of the money modulo $0 . 25, we find that there must be at least two dimes. Then, we treat the nickel and two dimes as a quarter, and reduce the problem to the previously solved case. Remark. There are probably many other solutions/algorithms for this specific problem. For example, many teams did casework based on the parities of q, d, n , after “getting rid of pennies”. Remark. It would certainly be interesting to investigate the natural generalizations of this problem (see e.g. the knapsack problem and partition problem). For instance, it’s true that given a set of Team positive integers ranging from 1 to n with sum no less than 2 n !, there exists a subset of them summing up to exactly n !. (See here and here for discussion on two AoPS blogs.) Remark. The problem author (Carl Lian) says the problem comes from algebraic geometry!