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