All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Which is Which II (Posted on 2012-02-15)
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 and:

(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.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Thoughts Comment 4 of 4 |
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.

 Posted by Brian Smith on 2016-07-09 23:13:47

 Search: Search body:
Forums (0)