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 teacher gave Kostya 4n+1 coins of distinct weights and told him which coin has the median weight.
Can Kostya check whether the teacher is right, using the box not more than n+2 times?
Source : Russian Euler contest 2012
Rem: Note that Kostya can't just put 4n+1 coins in the box.
The box accepts exactly 2n+1 coins.
Hint: start with n = 1. .
While I might not have come up with this on my own, I am often capable of correcting somebody else's solution. The following (partial credit to Chris, PhD) works:
/**************************************/
First let M be the median chosen by the teacher. Choose another 2n coins to go with M. We will call this collection of coins the "blue bag" (Leaving behind 2n coins in a "red" bag)
Test if M is the median of this set of 2n+1 coins in the blue bag.
If it isn't, add the actual median to a 3rd bag (perhaps it is white) and move one coin from the red bag to the blue bag. Do not put the actual median in the red bag, as we do not want to reselect in future steps.
Keep repeating this process up to the (n+1)th use of the box, or until M is returned as the median of the blue bag.
If M has never been the median of the blue bag for these n+1 tests, then M is not the median, because the n+1 coins that are now in the white bag are necessarily all greater or all less than M, as are at least n coins in the blue bag. Altogether, at least 2n+1 coins are all greater or all less than M.
Otherwise, M has been the median of a set of 2n+1 coins, and we still have one last test with the box. Take M and put it with all the red and white coins, and test these 2n+1 coins. If M is also the median of this subset, then M is truely the median of the whole set. If not, then M is not the median of the set.
Edited on August 14, 2012, 9:48 pm
Revised Solution (spoiler)
