This is in continuation of Which is Which
You have ten balls - five red and five black, having precisely the same shape and size. All the red balls weigh differently, i.e. one of them is very heavy
, the other heavy
, another is medium
, another is light
and the fifth very light
. Each red ball
has a black twin of the same weight. It is known that:
(i) A very heavy
and a medium ball
put together weigh as much as two heavy balls
(ii) A heavy
and a light ball
put together weigh as much as two medium balls
(iii) A medium
and a very light ball
put together weigh as much as two light balls
Determine the least number of weighings required on a balancing scale to determine which is which, given that:
(i) Each ball can only be paired with a ball of like color before weighing, but pairing a given ball with its twin is not allowed.
(ii) Each ball can also be paired with its twin (in addition to a ball of like color) before weighing.
Sorting just the five red balls can be done 7 weighings. Doing this with the black balls will bring the total to 14.
But with the red already sorted, comparing the known medium ball to four of the five black balls plus two additional weighings can sort the black balls, making a total of 13 weighings.
I tried some more complex methods which saved one more weighing, 12 total. But that got very messy for the more complicated subcases. The biggest problem I faced was the relative lack of equal weighings compared to the number of unequal weighings. It was very common for me to find a 2:1:2, or sometimes 3:4:3, distribution of weighing results to be the best option. Anything better (closer to 1:1:1) was rare.
Information theory puts a limit of log(120^2)/log(3) = 8.7155 rounded up to 9 as the minimum number of weighings. But this assumes that the weighings are dividing the solution space efficiently. By my efforts I found a 2.5 factor of reduction to be more realistic. Using that instead of a factor of 3 implies log(120^2)/log(2.5) = 10.4497 rounded up to 11 as a more realistic minimum.