//-------------------------------------------------------------------
// enigma1344.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Mixed Pairs" problem from New Scientist, 11 June 2005, page 51
//-------------------------------------------------------------------
// Two classes, different sizes, each has same number of boys and girls.
//
// Miss Take's class has m boys and m girls.
// The boys and girls are paired off.
// The number of different ways this can be done is trivially m!.
//
// Miss Giving's class has n boys and n girls.
// The boys and girls in her class are paired off as well, 
// but the pairs are to have "at least one single-sex pair."
// (But if there's one, there has to be another.)
// Also, there are two particular girls who cannot be paired together.
// The total number of different ways Miss Giving's class can be 
// paired off is amazingly the same as for Miss Take's class, 
// which we've already established is m!
//
// Assume that 2 boys in Miss Giving's class are paired together,
// as well as 2 girls. (There may be more but the problem gets
// more complicated. Let's hope this works.)
//
// The number of ways 2 boys from n boys can be paired off is:
//
//	(n - 1) + (n - 2) + ... + 1 = (n)(n - 1) / 2
//
// The number of pairings of 2 girls from n girls is the same
// except one less because of the prohibited pair:
//
//	(n)(n - 1) / 2 - 1
//
// The number of boys and girls left over is n - 2, allowing for
// (n - 2)! combinations.
//
// So,
//
//	(n(n-1)/2) * (n(n-1)/2 - 1) * (n-2)! = m!
//
// This is the equality the program below attempts to find, 
// but it can also be done more analytically.
//
// Let
//	k = (n(n-1)/2) * (n(n-1)/2 - 1)
// So,
//	k * (n - 2)! = m!
//
// For the two sides to be equal, k likely contributes to the (n-2)
// factorial to make it m!  Thus, k must be:
//
//		(n - 1)
// or:
//		(n - 1)(n)
// or:
//		(n - 1)(n)(n + 1)
// or:
//		(n - 1)(n)(n + 1)(n + 2)
//
// and so forth. Actually k cannot be equal to (n-1)(n) because that
// would make n equal to m, and we know the classes are different sizes.
// It doesn't seem reasonable that k could equal (n - 1), so let's
// try the third one:
//
//	k = (n - 1)(n)(n + 1)
// or:
//	(n(n-1)/2) * (n(n-1)/2 - 1) = (n - 1)(n)(n + 1)
// 
// Dividing both sides by (n-1)(n):
//
//	(1/2) * (n(n - 1) / 2 - 1) = n + 1
// or:
//	(1/2) * (n(n - 1) - 2) / 2 = n + 1
// or:
//	n(n - 1) - 2 = 4n + 4
// or:
//	nn = 5n + 6
// or:
//	n = 6
//
// which means that k = 7 * 6 * 5, and
//
//	k * (n - 2)! = m!
//
// so m equals 7.
//
// Miss Take's class has 14 children. Miss Giving's class has 12.
//---------------------------------------------------------------g
 
#include <stdio.h>

// Standard recursive function for calculating factorials

int Factorial(int i)
{
	return i == 1 ? 1 : i * Factorial(i - 1);
}

int main(void)
{
	int m;	// half the total number in Miss Take's class
	int n;	// half the total number in Miss Giving's class

	int ncombo, mcombo;	// number of ways classes can be paired off

	for (m = 4; ; m++)
	{
		mcombo = Factorial(m);

		for (n = 3; n < m; n++)
		{
			ncombo = (n * (n - 1) / 2) * (n * (n - 1) / 2 - 1) *
					Factorial(n - 2);

			if (ncombo == mcombo)
			{
				printf("Miss Take: %i, Miss Giving: %i\n", 
					2 * m, 2 * n);
				return 0;
			}
		}
	}
}