Brilliant Worldwide Competition

Let $m_i$ be the number of males on the $i$ th team and let $f_i$ be the number of females on the $i$ th team. We can write our two conditions as follows:

$\left|\sum_{i}(m_i - f_i)\right| \leq 2$ $\left|\sum_{i,j}(m_i - f_i)(m_j - f_j)\right| \leq 3$

(Here we are noting that, between schools i and j, the number of single games is $m_im_j + f_if_j$ and the number of double games is $m_if_j + m_jf_i$ , so their difference is $m_im_j - m_if_j - m_jf_i + f_if_j = (m_i - m_j)(f_i - f_j)$ ). From here on, let $n_i = m_i - f_i$ . Note that if school $i$ sends an odd number of people, then $n_i$ is at least 1 (since there cannot be the same number of males and females from this school).

Now, squaring the first inequality we get that

$\sum_{i} n_i^2 + 2\sum_{i,j}n_in_j \leq 4$

But we know that $\left|\sum_{i,j}n_in_j\right| \leq 3$ , so $\sum_{i,j}n_in_j \geq -3$ and it follows that

$\sum_{i} n_i^2 \leq 10$

This, along with our previous observation, implies that at most 10 schools can send an odd number of people. Equality is attained when six schools send one male and four schools send one female.

Suppose that School $i$ sends $m_i$ boys and $f_i$ girls. Then the total number of male and female entrants is $M \; = \; \sum_i m_i \qquad F \; =\; \sum_i f_i$ The total number of single and double games is $S \; = \; \tfrac12\sum_{i \neq j}(m_im_j + f_if_j) \qquad D \; = \; \tfrac12\sum_{i \neq j} (m_if_j + f_im_j)$ Thus we have $M-F \; = \; \sum_i (m_i - f_i) \qquad S-D \; = \; \tfrac12\sum_{i \neq j}(m_i-f_i)(m_j-f_j)$ and so the requirements that $|M-F| \le 2$ and $|S-D| \le 3$ can be restated as $\left|\sum_i (m_i-f_i)\right| \le 2 \qquad \left| \sum_{i \neq j}(m_i-f_i)(m_j-f_j)\right| \le 6$ and hence $\begin{array}{rcl} \displaystyle\sum_i (m_i - f_i)^2 & = & \displaystyle\Big[\sum_i (m_i-f_i)\Big]^2 - \sum_{i \neq j}(m_i-f_i)(m_j-f_j) \\ & \le & 2^2 + 6 \; \le \; 10 \end{array}$ Now School $i$ sends an odd number of entrants precisely when $m_i + f_i$ is odd, which occurs precisely when $m_i-f_i$ is odd. Since at most $10$ of the values $m_i-f_i$ can be nonzero, it is certainly true that no more than $10$ schools can send an odd number of entrants.

It remains to show that it is possible for $10$ schools to send an odd number of entrants. From the above calculations, it is clear that only the difference $m_i-f_i$ matters for each school, and so we can look for an example with small numbers, which makes the counting easier. Suppose that $4$ schools send $1$ boy and $0$ girls, while $6$ schools send $0$ boys and $1$ girl, while the other $990$ schools send nobody! Then $M=4$ and $F=6$ , so that $|M-F| = 2$ as required. Moreover $S \; = \; {}^4C_2 + {}^6C_2 \; = \; 6 + 15 \; =\; 21 \qquad D \; = \; 4\times6 \; = \;24$ and hence $|S-D| = 3$ . This is an example where $10$ schools send an odd number of entrants.

Let us call the schools 1 through 1000. We denote the number of males that School $i$ sends as $m_i$ and the number of females that School $i$ sends as $f_i$ . For example, School 26 would send $m_{26}$ male students and $f_{26}$ female students.

Now, consider a particular configuration of ${m_1, m_2, m_3, ..., m_{1000}, f_1, f_2, f_3, ..., f_{1000}}$ . We denote the difference in total male and female students as $x$ , and the difference between single and double matches as $y$ (let us for awhile ignore the conditions of $x\leq 2$ and $y \leq 3$ ).

We consider what happens when we decrease $m_1$ and $f_1$ each by 1 (of course assuming they are both $\geq 1$ to begin with).

1. The total number of male students decreases by 1, and the total number of female students decreases by 1 as well; hence $x$ remains constant.

2. The total number of single matches among the males decreases by $(m_2 + m_3 + m_4 + ... + m_{1000})$ , i.e. the number of single matches the removed male student would have played; similarly, the total number of single matches among the females decreases by $(f_2 + f_3 + f_4 + ... + f_{1000})$ . On the other hand, considering the double matches, the removed male student was supposed to play $(f_2 + f_3 + f_4 + ... + f_{1000})$ of these, and the removed female student was supposed to play $(m_2 + m_3 + m_4 + ... + m_{1000})$ of these; hence, the total number of single matches decreases by $(m_2 + m_3 + m_4 + ... + m_{1000} + f_2 + f_3 + f_4 + ... + f_{1000})$ , and the total number of double matches decreases by the same number, i.e. $y$ remains constant.

Of course, it is easy to see that this method works with any School $i$ , and illustrating with School $1$ was simply for ease of explanation

Hence, noting that $x$ and $y$ are invariant when we remove male-female pairs of students from each school, and that the parity of the number of students sent by each school is invariant with respect to this removal as well, we may simplify the problem by removing all possible male-female pairs of students from each school, i.e. each school sends students of only one sex, and we aim to find the maximum number of schools that send an odd number of students, while fulfilling the same two conditions in the question.

note that because we have removed all possible male-female pairs, it is possible that some schools will end up sending 0 students in this new problem, that is, the schools that would have sent an equal number of male-female students

With this new problem, let us re-denote the variables for convenience. Let there be $n$ schools sending all-males, and $m$ schools sending all-females, where $n+m=1000$ . We denote the number of males and females sent by these schools as ${a_1, a_2, a_3, ..., a_n}$ and ${b_1, b_2, b_3, ..., b_m}$ , respectively (again note that any of these can be 0, since some schools can end up sending 0 students). We also denote $A = a_1 + a_2 + a_3 + ... + a_n$ and $B = b_1 + b_2 + b_3 + ... + b_m$ for convenience.

Number of males in total: $A$

Number of females in total: $B$

Number of male single matches: $\frac{(a_1)*(a_2 + a_3 + a_4 + ... + a_n) + (a_2)*(a_1 + a_3 + a_4 + ... + a_n) + ... + (a_n)*(a_1 + a_2 + a_3 + ... + a_{n-1})}{2}$

$= \frac{(a_1)*(A-a_1) + (a_2)*(A-a_2) + (a_3)*(A-a_3) + ... + (a_n)*(A-a_n)}{2}$

$= \frac{A*(a_1 + a_2 + a_3 + ... + a_n) - (a_1^2 + a_2^2 + a_3^2 + ... + a_n^2)}{2}$

$= \frac{A^2 - (a_1^2 + a_2^2 + a_3^2 + ... + a_n^2)}{2}$

Number of female single matches (similarly): $\frac{B^2 - (b_1^2 + b_2^2 + b_3^2 + ... + b_m^2)}{2}$

Number of double matches: $AB$

Therefore, the conditions reduce to the following 2 equations:

1. $|A-B| \leq 2$
2. $| \frac{A^2 +B^2 - (a_1^2 + a_2^2 + a_3^2 + ... + a_n^2) - (b_1^2 + b_2^2 + b_3^2 + ... + b_m^2)}{2} - AB | \leq 3$

Note that (2) can be further simplified to:

$| \frac{A^2 +B^2 - 2AB}{2} - \frac{a_1^2 + a_2^2 + a_3^2 + ... + a_n^2 + b_1^2 + b_2^2 + b_3^2 + ... + b_m^2}{2} | \leq 3$

$\Rightarrow | \frac{(A-B)^2}{2} - \frac{a_1^2 + a_2^2 + a_3^2 + ... + a_n^2 + b_1^2 + b_2^2 + b_3^2 + ... + b_m^2}{2} | \leq 3$

Since both fractions are clearly $\geq 0$ ,

$\Rightarrow \frac{(A-B)^2}{2} - 3 \leq \frac{a_1^2 + a_2^2 + a_3^2 + ... + a_n^2 + b_1^2 + b_2^2 + b_3^2 + ... + b_m^2}{2} \leq \frac{(A-B)^2}{2} + 3$

By the first condition, $0 \leq (A-B)^2 \leq 4$ , so,

$\Rightarrow 0 - 3 \leq \frac{a_1^2 + a_2^2 + a_3^2 + ... + a_n^2 + b_1^2 + b_2^2 + b_3^2 + ... + b_m^2}{2} \leq 2 + 3$

The left half of the inequality is obvious, but when we examine the right half,

$\Rightarrow a_1^2 + a_2^2 + a_3^2 + ... + a_n^2 + b_1^2 + b_2^2 + b_3^2 + ... + b_m^2 \leq 10$

Of course, all of ${a_1, a_2, a_3, ..., a_n}$ and ${b_1, b_2, b_3, ..., b_m}$ are integers, hence, it is clear that at most 10 of these variables have a nonzero value. That is, at least $n + m - 10 = 990$ of the other variables will have to be 0. Recall here that if any of the variables here are 0, the corresponding school would have sent '0' students, i.e. an equal number of male-female students, which is an even number of students. Thus, there are at least 990 schools sending an even number of students, and the maximum number of schools which can send an odd number of students is simply 10 (of course this can be easily constructed by setting an arbitrary 10 of ${a_1, a_2, a_3, ..., a_n, b_1, b_2, b_3, ..., b_m}$ to be 1, and the rest 0).

Let's denote the number of males and females in the $i$ th school as $m_i$ and $f_i$ . The number of single matches is then $S = \sum_{i<j} m_i m_j + f_i f_j$ and the number of double matches is $D = \sum_{i<j} m_i f_j + f_i m_j .$

We want to get our hands on the difference $S - D$ . So let's write $S - D = \sum_{i<j} (m_i - f_i) ( m_j - f_j) .$

We note here the useful identity $2ab = (a+b)^2 - a^2 - b^2$ that helps us rewrite $S - D$ using only squares $2(S - D) = \left( \sum_i (m_i - f_i) \right)^2 - \sum_i (m_i - f_i)^2.$ The first term of the right is simply the square of the difference between the total number of males and females. Let's denote this as $A^2$ . The second sum is over squares of differences in individual teams. If every team had the same number of males and females the second sum would vanish and we would have $2(S-D) = A^2$ . But in this case every school would have even number of players. So what we want to do instead is maximize the second sum by having as many schools as possible having $k$ males and $k+1$ females (or vice versa). In that case the second sum precisely measures the number of schools having odd number of players. Denote the second sum by $B^2$ .

We have $B^2 = A^2 + 2(D-S)$ . We know that $|A|$ , the total difference in gender, is at most $2$ and $D-S$ is at most $3$ . Making them both as big as possible maximizes $B^2$ so that, $B^2 = 2^2 + 2\cdot 3 = {\bf 10}$ .

You can ignore any students at any school who can be paired off in a male-female pair, since they do not change any male-female or single-double differences.

Let M = # unpaired males

Let F = # unpaired females

Let S = # singles matches involving unpaired students of same sex

Let D = # doubles matches involving unpaired students of different sexes

S <= M(M-1)/2 + F(F-1)/2 (equality if max of 1 unpaired student per school)

D = MF

MF = D <= S + 3 <= (MM-M)/2 + (FF-F)/2 + 3

2MF <= MM - M + FF - F + 6

M+F <= MM - 2MF + FF + 6 = (M-F)^2 + 6 <= 2^2 + 6 = 10

Maximum # of odd schools <= Maximum # of unpaired students = M+F = 10

The maximum occurs when M=6, F=4 or when F=6, M=4 and no school has more than one unpaired student.

In that case: S = 6 5/2 + 4 3/2 = 15+6 = 21

D = 6*4 = 24

Without loss of generality we can number the schools, so we will say that there is a first, a second a third school and so on...

We will call $m_n$ the number of male students sent by the $n$ -th school, $f_n$ the number of female students sent by the $n$ -th school. And we will call $d_n$ the difference between them. i.e. $d_n:=m_n-d_n$

Now we can rewrite our problem in term of those variables. Saying that the difference between total male and female students is at most $2$ equivalent to say that $\left| \sum_{i=1}^{1000} d_i \right| \leq 2 \ .$ While saying that the difference between single and double matches is at most $3$ is the same as $\left| \sum_{1\leq i < j \leq 1000} d_i d_j \right| \leq 3$ In fact the total number of single matches is $\sum_{1\leq i < j \leq 1000}\left( m_i m_j\right) \ + \sum_{1\leq i < j \leq 1000}\left( f_i f_j\right) = \sum_{1\leq i < j \leq 1000}\left( m_i m_j +f_i f_j\right) \$ the total number of double matches is $\sum_{1\leq i < j \leq 1000}\left( m_i f_j\right) \ + \sum_{1\leq i < j \leq 1000}\left( f_i m_j\right) = \sum_{1\leq i < j \leq 1000}\left( m_i f_j +f_i m_j\right)$ Therefore the difference between them is $\sum_{1\leq i < j \leq 1000}\left(m_i m_j- m_i f_j -f_i m_j +f_i f_j\right) = \sum_{1\leq i < j \leq 1000}\left( \left( m_i-f_i \right) \left( m_j-f_j \right) \right)$ Whose absolute value is equal to the $LHS$ of the previous inequality.

We have a well known identity: $\sum_{i=1}^{1000} d_i^2=\left( \sum_{i=1}^{1000} d_i \right)^2 - 2\cdot \sum_{1\leq i < j \leq 1000}\left(d_i d_j\right)$ Using the inequalities we have found we can show that $\sum_{i=1}^{1000} d_i^2 \leq 2^2 + 2 \cdot 3 = 10$ We know that every $d_i$ is an integer. Therefore there are at most $10$ of them that are non-zero.

It should be clear at this stage that the number of students sent by the $n$ -th school has the same parity as $d_n$ . This can be seen by the fact that $m_n+f_n \equiv m_n +f_n - 2 \cdot f_n \equiv d_n \pmod{2}$

This means that there are at most $10$ schools that sent an odd number of students. We will now show that it is actually possible that only $10$ schools sent an odd number of students.

It is sufficient to take: $d_i=1 \qquad 1 \leq i \leq 6$ $d_j=-1 \qquad 7 \leq j \leq 10$ $d_k=0 \qquad 11 \leq k \leq 1000$

The $2$ inequalities holds, in fact: $\left| \sum_{i=1}^{1000} d_i \right| = 2 \ .$ and $\left| \sum_{1\leq i < j \leq 1000} d_i d_j \right| = {6 \choose 2}+ {4 \choose 2}-6\cdot 4 =15+6 - 24=3$ because we can ignore the $0$ s and we get $1$ iff we multiply $1$ by $1$ or $-1$ by $-1$ . While we get $-1$ otherwise.

Now... how came that this week I have solved all the combinatorics problem and I got from level $5$ to level $4$ ? I have even given this nice proof of the hardest one!

Looks like a big Trololo from Brilliant!

If we add or remove a boy,girl pair from one school then the difference between double and single matches is unchanged, by symmetry. So we can assume without loss of generality that each school only sends students of one gender, with some schools perhaps not sending any students.

Let $B$ be the total number of boys sent, and $G$ be the total number of girls sent. Then $D = B \times G$ is the total number of double matches.

To work out the number of single matches: if each boy is from a different school, then the number of boy-boy matches will be $\frac{1}{2}B(B-1)$ . However, if some boys are from the same school, they do not play each other. So we can say that the number of singles matches S:

$2S = B(B-1) + G(G-1) - k$

where $k$ is an even non-negative integer. Combining these two formulae with the constraint that $\lvert D - S \lvert \le 3$ we get:

$\begin{aligned} \lvert B(B-1) + G(G-1) - k - 2BG \lvert &\le 6 \\ \lvert B^2 - 2BG + G^2 - (B+G) -k \lvert &\le 6 \\ \lvert (B-G)^2 - (B+G+k) \lvert &\le 6 \end{aligned}$

We are also given the constraint $\lvert B-G \lvert \le 2$ . Applying this constraint to the last line above gives:

$B+G+k \le 10$

Thus the maximum possible value for $B+G$ is 10, which may occur when $B-G = 2$ . This maximal value can be realized by a configuration where all students are from a school that sent an odd number of students, i.e. 6 schools send 1 boy and 4 schools send 1 girl (or vice versa), so the answer we want is $\boxed{10}$ .