HMMT 二月 2015 · 团队赛 · 第 6 题

英文解析

6. [ 30 ] $indy has $100 in pennies (worth $0 . 01 each), nickels (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 withtotal value exactly $50.
   Answer: N/A Solution 1. First, observe that if there are pennies in the mix, there must be amultiple of 5 pennies (since 5 , 10 , 25 ≡ 0 (mod 5)), so we can treat each group of 5 pennies as nickelsand 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, wehave 5 q + 2 d < 1000 + 1000 = 2000, so there must be nickels in the mix. By similar reasoning, theremust 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 atmost $49 . 75, so now,
   • if possible, we keep adding in dimes until we get an amount equal to or greater than
   $50. If it is $50, then we are done. Otherwise, it must be $50 . 05 since the total money valuebefore the last dime is either $49 . 90 or $49 . 95. In that case, we take out the last dime and replaceit with a nickel, giving us $50.
   • if not possible (i.e. we run out of dimes before reaching $50 ) , then all the quarters anddimes have been used up, so we only have nickels left. Of course, our money value now has ahundredth’s place of 5 or 0 and is less than $50, so we simply keep adding nickels until we aredone.
   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 problemto the case of no pennies, treated below. Similarly, we can treat each group of 2 nickels as dimes, andreduce 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 $50, in which case $indycan form a pile with $50 worth of dimes and a pile with the rest of the money, or the quarters alonetotal to at least $50, in which case $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 reducethe 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
   Teampositive integers ranging from 1 to n with sum no less than 2 n !, there exists a subset of them summingup to exactly n !. (See here and here for discussion on two Ao pS blogs.)
   Remark. The problem author (Carl Lian) says the problem comes from algebraic geometry!