QUOTE(Zebbeddee @ Aug 20 2003, 05:54 AM)
Then following matches should be played.
GH, EF, CD, AB, GF, EG, CE, AC, GD, ED, CG, AE, GB, EB, CB, AG.
This answer does not work in all cases. Let's say G is the best player. G is the only opponent H played. Since the only information we have about H is that H lost to G, and
everyone lost to G, we have no way of knowing how H would fare vs. any of A through F.
QUOTE(kmsouthern @ Aug 20 2003, 08:46 AM)
G vs. B
G vs. E
B vs. E
B vs. C
E vs. C
E vs. A
C vs. D
C vs. F
C vs. A
A vs. D
A vs. F
A vs. H
H vs. F
F vs. D
B vs. D
E vs. D
This presents a similar, though slightly more subtle, conundrum. G and H each play two players, for a total of four (A, B, E and F). What if all of ABEF are better than both of G and H? There are multiple ways ABEF could turn out amongst themselves, but there's nothing left to distinguish between G and H.
One thing of which I'm absolutely certain with this puzzle is that the solution hinges on eliminating redundant information. For example, if A beats B and B beats C there's no information to be gained by having A play C; we already know the outcome. However, it's possible that both B and C will both win or both lose vs. A, so we need some way to distinguish between them. Having them play each other will tell us which is better, but it might not be the most "efficient" way. The solution is more likely to involve B and C having some other opponent in common, with them having common opponents etc. leading
indirectly back to A, so that finding the answer for B vs. C sort of "piggybacks" on finding other answers as well.
I'm also pretty sure that no "static" set of pairings will work. In other words, you can't just say at the outset to do these 16 matches and the answer will pop out. It's more like the coin problem, where you do some set of matches, then if you get one kind of result you do X but if you get another result you do Y. I can't prove that (the proof itself would be extremely hairy) but I'm pretty certain nonetheless. The most promising approaches I've found so far involve doing seven matches as though it's a single-elimination tournament yielding a "champion" who can then be left out of the remaining stages, then trying to sort out the seven remaining players in no more than nine more steps. I can definitely guarantee a seventeen-step solution in a couple of different variants, and average just over fifteen, but so far there always seem to be one or two "pathological" cases that prevent a guarantee of sixteen.