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