# Minimum number of tries to find the balance!

There are 8 distinct weights and a two-pan equal arm balance scale, and you know the weights' weight order: the lightest is numbered as 1 and the heaviest is numbered as 8 and the rest accordingly.

It is given that if you put 4 of them on the one side of the scale and the other 4 on the other side, two-pan will stay balanced in the middle. Unfortunately you do not know which weights you need to put to both sides to get the balance.

So What is the minimum number of tries on the scale to find the balance in the worst optimal case?

Note: I am looking for non-programming answer, because there is one!

• $x$ number of tries – Anthony Pham Apr 3 '16 at 22:21
• If you get lucky, the answer is 1, if it does not have to be verified the answer can even be 0. – k-l Apr 3 '16 at 22:23
• @KiranLinsuain you should have posted this very clever answer! – Oray Apr 4 '16 at 6:31

## 1 Answer

If you sort the weights on each side in order of their weight and label them L1,L2,L3, and L4 on the left (LHS) and R1,R2,R3, and R4 on the right (RHS), then for a valid balance it must be the case that at least one of the LHS weights is greater than the corresponding RHS weight, and at least one of the LHS weights is less than the corresponding RHS weight.

If this was not the case then we could pair the LHS weights up with the corresponding RHS weights and show for example L1 < R1 and L2 < R2 and L3 < R3 and L4 < R4 so necessarily L1+L2+L3+L4 < R1+R2+R3+R4 so LHS < RHS.

By inspection (and use of the back of an envelope), the only 20 sets of weights that match this requirement are (assuming weight 8 is on the LHS), LHS = 8761 or 8751 or 8741 or 8732 or 8731 or 8721 or 8651 or 8641 or 8632 or 8631 or 8621 or 8543 or 8542 or 8541 or 8532 or 8531 or 8521 or 8432 or 8421 or 8321. So at worst case you would need to do 19 weighings to find the balance.

But you can do better than that by taking into account the relative weight of each of the possible LHS weights. For example, 8761 > 8751 > 8741 > 8731 > 8721 and 8732 > 8632 > 8532 > 8432. If the possible LHS distributions could all be ordered then a simple binary search would only require a worst case 4 weighings to find the balance, but unfortunately this doesn't quite work as, for example, we can't confirm if 8751 is heavier or lighter than 8732. Without using a computer to confirm I believe this adds at worst two additional guesses to find the balance. So my answer is still 6 guesses (see below).

After posting the answer above I wrote a small emulator which produces 8 random hidden weights, adjusts one to achieve balance for a randomly chosen LHS and RHS combination, then sorts the weights from lightest to heaviest. I get to guess by 'asking' if a chosen LHS balances. Using an approximation to the binary search technique it never took me more than 6 guesses. The following is typical of the results I got the following : (which matches my prediction)

 8621:LHS light
8721:LHS light
8732:LHS Heavy
8731:Balance ->2.14310676651075 : 2.14310676651075
1 0.0885500395670533
2 0.111781250685453
3 0.19566530152224
4 0.564735802356154
5 0.57383177918382
6 0.892757934285328
7 0.914650390157476
8 0.944241035263985

8621:LHS light
8721:LHS Heavy
8641:LHS Heavy
8632:LHS Heavy
8631:LHS light
8532:Balance ->2.0075786341913 : 2.0075786341913
1 0.0320988968014717
2 0.116770339896902
3 0.409353783586994
4 0.489856718573719
5 0.493891363032162
6 0.499285214347765
7 0.986337804468349
8 0.987563147675246

8641:LHS light
8731:LHS light
8741:Balance ->1.88245022343472 : 1.88245022343472
1 -0.384558940306306
2 0.0816141343675554
3 0.311678517377004
4 0.328032567398623
5 0.574120345525444
6 0.915037226164714
7 0.961626660544425
8 0.977349935797974

8621:LHS light
8721:LHS light
8741:Balance ->1.88245022343472 : 1.88245022343472
1 -0.384558940306306
2 0.0816141343675554
3 0.311678517377004
4 0.328032567398623
5 0.574120345525444
6 0.915037226164714
7 0.961626660544425
8 0.977349935797974

8621:LHS Heavy
8521:Balance ->1.22040742682293 : 1.22040742682293
1 -0.12568692304194
2 0.142502291826531
3 0.143699390348047
4 0.1617623900529
5 0.20363402296789
6 0.282742973649874
7 0.63220267277211
8 0.999958035070449

8621:LHS light
8721:LHS Heavy
8631:LHS light
8641:LHS Heavy
8632:LHS Heavy
8541:Balance ->1.38451580004767 : 1.38451580004767
1 -0.157035004347563
2 0.0434248903766274
3 0.207215692382306
4 0.281037320150062
5 0.355567643884569
6 0.407183179398999
7 0.726692037889734
8 0.904945840360597

• "but unfortunately this doesn't quite work as, for example, we can't confirm if 8751 is heavier or lighter than 8732" -- Yes we can. Weigh 51 against 32. If 51 is lighter or heavier than 32, then 8751 will necessarily be heavier than 8732 – Tim C Apr 4 '16 at 18:27
• I mean we can't confirm it without making a weighing. My point was that we can't put the 20 possibilities into a monotonic sequence independent of the individual weights (if we could then the binary search would be simple). – Penguino Apr 5 '16 at 3:26