//-------------------------------------------------------------------
// 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;
}
}