5
$\begingroup$

Possible Duplicate:
Optimal algorithm for finding the odd spheres

You have 12 balls and you know that they all weigh the same except for 1 which is heavier or lighter than all the others (you don't know which though). How can you make sure you know which ball is the heaviest/lightest in only 3 weighings?

The way I approached it was to split up the 12 balls into three sets of 4 and weigh two of the sets. If the sets balanced the scale, then I know the ball I am looking for must be in the set of 4 balls not weighed, else, I disregard said set and arbitrarily choose the heaviest set of 4 (as opposed to choosing the lightest set). I split the heaviest set of 4 balls into 2 and weigh that... etc.

Repeating this process until all 3 tries have been "used up", even if everything just so happened to be in your favor (the arbitrary choice you have in choosing the heaviest or lightest set happens to be the correct choice) in the end you still end up having to choose between 2 balls. A 50% chance is good, but I am wondering, is there a way to make sure 100%?

  • 0
    Yes, there is a way that guarantees finding the odd-one-out and determining if it's heavier or lighter. Your first step (4 against 4) is good, but you should think harder about the second.2012-04-09
  • 0
    I believe there is a method to find the anomalous ball from 13 in three weighings - but it is not possible to guarantee that you will know whether it is heavier or lighter.2012-04-09
  • 0
    @Mark: of course there is such a method: just execute a 12-ball protocol leaving one ball aside. If one of the 12 is anomalous, you'll find it, and if not, you'll know it's the 13th. This works assuming you know there's precisely one anomalous ball.2012-04-09
  • 0
    @AlonAmit: and if I can tell the odd one from 13, I can do the same for 14 by your method? - Clearly not, but that depends on the nature of the solution for 13. I need the knowledge that exactly one is different.2012-04-09
  • 0
    @Mark: Yes, like I said... you need the knowledge that precisely one is different. Maybe I'm misunderstanding what you're trying to say? What, in your view, is wrong with my proposed solution for 13?2012-04-09
  • 0
    @AlonAmit - I've added a comment to your solution. My point was mainly that for your argument to work for 13 balls, it had to be based on a solution for 12 which hadn't already used the information.2012-04-09

3 Answers 3