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**