3

There are many variants of this problem. The one I am working with is

There are $17$ balls that weigh the same, and $1$ ball that could weigh either heavier or lighter than the other $17$. How many weighs on a balancing scale do you need to determine the odd one out and whether it's heavier or lighter?

The simpler case where you know if the the odd ball out is heavier or lighter can be found in $3$ weighs. The idea is to divide the $18$ balls into groups of $6$, say, $6A$, $6B$, $6C$. Weigh $6A$ and $6B$ on a scale. If they balance each other out, then $6C$ has the odd one out. If they don't balance each other out, and $6A$ is lower on the scale, then $6A$ has the heavier ball, and analogously for $6B$. So it takes a maximum of $1$ weigh to determine the group of $6$ with the heavier ball. Then you can divide this group of $6$ into $3$ groups of $2$, and using the same idea, you can find the odd group of $2$ out with a maximum of $1$ weigh. Then you're left with a group of $2$ and it takes $1$ weigh to determine the heavier ball. So, in total, you need $3$ weigh ins for this case.

But the harder variant of this problem is where you don't know if the odd ball out is heavier or lighter. In this case, I found that you need a maximum of $5$ tries to find the odd one out as well as to determine if it is heavier or lighter, but I have no idea if this is correct, or how to justify that this is the minimum number of maximum number of tries.

The idea is similar to the previous problem. Divide $18$ balls into $6A$, $6B$, $6C$. This time, it takes a maximum of $2$ tries to find the group of $6$. i.e., weigh $6A$ and $6B$ on a scale, if they match, then $6C$ is the odd group out. If $6A$ and $6B$ doesn't match, then we need an additional weigh to determine the odd one out. Hence, $2$ tries.

Now once we found the odd group of $6$, we apply the same idea, which takes another $2$ tries (maximum). Then we're left with a group of $2$. It takes exactly $1$ weigh because you can take $1$ ball from the group of $2$ and weigh it with one of the other $16$ balls that we know are the. If this ball is the same, then the remaining ball is the odd one out. So it takes a maximum of $2+2+1 = 5$ tries to find this odd ball out. We don't need an additional weigh to determine if this remaining ball is heavier or lighter.

This is because when we found the group of $6$, and the subsequent group of $2$, we took the maximum of $2$ tries. If it takes $2$ tries to find the odd group of $6$ out, then that means the 2nd weigh of the $2$ tries allows us to determine if this odd ball out is heavier or lighter.

For example, consider $6A$, $6B$, $6C$ again. Say we first weigh $6A$ and $6B$ and find they don't weigh the same. Then we weigh $6C$ with either $6A$ or $6B$. If we weigh $6A$ with $6C$ and find that $6A$ doesn't match $6C$, then $6A$ is the odd one out, but also if $6A < 6C (6A > 6C)$, then we know $6A$ has a ball that weights less (more).

Is this the most optimal approach or is there a method that takes only $4$ weigh ins? My gut is telling me there should be a $4$ weighing approach.

The $12$-ball variant of the problem and its solution is posted in here. You can see that they apply an analogous approach by breaking the $12$ balls into $3$ groups of $4$, but they apply some interesting mix and matching to find the odd one out in only $3$ moves.

Khashayar Baghizadeh
  • 1,477
24n8
  • 1,455
  • If the weight "direction" is known you may solve it for 27 balls! – Moti Aug 22 '20 at 17:16
  • When you do not know - you can find it out of 13. You are not requiring to find out if it is heavier or lighter. – Moti Aug 22 '20 at 17:19

2 Answers2

2

I did not check the solution for the classic $12$ balls version here. But if it works, it trivially leads to a $4$ weighing solution for the $18$ balls case.

Really, given the classic, there is very little extra work to do!

First you weigh $3A$ vs $3B$. If they are unbalanced, say $3A > 3B$, you can find out with $3A$ vs $3C$ (all $3C$ are good) whether the bad ball is heavier or lighter. Then surely you can find the culprit among a group of $3$ with just one more weighing. Total $3$ weighings.

And if $3A = 3B$, then you are reduced to the classic $12$-ball problem which can be solved with $3$ additional weighings, for a total of $4$.

Further thoughts: In fact, $4$ weighings can solve $30$ balls, not just $18$.

In the above, the $3A \neq 3B$ branch always leads to $3$ total weighings, which is wasteful. Imagine you have $9+9+12 = 30$ balls. The first weighing can be $9A$ vs $9B$. If they are unbalanced, again a second $9A$ vs $9C$ (all good) will tell you if the bad one is heavy or light, and then you can use $2$ more weighings to find the culprit among $9$ (tri-nary search), for a total of $4$ weighings.

Even further, years ago I solved a case (an extension to the classic) where $13$ balls (unknown heavy/light) can be solved with $3$ weighings, provided you have access to extra balls known to be good -- IIRC you need $2$ such good extras. This means $9+9+13 = 31$ can be solved with $4$ weighings, coz in the $9A=9B$ case you are indeed left with $13$ suspects but many extra balls known to be good.

I suspect even $31$ is not the limit (for $4$ weighings). When you weigh $9A$ vs $9C$, only two outcomes can happen (since $9A > 9B$). This is very inefficient and further exploitation might be possible...

You probably know the classic bound that with $n$ weighings there are only $3^n$ possible results, so with $n=4, 3^n = 81$, you cannot solve $\ge 41$ balls ($\ge 82$ outcomes). I'm not saying $40$ is achievable, but there is a wide gap between $31$ and $40$...

antkam
  • 15,363
  • ah yes, I didn't think about doing the 3A vs 3B first, although I wasn't familiar with the 12 ball solution when I first posted this, and discovered it shortly after. – 24n8 Aug 21 '20 at 20:35
  • For the 30 ball case, how do you determine the odd one out of the set of 9 in only 2 weighs? – 24n8 Aug 21 '20 at 20:39
  • 1
    Oh I think I get it. Say the group of 9 is divided into 3A, 3B, 3C. You weigh 3A against 3B. If they're equal, 3C contains the odd one out, and it takes 1 weigh to determine it. If 3A does not equal 3B, and because we already know whether this odd ball out is heavier or lighter, then we can single out whether it is in 3A or 3B when weighing 3A vs 3B. – 24n8 Aug 21 '20 at 20:41
1

Weighing 1: Weigh $1$-$6$ versus $7$-$12$. If the result balanced, then we know the odd ball is in the set $13$-$18$, which (indeed) takes $3$ more measurements for a total of 4 weighings.

If the first weighing is unbalanced, suppose without lack of generality that $1$-$6$ is heavier than $7$-$12$. Then perform...

Weighing 2: Weigh $1$-$3$ versus $7$-$9$. If the result is balanced, the odd ball is in $\{ 4, 5, 6, 10, 11, 12 \}$, which indeed takes $3$ more weighings, for a total of 5 weighings.

If instead the result is unbalanced, suppose without loss of generality that $1$-$3$ is heavier than $7$-$9$. Then we know the odd ball is in that set of six, which indeed requires two more weighings for a total of 5 weighings.

David G. Stork
  • 29,774
  • For weighting 1: if 13-18 contains the odd ball, why does it only take 2 more measurements? Using my approach in the OP it takes 3 tries. – 24n8 Aug 19 '20 at 19:32
  • @lamanon: I agree it takes three more if the first one balances. Weigh 13,14 against 15,16. If it balances, you can find the odd one by weighing 17 against 1, but if 18 is the odd one you need a third try to find out if it is heavy or light. If 13,14 are heavier than 15,16 you can weigh 13,15 vs 14,16 or 14,1, but in either case you might need another weighing. – Ross Millikan Aug 19 '20 at 19:39
  • @RossMillikan There's a 12-ball variant of this problem posted on http://www.mytechinterviews.com/12-identical-balls-problem. They do some interesting mix and match in the pile of 4s in that case. I wonder if there's an analogous approach for mixing and matching the pile of 6 in this case. – 24n8 Aug 19 '20 at 20:00
  • 1
    $12$ balls is the classic version, where you are allowed three weighting’s. I heard that une at least $55$ years ago – Ross Millikan Aug 19 '20 at 20:04
  • @RossMillikan Is every extension of this problem with more than 12 balls able to use the solution from the 12 ball version? – 24n8 Aug 21 '20 at 20:33
  • The classic $12$ ball solution can be extended to $36$ in four weighings. Weigh $12$ vs $12$. If they balance you are in the classic $12$ ball case. If not, you have $12$ that might be heavy and $12$ that might be light. Put four heavy and four light on each pan. Whether they balance or not you have four balls that might be heavy and four that might be light with two weighings available, which is again part of the $12$ ball solution. – Ross Millikan Aug 21 '20 at 20:47
  • @RossMillikan - why did you delete your answer, and instead just posted a comment? I think it's relevant to the OP question. – antkam Aug 21 '20 at 23:18
  • @antkam: I thought it was better as a comment because it is not answering the question that was asked. – Ross Millikan Aug 22 '20 at 00:10