Distinct ball weights but balance on the scale

Question

You are given eight identical-looking balls and a two-sided scale. All of the ball weights are distinct, but if you put 4 specific ones on the one side, and the rest on the other side of the scale, they balance themselves.

If you are only allowed to put exactly 4 balls on both sides at a time,

What is the minimum number of weighings required to find the balance in the worst case scenario?

Answer 1

Not a proper solution to the question asked, but per @Oray's request, perhaps a reasonably elegant benchmark?

Label the balls A-H, and start ABCD in the left pan, EFGH in the right. Add a dot to each ball in the heavier pan. For each subsequent weighing, the left pan should contain the lexicographically first combination of four balls among those which distribute the dots as evenly as possible between the two pans, excluding those which have already been tried. For example, the second weighing will be ABEF<>CDGH, since each pan will have two dots regardless of which initial set was heavier.

To take this for a test drive, I took two sets of balls which summed to one, and partitioned each into distinct fractions with coprime denominators. To start, (1,2,3,4)/10 and (1,2,3,5)/11. This does give two 2-subsets that add to 5/10, but as I mentioned above, I don't think this is actually relevant, and you can always add/subtract an epsilon if it bothers you without affecting the results. Then I assigned all 40320 permutations of A-H and counted weighings up to the one that balanced, with the following results.

1 1152
2 1152
3 1264
4 1388
5 1296
6 1396
7 1404
8 1517
9 1530
10 1532
11 1674
12 1782
13 1871
14 1777
15 1645
16 1832
17 1945
18 2028
19 2109
20 2199
21 2146
22 2183
23 1722
24 1033
25 504
26 171
27 38
28 29
29 1

for an average-case of ~13.68...an improvement over brute-force case-checking (17.5), but not as much as I might have hoped. There is something obscenely inefficient going on in my code, as it only checks about 20 cases/second, otherwise would have many more cases checked. That lone straggler, by the way, is:

[A,B,C,D,E,F,G,H]=[44, 10, 50, 11, 30, 20, 22, 33]

and the resulting sequence of marks and weightings:

1 [0, 0, 0, 0, 0, 0, 0, 0] ABCD 0 0 115 105
2 [1, 1, 1, 1, 0, 0, 0, 0] ABEF 2 2 104 116
3 [1, 1, 2, 2, 0, 0, 1, 1] ABCE 4 4 134 86
4 [2, 2, 3, 2, 1, 0, 1, 1] ABDF 6 6 85 135
5 [2, 2, 4, 2, 2, 0, 2, 2] ABCF 8 8 124 96
6 [3, 3, 5, 2, 2, 1, 2, 2] ABDE 10 10 95 125
7 [3, 3, 6, 2, 2, 2, 3, 3] ABGH 12 12 109 111
8 [3, 3, 7, 3, 3, 3, 3, 3] ABCG 16 12 126 94
9 [4, 4, 8, 3, 3, 3, 4, 3] ABDG 15 17 87 133
10 [4, 4, 9, 3, 4, 4, 4, 4] ABEG 16 20 106 114
11 [4, 4, 10, 4, 4, 5, 4, 5] ABFH 18 22 107 113
12 [4, 4, 11, 5, 5, 5, 5, 5] ABCH 24 20 137 83
13 [5, 5, 12, 5, 5, 5, 5, 6] ABDH 21 27 98 122
14 [5, 5, 13, 5, 6, 6, 6, 6] ACDE 29 23 135 85
15 [6, 5, 14, 6, 7, 6, 6, 6] ADEF 25 31 105 115
16 [6, 6, 15, 6, 7, 6, 7, 7] ACDF 33 27 125 95
17 [7, 6, 16, 7, 7, 7, 7, 7] ADEG 28 36 107 113
18 [7, 7, 17, 7, 7, 8, 7, 8] ACDG 38 30 127 93
19 [8, 7, 18, 8, 7, 8, 8, 8] ADFG 32 40 97 123
20 [8, 8, 19, 8, 8, 8, 8, 9] ABEH 33 43 117 103
21 [9, 9, 19, 8, 9, 8, 8, 10] ACFG 44 36 136 84
22 [10, 9, 20, 8, 9, 9, 9, 10] AEFH 38 46 127 93
23 [11, 9, 20, 8, 10, 10, 9, 11] AEGH 41 47 129 91
24 [12, 9, 20, 8, 11, 10, 10, 12] AFGH 44 48 119 101
25 [13, 9, 20, 8, 11, 11, 11, 13] AEFG 46 50 116 104
26 [14, 9, 20, 8, 12, 12, 12, 13] ABFG 47 53 96 124
27 [14, 9, 21, 9, 13, 12, 12, 14] ADEH 50 54 118 102
28 [15, 9, 21, 10, 14, 12, 12, 15] ADFH 52 56 108 112
29 [15, 10, 22, 10, 15, 12, 13, 15] ADGH 53 59 110 110

A long way from the lower bound of 6, but still better than exhaustively testing all 35. The other angle I was considering was to start with 7 weighings such that every triplet of balls shares a pan exactly once, but I suspect pathological cases will stop that from being sufficient, and this would be easier to execute from memory/by hand in a pinch.

UPDATE: Some combinations of 13ths and 14ths got up to a worst-case of 32, suggesting that additional heuristics like @Ben J's are needed to avoid particularly unfortunate orderings (with the same inputs his worst-case is 30, so they do help). I have a couple of refinements in mind myself, but perhaps a more binary-tree oriented approach would be better, if we could map out the feasible sum-orderings (which look to be a MUCH smaller set than I'd imagined, but tricky to make sure I've caught them all...)

...or maybe, per Dave B's suggestion, [1,2,3,25,26,27,28,100] renders the whole exercise moot. Well, at least it behaves interestingly for more uniform distributions. ^_^b

Answer 2

Since the question asks about

[T]he minimum number of weighings required to find the balance in the worst case scenario?

The answer is either

1 (We got lucky, despite having the worst-scenario setup - a lucky guess would always be the minimum, right?)

or

35 (Using an nCr of 8C4, then dividing by two because we count everythig twice - an A-B-C-D / E-F-G-H split is identical to E-F-G-H / A-B-C-D)

But why?

The worst-case scenario is a Jovian setup. If we let the letters A-H represent the weights of the orbs such that A > B > C > ... > H, a Jovian scenario is one where the balance is A (Jupiter) plus the three smallest weights (F + G + H) This is the worst case scenario because no matter how you mix the spheres, the side that contains Jupiter will always outweigh the other side, with the single exception of when Jupiter is partnered with the three lightest ones, which is our solution

Thus

There is no way, within the confines of this puzzle, to extract any additional information about any of the other orbs to take any short cuts. We can identify which orb is Jupiter after only a few moves, but once we have done so we are no closer to finding the correct combination - the only combinations we have ruled out are the exact combinations that we have already tried along the path to discovering that we have a Jupiter orb and a Jovian system.

Assuming 'Worst-Case-Scenario' means that, no matter what our strategy/setup is, we will guess wrong every time until we have 100% certainty:

35 operations is the worst-worst-case scenario, since we cannot gain any additional information about the identities of orbs B through H in a Jovian situation.

Another way to phrase this would be:

Given that there are 35 possible combinations, each attempt will rule out at least one of those 35 possibilities. If we can manipulate the scales in some way to learn more about the identities of the balls and their relative weights, we can potentially rule out more than one. However, when Jupiter is in the mix, we can never learn anything about the relative weights of orbs B-H. We can only figure out that A plus any three is heavier than the remaining four. This knowledge doesn't help us get to the solution any faster. Once we've identified Jupiter, every non-solution trial looks identical to every other non-solution trial, so there is no additional information to be gleaned by doing clever comparisons. Even if we fix Jupiter and only shuffle the remaining orbs, our choices total 7C3, which is exactly equal to (8C4)/2.

Note: Jason Kim has a good point in their partial answer:

If we don't need to actually verify that the last combination works, we can subtract 1 from the total number of weighings. Thus, once we have ruled out 34 of the possible combinations we know what the correct combination is.
However, if we're in a dastardly dungeon where the sealed door won't unlock until the correct distribution of mystic orbs are placed on the correct receptacles, the unlucky adventurers won't get through until their 35th try

Answer 3

Assuming only one combination will balance the scale:

You can fix one ball on one side of the scale. You are then left with 7 balls.

Then:

Divide the 7 balls into two groups of 3 and 4. This can be done in $^7C_4 = 35$ ways.

Answer 4

Partial for now:

A lot of people suggest it is $\dfrac{\dbinom84}2=35.$ We can actually remove $1$ from the answer since if it isn't the others, then we know that it must be the other combination... for a total of $35-1=34.$

I haven't made any significant progress for smaller examples, so this is it for now.

Answer 5

Here of some of my thoughts:

For:

With $4$ balls, you will need $3$ weighings, which is $^3C_1$. (If your initial guess isn't correct, you have no idea which of the $2$ remaining balls is correct). By an inductive logic, this is a minimum for $2k$ balls ($^{2k-1}C_k$).

Against:

There are no sub-combinations of equal weight as the distinct permutation must be unique. This might help in favour of finding a short-cut to a solution.

Also:

If the balls are weighted $b_0\gt b_1\gt\dots\gt b_7$, then the distinct permutation must lie somewhere in-between of this one and its reverse. Again, this might be useful.