I did not figure out the 9 coin case yet, but there might be errors in this 8 coin case as well, please check: Let us simply denote the coins by {1,2,3,4,5,6,7,8}. Furthermore, if we identify coin i to be the heavier fake, we put iH; or to be the lighter fake, then iL; or to be normal, then iN. There are only one H, one L and 6Ns. There is one fact we will use again and again: if a weigh of several coins, for example {i,j,k} vs. {p,q,r} yields a result like {i,j,k}>{p,q,r}, then none of i,j,k can be the lighter one and none of p,q,r can be the heavier one. (*) www.ddhw.com Another fact will be used repeatedly is that if a weigh containing more than 1 coin on each side yields equality, then either one side contains all normal coins or both fake coins. (**) And of course the trivial fact that if {i}={j} then both i, j are normal. (***) Step 1. Weigh {1,2,3} vs. {4,5,6} (Weigh #1) if the result is equal, go to Step 2a. Otherwise, go to Step 2b. Step 2a. we will take the next TWO weighs as: Weigh #2: {1} vs. {2} Weigh #3: {4} vs. {5}www.ddhw.com If the results of both #2 and #3 are equal, that means 1,2,4,5 are all normal. Therefore, 3N, 6N. (otherwise we won't have equality of weigh #1). Therefore we only need to take Weigh #4:{7} vs. {8}, which will tell us the final answer. If {1}>{2} and {4}={5}, this implies 4N, 5N. And therefore 6N (otherwise #1 can't be equal, using fact **). And therefore both fakes are in {1,2,3}. The last Weigh #4: {3} vs. {4} will tell us the final answer, because 4 is normal.www.ddhw.com The other cases of one equality and one inequality in weigh #2 and #3 are similar to the above case. Furthermore, it is IMPOSSIBLE to get two inequalities in #2 and #3. Because if so, we will definitely have one fake in {1,2} and another fake in {4,5}, hence making the first weight equality impossible. This concludes all cases of weigh #1 being equal. Step 2b. WLOG, we can assume the result of #1 is: {1,2,3} > {4,5,6}www.ddhw.com This implies none of 1,2,3 can be the lighter fake and none of 4,5,6 can be the heavier fake. Furthermore, it also implies that one and only one of 7 and 8 is fake. We will take the next weigh as: Weigh #2: {1,7} vs. {4, 8} www.ddhw.com If {1,7}={4,8}, since we already know that one of 7, 8 is fake, this equality implies that the other fake must also be in this weigh. Therefore, the rest (2,3,5,6) are all normal. Then we will simply take the other TWO weighs are Weigh #3: {1} vs. {2} and Weigh #4: {4} vs. {2}. One and only one of the results will be inequality and it will tell us the final answer. If {1,7}>{4,8}, this implies none of 1,2,3,7 are light, and none of 4,5,6,8 are heavy. Let us take Weigh #3: {7,8} vs. {1,4}. The result will never be equal (because there is one and only one fake in {7,8}). www.ddhw.com (#3) If {7,8}>{1,4}, this implies 7H, 8N (the reason is that one of 7 and 8 must be heavy since their side is heavier in this weigh, remember that they canNOT be both normal. Further we knew 8 cannot be heavy.). Therefore all of 1,2,3 are normal. The last weigh #4 will be {4} vs. {5}, if equal, then 6L. Otherwise, the lighter one will show itself. (#3) If {7,8}<{1,4}, this implies 8L, 7N. Therefore 4,5,6 are all normal. Take weigh #4 as {1} vs. {2}. If equal, then 3H. Otherwise the heavier one will show. This concludes the second case of weigh #2. www.ddhw.com If {1,7}<{4,8}, this implies 1, 7 cannot be heavy, and 4,8 cannot be light. But we knew already from #1, 1,2,3 cannot be light, and 4,5,6 cannot be heavy. Therefore, 1 and 4 are normal. Therefore it is either 7L, 8N or 7N, 8H. Take weigh #3: {7, 8} vs. {1,4}. Again, the result won't be equal. (#3) if {7,8} >{1,4}, then 7N, 8H, therefore 1,2,3 are all normal. Take weigh #4: {4} vs. {5}. www.ddhw.com (#3) if {7,8} <{1,4}, then 7L, 8N, therefore 4,5,6 are all normal. Take weigh #4: {1} vs. {2}. This exhausted all possbilities. www.ddhw.com
|
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2009-2-22 23:55:21
收藏
分享
支持
反对
置顶卡
千斤顶
楼主