//------------------------------------------------------------------- // enigma1348.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Team Promotions" from New Scientist, 9 July 2005, page 45. // // The problem involves finding the number of teams in a league. // Let's call the answer N. // // The first sentence states that the teams were once divided into // "a number of identical local leagues." This seems like superfluous // information until you realize that it's telling you that N is not // prime. This fact is crucial for narrowing down the possibilities. // It's also implied that N is at least 4. // // The second sentence in the problem about all the matches during // the year implies that N is less than 52. // // At the end of the season, either 2, 3, or 4 teams will be promoted. // The number of combinations for 4 teams is a multiple of the number // of combinations for 3 teams, which in turn is a multiple of the // number of combinations of 2 teams. // // We know from Probability 101 that the number of ways of selecting // K unordered items from a population of N is: // // N! // --------- // (N-K)! K! // // Hence, // // N! N! N! // --------- is a multiple of --------- is a multiple of --------- // (N-4)! 4! (N-3)! 3! (N-2)! 2! // // The program below attempts to find N from this relationship, but // let's continue the analysis ourselves. // // We can rewrite the ratios as: // // N(N-1)(N-2)(N-3) N(N-1)(N-2) N(N-1) // ---------------- is a mult. of ----------- is a mult. of ------ // (4)(3)(2) (3)(2) 2 // // Dividing out factors common to all three ratios we're left with: // // (N-2)(N-3) (N-2) // ---------- is a multiple of ----- is a multiple of 1. // (3) (4) 3 // // Therefore, (N-2)/3 is a whole number, and (N-3)/4 is a whole number. // // (N-2)/3 is a whole number for N = 5, 8, 11, 14, 17, 20, 23, 26, 29, // 32, 35, 38, 41, 44, 47, and 50. // // (N-3)/4 is a whole number for N = 7, 11, 15, 19, 23, 27, 31, 35, // 39, 43, 47, and 51. // // The only non-prime number common to both lists is 35. //------------------------------------------------------------------- #include // Returns 1 if argument is prime int IsPrime(int i) { int j = 2; if (i < 2) return 0; while (j * j <= i) { if (i % j == 0) return 0; j += 1; } return 1; } // Standard recursive factorial function int Factorial(int i) { return i == 0 ? 1 : i * Factorial(i - 1); } // Because factorials get very big for even modest N, // this Combination function uses factorials sparingly. int Combinations(int N, int K) { int i, R = 1; // for "result" for (i = N; i > N - K; i--) R *= i; return R / Factorial(K); } int main(void) { int N; for (N = 4; N < 52; N++) { if (IsPrime(N)) continue; if (Combinations(N,3) % Combinations(N,2) != 0) continue; if (Combinations(N,4) % Combinations(N,3) != 0) continue; printf("%i\n",N); break; } }