## The 12 Balls/Coins problem with solution.

Hi,

Any one who may have taken any programming or technical interview he/she may be familiar with the famous 9 balls or 8 coins/balls problem. Which is stated as, you have 8/9 balls and you know that one ball is heavier/lighter, in how many minimum tries the odd one can be found out. Many people are able to solve it in 2 tries when given an analytical weight balance. Recently I tried the tougher version of this problem which is , When you are given 12 balls and you don’t know that if the odd ball is heavy or lighter, now the task is to find out the odd ball in minimum (3) possible tries and also determine if it is heavier or lighter. Believe me if you try it your self its is really time taking and intelligent process. However here I go with my solution

Divide the balls in 3 groups of 4 each. Name each ball 1, 2, 3, … 12.

Now place the groups A (1,2,3,4) in left pan and group B (5,6,7,8) in right pane of analytical balance. There are two possible outcomes

(Try 1) GROUP A and B Balance Out:

The groups of balls balance out. Now it is sure that the odd ball is in group C (9,10,11,12) lighter or heavier we still don’t know. I thing is sure at this stage is that 1,2, …8 labelled balls are ok, this info will we use.

(Try 2) Now take balls 1,2,3 in left pane and take 9,10,11 in right pane. Now possibility is they either balance out or not.

Case 1: if in try 2 groups of balls balance. Then the odd ball is ball number 12.

(Try 3 in Case 1) Weigh Ball 12 against any other ball. If the 12 weighs heavier than the ball 12 is the odd one heavier ball other wise it is the odd lighter ball.

Case 2: if in try 2 groups of ball don’t balance. If right pane containing (9,10,11) is heavier then the odd heavy ball is in this pane, other wise the odd ball is lighter in this case.

(Try 3 in case 2) : if (9,10,11) are heavy then weigh 9 and 10. if they balance out 11 is the odd heavy ball. Other wise which ever remains heavy is the odd heavy ball. if (9,10,11) are lighter then weigh 9 and 10. if they balance out 11 is the odd lighter ball. Other wise which ever remains lighter is the odd lighter ball.

So far I dealt the case in which group A and B balanced out and tries I took are exactly 3. Now lets deal the case if the Group A and B do not balance.

(Try 1) Group A and B do not balance.

If the group A and B donot balance then odd ball is in 1,2,3…,8 and group C (9,10,11,12) is not containing odd ball. This info can be intelligently used.

(Try 2) If the left pane containing (1,2,3,4) is heavy then (1,2,3,4) contains heavy odd ball or (5,6,7,8) contains odd lighter ball. Take (1,2,5) in left pane and (3,6,10) in right pane if they balance out then odd ball is either 4th one (heavy) or 7, 8 (lighter). Now for Try 3 in this case weigh 7 and 8 if they balance 4th is odd heavy ball other wise whichever remains lighter is the odd lighter ball. If (1,2,5) and (3,6,10) do not balance then and (1,2,5) is heavy then odd ball is either (1,2) heavy or the ball 6 (lighter). [Try 3] Weigh (1,2) if they balance 6 is odd lighter ball or whichever remain heavier is heavy odd ball. If(1,2,5) is lighter then 5 is lighter or 3 is heavier. [Try 3] Weigh 5 against ball 10 if they balance then 3 is heavier odd ball else 5 is lighter odd ball.

In Try 2 if left pane(1,2,3,4) is lighter then repeat the process in reverse and you will find out the lighter odd ball in Group A or heavier ball in group B.

Well this solution costed a comprehensive amout of time to think because there was a lot of interruption in office. Any ways some one may come up with better and fast solution if it exists.

Haroon

i guess your solution is the optimal, BTW what is the complexity of your solution , i think its n! ????…

Omer, acutally this is not a programmable solution, it is hard coded kind of solution for 12 balls only. I have yet to devise such a solution for ‘n’ balls, which should be programmable as well so this code has O(1) complexity 🙂

Hi Haroon,

Just one question. It is still not clear to me what drives you to the ideea to weight 1 2 5 vs 3 6 10 ? Why did you choose this combination? Can you please explain it to me?

Thanks very much!

Alin

Substances:Glyerin – 1 tablesspoon Bath salts -. Cook over medium heat,

stirring constantly, til mixture comes to full rolling boil; boil, stirring constantly,

7 minutes. In a small steam-resistant bowl (ceramic is best), beat

the eggs and brandy extract for aboujt 5 minutes.