8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ $x$ number of tries $\endgroup$ – Anthony Pham Apr 3 '16 at 22:21
  • 1
    $\begingroup$ If you get lucky, the answer is 1, if it does not have to be verified the answer can even be 0. $\endgroup$ – k-l Apr 3 '16 at 22:23
  • $\begingroup$ @KiranLinsuain you should have posted this very clever answer! $\endgroup$ – Oray Apr 4 '16 at 6:31
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. $\endgroup$ – Rubio Sep 2 at 4:25
3
$\begingroup$

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 
$\endgroup$
  • $\begingroup$ "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 $\endgroup$ – Tim C Apr 4 '16 at 18:27
  • $\begingroup$ 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). $\endgroup$ – Penguino Apr 5 '16 at 3:26
0
$\begingroup$

The worst-case scenario requires 8 weighings to identify the balanced permutation, and a 9$^{th}$ weighing to verify it.

As Penguino pointed out:

  • A balanced permutation will not have each of the four balls on one side lighter than a different one on the right. Thus, 8642 cannot balance because $8>7$, $6>5$, $4>3$, and $2>1$. But 8641 could balance because $1<2$.
  • This leaves 21 potential balancing scenarios, which they listed (but missed 8431).

I've arranged the 21 into a sort of tree:

$$\begin{matrix} \\ &&& 8761 & & & &\\ &&& 8751 & 8651 & & &\\\ &&& 8741 & 8641 & 8541 & & \\ && 8732& 8731 & 8631 & 8531 & 8431 & \\ &&& 8721 & 8621 & 8521 & 8421 & 8321 \\ && 8632\\ 8543 & 8542 & 8532\\ & & 8432 \end{matrix}$$

These permutations are partially ordered. Any entry directly below or directly to the right of another must weigh less than that other. I.E., we know 8741 weighs less than 8751 because $4<5$. Likewise by transitivity, we know 8421 must weigh less than 8751.

Going along the other diagonal, we don't know for sure about the relative weights. For example, we can't predict which of 8541 and 8621 weighs more without weighing. There are a few others that are not shown clearly, due to the 2-dimensional nature of the chart. For example, we know 8632 weighs more than 8631, even though it's below, to the left.

The longest chains are from 8761 to 8321. There are 16 of them, each of length 9.

The best choice for first weighing is 8631. This permutation has 8 heavier permutations and 6 lighter ones. Thus weighing it will eliminate at least 7 permutations (including 8631, itself).

The worst-case is when 8631 weighs more than its counterpart, eliminating only 7 cases, leaving 14:

$$\begin{matrix} \\ &&& 8761 & & & &\\ &&& 8751 & 8651 & & &\\\ &&& 8741 & 8641 & 8541 & & \\ && 8732& 8731 & & & & \\ &&& 8721 & & & & \\ && 8632\\ 8543 & 8542 & 8532\\ && 8432 \end{matrix}$$

The next best choice is 8741, which will eliminate 3 cases if it is lighter than its counterpart, and 5 cases if it is heavier. Worst case: lighter, leaving us with 11 (rearranging columns for clarity of ordering):

$$\begin{matrix} \\ 8732 & & & & 8731 \\ & & & & 8721 \\ & & & 8651\\ & & & 8641 \\ & 8543 \\ & 8542 & & 8541\\ 8632 & 8532 & 8432 \\ \end{matrix}$$

At this point, no chain is longer than 4 permutations, so no guess can be guaranteed to eliminate more than 2 options. There are 4 guesses: 8731, 8641, 8542, and 8532, which, between them are guaranteed to eliminate 8 permutations, leaving us with three.

Of the remaining options, the longest possible chain is of length 2, so no guess can be guaranteed to remove more than one permutation. For example, the last three might be: 8732, 8632, 8541. Two more weighings are required to limit the options down to 1 permutation.

So, one possible worst-case set of weighings is:

  • First: 8631: result: heavy, reduce 21 to 14
  • Second: 8741: result: light, reduce 14 to 11
  • Third: 8731: result: heavy, reduce 11 to 9
  • Fourth: 8641: result: light, reduce 9 to 7
  • Fifth: 8542: result: light, reduce 7 to 5
  • Sixth: 8532: result: heavy, reduce 5 to 3
  • Seventh: 8632: result: light, reduce 3 to 2
  • Eighth: 8732: result: heavy, reduce 2 to 1.
  • Conclude: 8541 is the balanced permutation.

There are other options than the above, for example first and second weighing of 8541, 8731 is guaranteed to reduce the number of permutations to at most 11, as well.

But in any case, no matter the algorithm chosen, it could take up to 8 weighings to identify the correct permutation, and a 9$^{th}$ weighing to verify that it does balance.

$\endgroup$

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.