2

A great friend of mine recently sat for an interview. He was asked a question which has fascinated me since some days now. It is

Consider you have 100 balls which look the same but one out of them is either heavier or lighter than the rest . You are given a beam balance , then find out in minimum how many steps can you determine which ball is the odd one out?

The question is what is the solution to this problem? I can do this in 7 moves. Can we do anything better than it. How would one solve the generalized case of $100$ balls and $n$ of different weight ?

Shivam Patel
  • 4,012
  • Do you actually know whether the odd-ball is heavier or lighter? Or are you just told that one of the balls is a different weight than the rest? – pancini Dec 14 '15 at 08:27
  • See http://math.stackexchange.com/questions/15423/optimal-algorithm-for-finding-the-odd-spheres/15430#15430 for a discussion. If you don't need to know heavier or lighter, just odd, you can do $13$ with three weighings, $40$ with four and up to $121$ with five. If you need to know which way the ball is wrong the figures are $12$, $39$ and $120$ - the difference is that you can add an extra ball to the "known" case which doesn't get weighed at all. Then if all the weighings come out level, you know it is odd, but not which way. Otherwise the original solution works. – Mark Bennet Dec 14 '15 at 08:38

1 Answers1

2

Divide the balls into three piles of as equal size as possible: two piles of 33 balls each, and one pile of 34 balls.

Weigh the equally sized piles. If the two piles are the same weight, then the odd ball must be in the 34.

If the two piles are different weights, we need to figure out if it is a result of a ball being heavier or lighter, so take 33 of the balls from the pile of 34 to compare to the heavier of the two piles. If it is again unbalanced, then the heavier pile must have a heavier ball. Otherwise, the lighter of the original piles has a lighter ball. Discard all balls except those in the odd pile.

From there, continue dividing the pile into thirds and testing two equally sized piles until none left.

$100\mapsto 34\mapsto 12\mapsto 4\mapsto 2\mapsto 1$, and a possible one additional step somewhere in the middle to determine whether the odd ball is heavier or lighter, for a total of $6$ steps.

JMoravitz
  • 79,518
  • thank you can you tell me how to solve for $101$ balls instead of $100$ ? – Shivam Patel Dec 14 '15 at 17:14
  • @ShivamPatel It works exactly the same way. Start with two piles of 33 and one pile of 35. Compare the size 33 piles. Always have two piles of $\lfloor\frac{n}{3}\rfloor$ if you have $n$ left. You'll have it go $101\mapsto 35\mapsto 13\mapsto 5\mapsto 3\mapsto 1$ with one extra comparison thrown in the middle at the first time you have a nonequal weighing for a total of 6 comparisons again. – JMoravitz Dec 14 '15 at 18:02
  • OP is asking for the minimum number of steps to detect the odd ball. Is your algorithm optimal? – Hans Jan 28 '16 at 03:38
  • @Hans I interpreted it as simply a challenge to find a better solution than the OP's, which I did. The question of whether it is optimal is apparently a no. See the linked question here which was shared above after I had originally posted this answer. – JMoravitz Jan 28 '16 at 03:52
  • OK. I raised the question because the quoted portion of the question says "find out in minimum how many steps". Now I see the OP follows that with "Can we do anything better than it?" So you answered the second question. Thank you for pointing to the link. – Hans Jan 28 '16 at 04:12