Given the previous puzzle (click here to read it), with 8 marbles, how would you generalize the solution to find the minimum number of weighings if you are given n marbles?
You should take a look at the previous riddle in order to understand this question better. Now the interviewer wants to see whether you just got lucky and stumbled on an answer in solving the previous riddle, or if you actually understood the problem.
What’s the best way to start generalizing our solution so that it works even for n marbles? Well, let’s try to break down the solution we found when we had exactly 8 marbles – and we only had to do 2 weghings to find the heaviest marble. What exactly happened after each weighing? Well, after each weighing we were able to eliminate 2/3 of the marbles, but we kept 1/3 of the marbles for the next weighing.
Is there a way we can take this information and generalize it into a solution for n marbles? What if we started out with 9 marbles? Well, we could find the heaviest marble with just 2 weighings as well – because in the first weighing we could eliminate 2/3 or 6 of the marbles, and in the second weighing we could eliminate 2/3 of the remaining 3 marbles – or 2 marbles, which would leave us with just the heaviest marble. It sounds like with every weighing we would be left with 1/3 of the marbles, and once we get to just one marble, then we are done since we have found the heaviest marble.
Come up with an equation
Another way of saying this is that, if x is the number of weighings and n is the number of marbles, then 3x would equal n. This is true in the scenario where we have 9 marbles, because 32 is equal to 9 – so it takes 2 weighings to find the heavy marble out of 9 marbles. So, if x is the minimum number of weighings to find the heavy marble, then this would mean that x = log3n.
What if we just had 8 marbles – would that equation (x = log3n) still apply? Actually, it would not because of the fact that the the log38 is equal to 1.893 – and we can not have 1.893 weighings – we can only have whole numbers. So, what needs to be done here? Well, we would need to round up to 2. But, the real question is whether rounding up would be valid for all other number of marbles.
Does rounding up always work?
Let’s see if rounding up works for 10 marbles. log310 would give us a little more than 2 – so if we round up to 3 would that be valid? In other words, in only 3 weighings can we find the heavy marble out of 10 marbles? Let’s break it down – we would start out with 2 groups of 3 (which we put on the scale) and one group of 4. Then, after one weighing we would be left with either 3 marbles or 4 marbles, depending on which group the heavy marble is in. If it’s in the group of 3 marbles we would need one more weighing to find the heavy marble, for a total of 2 weighings. However, if the heavy marble is in the group of 4, then we would need 2 more weighings for a total of 3 weighings. So, the answer varies depending on where the marble is. But, the question asks us to find the minimum number of weighings in which we are guaranteed to find the heavy marble, and that would be 3 weighings in this case.
So, we would have to round up in every case we have a fractional number in order to find the heaviest marble, and another way of saying that is we want to find the ceiling of log3n. And that is the correct answer – given n marbles, it takes ceiling (log3n) weighings to find the heavy marble.
One interesting thing to note here is how much easier it would have been to solve the previous problem if the number of marbles was 9, because you are able to split the marbles into 3 groups of 3. But, with 8 marbles, the problem becomes more difficult and forces you to think a bit more. So, it’s always good to remember to try out different scenarios, and not to be misled into thinking about the problem in the wrong way because of a small detail in the problem.