4
$\begingroup$

A few days ago this question was asked on puzzling.SE:

There are 10 balls which come in two possible weights. Using a balance scale at most 3 times, determine whether all the balls are the same weight or not.

The solution is not terribly satisfying, because there's no obvious way to generalize it. Can it be generalized?

Given N balls, how many weighings are required to determine if all balls are the same weight? Equivalently, for a given number of weighings, what's the maximum number of balls we can weigh?

$\endgroup$
10
  • $\begingroup$ Have you established any general result? Is it, say, obvious that $w_ n≥w_{n-1}$ (where $w_n$ is the minimal number given $n$ balls)? $\endgroup$
    – lulu
    Commented Jan 1, 2020 at 14:04
  • 1
    $\begingroup$ I guess it's clear that $w_n≤w_{n-1}+1$ since you can always handle the first $n-1$, in $w_{n-1}$ moves, and then weigh one of those against the odd man out. But it's not immediately clear to me that the sequence can't go down (though it would certainly be counter intuitive). $\endgroup$
    – lulu
    Commented Jan 1, 2020 at 14:06
  • 2
    $\begingroup$ More generally we have $w(k) \le w(n) + 1$ for all $ k \in \{n+1, n+2, \dots 2n\}$, by the same logic, i.e. handle $n$ first, then weigh some/all of these "good" ones vs the remaining $k-n$. $\endgroup$
    – antkam
    Commented Jan 2, 2020 at 5:51
  • $\begingroup$ @antkam: Right, and that leads to the obvious algorithm to do $n$ balls in $\lceil \log_2{n} \rceil$ weighings (mentioned in the original question) by weighing 1v1, then 2v2, then 4v4, etc. But, as can be seen by this question, that algorithm is not minimal. $\endgroup$ Commented Jan 2, 2020 at 19:07
  • 1
    $\begingroup$ I finally had to write some code to search: $w(9) = 3$ e.g. ({0, 1, 2, 3}, {4, 5, 6, 7}), ({0, 1, 4, 5}, {2, 3, 6, 8}), ({0, 1, 7, 8}, {2, 3, 4, 5}) $\endgroup$
    – antkam
    Commented Jan 5, 2020 at 5:03

1 Answer 1

1
$\begingroup$

$N=30$ for 4 weighings:

Let's divide all 30 balls into several groups. Namely, let in groups there will be 2, 5, 6, 8 and 9 balls. If we use four equalities to prove that the weights of the groups are also related as $2:5:6:8:9$, then we will solve the problem.

The required equalities are:

2+6 = 8

2+9 = 5+6

5+9 = 6+8

2+5+8 = 6+9

Let $w_2$, $w_5$, $w_6$, $w_8$ and $w_9$ be weights of our groups. Then $w_2+w_6=w_8$, $w_2+w_9=w_5+w_6$, $w_5+w_9$=$w_6+w_8$ and $w_2+w_5+w_8=w_6+w_9$. So, we solve and conclude that $w_6=3w_2$, $w_8=4w_2$, $w_5=2.5w_2$ and $w_9=4.5w_2$. If both balls in 2-group are the same (with weight $m$) then $m=w_2/2 = w_5/5 = w_6/6 = w_8/8 = w_9/9$, so all balls are equal. If balls from 2-group are not the same, then $w_2=M+m$ and $w_5=2.5(M+m)$, i.e. $2m+3M < w_5 < 3m +2M$, that's impossible.

So, the proof is over.

$\endgroup$
3
  • 1
    $\begingroup$ Sorry my linear algebra is a bit rusty. Does your proof rely on the fact that you have $5$ unknowns and $4$ equations and the relevant $5 \times 4$ matrix has rank $4$? If so can you more fully explain the reasoning? It might be obvious to others but as I said my linear algebra is rusty. Thanks! $\endgroup$
    – antkam
    Commented May 15, 2022 at 13:11
  • $\begingroup$ This shows that it's possible to do N=30 in 4 weighings, but not that 3 weighings isn't possible, nor that N > 30 in 4 weighings isn't possible. $\endgroup$ Commented May 15, 2022 at 21:07
  • $\begingroup$ I don't know proof that $N>30$ is not possible. $\endgroup$ Commented May 16, 2022 at 7:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .