3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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... $\endgroup$
    – Evargalo
    Commented Jun 30, 2023 at 12:34
  • 2
    $\begingroup$ Sounds like a job for Hoare's selection algorithm. $\endgroup$
    – Bass
    Commented Jun 30, 2023 at 16:33
  • 2
    $\begingroup$ @Bass or introselect if you care about worst-case. $\endgroup$ Commented Jun 30, 2023 at 18:52

1 Answer 1

3
$\begingroup$

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.


enter image description here


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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.