//-------------------------------------------------------------------
// 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 <stdio.h>

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