matt@oddjob.UChicago.UUCP (Matt Crawford) (05/30/84)
There are 24 cases to distinguish and only 27 possible outcomes of 3 successive 3-valued comparisons, so every test must divide the remaining solution space up into 3 nearly equal portions. The first test will split the 24 possible answers into 3 disjoint sets of 8. The second test will split the 8 into groups of 2, 3, and 3. The third test must then give the answer. Call the coins a b c d e f g h i j k l. compare a+b+c+d : e+f+g+h = then i,j,k,l is heavy or light (8 possibilities) compare a+b+c : i+j+k = then l is heavy or light (2) compare a : l = error > l is light < l is heavy > then i,j,k is light (3) compare i : j = k is light > j is light < i is light < then i,j,k is heavy (3) compare i : j = k is heavy > i is heavy < j is heavy > then a,b,c,d is heavy or e,f,g,h is light (8) compare a+b+c+e+f : i+j+k+l+d = then g,h is light (2) compare g : h = error > h is light < g is light > then a,b,c is heavy (3) compare a : b = c is heavy > a is heavy < b is heavy < then d heavy or e,f light (3) compare e : f = d is heavy > f is light < e is light < then a,b,c,d is light or e,f,g,h is heavy (8) compare a+b+c+e+f : i+j+k+l+d = then g,h is heavy (2) compare g : h = error > g is heavy < h is heavy > then d light or e,f heavy (3) compare e : f = d is light > e is heavy < f is heavy < then a,b,c is light (3) compare a : b = c is light > b is light < a is light ___________________________________________________ Matt ARPA: crawford@anl-mcs.arpa Crawford UUCP: ihnp4!oddjob!matt