Several schools participated in a tennis tourney. Each player played every player from different school than his/her own. The total number of girls participating differed from the total number of boys by at most 1. Also, the total number of same sex matches differed from the total number of opposite sex matches by at most 1. What is the maximum number of schools that could have sent an odd number of players?

BottleAbuser

Korea (South)1888 Posts

September 09 2010 22:32 GMT

Infinite, if we can control the variables to our liking.

School 1: sends x boys, x+1 girls.
School 2: sends x+1 boys, x girls.

No problem.

Add School 3: sends x boys, x+1 girls.

This would actually break the rule, because the girl plays 2 more boys than girls.

This is fixed by adding School 4: sends x+1 boys, x girls.

If we're out of schools, then just make School 3 send an even number of girls and boys.

In short, an even number of schools can send an odd number of players. The maximum even number is.... .... ....

LastPrime

United States109 Posts

September 09 2010 22:47 GMT

Ok, based on what you said, let's take for example the following:

School #--Boy--Girl
1-----------1------2
2-----------2------1
3-----------1------2
4-----------2------1

Same sex matches: 1(2+1+2)+2(1+1+2)+1(1+2+2)+2(1+2+1))/2 + 1(2+1+2)+2(1+1+2)+1(1+2+2)+2(1+2+1))/2. That's 26.

Opposite sex matches: 1(1+2+1)+2(2+2+1)+1(2+1+1)+2(2+1+2)
That's 28.

In fact if you do this out algebraically you get that # of same sex matches in this scenario is 12x^2+12x+2, while the # of opposite sex matches is 12x^2+12x+4.

TanGeng

Sanya12364 Posts

September 09 2010 23:06 GMT

If School n has even number of players then
Bn (boys) = Gn (girls)

If School n had odd number of players then
Bn = Gn +/- 1
and
Gn-Bn = -1, 0, 1 (three possibilities)

we also have
Bt = sum(Bn) over all n
Gt = sum(Gn) over all n

total difference in same sex vs opposite sex matches is (double counted)
DIFFt = sum( Bn(Bt - Bn) + Gn(Gt - Gn) - Bn(Gt - Gn) - Gn(Bt - Bn) ) over all n
DIFFt = sum( (Gn-Bn) (Gt-Gn -Bt + Bn) ) over all n
DIFFt = sum( (Gn-Bn) ((Gt - Bt) - (Gn - Bn))) over all n
Gt - Bt = sum (Gn - Bn) over all n

DIFFt = sum ((Gn-Bn) ^ 2) - (sum(Gn-Bn))^2 over all n

now Gn - Bn has range -1, 0, 1
and when Gn - Bn the summation term reduces to 0.
Only interesting points are when Gn - Bn is not equal to zero or when school has odd number players
let's call this count Z.

Since (Gn-Bn)^2 = 1 for all interesting points

sum ((Gn-Bn) ^ 2) = Z

DIFFt = Z - (sum(Gn-Bn))^2 with Z values of either 1 or -1

if DIFFt needs to be +/- 1 then Z must be +/- of a perfect square, and Z must match the perfect square in evenness or oddness. That means Z has to be the perfect square itself.

edit: oops I forgot the double counting part, so Z is a perfect square or +/- 2.

example of with 4 odds (2^2)
0 1
0 1
0 1
1 0

3 same sex matches 3 cross sex matches

example with 6 odds (2^2 + 2)
0 1
0 1
0 1
1 0
0 1
1 0

7 same sex matches 8 cross sex matches

Steve496

United States60 Posts

September 09 2010 23:09 GMT

3.

Let the number of boys sent by each school by b_1, b_2, ... b_n, the number of girls sent by each be g_1, g_2, ... g_n, and the total number of each gender be B and G (respectively).

We know (B-G)^2 = 0 or 1.

Each of b_1 boys plays B-b_1 same-sex games, and G-g1 opposite-sex ones; the girls do this in reverse. Adding this for all schools, we find that the boys play (B^2 - (b_1^2+...+b_n^2))/2 same-sex games, girls the same thing with gs, and there are BG-(b_1*g_1+...+b_n*g_n) opposite sex games, and the difference between those is +/- 1. Rearranging, we get
(B-G)^2-(b_1-g_1)^2-(b_2-g_2)^2-...-(b_n-g_n)^2 = +/- 2. So, 0 or 1, minus a lot of terms that can't be negative, equals +/- 2. Hence, "most" of those terms must have b_k=g_k and thus an even number of students; at most 3 of them can be nonzero, giving us 1 -1 -1 -1 = -2. This is achieved, for instance, when there are three schools, each sending 1 student, 2 of which are boys and one of which is a girl; total students are 2 vs 1, and there is one same-sex and 2 opposite-sex games.

BottleAbuser

Korea (South)1888 Posts

September 09 2010 23:10 GMT

Okay. A simpler way of looking at it:

Each school sends 1 boy or 1 girl. Then, we can construct a table like this:

         boy girl
school 1: 0   1
       2: 1   0
       3: 0   1
       4: 1   0
       5: 0   1
...

We can then easily see that each player plays every other student in the event, which necessarily means one more opposite-sex match than same-sex match (the students don't play themselves). Adding students to schools doesn't help, because that just serves to increase the discrepancy.

It looks like two schools can send an odd number of students.

rasnj

United States1959 Posts

September 09 2010 23:12 GMT

EDIT: See Steve496 posted essentially the same solution as me.

Dunno if this kind of thing deserves a spoiler tag, but better be safe:
+ Show Spoiler +

The answer is 3.

Let us number the schools 1,2,...,n.

Let bi denote the number of boys send from school i.
Let gi denote the number of girls send from school i.
Let B denote the total number of boys and let G denote the total number of girls.
Let ki = bi - gi.

For an arbitrary boy from school i he has to play against (B-bi) boys, and (G-gi) girls (similar formulas hold for girls). Thus school i participate in precisely
SSMi = bi(B-bi) + gi(G-gi)
Same-sex matches and
OSMi = gi(B-bi)+bi(G-gi)
Opposite-sex matches.
Every same-sex match is counted in exactly two SSMi (once for each school sending a participant), and similarily for opposite-sex matches. Thus the total number of same-sex matches is:
SSM=(SSM1 + SSM2 + .... + SSMn)/2
The total number of opposite-sex matches is:
OSM = (OSM1 + OSM2 + ....+ OSMn)/2
We have,
SSMi - OSMi = (bi-gi)(B-G) - (bi-gi)^2
Which gives us:
2(SSM-OSM) = (B-G)^2 - (b1-g1)^2 - (b2-g2)^2 - ... - (bn-gn)^2
= k1^2 + k2^2 + k3^2 + ....+kn^2
We assumed SSM-OSM and B-G are both in the set {-1,0,1} so
(B-G)^2 - 2(SSM-OSM) = k1^2 + k2^2 + k3^2 + ....+kn^2
can only take on the values -3,-2,-1,0,1,2,-3. In particular at most three of the values k1, k2, ..., kn are non-zero. Since we haven't imposed an order on the schools we may order them such that k4,...,kn are 0. Then schools k4,...,kn sends an equal number of boys and girls and therefore an even number of players (2bi = 2gi for school i, where i > 3). We have now shown that at most 3 schools can send an odd number of players. To see that this can be achieved we can just let there be 3 schools and let them send:
School 1: 1 boy, 0 girls.
School 2: 1 boy, 0 girls.
School 3: 0 boys, 1 girl.
Then there is 1 same-sex match (between school 1 and 2), and 2 opposite sex matches (1 vs 3 and 2 vs 3).

LastPrime

United States109 Posts

September 09 2010 23:19 GMT

On September 10 2010 08:09 Steve496 wrote:
3.

Let the number of boys sent by each school by b_1, b_2, ... b_n, the number of girls sent by each be g_1, g_2, ... g_n, and the total number of each gender be B and G (respectively).

We know (B-G)^2 = 0 or 1.

Each of b_1 boys plays B-b_1 same-sex games, and G-g1 opposite-sex ones; the girls do this in reverse. Adding this for all schools, we find that the boys play (B^2 - (b_1^2+...+b_n^2))/2 same-sex games, girls the same thing with gs, and there are BG-(b_1*g_1+...+b_n*g_n) opposite sex games, and the difference between those is +/- 1. Rearranging, we get
(B-G)^2-(b_1-g_1)^2-(b_2-g_2)^2-...-(b_n-g_n)^2 = +/- 2. So, 0 or 1, minus a lot of terms that can't be negative, equals +/- 2. Hence, "most" of those terms must have b_k=g_k and thus an even number of students; at most 3 of them can be nonzero, giving us 1 -1 -1 -1 = -2. This is achieved, for instance, when there are three schools, each sending 1 student, 2 of which are boys and one of which is a girl; total students are 2 vs 1, and there is one same-sex and 2 opposite-sex games.

We have a winner.

Please or register to reply.

Live Events Refresh