Best Answer plasmid, 28 November 2013 - 08:04 AM

Spoiler for theoretical minimum

There are 5! = 120 ways of arranging weights 1-5 to balls A-E.

We seek a solution where a set of N weighing outcomes leads to an unambiguous assignment to one of those 120 possible arrangements.

If possible weighing outcomes are "left side heavier", "right side heavier", or "both equal" then after N weighings there are 3

3

We seek a solution where a set of N weighing outcomes leads to an unambiguous assignment to one of those 120 possible arrangements.

If possible weighing outcomes are "left side heavier", "right side heavier", or "both equal" then after N weighings there are 3

^{N}possible sets of outcomes.3

^{5}= 243 while 3^{4}= 81, so 5 is the minimum theoretically possible that can distinguish among the 120 possible arrangements.
Spoiler for achieving that minimum

Go to the full post
Weigh A+B versus C+D, then weigh A+C versus B+D, then weigh A+D vs B+C. There are then two possible scenarios to worry about: either 1) none of those weighings led to balance, or 2) one of those weighings led to balance.

If none of the first three weighings are balanced, then E must be either 2 or 4.

If any of the first three weighings are balanced, then E must be 1, 3, or 5.

The reason for this is that, if E is either 1, 3, or 5, then there exists some combination of pairs of A, B, C, and D such that the two pairs are equal weight, and the first three weighings tested all possible pairings. If E is 2 or 4, then A, B, C, and D must contain three odd numbers and one even number so they will never be balanced.

If none of the first three weighings are balanced, then E must be either 2 or 4.

If any of the first three weighings are balanced, then E must be 1, 3, or 5.

The reason for this is that, if E is either 1, 3, or 5, then there exists some combination of pairs of A, B, C, and D such that the two pairs are equal weight, and the first three weighings tested all possible pairings. If E is 2 or 4, then A, B, C, and D must contain three odd numbers and one even number so they will never be balanced.

Spoiler for scenario 1: no balanced weighings in the first three

We know that E must be either 2 or 4. Suppose E is weight 4: then the mass with weight 5 will always be on the heaviest side of the first three weighings and can be identified, but the mass with weight 1 will not always be on the lightest side (1+5 > 2+3). Suppose E is weight 2: then the mass with weight 1 will always be on the lightest side but the mass with weight 5 will not always be on the heaviest side. So after the first three weighings, you will be able to identify the weight of E based on whether there was a mass that was always on the lighter side or a mass that was always on the heavier side, and you will know either the mass with weight 1 (if E is weight 2) or the mass with weight 5 (if E is weight 4). Label the remaining unknown masses X, Y, and Z.

If you know weights 1 and 2, you can figure out the rest by weighing 1+X versus Y followed by one more weighing.

Possible values for (X,Y) after the fourth weighing

1+X > Y: (4,3), (5,3), (5,4)... weigh Z versus Y+1 and you'll be able to distinguish these scenarios

1+X = Y: (3,4), (4,5)... weigh Z versus X and you'll be able to distinguish these scenarios

1+X < Y: (3,5)... you're done

If you know weights 4 and 5, you can figure out the rest by weighing X+Y versus 4 followed by X versus Y.

Possible values for (X,Y) after the fourth weighing

X+Y < 4: (1,2), (2,1)...

X+Y = 4: (1,3), (3,1)...

X+Y > 4: (2,3), (3,2)... in any of those cases you can weigh X versus Y to figure out the rest of the weights.

If you know weights 1 and 2, you can figure out the rest by weighing 1+X versus Y followed by one more weighing.

Possible values for (X,Y) after the fourth weighing

1+X > Y: (4,3), (5,3), (5,4)... weigh Z versus Y+1 and you'll be able to distinguish these scenarios

1+X = Y: (3,4), (4,5)... weigh Z versus X and you'll be able to distinguish these scenarios

1+X < Y: (3,5)... you're done

If you know weights 4 and 5, you can figure out the rest by weighing X+Y versus 4 followed by X versus Y.

Possible values for (X,Y) after the fourth weighing

X+Y < 4: (1,2), (2,1)...

X+Y = 4: (1,3), (3,1)...

X+Y > 4: (2,3), (3,2)... in any of those cases you can weigh X versus Y to figure out the rest of the weights.

Spoiler for scenario 2: one of the first three weighings was balanced

Relabel the masses A, B, C, and D with labels M, N, P, and Q such that M+N = P+Q is the weighing that was balanced. The other two weighings would be M+P versus N+Q and M+Q versus N+P. Without loss of generality, have label M go to the mass that was heaviest in both of those subsequent weighings (one mass must have been on the heaviest side in both of them), and you'll know that M is the heaviest out of the four and N must therefore be the lightest.

For the fourth weighing, weigh P versus Q. Label the heavier of them R and the lighter S. You now know that the order of the four weights is M > R > S > N, and all you have to do is find out whether E is 1, 3, or 5 and you'll have the problem solved.

Weigh E versus S+N. If E=1, then E < S+N. If E=3, then E = S+N. If E=5, then E > S+N.

For the fourth weighing, weigh P versus Q. Label the heavier of them R and the lighter S. You now know that the order of the four weights is M > R > S > N, and all you have to do is find out whether E is 1, 3, or 5 and you'll have the problem solved.

Weigh E versus S+N. If E=1, then E < S+N. If E=3, then E = S+N. If E=5, then E > S+N.