You have 5 coins of distinct weights, and you have a machine that if you put in 3 coins of distinct weights it will identify the coin of median weight. Of the 5 coins, find the coin of median weight using the machine no more than 3 times.
And a somewhat generalized version:
You have 4n+1 coins of distinct weights, and you have a machine that if you put in 2n+1 coins of distinct weights it will identify the coin of median weight. Of the 4n+1 coins, find the coin of median weight using the machine no more than n+2 times.
In Tanyas version, Baron Münchhausen identifies the coin of median weight ahead of time, and you must use the machine no more than n+2 times to confirm if he is right. When I found my solution to the problem though, I noticed that I didn't need that extra information, I could simply confirm if he was right by using my method and checking if his median was the same as mine. Anyway, I guess its still possible I did something stupid and am wrong, so if you are unable to solve the problem as I posted it try Tanyas version instead, mine might just be impossible.
1 comment:
So far, I can do no better than to use the machine 2n+1 times. My idea:
Divide the 4n+1 coins into a set of 2n+1 and a set of 2n. Then repeat the following steps over and over:
1. Find the median coin from the set of 2n+1 coins.
2. Move that median coin to the set of 2n coins, thus forming a set of 2n+1. (You'll next use the machine on THOSE 2n+1 coins.)
If you get the same median coin twice in a row, then that's the overall median. Keep going until that happens.
If you use the machine 2n+1 times and you still haven't gotten the same median coin twice in a row, then the last median coin you got IS the overall median coin. This can only happen if you started by checking the 2n+1 heaviest coins, or the 2n+1 lightest.
Unfortunately, "2n+1 tests" is a far cry from "n+2 tests". So, back to the drawing board.
Post a Comment