//------------------------------------------------------------------- // enigma1359.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "The Weaker Sex" by Susan Denham, New Scientist, 24 September 2005, page 52. // // N couples play round robin squash. Each of the 2N players plays // every other player once. At least one man and one woman have // scores that are prime. The lowest scoring woman has a score // at least 3 times the highest scoring man. // // How many couples played? How many times did a man beat a woman? // // There are N couples and 2N players. The total number of matches is: // // (2N - 1) + (2N - 2) + ... + 1 // // or: // // (2N - 1)(2N) // ------------ = (2N - 1)(N) = T // 2 // // where T stands for Total. // // The number of matches where a man plays another man is: // // (N - 1)(N) // ---------- = U // 2 // // and that's also the number of matches where a woman plays another woman. // The U stands for Unisex. // // It is useful to look at the scores of each player as a "partition" of the // total number of matches. "A partition is a way of writing an integer n // as a sum of positive integers..." (Eric W. Weisstein. "Partition." From // MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Partition.html) // // In this case, were writing T (the total scoare) as the sum of 2N scores for each // of the 2N players. (If there is a player who wins no matches, then we're actually // writing T as the sum of 2N-1 scores. Only one player can have no wins. If two // players have no wins, then what happened to the match between those two?) // // For this exercise, let's write our partitions with the highest number first. // For example, if N = 5, then T = 45 and U = 10. The most lopsided distribution of // scores among the 10 players is this partition of 45: // // 9 8 7 6 5 4 3 2 1 0 // // Because we know that the lowest-scoring woman scored higher than the highest- // scoring men, the 5 women's scores are the first five numbers, followed by the // 5 men's scores. // // The two numbers in the center of the paritition are, in fact, the lowest women's // score and the highest men's score. The former must be at least 3 times the latter. // These two scores verge most greatly when both the men's scores and the women's // scores tend to even out. Here's the extreme case: // // 7 7 7 7 7 2 2 2 2 2 // // Because the men play 10 matches among themselves, the men's total score must be // at least 10, and here we have 10 spread out among the 5 men. Similarly, the // total women's score can be no greater than T - U (35 in this example), and that // too is spread out among the 5 women. // // Lo and behold, this distribution solves the problem. The lowest women's score is // 7 and that's more than 3 times the highest man's score of 2. At least one man // and one woman (actually, all of them) have prime scores. // // The solution is: 5 couples, with 0 matches with a man beating a woman. // // Notice there's not a lot of wiggle room. If one man won one more match, the // partition would look like this: // // 7 7 7 7 6 3 2 2 2 2 // // Now the lowest woman's score is only double the highest man's score. // // Is this the only solution? Let's look at cases where no men win a match against // woman, and the scores are evenly distributed as in the solution with 5 couples. // // If no man wins a match against a woman, the average man's score is U / N, or: // // N - 1 // Average man's score = ----- // 2 // // The average women's score is (T - U) / N or: // // 3N - 1 // Average woman's score = ------ // 2 // // If N is odd, then the men's scores can be evenly distributed among the N // men, and so can the women's. Each man scores (N - 1) / 2 and each woman // scores (3N - 1) / 2. Each women's score is 3 times plus 1 of each men's // score. // // If N is even, then the men's and women's scores cannot be equally // distributed among the N men and women. Half the men score N/2 and half // score (N-1)/2. Half of the women score 3N/2 and half score 3N/2 - 1. // The lowest women's score is no longer more than 3 times the highest man's. // // So, the only cases that work right are those where N is odd, and all the // men and women have the same score: // // N Men Women // - --- ----- // 3 1 4 // 5 2 7 // 7 3 10 // 9 4 13 // 11 5 16 // // and so forth. The men's scores alternate between odd and even, and the // women's altenate between even and odd. The only time both men and women // have prime scores is when the men have the only even prime number of 2. // // Let's code up a solution anyway. //----------------------------------------------------------------------------- #include #include typedef int BOOL; #define TRUE 1 #define FALSE 0 #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) // a is an array of 'num' integers, where a[i] >= a[i + 1]. // The 'num' integers are a partition of the sum of the integers in a. // This function methodically "flattens out" the partition. // Each call rearranges the elements of the array and normally returns TRUE. // A FALSE return value means the partition is as flat as possible. BOOL NextPartition(int a[], int num) { int i, new, accum = 0; for (i = num - 1; i > 0; i--) { accum += a[i]; if (a[i - 1] > 1 + a[num - 1]) break; } if (i == 0) return FALSE; new = a[i - 1] -= 1; accum += 1; for ( ; i < num; i++) { a[i] = MIN(new, accum); accum -= MIN(new, accum); } return TRUE; } // Returns the sum of 'num' integers in array a. int Sum(int a[], int num) { int i, sum = 0; for (i = 0; i < num; i++) sum += a[i]; return sum; } BOOL IsPrime(int i) { int j = 2; if (i < 2) return FALSE; while (j * j <= i) { if (i % j == 0) return FALSE; j += 1; } return TRUE; } int main(void) { int couples, i; // 'couples' is the number of couples. for (couples = 2; couples < 10; couples++) { // This array holds the scores and is also a partition of the // the total of all the scores. THe first 'couples' elements // are the women, followed by the men. int scores[2 * couples]; // Initialize the 'scores' array to be as lopsided as possible. for (i = 0; i < 2 * couples; i++) scores[i] = 2 * couples - 1 - i; printf("Couples = %i\n", couples); // This loop cycles through the partitions of 'scores'. do { // Initialize these two variables BOOL OneMalePrime = FALSE, OneFemalePrime = FALSE; // Check that the women have sufficient scores among themselves. if (Sum(scores, couples) < (couples - 1) * couples / 2) continue; // Check that the men have sufficient scores among themselves if (Sum(scores + couples, couples) < (couples - 1) * couples / 2) continue; // Check that at least one woman and one man have a prime score. for (i = 0; i < couples; i++) { OneFemalePrime |= IsPrime(scores[i]); OneMalePrime |= IsPrime(scores[i + couples]); } if (!OneFemalePrime || !OneMalePrime) continue; // Check if the highest scoring woman is more than 3 times the // highest scoring man. // If so, we have a winner. if (scores[couples - 1] > 3 * scores[couples]) { printf("scores: "); for (i = 0; i < 2 * couples; i++) printf("%i ", scores[i]); printf("\n"); printf("Men defeat women: %i\n", Sum(scores + couples, couples) - (couples - 1) * couples / 2); } } while (NextPartition(scores, 2 * couples)); } return 0; }