Problem With Balls

Scroll to see replies

Reply 40

Gauss

cms271828

...so in this case W(12)=3, W(13)=4

Do you have a proof that W(13) = 4?

I claim W(13) = 3.

Galois.

Reply 41

cms271828

Well I can certainly do it in 4, but havent yet tried do it in 3, but I'm
very confident that it is impossible, just a hunch I spose.
I would rather look for some more general answers then spend time proving
W(13)=4.

Reply 42

SsEe

OK. It's far too late. Here goes.

If there was such a way to always weigh 4 balls on each side but do it in such a way that each ball follows its own unique path involving left pan, right pan and unused then depending on which way the scales tip on each weighing we'd be able to work out which was the oddball and its weight.

So, putting left numbers in left pan and right numbers in right pan:
1,2,3,4 against 5,6,7,8
1,5,6,9 against 2,8,10,11
3,5,8,12 against 4,6,9,11

Say the scales went right pan heavy, equal, equal then 7 is heavy.
Equal, left pan heavy, equal then 10 is light.
Try with others to convince yourself.

A property that this system must have is shown in this example:

Weigh 1,2,3, against 4,5,6. Say 1,2,3 is heavier.
Now weigh 4,7,8 against 1,9,10 . Say 1,9,10 is heavier.

As both weighings were unbalanced the oddball must've been present in both. The only ones in both weighings were 1 and 4. From the first one either 1 is heavy or 4 is light. And the same for the second. So there is no way of telling which of 1 or 4 it is. This is only hypothetical but it shows a possibility that must be avoided to make the system work every go. Basically no ball is allowed to "mirror" another's path. So if ball 1 went in the left pan on the 1st weighing, then right then right. No other ball could take the path right, left, left or you wouldn't be able to tell if eg it was ball 1 that was heavy or ball x that was light.

If any ball was not used and it turned out to be the odd one there would be no way of knowing whether it was heavy or light after the 3 weighings. So each ball is used at least once. So equal, equal, equal is impossible.
Also, for reasons that I won't explain but I have scribbled on a piece of paper, no ball may appear in the same pan for all 3 weighings. If it did then another would have to appear in the other pan 3 times and that would be a mirror which isn't allowed. So no pan can be heavy 3 consecutive times.

Reply 43

cms271828

Suppose you were to use the scales 3 times, this would lead to a maximum of 27 possible outcomes, but with some weighings, it may be impossible for ,say a balance, thus reducing the possible number of outcomes.

I haven't quite proved W(13)=4 yet, but W(14)=4 since with 14 balls there are 28 outcomes >27, so it is impossible to solve 14 balls in 3 weighs.
By the same principle, it is impossible to solve 41 balls in 4 weighings, thus
W(41)>=5.

It would be nice if W(40)=4, but I am very doubtful of this. If you weighed 14 balls against 14, and it were level, then the oddball is in the remaining 12, and thus can be found in 3 weighings. But then theres the problem if it doesn't balance, so I reckon W(40)=5, I'm sure someone will crack it soon, it can't be that hard, can it??