A Median Coin
Baron Münchhausen is famous for his tall tales. My co-author Konstantin Knop wants to rehabilitate him and so invents problems where the Baron is proven to be truthful from the start. We already wrote a paper about one such problem. Here is a new problem by Konstantin:
Kostya has a black box, such that if you put in exactly 3 coins of distinct weights, the box will expose the coin of median weight. The Baron gave Kostya 5 coins of distinct weights and told him which coin has the median weight. Can Kostya check that the Baron is right, using the box not more than 3 times?
Actually, Konstantin designed a more complicated problem that was given at the Euler Olympiad, 2012 in Russia.
Let n be a fixed integer. Kostya has a black box, such that if you put in exactly 2n+1 coins of distinct weights, the box will expose the coin of median weight. The Baron gave Kostya 4n+1 coins of distinct weights and told him which coin has the median weight. Can Kostya check that the Baron is right, using the box not more than n+2 times?
Note that Kostya can’t just put 4n+1 coins in the box. The box accepts exactly 2n+1 coins. The problem that I started with is for n = 1. Even such a simple variation was a lot of fun for me to solve. So, have fun.
Share:
lvps1000vm:
It’s been easier for me the general problem than the n=1 variation, because I’ve able to think of n and 2n coins as a “blob”.
Separate the coins in two bags of 2n+1 and 2n coins. Put the 2n+1 bag in the black box, and the coin chosen by the black box gets switched to the other bag, which is now the new 2n+1 bag.
Iterate the above until a coin gets chosen twice by the black box. Said coin is the general median.
9 May 2012, 10:14 pmsaar:
take the coin that baron tells u, with 2 others.
10 May 2012, 9:42 amif the box says this is tae miterian, u can chek with the other 2. if not, than with the other 2 it can not be miterian and it has to be miterian for 1 coin from the 2 in each side/
Chris Chang:
lvps: Your algorithm, as stated, is not guaranteed to terminate in (n+2) steps. E.g. suppose the lightest three coins start in the 2n+1 bag, and the heaviest two in the 2n bag; then your algorithm proceeds as follows:
Step 1. Median of [1 2 3] = 2, new bags are [2 4 5] [1 3]
Step 2. Median of [2 4 5] = 4, new bags are [1 3 4] [2 5]
Step 3. Median of [1 3 4] = 3, new bags are [2 3 5] [1 4]
Step 4. Median of [2 3 5] = 3, terminate. Unfortunately, 4 > (n+2).
saar: Yes, this works for n=1. Can you generalize?
10 May 2012, 1:56 pmlvps1000vm:
^^^ Yes, you’re right. I missed a factor of two in the proof I had in mind. Worst possible case is the median coin in the 2n+1 bag grouped with 2n coins all lesser (or bigger), and it takes 2n+2 steps instead of n+2.
Actually I can save one step by noticing that if my algorithm hasn’t terminated after 2n+1 steps, whatever coin was moved at the last step will be the final median, which reduces the required steps to 2n+1. This saves the case n=1, but not the cases n>=2
10 May 2012, 6:23 pmsaar:
if one time the coin that the Baron give us ia the maedin, then if he is right we can check easily, by checking this coin with the other 2N coins.
11 May 2012, 9:07 amso we just need to check in N+1 times if this coin can be median.
if we cange 1 coin each time, we can prove that if this coin is medizn, must be 1 time that we will get it as median (it is hard for me to prove in english, sorry)
Chris Chang:
Okay, sounds like saar got it.
11 May 2012, 2:53 pmAndrei Zelevinsky:
Here is my solution for n=1 (took 2 minutes to find). Denote Baron’s coin by B.
Step 1: test any 3 coins NOT having B among them. Let the output be coin A.
Step 2: remove A and B, and test the remaining 3 coins. Let the output be C.
Step 3: test A, B, and C. Claim: Baron is truthful if and only if the output of this test is B. This follows at once from an obvious observation that both A and C must be among the three middle weight coins.
Greeings from Beijing.
11 May 2012, 3:26 pmHarry:
I’ve solved the first case but was having trouble with the general case until I reread the problem. And the important bit is; you’re checking a claimed median not just finding the median with no previous information.
It is possible to do this in the fist case (3 out of 5 in 3 moves) and thus solves the given problem too, but is it in the general case ie. given 4n+1 stones and a box that gives the median of 2n+1 stones, can you find the groups median in n+2 moves? I’m not sure.
12 May 2012, 4:29 pmlvps1000vm:
^^^ Ha, ha. I’ve been banging my head because I made the same mistake. Though Saar solved it in the 5th comment, only he doesn’t find how to explain it. I’m trying:
Group Baron’s coin with 2n more coins in the black box (put the other 2n in a bag of spares). Call “red” the coins above the median and “blue” the coins below it. Without loss of generality, say that there are more red than blue coins in the box by a difference 2d. So we have a box with n+d red coins, n-d blue coins and Baron’s coin, and 0<=d<=n
Now iterate the following: Take away the coin chosen by the box (which is always red) and replace it with a random coin from the bag of spares. In at most n moves the black box will contain the same number of red and blue coins, and Baron’s coin will be picked by the black box at the following iteration (iteration n+1 at most).
Now that Baron’s coin is grouped with exactly n red and n blue coins, remove all the coins from the box and check Baron’s coin against the remaining 2n coins (altogether those that were thrown away and those unused, still at the bag of spares), of which n should be red, n blue and Baron’s coin would emerge again as chosen by the black box.
12 May 2012, 10:04 pmVudoo:
It is simple this way (based on saar’s correct original solution):
15 May 2012, 10:24 pm1) Let label the coin that the Baron said it is a median coin = M
2) Let assume that Baron is correct, then there are 2 coins will lighter than M, and 2 coins heavier than M.
3) Divide the 4 coins in 2 groups of 2 coins each. When we use the black box for the M coin with each of these group, TRUE is define when the black box said M is the median coin and FALSE is define as other coin was identified as median (other than M coin.)
4) If, we are lucky enough, two groups each have 1 lighter coin and 1 heavier coin then 2 run from the black box for each group plus M coin will result in M (both TRUE) as the selection for each group run. If the 2 run result in TRUE and FALSE then the M coin is not the median coin. We are done, only 2 run were necessary to determine the median coin.
5) The other case is 2 groups with both coin either lighter or heavier (one group is lighter than M and the other group is heavier than M) than the M coin. 2 black box run with each group and M coin will result in both FALSE (coin other than M was selected). Again TRUE and FALSE result will meant than the M coin is not a median coin. We still have one more measure in case the M coin is the HEAVIEST or LIGHTEST of the 5 coins which would gave the result above 2 FALSEs. Take a coin from each group (preferable the one that was not select as median in the prior 2 runs) and the M coin. This run the result should be TRUE (to confirm that M coin is the median).
Gareth:
how would you solve the following problem. PLEASE SOMEBODY HELP ME!
55 176 539 1628
Q. In the sequence, above, each term after the first is determined by multiplying by X and then adding Y. If X and Y are each greater than zero, and if they are integers, then what does the term X+Y equal to?
19 May 2012, 2:02 amBrian:
@Gareth: Simple guess and check; 55*3 is 165, which is 11 less than 176. Check if this works for 176: 176*3 = 528, add 11 and you get 539. Thus x = 3 and y = 11; the answer is therefore 14.
26 May 2012, 2:56 pmChris Chang:
lvps, here’s how I’d explain it.
We proceed as follows:
1. Designate the claimed median as “M”. Put M and any other 2n coins into the box.
2. As long as M is not the median of the 2n+1 coins in the box, replace the actual median with another coin that previously has not been put in the box. Repeat this replacement up to n times (resulting a total of up to n+1 uses of the box).
3. We claim that the Baron is wrong if, after n+1 box uses, M has never been the median.
4. Otherwise, we have a set S of 2n+1 coins among which M is the median, and we have at least one box use left. Put all coins not in (S{M}) into the box; we claim the Baron is right if and only if M is also the median of this set.
Proof of step 3 claim: Any median of a size-(2n+1) subset of coins is heavier than at least n coins in the whole collection, and lighter than at least n coins in the whole collection, so it must be between the (n+1)th lightest and the (3n+1)th lightest coin overall. Designate the median found in the kth box usage as B_k, and suppose without loss of generality that M is heavier than B_1. Then M must be heavier than at least n+1 coins in the first box usage… so it also must be heavier than at least n coins in the second box usage, because only one coin was replaced in between. But it can’t be heavier than exactly n coins, because then it would have been the median. Continuing this line of reasoning, we find that M is heavier than all of B_1, B_2, …, B_{n+1}, and because {B_1, B_2, …, B_{n+1}} are all distinct coins each no lighter than (n+1)th lightest, the heaviest among them can be no lighter than the global median. It follows that M must be heavier than the global median.
Proof of step 4 claim: Between the last two box uses, M appears both times and all other coins appear exactly once. If M is the median both times, then M is heavier than exactly n other coins in the first set and exactly n other coins in the second set, meaning it is heavier than exactly 2n other coins globally and is the global median. Otherwise, M is heavier than exactly n other coins in the first set and is heavier than exactly m other coins in the second set for some m != n. Thus, M is heavier than exactly n+m other coins globally, and since m != n, n+m != 2n so M can’t be the global median.
28 May 2012, 10:42 am