1
$\begingroup$

You are given 5 balls that look identical but one of them has a different weight from the others. You are given a balance scale to find the odd ball. Give an algorithm to solve this task that minimises the use of the scale. State how often your algorithm uses the scale in the worst case. Prove that your algorithm is optimal by showing that no other algorithm can solve the problem with fewer uses of the scale in the worst case.

You might notice this problem is similar to the 12 coins problem. I have solved the first part of the problem but I don't know how to show it's optimal. If possible I would like to learn how prove optimality in general - not just for this particular problem.

If it helps, my algorithm is as follows:

  • Label the balls $a,b,c,d,e$.
  • Weigh $a+b$ against $c+d$.
    • If equal, $e$ is the odd ball.
    • If $a+b<c+d$, weigh $a+d$ against $b+c$.
      • If $a+d<b+c$, either $a$ is the odd light ball, or $c$ is the odd heavy ball. Weigh $a$ against $e$. If $a=e$ then $c$ is the odd ball, otherwise $a$ is.
      • Else $a+d>b+c$, either $b$ is the odd light ball, or $d$ is the odd heavy ball. Weigh $b$ against $e$. If $b=e$ then $d$ is the odd ball, otherwise $b$ is.
    • Else $a+b>c+d$, weigh $a+d$ against $b+c$.
      • If $a+d<b+c$, either $d$ is the odd light ball, or $b$ is the odd heavy ball. Weigh $b$ against $e$. If $b=e$ then $d$ is the odd ball, otherwise $b$ is.
      • Else $a+d>b+c$, either $c$ is the odd light ball, or $a$ is the odd heavy ball. Weigh $a$ against $e$. If $a=e$ then $c$ is the odd ball, otherwise $a$ is.

And in the worst case the scale is used three times.

How do I prove that no other algorithm can solve the problem faster in the worst case? Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Suppose there be a 2-times-scale-used algorithm. Let $\{a+,a-,b+,b-,c+,c-,d+,d-,e+,e-\}$ are the cases and $\{(<,<),(<,=),(<,>),\dots,(>,>)\}$ are the scale results. By pigeonhole principle there have to be 2 cases which results the same result-set... $\endgroup$ – Alexey Burdin May 10 '15 at 23:41
  • $\begingroup$ thank you! didn't quite think of that. would this sort of reasoning work in other cases? $\endgroup$ – dessskris May 12 '15 at 4:20
  • $\begingroup$ Yes, sure. Welcome :) $\endgroup$ – Alexey Burdin May 12 '15 at 13:00

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.