The final standings in Group C of the 2010 World Cup were as follows: USA 5, England 5, Slovenia 4, Algeria 1.
Question: given this information, can we reconstruct the results of the individual games? Each team plays each other team once; they get three points for a win, one for a draw, zero for a loss.
First we can tell that USA and England must have had a win and two draws, each; Slovenia, a win, a draw, and a loss; Algeria, a draw and two losses. (In fact you can always reconstruct the number of wins, draws, and losses from the number of points, except in the case of three points, which can be a win and two losses, or three draws.)
Since neither USA nor England have a loss, they must have drawn. Similarly, Slovenia's win must have been against Algeria.
But now there are two possibilities; we have to break the symmetry between USA and England. Let's say, arbitrarily, that USA drew against Slovenia and defeated Algeria, instead of the other way around. (This is, in fact, what happened.) Then Algeria's draw must have been against England, and England's win against Slovenia.
In an alternate universe where USA and England switch roles (does this mean that England was a USA colony in this universe?) USA defeated Slovenia and drew against Algeria, and England draws against Slovenia and defeats Algeria.
Of course, the next question is: given the goal differentials (+1 for USA and England, 0 for Slovenia, -2 for Algeria), can we figure out the margins in the various games? (Assume we know which of the two universes above we're in; for the sake of avoiding cognitive dissonance, say we're in the first one.) Since Algeria was only defeated by a total of two goals, the margin in each of their losses must have been 1. And the margin in the Slovenian win (to Algeria) and loss (to England) must have been the same, namely 1.
If you in addition are given the total number of goals scored (USA 4, Slovenia 3, England 2, Algeria 0) you can reconstruct the scores of each match. I leave this as an exercise for the reader. Hint: start with Algeria.
Another question: is it the "usual case" that individual match results can be recovered from the final standings, or is this unusual? The table of standings in a group in the World Cup has something like thirteen degrees of freedom. Given the number of wins and draws, goals scored, and goals against for three of the teams, we can find the number of losses and goal differential for each team, the number of wins, draws and losses for the fourth team, and the goal differential of the fourth team. We need one more piece of information - say, the number of goals scored by that fourth team - to reconstruct the whole table. We're trying to derive twelve numbers from this (the number of goals scored by each team in each match). It will be close.
In an n-team round robin, the number of degrees of freedom in the table of standings grows linearly with n, but the number of games grows quadratically with n. For large n it would be impossible to do this reconstruction; for n=1 it would be trivial.
Subscribe to:
Post Comments (Atom)
4 comments:
According to my (computerized) efforts so far, none of Groups A through D in this World Cup is uniquely determined by the score table. Groups A, C, and D have two possibilities (for the scores of *all* of the matches), while Group B has three possibilities.
According to the same program, the number of different possibilities for the match scores for Groups A through H in the previous World Cup are 11, 1, 5, 3, 2, 6, 1, and 8. That is, I claim only Groups B and G are uniquely recoverable.
This is modulo potential errors and the fact that I'm not using advanced tie-breaking reasoning. I hope it's right ...
"In fact you can always reconstruct the number of wins, draws, and losses from the number of points, except in the case of three points, which can be a win and two losses, or three draws."
Even in this case, it is possible to reconstruct the number of wins, draws, and losses for each team, if you know the other teams points: The total number of points given for a win is 3 and for a draw it is 2, so you can calculate the number of draws in the group. This way, you can calculate how many of the teams with 3 point who got them by playing 3 draws. And this must be either all the teams with 3 point or none of them, since if a team plays 3 draws, all the other teams played at least one draw.
Is the same thing possible for 5 teams?
Sune, you cannot determine wins, losses, and draws from just the points if there are 5 or more teams per group. There are tons of different point distributions that demonstrate this, but I like 10-4-4-4-4. In that case, one team drew all the rest, but you can't tell which.
In some cases, like 6-6-6-3-3, you can't even determine the win-loss digraph up to isomorphism.
It's no surprise that when teams tie in points, it will often be impossible to reconstruct the individual match results from the points -- the usual difficulty of nontrivial automorphism groups that mathematicians are well-accustomed to struggling with!
So it's probably worth mentioning that in four-team groups with 3 points for a win and 1 point for a draw, if the four teams end up with distinct point totals then it's always possible to reconstruct who won (or drew) each match.
This fails with five-team groups and any point assignments. For instance even if you can tell that the five individual records were:
A: 3W 1T
B: 2W 2L
C: 1W 2T 1L
D: 1W 1T 2L
E: 1W 3L
then E could have beaten any of B, C, D, and there's exactly one set of outcomes consistent with each of those possibilities.
Post a Comment