I guess its about time I post the solution to the coin puzzle from last time. I guess I could solve out the n=1 case first and then generalize, but it isn't particularly interesting to do that, so I think I'll just solve the general problem outright.
So we have 4n+1 coins and in a single step we can find the median of 2n+1 of them, and we have n+2 steps to work with. Now, the goal is to identify the median coin, which I shall call M. We will know a particular coin is coin M if there are exactly 2n coins heavier than it and 2n coins lighter than it.
Begin by selecting any 2n+1 coins and putting then in the machine (there is no other first step, of course), take the median coin and paint it red (I will be painting coins as we move along so that I can refer to particular groups of coins). Set the red coin aside and grab any other coin to measure with those same 2n coins. Repeat this process until you have done n+1 measurements and have n+1 red coins. Paint the other 2n coins involved in those measurements yellow, and the remaining n coins blue.
I claim that if you sorted the yellow and red coins by weight, the order would be n yellow coins, followed by all n+1 red coins, followed by the other n yellow coins, that is to say that each red coin has exactly n yellow coins lighter than it and n yellow coins heavier than it. This happens because if you were to start with the 3n+1 yellow and red coins and measure any 2n+1 of them, each time a coin from the middle n+1 of them will come out, that is, by finding medians and setting them aside, you find the middle n+1 of them, and those are the ones we are calling the red ones.
Now, with our last measurement, measure the n+1 red coins with the n blue ones, and call the median of that measurement P. I claim the P is the median coin M. We can see this in two cases, first if P is red, we know that P has n yellows above it and n yellows below it in weight. But P also has n non-yellows above and n non-yellows below it in weight (because it was the median of the final measurement), proving P is M. If P is blue, then it must lie strictly between two reds, since there must be n non-yellows above it and n non-yellows below it and n+1 of the non-yellows are red. Since it lies between two reds, it must have n yellows above it and n yellows below it. So this coin is had n yellows and n non-yellows above it, and also n yellows and n non-yellows below it.
Fun stuff.
1 comment:
Since I can't leave well enough alone, I'll point out that this method can be extended to the case where you have 6n+1 coins, or 8n+1, or 2kn+1 in general.
With 6n+1 coins: start by following the same procedure you used in the 4n+1 case. Test 2n+1 coins, paint the median coin red, then replace it with an unused coin. Continue until you have 2n+1 red coins. At that point, paint the other 2n coins from the last test yellow, and paint the 2n unused coins blue. As before, every red coin will be heavier than half the yellows, and lighter than the other half.
Having done that, take the 4n+1 red and blue coins, and find the median of those coins using n+2 tests (using the method you described before). If the median coin from those 4n+1 coins is red, it will be the overall median coin. If the median coin from those 4n+1 coins is blue, then it will have to be heavier than a red coin and lighter than another red coin (since there are more reds than blues). So it must be heavier than half the yellows and lighter than the other half, so it must be the overall median coin. Either way, you've found the overall median coin, and it took 3n+3 tests overall.
With 8n+1 coins: start off with 3n+1 tests, obtaining 2n yellows, 3n+1 reds, and 3n blues. Then find the median coin among the 6n+1 reds and blues using the method given above (with 3n+3 tests). That gives you the overall median coin, with a grand total of 6n+4 tests.
Similarly, you can find the median coin from 10n+1 coins with 10n+5 tests, or from 12n+1 coins with 15n+6 tests... and in general, if you start with 2kn+1 coins, you need (k choose 2)*n+k tests.
Post a Comment