USA IMO

First Solution. (By Zhiqiang Zhang, China) We proceed indirectly. Assume that no problem is both girl-easy and boy-easy.

Lemma 1. Let $A=\{p_1,p_2,\dots ,p_k\}$ denote the set of all girl-hard problems. Let $B=\{p_{k+1},p_{k+2},\dots ,p_{k+m}\}$ denote the set of all boy-hard problems that are not in $A$. Then $k\ge 11$, $m\ge 11$, and consequently, $$k+m\ge 22.\text{\hspace{1em}(1)}$$ Proof. By our assumption, each problem is either girl-hard, boy-hard, or both. Thus, if $P$ is the set of all the problems, then $A\cup B=P$. A boy contestant $b$ can solve at most 6 problems in set $A$, so there are at most $2\cdot 6=12$ girls who each solved a problem in $A$ that $b$ solved. By condition (b), there are at least $21-12$ girls who each solved a problem in $B$ that $b$ solved. It follows that each boy must solve some problems in set $B$. But each problem in set $B$ can be solved by at most 2 boys, implying that $21\le 2m$ and hence $m\ge 11$. In exactly the same way, we can prove that $k\ge 11$. ■

For $1\le i\le k+m$, let $x_i$ be the number of contestants who solved problem $p_i$. In the light of condition (a), we have $$x_1+x_2+\cdots +x_{k+m}\le 6\times 42.\text{\hspace{1em}(2)}$$ For each $p_i\in P=A\cup B$, let $q_i$ be the number of girl and boy pairs $(g,b)$ such that girl $g$ and boy $b$ both solved $p_i$. By condition (b), ${\sum }_{i=1}^{k+m}{q}_i\ge 21^2$. For each $i=1,2,\dots ,k+m$, note that $x_i\ge 2$ because each problem was solved by at least one girl and one boy. Therefore, $$q_i\le \max \{(x_i-1)\times 1,(x_i-2)\times 2\}\le 2x_i-3.$$ Hence, by (2) we obtain $$\begin{array}{rl}21^2& \le \sum _{i=1}^{k+m}{q}_i\le (2x_1-3)+(2x_2-3)+\cdots +(2x_{k+m}-3)\\ & =2(x_1+x_2+\cdots +x_{k+m})-3(k+m)\\ & \le 2\times 6\times 42-3(k+m),\end{array}$$ or $k+m\le 21,$ contradicting (1).

Thus, our assumption was wrong and there is a problem solved by at least three girls and three boys.

Second Solution. (By Gabriel Carroll and Liang Xiao, China) Let $p$ be the number of problems. For the sake of contradiction, we assume that no problem is both girl-easy and boy-easy. As in the first solution, we prove that this assumption implies both that $p\ge 22$ and that $p\le 21$, which is impossible.

Lemma 2. There are at least 11 girl-easy problems and 11 boy-easy problems.

Proof. Suppose some girl solves no boy-easy problems. Then every problem she solves was solved by at most two boys. Since she solves at most six problems, at most 12 boys solve a problem that she solves, contradicting condition (b). Thus, every girl solved a boy-easy problem. Since each boy-easy problem was solved by at most two girls, there must be at least $\lceil \frac{21}{2}\rceil =11$ boy-easy problems. Likewise, there are at least 11 girl-easy problems. ■

By our assumption, there is no problem that is both boy-easy and girl easy. Thus, there are at least 22 problems, that is, $$p\ge 22.\text{\hspace{1em}(3)}$$ Assume that the $i$th problem was solved by $g_i$ girls and $b_i$ boys. For each $i$, either $g_i\in \{1,2\}$, or $g_i>2$ and $b_i\le 2$. Consider the quantity $$Q=(g_i-2)(b_i-2).$$ If $g_i=2$, then $Q=0$; if $g_i=1$, then $Q=2-b_i\le 1$ since $b_i\ge 1$ by assumption; finally, if $g_i>2$ and $b_i\le 2$, then $Q\le 0$. In any case, we have $Q=(g_i-2)(b_i-2)\le 1$, that is, $$g_i{b}_i\le 2g_i+2b_i-3.(4)$$ Now $g_i{b}_i$ counts the number of pairs $(g,b)$ in which girl $g$ and boy $b$ both solved problem $i$. It is given that every possible pair $(g,b)$ is counted for some $i$, so $$\sum _{i=1}^p{g}_i{b}_i\ge 21^2.(5)$$ On the other hand, everyone solved at most six problems, so ${\sum }_{i=1}^p{g}_i\le 21\cdot 6$, and likewise ${\sum }_{i=1}^p{b}_i\le 21\cdot 6$. Thus, by (4) and (5), we obtain $$\begin{array}{rl}21^2& \le \sum _{i=1}^p{g}_i{b}_i\le \sum _{i=1}^p(2g_i+2b_i-3)\\ & =2\left(\sum _{i=1}^p{g}_i+\sum _{i=1}^p{b}_i\right)-3p\\ & \le 2(21\cdot 6+21\cdot 6)-3p=21\cdot 24-3p.\end{array}$$ It follows that $3p\le 21\cdot 24-21^2=21\cdot 3$, or $$p\le 21,(6)$$ contradicting (3).

Thus, our initial assumption was wrong, and there is a problem that was solved by three boys and three girls.

Third Solution. (Based on work by Ian Le) We provide an alternative proof of (6).

For each $i=1,2,\dots ,p$, let ${ϵ}_i=\min \{g_i,b_i\}$, and let $M_i=\max \{g_i,b_i\}$. Note that ${ϵ}_i$ is either 1 or 2. Assume without loss of generality that ${ϵ}_1={ϵ}_2=\cdots ={ϵ}_r=2$ and that ${ϵ}_{r+1}={ϵ}_{r+2}=\cdots ={ϵ}_p=1$. Then, by (5), $$\begin{array}{rl}441& \le \sum _{i=1}^p{g}_i{b}_i=\sum _{i=1}^p{ϵ}_i{M}_i=2\sum _{i=1}^r{M}_i+\sum _{i=r+1}^p{M}_i\\ & =2\sum _{i=1}^p{M}_i-\sum _{i=r+1}^p{M}_i.\end{array}$$ Note that $M_i\ge 1$. It follows that $$441\le 2\sum _{i=1}^p{M}_i-p+r.(7)$$ On the other hand, since each girl or boy solved at most 6 problems, we must have ${\sum }_{i=1}^p(g_i+b_i)\le 2\cdot 6\cdot 21=252$, or $$252\ge \sum _{i=1}^p(g_i+b_i)=\sum _{i=1}^p({ϵ}_i+M_i)=p+r+\sum _{i=1}^p{M}_i.$$ Multiplying by 2 on both sides of this inequality and rearranging gives $$2\sum _{i=1}^p{M}_i-p+r\le 2\cdot 252-3p-r=504-3p-r.(8)$$ Combining (7) and (8), we obtain $441\le 504-3p-r$, or $$p\le (504-441)/3=21,$$ as desired.

Fourth Solution. We introduce the following symbols: $G$ is the set of girls at the competition, $B$ is the set of boys, $P$ is the set of problems, $P(g)$ is the set of problems solved by $g\in G$, and $P(b)$ is the set of problems solved by $b\in B$. Finally, $G(p)$ is the set of girls that solve $p\in P$ and $B(p)$ is the set of boys that solve $p$. In terms of this notation, we have that for all $g\in G$ and $b\in B$, (a) $|P(g)|\le 6$, $|P(b)|\le 6$, and (b) $P(g)\cap P(b)\ne \varnothing$

Hence, a problem is boy-easy (resp., boy-hard) if and only if $|B(p)|\ge 3$ ($|B(p)|\le 2$); a problem is girl-easy (resp., girl-hard) if and only if $|G(p)|\ge 3$ (resp., $|G(p)|\le 2$). We wish to prove that some $p\in P$ satisfies $|G(p)|\ge 3$ and $|B(p)|\ge 3$. For sake of contradiction, assume instead that every problem is either boy-hard or girl-hard or both, that is, for each $p\in P$, either $|G(p)|\le 2$ or $|B(p)|\le 2$ or both. We shall reach a contradiction by counting, in two different ways, all ordered triples $(p,g,b)$ such that $p\in P(g)\cap P(b)$. With $$T=\{(p,g,b)\mid p\in P(g)\cap P(b)\},$$ condition (b) yields $$|T|=\sum _{g\in G}\sum _{b\in B}|P(g)\cap P(b)|\ge |G|\cdot |B|=21^2.(9)$$ We continue by noting that $$\sum _{p\in P}|G(p)|=\sum _{g\in G}|P(g)|\le 6|G|\text{and}\sum _{p\in P}|B(p)|\le 6|B|.(10)$$ The equality in (10) is obtained by counting the total number of problems, including multiplicity, solved by all the girls. (That is, if a problem solved by n girls, then it is counted n times.)

Let $P_{ge}$ and $P_{gh}$ denote the sets of all girl-easy and girl-hard problems, respectively. By our assumption, if $p\in P_{ge}$, then it must be boy-hard, i.e. $|B(p)|\le 2$. Hence, $$\begin{array}{rl}|T|& =\sum _{p\in P}|G(p)|\cdot |B(p)|\\ & =\sum _{p\in P_{ge}}|G(p)|\cdot |B(p)|+\sum _{p\in P_{gh}}|G(p)|\cdot |B(p)|,\end{array}$$ or $$|T|\le 2\sum _{p\in P_{ge}}|G(p)|+2\sum _{p\in P_{gh}}|B(p)|.(11)$$ Lemma 3. We have $$\sum _{p\in P_{gh}}|G(p)|\ge |G|;\sum _{p\in P_{ge}}|G(p)|\le 5|G|.$$ and $$\sum _{p\in P_{ge}}|B(p)|\ge |B|;\sum _{p\in P_{gh}}|B(p)|\le 5|B|.$$ Proof. Let $g\in G$ be arbitrary. By the Pigeonhole Principle, conditions (a) and (b) imply that $g$ solves some problem $p$ that is solved by at least \lceil 21/6\rceil = 4 boys. By assumption, $p$ is boy-easy, implying that $p$ is girl-hard. Thus, every girl solves at least one problem in $P_{gh}$. Hence, $$\sum _{p\in P_{gh}}|G(p)|\ge |G|.(12)$$ In view of (10) and (12) we have $$\sum _{p\in P_{ge}}|G(p)|=\sum _{p\in P}|G(p)|-\sum _{p\in P_{gh}}|G(p)|\le 5|G|.$$ Also, each boy solves a problem that is solved by at least four girls, so each boy solves a girl-easy problem. Thus, $$\sum _{p\in P_{ge}}|B(p)|\ge |B|.$$ It follows from this inequality and (10) that $$\sum _{p\in P_{gh}}|B(p)|\le 5|B|$$ as well.

Using Lemma 3 and equality (11), we find $$T\le 10|G|+10|B|=20\times 21.$$ This contradicts (9), so the proof is complete.

Fifth Solution. Keep the notation of the fifth solution, and again assume that no problem is both girl-easy and boy-easy. For each $p\in P$, color $p$ red if it is boy-easy, color $p$ blue if it is girl-easy, and color $p$ either color if it is both boy- and girl-hard.

Consider a chessboard with 21 rows, each representing one of the girls, and 21 columns, each representing one of the boys. For each $g\in G$ and $b\in B$, by condition (b) there exists a problem $p$ in $P(g)\cap P(b)$; and assign $p$'s color to the square corresponding to $(g,b)$. By the Pigeonhole Principle, one of the two colors is assigned to at least \lceil 441/2\rceil = 221 squares, and thus some row has at least \lceil 221/21\rceil = 11 blue squares or some column has at least 11 red squares.

First suppose that there is a row, corresponding to $g\in G$, which has at least 11 blue squares. Then for each of the 11 squares, the blue problem that was chosen in assigning the color was solved by at most 2 boys. Thus, we account for at least \lceil 11/2\rceil = 6 distinct problems solved by $g$. In view of condition (a), $g$ solves only these problems. But then at most 12 boys solve a problem also solved by $g$, in violation of condition (b). A similar proof shows that it is impossible for any column to contain 11 red squares.

Hence, our original assumption was wrong and there are some $p\in P$ satisfying $|G(p)|\ge 3$ and $|B(p)|\ge 3$.

Sixth Solution. (By Reid Barton) Assign each problem a unique letter, and also number the boys 1, 2, ..., 21 and number the girls 1, 2, ..., 21. Construct a 21 × 21 matrix of letters as follows: in the $i$th row and $j$th column, write the letter of any problem that both the $i$th girl and the $j$th boy solved — at least one such problem exists by condition (b). If we consider the $i$th row, each letter in that row corresponds to a problem that the $i$th girl solved. Since each girl solved at most six problems, each row contains at most 6 distinct letters. Similarly, each column contains at most 6 distinct letters.

Lemma 4. In each row (resp., column), consider the letters which appear at least three times. At least 11 squares in the row (resp., column) contain one of these letters.

Proof. There are at most 6 different letters, and they cannot all appear at most twice, since there are $21>12$ letters total. So at most 5 different letters appear at most twice, giving a total of at most 10 squares containing letters appearing at most twice. Then at least 11 other squares each contain a letter that appears at least three times. ■

In the matrix, color all the squares which contain letters appearing at least three times in the same row (resp., column) in red (resp., blue). By Lemma 4, each row contains at least 11 red squares, so the total number of red squares is at least $21\times 11$. Similarly, each column contains at least 11 blue squares, so the total number of blue squares is at least $21\times 11$. Since there are only $21\times 21<21\times 11+21\times 11$ total squares, some square is colored both red and blue. Because the letter in this square appears in three different columns and three different rows, at least three boys and three girls solved the corresponding problem. Thus, we find the problem satisfying the desired property.