//---------------------------------------------------------------------- // enigma1365.c (c) 2005 by Charles Petzold // // "European Champions Leagues" by Richard England, New Scientist, 5 November 2005, page 50 // // // 4 teams in each group playing each other twice. // Score 3 points for a win, 1 point for a draw // Top 2 teams in each group move on. // 8 matches have already taken place with 4 to go. // In 5 groups, two teams have already assured themselves of moving on, // but all with a different scoring pattern. // What are the total draws so far? //---------------------------------------------------------------------- #include // The match array has num elements, each can be 0 (first team win), // 1 (second team win), or 2 (a draw). int NextPossibility(int match[], int num) { int iFlip = 0; while (1) { if (iFlip == num) return 0; match[iFlip] += 1; if (match[iFlip] == 3) match[iFlip] = 0; else return 1; iFlip++; } } // Based on the players array, the outcomes array, calculate a // scores array for the 4 teams. void Tally(int players[][2], int outcomes[], int num, int scores[]) { int i; // Initialize the scores array to 0. for (i = 0; i < 4; i++) scores[i] = 0; // Loop through the matches. for (i = 0; i < num; i++) { if (outcomes[i] == 2) // draw { scores[players[i][0]] += 1; scores[players[i][1]] += 1; } else scores[players[i][outcomes[i]]] += 3; } } // For team 0 to 3, return 1 if that team has a higher // score than at least two other teams. int MoveOn(int scores[], int team) { int i, iAhead = 0; for (i = 0; i < 4; i++) { if (scores[team] > scores[i]) iAhead++; } return (iAhead >= 2); } int main(void) { // This represents the 12 matches in each group. // In the first match, team 0 plays team 1, etc. // There have been 8 matches played already, and 4 to go. int MatchPlayers[12][2] = { 0,1, 2,3, 0,2, 1,3, 0,3, 1,2, 0,1, 2,3, 0,2, 1,3, 0,3, 1,2 }; // This is the outcome of each match. // 0 means the first team (in MatchPlayers) won, 1 means the second team, 2 is a draw. int MatchOutcomes[12] = { 0, 0, 0, 0, 0, 0, 0, 0 }; // Scores of each of the 4 teams. int Scores[4]; int MoveOnFlag[4]; int i, iNoGood; do { iNoGood = 0; // Determine each player's score after 8 matches. Tally(MatchPlayers, MatchOutcomes, 8, Scores); // Find which top two players will be moving on based on these 8 matches. for (i = 0; i < 4; i++) MoveOnFlag[i] = MoveOn(Scores, i); // Initalize the last 4 matches to 0 to start. for (i = 0; i < 4; i++) MatchOutcomes[8 + i] = 0; do { // Find each player's score after 12 matches. Tally(MatchPlayers, MatchOutcomes, 12, Scores); // Check if those players moving on are still moving on. for (i = 0; i < 4; i++) if (MoveOnFlag[i] != MoveOn(Scores, i)) { iNoGood = 1; break; } } while (NextPossibility(MatchOutcomes + 8, 4)); if (iNoGood) continue; // Print the outcomes of the 8 matches if the next 4 don't matter for (i = 0; i < 8; i++) printf("%i ", MatchOutcomes[i]); printf(" "); // Print the scores of the 4 players for (i = 0; i < 4; i++) printf("%i ", Scores[i]); printf("\n"); // There will be a lot of duplicate patterns, but only five unique one: // 14 11 3 3 (1 draw) // 12 12 5 2 (1 draw) // 12 12 3 3 (2 draws) // 12 11 4 3 (2 draws) // 11 11 4 4 (2 draws) // // Total draws: 8 } while (NextPossibility(MatchOutcomes, 8)); return 0; }