larry@harvard.ARPA (Larry Denenberg) (04/13/85)
> Given 12 identical items all weighing the same but only one is "different" in > weight from all the others. You are given a balance (no weights), a pen > (just in case you need to mark items) and nothing else to use. You are asked > to identify the different item using the balance the least number of times. > Amr F. Fahmy > It's pretty obvious that you can't do this problem in two weighings; I > won't go through the tedium of demonstrating it. However, there is a > way to do it in three, yes *three* weighings. Here's how: . . . > Greg Kuperberg The demonstration that two weighings cannot suffice is trivial: each weighing has three possible outcomes, so in two weighings there are nine possible outcomes. But there are twenty-four cases to be distinguished. This argument is not affected by the observation that the choice of coins for the second weighing can depend on the first outcome. Ready for a harder one? OK, here goes. You are given an accurate indicating scale (not a balance) and seven coins, each of which weighs either x or y, where x and y are unknown. In five weighings, determine the weight of each coin. Credit for this problem goes to J. G. Mauldon of Amherst College. Larry Denenberg larry@harvard