PUMaC 2014 · 团队赛 · 第 15 题
PUMaC 2014 — Team Round — Problem 15
题目详情
- [ 10 ] Jason has n coins, among which at most one of them is counterfeit. The counterfeit coin (if there is any) is either heavier or lighter than a real coin. Jason’s grandfather also left him an old weighing balance, on which he can place any number of coins on either side and the balance will show which side is heavier. However, the old weighing balance is in fact really really old and can only be used 4 more times. What is the largest number n for which is it possible for Jason to find the counterfeit coin (if it exist)? 3
解析
- [ 10 ] Jason has n coins, among which at most one of them is counterfeit. The counterfeit coin (if there is any) is either heavier or lighter than a real coin. Jason’s grandfather also left him an old weighing balance, on which he can place any number of coins on either side and the balance will show which side is heavier. However, the old weighing balance is in fact really really old and can only be used 4 more times. What is the largest number n for which is it possible for Jason to find the counterfeit coin (if it exist)? Solution: For n = 39, we split it into 3 groups of 13. Let the coins from the groups be group A, B, C coins. We weight 13 A against 13 B . Case 1: 13 A = 13 B Hence the fake can only be among 13 C and the other 26 coins are reals. Hence we weigh 9 C against 9 A . Case 1a: 9 C = 9 A . Hence the fake can only be among the remaining 4 C . We weigh 3 C agaisnt 3 A If equal, then only the last C coin can be fake, which can be checked by weighing against a A coin. If 3 C > 3 A , then take any two of the 3 C and weigh them. The heavier is fake and if they are the same, the last C coin of the three is fake. 3 C < 3 A is similar. 5 Case 1b: 9 C < 9 A Hence the fake is among the 9 C . Take two groups of 3 C and weigh them. The fake is among the lighter group and if they are equal, the fake is among the remaining 3 C . Hence we take any two of the set of 3 C and weigh them. The lighter is fake and if they are the same, the last C coin of the three is fake. Case 1c: 9 C > 9 A This is similar to case 1b. Case 2: 13 A < 13 B . Hence the 13 C coins are all real. Weigh 9 A + 4 B agaisnt 4 A + 9 C . Case 2a: 9 A + 4 B = 4 A + 9 C Hence the fake is among the remaining 9 B and heavier, making this similar to case 1c. Case 2b: 9 A + 4 B < 4 A + 9 C Hence the fake is among the remaining 9 A and lighter, making this similar to case 1b. Case 2c: 9 A + 4 B > 4 A + 9 C Hence the fake is among the 4 B on the LHS or the 4 A on the RHS. We weight 3 A + 3 B against 6 C . If equal, then the fake is among the remaining A, B which can be easily identified by weighing A with C . If 3 A + 3 B > 6 C , the fake is heavier and among the 3 B . Otherwise, it is lighter and among 3 A . Either of which case can be checked just as in case 1a. Case 3: 13 A > 13 B Similar to case 2. We see that for n = 40, since there are 81 scenarios, with each of the 40 coins being heavier or lighter, or all being real, and there are 4 weighings, with 3 outcomes each, for a total of 81 outcomes, we need each weighing to eliminate the possible outcomes down to 1 / 3. Otherwise, if scenarios is larger than outcomes, it will be impossible for the fake coin to be found with certainty. Let the first weighing be between x coins and x coins. If x ≤ 13, in the case that the two piles of x coins are equal, the fake can only be among the remaining 40 − 2 x coins, which give rise to 2(40 − 2 x ) + 1 = 81 − 4 x ≥ 29 scenarios. If x ≥ 14, then in the case that one of the x coins is heavier than the other, there will be 2 x ≥ 28 scenarios. Thus in all cases, there might be more scenarios than the 27 outcomes possible with 3 weighing remaining. Hence it is impossible to always find the fake coin for n = 40, and n = 39 is the maximum possible. 6