11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ By carrying the balls, can I know which ball is heavier than the other (without knowing their weights)? $\endgroup$ – Wais Kamal Sep 30 '18 at 19:49
  • $\begingroup$ @WaisKamal every time you weight, it says which side is heavier or lighter, nothing more. it is old two sided scale. $\endgroup$ – Oray Sep 30 '18 at 19:50
  • 1
    $\begingroup$ @WaisKamal this is not lateral thinking, so only option is weighing on the scale and see which one is heavier or lighter. $\endgroup$ – Oray Sep 30 '18 at 19:53
  • 1
    $\begingroup$ Honestly, I'm not sure it would make things any easier if subsets could be equal. @_@ $\endgroup$ – Zomulgustar Oct 1 '18 at 15:36
  • 1
    $\begingroup$ It would appear my above confidence was misplaced... but as I always tell my students, if you're always getting the right answers, you're not asking hard enough questions... $\endgroup$ – Zomulgustar Oct 3 '18 at 15:59
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "(1,2,3,4)/10 and (1,2,3,5)/11" Note that this is equivalent to (1,2,3,4)*11 and (1,2,3,5)*10. If you share your code, I can see whether I see a way to improve it. $\endgroup$ – Acccumulation Oct 2 '18 at 21:11
  • $\begingroup$ Yes, even though sagemath handles rationals, ints are much faster (and already in use above), and using numpy vectors rather than lists of ints should be another big improvement...will add to my google drive and post link later if there's interest. Tested up through 11ths+12ths and 12ths+13ths in the meantime, still nothing worse than 29, though they do become more common proportionately. Avg now stands at ~13.73 $\endgroup$ – Zomulgustar Oct 2 '18 at 22:53
  • $\begingroup$ In the meantime...to turn this into a legitimate upper bound would require testing sets of weights that realize every feasible ordering of sums...@_@ $\endgroup$ – Zomulgustar Oct 2 '18 at 23:16
  • $\begingroup$ On second thought...it's really only the disjoint sums whose order matters...2^34 isn't completely insane to search exhaustively, and we should be able to eliminate some pretty big subsets of that... think think $\endgroup$ – Zomulgustar Oct 3 '18 at 1:33
  • 1
    $\begingroup$ I found that I could get the worst case down to 28 attempts (13.66 average) for the weights you used. The difference was that I tried to keep the balls with the most and fewest marks on the same side of the scale, to keep the amount of marks on different balls from getting too uneven. Here is the code I used. $\endgroup$ – Ben J Oct 3 '18 at 13:17
5
+25
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Let me know if more detail is needed to prove the statement following the But Why? header. It seems self-evident to me, but that might be because I do a lot of Kakuro puzzles $\endgroup$ – Dave B Oct 3 '18 at 14:36
  • $\begingroup$ Glad I didn't spend too much more time refining that code, now... $\endgroup$ – Zomulgustar Oct 3 '18 at 15:04
  • $\begingroup$ Yeah - I started along a similar vein as you did, but then I got thinking about what the actual worst-case scenario would actually look like. Starting from the worst possible distribution of weights, the above conclusion was inevitable. $\endgroup$ – Dave B Oct 3 '18 at 15:42
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I would say, good start... $\endgroup$ – Oray Sep 30 '18 at 19:47
  • $\begingroup$ So you mean it's not right?! $\endgroup$ – Wais Kamal Sep 30 '18 at 19:47
  • 1
    $\begingroup$ I say it is not minimum :) $\endgroup$ – Oray Sep 30 '18 at 19:48
  • 1
    $\begingroup$ @Oray - Unless you accept that the minimum is 1 (Lucky Guess!) or that you don't need to make the final measurement once you're 100% sure of your choice, this is actually correct for the worst-case scenario. $\endgroup$ – Dave B Oct 3 '18 at 16:06
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The question could be clearer whether the count needed is to identify the correct combination, or to actually place it on the balance. I've been working from the latter assumption... $\endgroup$ – Zomulgustar Oct 3 '18 at 3:23
  • $\begingroup$ It says find the balance, so I went with the first :) $\endgroup$ – Jason Kim Oct 3 '18 at 3:36
  • $\begingroup$ :P We should ask for clarification... $\endgroup$ – Jason Kim Oct 4 '18 at 2:57
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I can't understand this answer. There are 8 balls. What does "which if the 2 remaining balls is correct" mean? $\endgroup$ – Kate Gregory Oct 1 '18 at 15:56
  • $\begingroup$ @KateGregory; it's not 4 balls on either side, it's the smaller case of just 4 balls. if you weigh say ABvCD, and that's not it, you still have no way to decide between AC or AD. $\endgroup$ – JMP Oct 1 '18 at 16:11

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.