Assume we have a two-pan balance. We are given a set of 2n + 1 coins which by condition all have different masses. Our task is to find the median coin, i. e. the coin that weighs more than any of n certain coins, but, at the same time, less than any of another (remaining) n coins. You are not allowed to directly weigh each of the coins.
What would the optimal algorithm be?
Plus an additional question. How many weighings would you need for the worst case?
I have found this puzzle in an old late Soviet informatics textbook. The problem was marked with three stars—it means it is a very difficult one. Unfortunately, the textbook did not provide the answer, and I am not extra good in maths. I consider it to be an amazing algorithmic problem though.
P.S. I tried to read through this post (15 persons). However, the solution (accepted answer) is very difficult for my humble brain. I just wonder if there exists smth simpler.