1
$\begingroup$

So the classical coin weighing problem with $3^n$ coins all equal weight except for one light coin, where we want to find the one light coin, can be solved optimally with $n$ uses of a balancing scale, assuming that the scale either tips in the heavy direction or balances if the two weights are equal. But what if we have $N$ coins (it's possible that $N$ should be parametrized for simplicity, like $N = 3^n$ but I'm not sure how), and we know there are $k$ lighter coins all of equal weight (so there are $N \choose k$ possibilities for which coins might be lighter). How can the scale optimally be used to find the $k$ lighter coins? And what if the $k$ lighter coins are all of different weights and we want to know the $k$ lighter coins as well as their ordering according to weight? Then there are $k! {N \choose k}$ possibilities. Again how can the scale optimally be used to find the $k$ lighter coins and their weight ordering?

$\endgroup$
  • $\begingroup$ This may be of interest (but deals with the case that $k$ is unknown, and optimality is unknown - in fact, unlikely) $\endgroup$ – Hagen von Eitzen Dec 11 '14 at 11:29
  • $\begingroup$ The straightforward informationtheoretical bound is not always obtainable. For example ${50\choose 3}=19600<3^9$, but the best "first move" is to compare $12:12$ coins; then the balance shows "equal" in $6344$ and "left" (and "right") in $6628$ cases; since $6628>3^8$, more than $9$ rounds may be needed. $\endgroup$ – Hagen von Eitzen Dec 15 '14 at 18:10
  • $\begingroup$ The special case $k=N$ of your second problem is well-known: As the weights can be arbitrary, it makes no sense to ever put more than one coin into each pan of the balance. Then the problem reduces to sort with the minimal number of comparisons. You should find something in Knuth, The Art of Computer Programming, Sorting and Searching. $\endgroup$ – Hagen von Eitzen Dec 15 '14 at 18:19
  • $\begingroup$ Thanks, I'm familiar with the $k = N$ sorting equivalence but it's good to note here (I should have done that in my problem statement). It's also good to know that naive information theoretic bounds on number of weighings might not always be obtainable; to me this says the problem is highly non-trivial. I'm glad I put a bounty, I just wish someone could shed some light on these hard cases when $k < N$. (when $k$ is known) Thanks for the link for unknown $k$, I agree optimality is either unlikely or very hard to prove. $\endgroup$ – user2566092 Dec 15 '14 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.