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

Question

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.

Answer 1

Short answer to the question in the title: No.

A bit longer answer: We, as the humanity, don't know if an optimal general method exists, and certainly not what it might be.

Even longer answer still: Several scientific papers and even books have been written on the subject. The one I got most my info from is "The Art of Computer Programming. Volume 3. Sorting and Searching." by Donald E. Knuth, which has a long chapter on exactly this problem. It even has a pretty table listing the exact values of comparisons needed for selecting the tth largest item from a group of n items, for some small n. (See picture below, circles highlighting the medians of odd n added by yours truly.) Notice especially the asterisk pointing out how one proposed upper limit loses its tightness pretty much immediately, as better methods become available with increasing n.

---

---

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.

For a practically applicable method of finding the median, you can try the Quickselect algorithm, with or without the median-of-medians pivot selection that gives better worst case performance at the cost of worse average case. Or you can use an adaptive method, which makes that choice for you on the fly, as suggested by @Albert.Lang in the comments.