30
$\begingroup$

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.

Notes: I got this riddle from this Mathoverflow page of riddles. A few coworkers and I have tried to solve it; we can do 8 balls pretty easily, but even 9 doesn't seem possible.

Unfortunately the page doesn't contain the answer, the riddle doesn't exist anywhere else on the Internet, and the original author is no longer active. So, I don't know the answer.

[Edit] I've asked about the more general case on math.SE

Improve this question
$\endgroup$

7 Answers 7

Reset to default
29
$\begingroup$

Building on Lawrence’s answer:

Weigh 5 against 5. If they don’t balance then we are done.

If they balance, then either they are all the same weight or each side has the same mix: either 3 of one kind and two or the other or 4 of one kind and 1 of the other. I will call these M (More) and F (Fewer). I will use upper case for the group on the left and lower case for the group on the right. Thus we have either MMMFF versus mmmff or MMMMF versus mmmmf.

As in Lawrence’s answer, we will then take the 5 from the left side and one from the right and weigh 3 against 3. We keep track of which ball we have taken from the right and place it in the right hand group of 3. If they don’t balance, we are done. If they do, then we know we have two “mores” and one “fewer” on each side.

Case 1:
If we started with MMMMF then we know we have MMF versus MMf with mmmm remaining from the right.

Case 2:
If we started with MMMFF then we know we have MMF versus MFm with mmff remaining from the right.

We take the three from the left and the one “added” ball and weigh them against the four balls omitted from the second weighing. In case 1 we now have MMFf versus mmmm which will not balance. In case 2 we have MMFm versus mmff which will not balance. If it does balance we know that all balls are the same weight.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Yeah, this is good. $\endgroup$
    – FIreCase
    Commented Dec 26, 2019 at 19:10
  • 1
    $\begingroup$ I also think this works, so what is wrong with the proof in my answer? $\endgroup$
    – melfnt
    Commented Dec 26, 2019 at 20:27
  • $\begingroup$ @melfnt I believe your reasoning depends on no new strategy becoming available. $\endgroup$
    – Hugh Meyers
    Commented Dec 26, 2019 at 20:55
  • 3
    $\begingroup$ @melfnt, your answer proves that any method that depends on expanding "positive knowledge" can only work for $2^N$ balls. This answer works by enumerating and then disproving every possible case of non-perfectness, and in the case with 10 balls, the "negative knowledge" is handily clumped up, so can you get more information out of every weighing. $\endgroup$
    – Bass
    Commented Dec 26, 2019 at 22:36
  • 2
    $\begingroup$ This perhaps a minor nit pick, but I found the use of "more" and "fewer" as the designation for the two weights confusing. At first I thought you meant that it was the set of balls that weighted more rather than the weight that there are more balls of and it took me a second to realize what you meant. $\endgroup$
    – Barker
    Commented Dec 29, 2019 at 3:41
6
$\begingroup$

In each weighing below, if they don’t balance, the balls aren’t all of the same weight.

  1. L5 vs R5 using all 10 balls. Without loss of generality, we have the same distribution on each side if they balance, the distribution being either D=AAAAB or D=AABBB. If A=B, all balls are of the same weight, but we can't determine that yet.

  2. L3 vs R3 using all 5 balls from L5 and one ball (x) from R5, with x in R3. Since both cases of a balanced first weighing require an even number of A’s and an odd number of B’s on each side, and balancing the second weighing requires an even number of B’s on each side, we know that x=B if the second weighing balances.

  3. L4 vs R4, where L4=L3+x and R4=R5-x. If D=AAAAB, then L4=AABB and R4=AAAA. If D=AABBB, then L4=ABBB and R4=AABB. Neither case balances unless A=B.

If all 3 attempts balance, then A=B and all balls are of equal weight. If any attempt doesn't balance, not all balls are of equal weight.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ In the third paragraph you are claiming that x must weight B, but I don't understand why: if in the first weighting the two groups were AAABB-AAABB then x must be A in order to get a balanced second weighting (AAB-AAB). Or am I just missing something? $\endgroup$
    – melfnt
    Commented Dec 26, 2019 at 15:02
  • 1
    $\begingroup$ "Weigh A against B" is impossible because you have AAB and you don't know which ones are A and which is B $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Dec 26, 2019 at 18:12
  • $\begingroup$ @melfnt Thanks; fixed now. I should have labelled the balls to give an odd number of B’s on each side for both cases. I’ve also changed the third weighing since the only information we now have is x=B. $\endgroup$
    – Lawrence
    Commented Dec 26, 2019 at 23:55
  • $\begingroup$ @BlueRaja Thanks; fixed now. Please see my comment above to melfnt above. $\endgroup$
    – Lawrence
    Commented Dec 26, 2019 at 23:56
  • $\begingroup$ (By the way, I noticed after correcting my answer that Hugh Meyers built off my original. We came up with a similar third weighing independently.) $\endgroup$
    – Lawrence
    Commented Dec 27, 2019 at 0:06
2
$\begingroup$

Edit: this answer is wrong as pojnted out by @Bass in a comment to another answer.

I think

it is not possible

If a set is composed by balls that have all the same weight I call it a perfect set.

because (Lemma)

Suppose you have a perfect set $S$ formed by $k$ balls. If you want to check whether a superset $T$ of $S$ is perfect or not and you can use the scales just one time, the maximum cardinality of $T$ is $2k$.

so

with one weighting you can just tell whether two balls have the same weight or not. By the Lemma with 2 weightings the cardinality of the biggest perfect set you can handle is 4, with 3 weightings it is 8 and so on. For 10 balls you will need at least 4 weightings.

Proof for the lemma:

Suppose you have $k$ balls that you know for sure they all have the same weight $w$ (they form a perfect set $S$ by the definition of perfect I stated earlier). You also have a big pool of "new" balls and you don't know the weights of the balls in the pool. You are allowed to use the scales just once to "expand your knowledge" i.e. to come up with a bigger perfect set composed by more than $k$ balls (the original ones plus other balls you picked up from the pool).
Remember that the balls come in two possible weights (it was stated in the original puzzle text). Let the two weights be $w$ and $x$, with $w \neq x$.
you can put $S$ on the left hand side plate of the scales and $k$ new balls on the right hand side: the weight of the left hand side plate is $kw$. The weight on the right hand side plate can be any of $kw, (k-1)w+x, (k-2)w+2x...$ up to $kx$ depending on how many new balls with weight $w$ you added. The scales is balanced if and only if all the $2k$ balls have the same weight $w$.
Now suppose that you want a method to "expand your knowledge" by more than $k$ balls using a single weighting. If you take $k+1$ or more "new" balls from the pool and put all of them on the scales along with $k$ or less taken from $S$ there will be at least one new ball on each plate (think about it for a moment). Since you don't know the weights of the balls in the pool, the scales can be balanced even if some balls have different weights.
Thus the statement of the lemma: with each weighting you can at most double the number of balls for which you are sure they weight is the same.

Bonus: a procedure to tell if $n$ balls have the same weights for any $n$:

General rule: if a weighting is unbalanced then you can claim that the weights are not all the same (because the balls come in two possible weights as stated in the original puzzle text). Otherwise you can proceed with the next weighting.
If $n$ is even, form two groups $G_1$ and $G_2$ of $n/2$ balls each. Put $G_1$ and $G_2$ on the two plates of the scales. If the scales is balanced repeat the procedure from scratch with $G_1$ ($n/2$ balls).
If $n$ is odd, put one ball aside, then form $G_1$ and $G_2$ with half of the remaining balls each. Weight $G_1$ against $G_2$: if the scales is balanced repeat the procedure from scratch with $G_1$ plus the ball you put aside at the beginning ($n/2$ balls rounded up).
This procedure will use $log_2{n}$ steps rounded up.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you @Adam I edited the answer but the spoilers didn't show up $\endgroup$
    – melfnt
    Commented Dec 26, 2019 at 19:05
  • 1
    $\begingroup$ I think the error with this is that "expanding a known perfect set" is not the only way of showing that all balls are equal (as proved by Hugh Meyer's answer). $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Dec 26, 2019 at 20:34
0
$\begingroup$
  1. $10\to5+5$
  2. $5\ne5\implies false.$ Exit.

  3. $else\\5\equiv a4b \, ||\,2a3b.\\5\to1+4\equiv a+4b\,||\,b+a3b \,||\,a+a3b\,||\,b+2a2b$

  4. $4\to2+2\equiv2b+2b \,||\,ab+2b\,||\,2a+2b\,||\,ab+ab$

  5. $2\ne2\implies false.$ Exit.
  6. $else\\2\equiv2b\,||\,ab\\\implies5\equiv a+2b+2b\,||\,b+ab+ab$
  7. $5+5\\\equiv1+2+2+1+2+2\\\to(1+1)+2+...\\\equiv(a+a)+2b+...\, ||\,(b+b)+ab+...\\\to2+2+...\\\equiv2a+2b+...||\,2b+ab+...$
  8. $2\ne2\implies false.$ Exit.
  9. $else\ true.$ Exit.

$a,b$ are the two weights. $true\implies a=b$

$N\to i+j+k...$ denotes splitting $N$ balls into groups of size $i,j,k,...$

$i\equiv n_1an_2b$ denotes a group of $i$ balls with $n_1$ weighing $a$, $n_2$ weighing $b$

$i+j+...\equiv n_1an_2b+m_1am_2b+...$denotes a group of $i$ balls with $n_1,n_2$ weights, another group of $j$ balls with $m_1,m_2$ weights and so on.

$n\times i \equiv i+i+i+...\}n\,times$

Improve this answer
$\endgroup$
-2
$\begingroup$

1) Weigh 6 balls at a time, i.e 3 on each side. If it's equal, they are of the same weight. Otherwise, proceed to step 2. 2) Weigh the remaining 4 balls, 2 on each side. If it's equal, they are of the same weight. Otherwise, proceed to step 3. 3) Last step. Take from any side 2 balls, and put them on different sides of the balance, if they are of similar weight, all balls are equal, otherwise, not.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I'll assume you meant "if they're equal proceed to step 2", since if they're not equal you can stop immediately. However, either way this fails. Just because both sides are equal doesn't mean every ball on each side is equal. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Dec 26, 2019 at 12:17
  • 2
    $\begingroup$ Let the weights be 2 1 2 2 1 2 2 2 2 2 respectively (arbituary units). 1) 2 1 2 vs 2 1 2. Equal. 2) 2 2 vs 2 2. Equal 3) 2 2 vs 2 2 Equal. But then the balls aren't weighing the same $\endgroup$
    – Omega Krypton
    Commented Dec 26, 2019 at 12:19
-2
$\begingroup$

I must be missing something here. If you weigh all ten and divide the weight by ten you get an average weight. Then weigh 9 balls and divide by nine and see if you get the same average. If not then at least one ball is a different weight. If you do then weigh the remaining one ball, if it is the same as the average they are all the same weight otherwise you have two different weights.

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ I think that would work for scales however this question is about using balance scales so you wouldn't be able to make measurements $\endgroup$
    – Adam
    Commented Dec 27, 2019 at 19:07
  • $\begingroup$ Ahh I did miss something, thanks for pointing that out. It seemed way too easy, maybe I should have posted a comment instead. $\endgroup$
    – Joe
    Commented Dec 30, 2019 at 14:16
-3
$\begingroup$

Take any 6 balls, split them into two groups of 3 balls each, grp1a & grp1b. Take the remaining 4 balls and split them into two groups of 2 balls each, grp2a & grp2b.

If weight(grp1a) != weight(grp1b), you are done. If weight(grp2a) != weight(grp2b), you are done.

Take any 2 balls from grp1a + grp2a (any 2 of the 6 balls - it doesn't matter because they all weigh the same if you made it this far), call it grp3a.

If weight(grp2a) != weight(grp3a), you are done.

Otherwise, all balls weigh the same.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There are 3 in grp1a and 2 in grp2a for a total of 5, not 6. If grp3a contains a ball from grp2a, you can’t weigh grp2a against grp3a since you would have to put that ball on both sides of the balance. $\endgroup$
    – Hugh Meyers
    Commented Dec 26, 2019 at 21:02
  • 1
    $\begingroup$ This fails for the same reason as gopal's answer $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Dec 27, 2019 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.