7
$\begingroup$

Five identical looking balls have known distinct positive integer valued weights (let's say $w_1$, $w_2$, $w_3$, $w_4$ and $w_5$). You want to find weight of each ball using a digital scale with a single pan by always measuring total weight of 3 balls exactly. That means you cannot put less or more than 3 balls on the pan while measuring the weights.

What is the minimum weight of heaviest one which guarantees to find all weights of the balls after 3 measurements?

$\endgroup$
  • $\begingroup$ Compared to the usual fake coin puzzles, there's a small problem with the practical execution here: if one ball weighs 1 and another weighs 5, there is absolutely no way I wouldn't realise which one is heavier when placing them on the scale. $\endgroup$ – Bass Dec 24 '17 at 21:12
  • $\begingroup$ Does the experimenter know the weight of the heaviest ball? Otherwise I couldn't imagine how determining all the weights would be possible in this system of 3 equations with 5 unknowns. $\endgroup$ – A. P. Dec 24 '17 at 22:59
  • $\begingroup$ @A.P.: The fact that the weights are distinct positive integers constrains the problem.  If balls A, B, and C together weigh 6, then you know that they must be 1, 2, and 3 (in some order).  Likewise, 7 must be 1+2+4.  Eight can be either 1+2+5 or 1+3+4. That said, I don’t see how this can be done, either. $\endgroup$ – Peregrine Rook Dec 25 '17 at 1:37
  • $\begingroup$ @A.P. no he doesnt know which one is the heaviest, but he knows every single weight values. $\endgroup$ – Oray Dec 25 '17 at 7:39
  • 1
    $\begingroup$ Wow. I thought I understood the question, but, seeing the accepted answer, I realize that I don’t understand it — and I still don’t. $\endgroup$ – Peregrine Rook Dec 26 '17 at 2:43
7
$\begingroup$

I'm gonna go with

8

This is the smallest possible big ball weight because

Choosing the weights 1, 2, 3, 5 and 8, every possible combination of exactly three balls yields a unique sum. Therefore, every weighing reveals exactly which three ball were weighed. There is no combination with this property where the heaviest ball is lighter than 8.

1,4,6,7,8 ("differences between the numbers in reverse order", obtainable by subtracting each number in the original sequence from 9) would also work, but I like 1,2,3,5,8 better.

If (and only if) the weight distribution satisfies the above condition, a guaranteed identification strategy exists. Here’s an example strategy: label the unknown balls A, B, C, D, and E, and then weigh the balls like so

A+B+C (weighing X)
A+B+D (weighing Y)
A+D+E (weighing Z)

This will identify each ball:

Rebember that each weighing exactly reveals which three balls were weighed. Then

   * A is the ball that is present both in X and Z
   * B is the other ball besides A that is present in both X and Y
   * C is the ball present in X that isn't A or B
   * D is the ball present in Y that isn't A or B
   * E is the remaining ball

For example, using the distribution with the lightest possible big ball:

if the shuffle happens to be A=8, B=1, C=2, D=5, E=3, then the measurements are

 X: 11 -> 1, 2 and 8
 Y: 14 -> 1, 5 and 8
 Z: 16 -> 3, 5 and 8
and the balls are
 A: present in X and Z           -> 8
 B: present in X and Y, is not A -> 1
 C: present in X, isn't A or B   -> 2
 D: present in Y, isn't A or B   -> 5
 E: the remaining ball           -> 3

$\endgroup$
0
$\begingroup$

I think the heaviest ball weighs at most:

16

Put them in five separate containers, to keep them straight.
Weigh the first three and call it 00111.
Weigh the third through fifth as 11100.
Weigh the ends and middle as 10101.

We then have:

00111 (Weight 1)
11100 (Weight 2)
10101 (Weight 3)

Then use these operations to find the individual weights.

00100 (00111 AND 11100) (Weight of ball 3)
10100 (11100 AND 10101)
10000 (00100 XOR 10100) (Weight of ball 5)
00101 (00111 AND 10101)
00001 (00100 XOR 00101) (Weight of ball 1)
11101 (11100 OR 10101)
01000 (10101 XOR 11101) (Weight of ball 4)
10111 (00111 OR 10101)
00010 (10101 XOR 10111) (Weight of ball 2)

Assigning the standard powers of two for each bit, the heaviest ball weighs 16.

Example:

00111 weighs 19
11100 weighs 28
10101 weighs 21
00100 = 00111 AND 11100 = 19 AND 28 = 16 (ball 3)
10100 = 11100 AND 10101 = 28 AND 21 = 20
10000 = 00100 XOR 10100 = 16 XOR 20 = 4 (ball 5)
00101 = 00111 AND 10101 = 19 AND 21 = 17
00001 = 00100 XOR 00101 = 16 XOR 17 = 1 (ball 1)
11101 = 11100 OR 10101 = 28 OR 21 = 29
01000 = 10101 XOR 11101 = 21 XOR 29 = 8 (ball 4)
10111 = 00111 OR 10101 = 19 OR 21 = 23
00010 = 10101 XOR 10111 = 21 XOR 23 = 2 (ball 2)

Thanks @YowE3K and @Bass, you're both quite right. Based on the other comments as well, it appears I read into the question that if a system exists, satisfying the given constraints, then it must be that

each weight is a consecutive power of some base, the least of which is two, making the heaviest at most 16, and the rest known weights as @Bass clarified. It most certainly doesn't work for arbitrary weights.

At best this is a lower bound, if it's even close to the intended answer.

$\endgroup$
  • $\begingroup$ If the weights were 1,2,4,5,6 then the first three weigh 7 and the last three weigh 15. An AND of 7 and 15 is 7, which you are saying is the weight of the third ball, but it actually weighs 4. I don't think your method is going to work. $\endgroup$ – YowE3K Dec 25 '17 at 6:01
  • $\begingroup$ The weights intended by @zimpsonr are 1, 2, 4, 8 and 16, although that was expressed most unclearly in the answer. $\endgroup$ – Bass Dec 25 '17 at 8:59
  • $\begingroup$ Having each weight a power of 2 would solve a more general problem, where you needed to identify each involved ball, given the combined weight of any number of balls. As it happens, I was able to adapt your solution for the case where the only possible weighing results are the combinations of exactly three balls, thus limiting the number of possible weighing results. $\endgroup$ – Bass Dec 25 '17 at 21:51
  • $\begingroup$ Nicely done! Bet yours is general and optimal given a set number of balls, weighings, and balls per weighing. Food for thought. Great question @Oray! $\endgroup$ – zimpsonr Dec 28 '17 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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