# Finding the median mass: is there a general solution for 2n + 1 objects?

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.

• Given that the other post cannot reach a solution for N=15 objects, it sounds optimistic to hope for a general solution for 2n+1 objects... Commented Jun 30, 2023 at 12:34
• Sounds like a job for Hoare's selection algorithm.
– Bass
Commented Jun 30, 2023 at 16:33
• @Bass or introselect if you care about worst-case. Commented Jun 30, 2023 at 18:52

A result later in the book suggests that $$15n - 163$$ comparisons will always suffice for odd $$n>32, 1\le t \le n$$. That result is from 50 years ago though, so better upper bounds have almost certainly been found since then.