Weighing half-balls

Question

A bearing factory cuts four solid steel balls into halves by rolling them through the vertical laser and then drops into a collecting bin. The eight half-balls looks identical but due to rail precision error the slice makes halves with 1gram difference in weight. To sort them into four 100g pair with lighter and heavier halves,a digital and/or the balance scale are available for use. How many weighings is needed?

Answer 1

3 is the worst-case bound, but you can do better on average by enabling short-circuit outcomes using a digital scale. Number the 8 things 1-8.

1. First weigh 1234.
   1. If you get 4-0, that is, HHHH (or LLLL), you're immediately done - (15)(26)(37)(48) works. This happens with probability $1/35$, saving you 2 weighings.
   2. If you get 3-1, probability $16/35$ (WOLOG presume you've gotten HHHL unknown order), next weigh 1256. Note that 12 cannot be LL, 56 cannot be HH.
      1. If this second weighing gets HHHL, 12 must be HH, and you save the third weighing as (17)(28)(34)(56) works. This happens with probability $1/4$.
      2. Similarly, if the second weighing gets HLLL, 56 must be LL, and (12)(35)(46)(78) works.
      3. If you get 2-2, simply weigh 12 itself, and you can still figure it out.
         1. If HH, then (15)(26)(34)(78)
         2. If HL, then (12)(56)(37)(48)
   3. If you get 2-2, still weigh 1256 next.
      1. If you get HHHH or LLLL, you save the third weighing with probability $1/18$ - (13)(24)(57)(68) works.
      2. If you get HHHL (HLLL similar), weigh 12 itself:
         1. If HH, then (13)(24)(56)(78)
         2. If HL, then (12)(34)(57)(68)
      3. If you get HHLL, again weigh 12 itself:
         1. If HH or LL, then (13)(24)(57)(68)
         2. If HL, then (12)(34)(56)(78)

Therefore, you can save $1/35\times2+16/35\times2/4+18/35\times1/18$ to use $94/35$ weighings on average.

Answer 2

Put all the 8 halves on the digital scale. It will read 400 gm (not considered as a reading as this is a known fact).

Remove 2 halves at a time and read the digital scale. If the weight reduces by 101 gm, it means HH - two heavier halves were taken out. Put them separate. if the weight reduces by 99 gm, it means LL - two lighter halves were taken out. Otherwise, LH - two complementary halves were taken out completing one pair. In either of the case, keep the comppair separate.

Do this 2 more times, you'll 3 pairs of halves out. And it is known to you whether they are LL, LH or HH. Basis this, you already know the combination in the last pair that is still on the scale (so no need to get the scale reading).

Now, all you need to do is arrange them into complementary pairs of halves since you already know the combinations taken out of the scale.

So, in total, this can be done with 3 readings of digital scale.

Answer 3

It seems like 4 balance weighings is an upper bound. In some outcomes, we don't find out the individual weights of some halves. But they can be paired up correctly nonetheless.

Note also that any partitioning of the 8 halves into 4 pairs can only have a small number of "configurations", by counting mixed pairs (M), pairs with 2 heavy halves (H) and pairs with 2 light halves (L). The possible configurations are (4M), (2M,1L,1H), (2L,2H). Our target is to find a partitioning with (4M).

Name the half-balls 1...8. Weigh 1 against 2 (1).

Case 1: 1 and 2 are not equal. Weigh 1+2 against 3+4 (2). The result will tell you that 3 and 4 are either both heavy, both light, or mixed. Now weigh 1+2 against 5+6 (3). Again, this will tell you whether 5 and 6 are heavy, light, or mixed. Whatever the outcomes are, you can infer enough to pair everything up. For example, if 3 and 4 are heavy, and 5 and 6 are mixed, then 7 and 8 are light. If 3 and 4 are mixed, and 5 and 6 are mixed, then 7 and 8 are mixed. Et cetera. In any event, keep any known mixed pairs together, and pair up light+heavy halves to get the others.

Case 2: 1 and 2 are equal. Weigh 1+2 against 3+4 (2). If they are equal, we are done because we know 1234 are equal, thus 5678 are equal to each other and we can just make pairs. So we only care about when 1+2 are not equal to 3+4. Assume 1+2 is heavier (we can reverse all subsequent logic if 1+2 is lighter).

So we know that 1 and 2 are heavy, and we know that 3 and 4 are either mixed or both light. Weigh 3+4 against 5+6 (3). If 5+6 is lighter, then 3 and 4 are mixed, 5 and 6 are light, and 7 and 8 are mixed. If 5+6 is heavier than 3+4, then 3 and 4 are light [proof: assume 3 and 4 are mixed. then 5 and 6 are heavy, making for a total of at least 5 heavy halves (1, 2, 5, 6, and either 3 or 4)] and we can weigh 5 vs. 6 (4) to determine the rest of the halves.

Finally, if 5+6 is equal to 3+4, then either each of those pairs is mixed, or each of those pairs is light. If each pair is mixed, then 7 and 8 must be light. If each pair is light, then 7 and 8 must be heavy. You can determine which of these is the case by weighting 1 against 7 (4).

Answer 4

Using Balance Scale with 3 trials or less :

1st) Place 4 halves on each pan . Always rotate the scale 180° when it tilt to right so we have 3 cases:

HHHH > LLLL

HHHL > LLLH

HHLL = HHLL

From the tilted cases in 1st trial :

2nd) Place 2 halves on each pan from 1st trial's left pan .We have 2 cases:

HH = HH with (LLLL) set aside (only case done with 2 trials)

HH > HL with (LLLH) set aside (done with the next trial)

3rd) Replace the 4 halves on the scale with 4 set aside halves. 2 halves on each pan and we are done with 1 case.

LH > LL with (HH) (HL) set aside

From the balance case in 1st trial :

2nd) Place 2 halves on each pan from 1st trial's left pan .We have 2 cases:

HL = HL with (HHLL) set aside (done with the next trial)

HH > LL with (HHLL) set aside (done with the next trial)

3rd) Replace the 4 halves on the scale with 4 set aside halves. 2 halves on each pan and we are done with 4 cases.

HL = HL with (HL)(HL) set aside
HH > LL with (HL)(HL) set aside

HL = HL with (HH)(LL) set aside
HH > LL with (HH)(LL) set aside