13 Balls problem : One of Hardest Interview Questions

Tweet

One of the most classic puzzles involving balls is figuring out the odd one out using common balance.There are many levels of puzzles based on the same concept for different levels of interviews - Simple ones for phone interviews to the most gruelling 1 hour hard work needing hard ones. Problem space The general problem is you will be given n balls and one of them is either heavier or lighter and you are asked to find out the minimum number of weighings using a common balance required to find out the odd one out. Example 1:8 Balls,Odd ball being heavier This is the simplest question among the lot and is often used during phone screenings.The question is to find out the minimum number of weighings required to spot the odd heavier ball among 8 identically looking balls using a common balance.Answer is 2 and the solution is given in the next paragraph. For simplicity let us name the balls as A1,A2,A3,B1,B2,B3,C1 and C2.We weigh with A's on one side and B's on the other side of the balance.If both sides are equal this means the heavier odd ball is among C1 and C2.We can figure out the heavier ball with one more weighing.If A's are heavier than B's then the heavier odd ball is among A's.Now we balance A1 and A2.If both are same then A3 is the odd ball or else the heavier one of A1 and A2 .Thus, we can find out the heavier ball using only 2 weighings. Example 2:8 Balls,Odd ball can be either heavier or lighter than the rest. This is a little trickier to solve.Let us name the 8 balls as A1,A2,A3,B1,B2,B3,C1 and C2.Now weigh with A1,A2,A3 on one side and B1,B2,B3 on the other side.If both weigh equal then the odd ball is among C1 and C2.Now we know that A's and B's are all normal ones we can weigh C1 with A1 and check whether C1 weighs the same as the normal ball.In this way, we can figure out in one weigh which of C1 and C2 is odd.Now if A's weighed more than B's then we know for sure C's are normal ones.Now lets assume A's heavier than B's and we still don't know whether the odd is among A's or B's. We know A1 A2 A3 < B1 B2 B3 Now we compare A1 B2 B3 to B1 C1 C2 . Now if the A1 B2 B3 is heavier than B1 C1 C2 Then it means the odd ball is among A1 and B1.If A1 B2 B3 is lighter than B1 C1 C2 then the odd ball is among B2 and B3.If A1 B2 B3 equal to B1 C1 C2 then odd ball is among A2 and A3.So we have zeroed down to 2 balls.Now its very easy as we can compare any of the normal ball with one of the 2 balls.So answer is 3,ie in 3 weighings we can find out the odd ball. Problem: You are given 13 balls.The odd ball may be either heavier or lighter.Find out the odd ball in 3 weightings.(There is an equally difficult smaller version of the puzzle involving 12 balls also but because both require the same solution technique i am leaving that problem) Hint: I have already given the hint for this question.This mammoth looking task only requires the techniques already discussed in the page.If you have not read all the steps mentioned above i request you to please go through the above solutions carefully.

  Adjust the font size     Reset ↕

One of the most classic puzzles involving balls is figuring out the odd one out using common balance.There are many levels of puzzles based on the same concept for different levels of interviews - Simple ones for phone interviews to the most gruelling 1 hour hard work needing hard ones.

Problem space
The general problem is you will be given n balls and one of them is either heavier or lighter and you are asked to find out the minimum number of weighings using a common balance required to find out the odd one out.

Example 1:8 Balls,Odd ball being heavier
This is the simplest question among the lot and is often used during phone screenings.The question is to find out the minimum number of weighings required to spot the odd heavier ball among 8 identically looking balls using a common balance.Answer is 2 and the solution is given in the next paragraph.

For simplicity let us name the balls as A1,A2,A3,B1,B2,B3,C1 and C2.We weigh with A's on one side and B's on the other side of the balance.If both sides are equal this means the heavier odd ball is among C1 and C2.We can figure out the heavier ball with one more weighing.If A's are heavier than B's then the heavier odd ball is among A's.Now we balance A1 and A2.If both are same then A3 is the odd ball or else the heavier one of A1 and A2 .Thus, we can find out the heavier ball using only 2 weighings.

Example 2:8 Balls,Odd ball can be either heavier or lighter than the rest.

This is a little trickier to solve.Let us name the 8 balls as A1,A2,A3,B1,B2,B3,C1 and C2.Now weigh with A1,A2,A3 on one side and B1,B2,B3 on the other side.If both weigh equal then the odd ball is among C1 and C2.Now we know that A's and B's are all normal ones we can weigh C1 with A1 and check whether C1 weighs the same as the normal ball.In this way, we can figure out in one weigh which of C1 and C2 is odd.Now if A's weighed more than B's then we know for sure C's are normal ones.Now lets assume A's heavier than B's and we still don't know whether the odd is among A's or B's.

We know
A1 A2 A3 < B1 B2 B3

Now we compare
A1 B2 B3 to B1 C1 C2 .
Now if the A1 B2 B3 is heavier than B1 C1 C2 Then it means the odd ball is among A1 and B1.If A1 B2 B3 is lighter than B1 C1 C2 then the odd ball is among B2 and B3.If A1 B2 B3 equal to B1 C1 C2 then odd ball is among A2 and A3.So we have zeroed down to 2 balls.Now its very easy as we can compare any of the normal ball with one of the 2 balls.So answer is 3,ie in 3 weighings we can find out the odd ball.


Problem:
You are given 13 balls.The odd ball may be either heavier or lighter.Find out the odd ball in 3 weightings.(There is an equally difficult smaller version of the puzzle involving 12 balls also but because both require the same solution technique i am leaving that problem) Hint: I have already given the hint for this question.This mammoth looking task only requires the techniques already discussed in the page.If you have not read all the steps mentioned above i request you to please go through the above solutions carefully.