After reading Count Down, I decided to look up this problem. However, I've spent about 30 minutes reading this proof (for there is no other that I can find) and am still stumped. Phelpedo wrote: Suppose to the contrary that the only $ 1$'s are in rows solved by at most two boys or two girls. This contradiction doesn't cover the case where there are 1's in rows solved by THREE boys, but at most two girls. Or does it? The bounds definitely don't work considering this.

I have the same problem as eternica but i have an alternate solution. call a problem Legit if it is solved by atleast 3 boiz and Legitimate if it is solved by atleast 3 gurlz. out of the 21 pairs formed with any gurl, there must be atleast 11 legit problems and with 21 gurlz there are 21*11 legit problems and by the same argument there are 21*11 legitimate problems making 22*21 problems but there are only 21*21 problems so some problems must be legit and legitimate.

Call a problem bad if it's solved by at most $2$ boys, and good if it's solved by at most $2$ girls. Assume every problem is either good or bad and argue by contradiction. Construct a $21$x$21$ grid where the entry at position $(i, j)$ gives a problem solved by both boy $i$ and girl $j$. By PHP at least $\lceil 441/2 \rceil = 221$ squares in this grid contain (WLOG) bad problems; PHP once again on the row these bad problems appear in gives a row with at least $\lceil 221 / 21 \rceil = 11$ squares with bad problems. Yet any bad problem is solved by at most $2$ boys, so any particular bad problem can appear in at most $2$ of the squares in this row. It follows that there are at least $\lceil 11 / 2 \rceil = 6$ distinct bad problems in this row. This is impossible; $6$ distinct bad problems are solved by at most $12$ boys, leaving $9$ boys who solved no problems in common with this particular girl, contradiction. It follows that there exists some problem solved both by at least $3$ boys and at least $3$ girls.

Incorrect, please ignore.

Assume the conclusion is false. $(*)$If there exists a problem which was solved by only boys or only girls,we remove it.The configuration left still satisfies the hypothesis. So now each problem has been solved by at least 1 boy and 1 girl. From now on we work under the conditions of $(*)$, that is, every problem was solved by 1 of each gender. Say there are $m$ problems, and denote by $x_i$ and $y_i$ the number of boys respectively girls which solved problem $i$; due to $(*)$ we have $x_i>0,y_i>0$, and due to our negation of the conclusion we cannot simultaneously have $x_i \ge 3,y_i \ge 3$.Also, since every contestant solved at most 6 problems, there are exactly 21 of them, and $\sum x_i$ is the total number of problems solved by the boys,we get that $\sum x_i \le 21*6,\sum y_i \le 21*6(1)$. Now consider the bipartite graphs $G_i$, $i=1,2,...,m$, which has 21 vertices on one side, name it the left side, and 21 on the other, name it the right side, and vertices $k$ on the left and $l$ on the right are connected if and only if boy $k$ and girl $l$ both solved problem $i$; we also consider the graph $G$, built by adjoining the $m$ $G_i$'s, and the corresponding edge sets $E_i$ and $E$. It is obvious that $|E_i|$ is the number of boy-girl pairs that both solved problem $i$, equal to $x_iy_i$,while $|E|=\sum |E_i|=\sum x_iy_i(2)$; however,$|E|$ being the number of boy-girl pairs which solved a problem counted over all the m problems leads to $|E| \ge 21^2(3)$, due to every boy-girl pair having solved at least one problem in common, and there being $21^2$ of them. We also have the bound $x_iy_i \le 2x_i+2y_i-3(4)$, which is true due to being equivalent to $(x_i-2)(y_i-2) \le 1$, which can be easily proven using the conditions set on $x_i,y_i$. Putting together $(1),(2),(3)$ and $(4)$ we obtain a bound on $m$: $21^2 \le |E|=\sum x_iy_i \le \sum 2x_i+2y_i-3=(\sum 2x_i)+(\sum2y_i)-3m \le 21*6*4-3m \Rightarrow m \le 21$. Now,of these $m$ problems,let's say $k$ have been solved by 2 or fewer boys;then the other $m-k$ have been solved by 2 or fewer girls.It is trivial to notice that $m \le 21$ forces $min(k,m-k) \le 10$;assume WLOG the minimum is $k$;then $k\le 10$.Now out of the 21 boys,there must be one,name him $B$, that didn't solve any of those problems, since there are at most $2*10=20$ boys who solved them; then he will have solved problems only from the $m-k$ remaining ones. However,now for each of the problems he solved, there exist at most 2 girls who also solved them,so there exist at most $6*2=12$ girls who could have solved a problem that $B$ also solved,leaving 9 girls who don't have any problem in common with $B$,contradiction. This contradiction stems from our initial assumption,which was the negation of our conclusion,so our proof is finished.

A standard double count helps : My solution is basically same as the official one; though I named the problems differently, not tough for boys or tough for girls .

Is there a way of solving this problem without finding a person that violates the first condition? In other words can one show that there are no integer numbers $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$ that satisfy ($a_i,b_i$ denote the number of boys and girls that solved problem $i$ respectively). $0 \leq a_i,b_i \leq 21$ and $\sum a_i \leq 6\cdot 21$ and $\sum b_i \leq 6\cdot 21$ such that $\sum a_i b_i \geq 21\cdot 21$

With at least one of $a_i$ and $b_i$ being less than or equal to $2$ for each $i$. *

mcdonalds106_7 wrote: Assume that no problem is solved by at least three girls and three boys, and discard any problem that is solved by only boys and only girls (Clearly this can only help us). Let there be $n$ problems left, and for problem $i$, assign the ordered pair $(b_i, g_i)$ such that $b_i$ boys and $g_i$ girls solved the problem. Then, it's clear that $b_1g_1+\ldots +b_ng_n\ge 441$ and $b_1+\ldots +b_n\ge 126$ as well as $g_1+\cdots +g_n\ge 126$. Now, note that we must have $(b_i-2)(g_i-2)\le 1$ for all $i$, so $b_ig_1\le 2b_i+2g_i-3$, hence it follows that $441\le b_1g_1+\ldots +b_ng_n\le 504-3n$, so $n\le 21$. Now, consider any boy. Since he solved $6$ problems, he must have solved a problem solved by at least $4$ girls. Label the boy with the number of this problem, and do the same with the girls. No three boys can have the same label, otherwise we have a contradiction. Then the boys have $11$ different problem labels among them, and same for the girls. But this is a contradiction since a boy and a girl can't share the same label, so we are done. e] Wasn't it done from n =<. 21?? since it implies that bi,gi all equal 6 for all i and it's a contradiction. Maybe i'm misunderstanding something.

Just commenting to come back

peregrinefalcon88 wrote: I have the same problem as eternica but i have an alternate solution. call a problem Legit if it is solved by atleast 3 boiz and Legitimate if it is solved by atleast 3 gurlz. out of the 21 pairs formed with any gurl, there must be atleast 11 legit problems and with 21 gurlz there are 21*11 legit problems and by the same argument there are 21*11 legitimate problems making 22*21 problems but there are only 21*21 problems so some problems must be legit and legitimate. Is this solution good? It's a bit cloudy for me yet..

Or just give me a reason why are there 11 legit (and legitimate) problems

Nvm I figured it out, also he basically "marked" the problems in such way that we could count them more times, I don't get why there is only 21^2 problems with marking.

Not the prettiest solution, there is a bit of casework at the end that I didn't include. Basically I counted triples $(b_i, g_j, P_k)$ such that both $b_i, g_j$ solved $P_k$ and tried finding a contradiction that the # of triples is less than $21^2$.

We will show the contrapositive. That is, assume that For each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Assume every problem is either solved mostly by girls (at most two boys) or mostly by boys (at most two girls). Then we will prove that then some contestant solved more than six problems. Create a $21 \times 21$ grid with boys as columns and girls as rows, and in each cell write the name of a problem solved by the pair. Color the cell green if at most two girls solved that problem, and color it blue if at most two boys solved that problem. (G for girl, B for boy. It's possible both colors are used for some cell.) WLOG, there are more green cells than blue, so (by pigeonhole) take a column (boy) with that property. That means the boy's column has at least $11$ green squares. By hypothesis, those corresponds to at least $6$ different problems solved. Now there are two cases: If there are any blue-only squares, then that square means a seventh distinct problems. If the entire column is green, then among the $21$ green squares there are at least $11$ distinct problems solved in that column.

Let the boys and girls be $b_1, \dots , b_{21}, g_1, \dots , g_{21}$. Say a problem is bad-for-girls if at most 2 girls solve it. For a pair $(b_i,g_j)$, we say that the pair is bad-for-girls if there was a bad-for-girls problem solved by both of them. Similarly define bad-for-boys problems/pairs. For each $i$, let $B_i$ be the set of problems solved by $b_i$. By the given conditions we must have that some problem in $B_i$ is solved at least $\lceil \frac{21}{6} \rceil > 3$ times by girls; thus at most 5 problems in $B_i$ are bad-for-girls. By definition, this means that for any fixed $i$, at most 10 of the 21 pairs $(b_i, g_1), (b_i, g_2), \dots , (b_i, g_{21})$ are bad-for-girls. Summing across all $i$ we get that there are in total at most $10 \cdot 21 = 210$ bad-for-girl pairs. Similarly, at most $210$ of the $441$ pairs of students are bad-for-boys. Since $210+210<441$ there must be a pair of students which is neither bad-for-girls nor bad-for-boys; then this pair must have solved a problem that was neither bad-for-girls nor bad-for-boys, as desired.

Consider a complete bipartite graph with the $21$ boys $b_1,\ldots,b_{21}$ on the left and the $21$ girls $g_1,\ldots,g_{21}$ on the right. Label the edge $b_ig_j$ by a common problem solved by the two (pick arbitrarily if many). Call a problem good if at least $3$ girls solved it, and call an edge good if it is labeled by a good problem. We have the following key claim. Claim: There are at least $21\cdot 11$ good edges. Proof: Consider a boy $b_i$, and suppose he solved $m$ problems (note that $m\le 6$). Let the outdegrees from $b_i$ be $x_1,\ldots,x_m$ for each of the $m$ labels. We see that if $x_i\ge 3$, then those $x_i$ edges are good. Thus, there are at least \[\sum_{i:x_i\ge 3}x_i\]good edges coming out of $b_i$. It is easy to verify that this is always at least $21-5\cdot 2=11$, so we're done. $\blacksquare$ If we swap boys and girls, then the same claim implies that there at least $21\cdot 11$ "boy-good" edges, so some edge is boy-good and girl good. Then, that problem has at least three solves from both genders, so we're done.

Draw the graph $a_{1}, a_{2}, \ldots a_{21}, b_{1}, \ldots b_{21}$, where $a_{i}$ represents the ith boy, and $b_{j}$ represents the $j$th girl. Draw directed edge between $a_{i}$ and $b_{j}$ if there exists a problem that $a_{i}$ and $b_{j}$ both solved, and that problem has more than $3$ solutions from girls. Similarly, draw the directed edge in the other direction with boys and girls reversed. I claim there are at least $21\cdot 11$ edges going from $a_{i}$ to $b_{j}$, for some $i$ and $j$. Observe that for any boy $a_{i}$, there will be some positive number of problems that are solved by at least $3$ girls and $a_{i}$. This means there are at least $21 - 5\cdot 2$ girls who solved a problem that $a_{i}$ did, in which the problem has more than $3$ solves. Similarly, there are at least $21\cdot 11$ edges going from $b_{j}$ to $a_{i}$. Since $21\cdot 11 + 21\cdot 11 > 21^2$, there must be some edge that is bidirectional, so some problem is solved by at least $3$ boys and $3$ girls.

orl wrote: Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys. Fix a girl $G$ and consider all pairings with the boys.By PHP,at least 3 boys and the girl $G$ have attempted the same question.Do the same thing for the boys and for each boy let $$D_{b_x}=\{g_x,g_{x+1},g_{x+2} \}$$be the set of the three girls who have attempted the same question as $b_x$;do the same thing for girls as well. By PHP again there are atleast $\frac{21 \cdot 3}{21}=3$ boys and girls having solved the same question.

We count the number of boy-girl pairs that solved a problem that at most two people of the same gender have solved. For any person, at most five of the six problems they solved were solved by at most two people of the opposite gender. Thus the maximum number of these pairs is $21\cdot2\cdot5=210$. But there are $21^2>2\cdot210$ boy-girl pairs with one common problem solved. This proves the statement.

Suppose that each problem is solved either by at most two girls or at most two boys. Construct a grid $21 \times 21$ the obvious way (the rows represent girls and the columns - boys; in each cell write the number of the problem solved by both the girl and the boy) and color a cell blue if it is a problem solved by at most two girls and red otherwise. By PHP at least $\lceil \frac {21^2}{2} \rceil =221$ cells are red (WLOG). Thus there is a row (a girl) having at least $\lceil \frac{221}{21} \rceil =11$ red cells (problems solved by at most two boys). Hence there are at least $6$ red numbers on this row (every red number can appear at most twice). But everyone has solved at most $6$ problems, so there are exactly $6$ different numbers on this row and we actually have $21$ red cells on this row. But using again the fact that each red number appears at most twice, we get that there are at least $11$ different numbers on that row, contradiction.

c8????? say that a problem is type 1 hard if it is solved by at most 2 boys, and say that a problem is type 2 hard if it is solved by at most 2 girls. Suppose FTSOC that each problem is either type 1 hard or type 2 hard (possibly both). Then, make a 21x21 grid, with the rows corresponding to the boys and the columns corresponding to the girls, and in each cell, put a problem that was solved by both of the. Note that if every problem is either type 1 hard or type 2 hard, then there are at least 221 cells that contain type 1 hard problems. Consequently, there must be some column that contains at least 11 type 1 hard problems. However, note that each type 1 hard problem is solved by at most 2 boys, so there must be at least 6 different type 1 hard problems that appear in this column. This means that the chosen girl solved 6 type 1 hard problems, so they could not have solved any other problems. However, if this girl solved only 6 type 1 hard problems, then they can only share a problem with at most 12 boys, contradiction so we are done.

Call a problem buggy if it was solved by at most two boys, and glitchy if it was solved by at most two girls. Assume for the sake of contradiction that every problem was buggy or glitchy. Let a buggy solve be an ordered pair $(B,p)$ of a boy and a problem such that $B$ solved $p$ and $p$ was buggy. Let a glitchy solve be an ordered pair $(G,p)$ of a girl and a problem such that $G$ solved $p$ and $p$ was glitchy. Now, consider each of the $441$ boy-girl pairs, and there exists a problem that they both solved. Thus, for each boy $B$ and girl $G$, there exists a problem $p$ so that $(B,p)$ was buggy or $(G,p)$ was glitchy. Without loss of generality, assume that of the $441$ such boy-girl pairs, at least $221$ of them has $(B,p)$ as a buggy pair. If it has a buggy pair, call the boy-girl pair bugged. Otherwise, call it glitched. Now, there are $21$ girls, so by pigeonhole principle there exists a girl $G_0$ such that $(B,G_0)$ is buggy $11$ times. Each buggy problem can only be solved by two boys, so there are six buggy problems. These buggy problems clearly must be the only ones solved by $G_0$. However, these $6$ buggy problems can only be solved by $12$ boys, so for $9$ boys $B$, $(B,G_0)$ is not buggy. Thus, $G_0$ must've solved a problem that is none of the six buggy problems before, contradiction.

We reinterpret the problem as follows: for each pair of boy and girl, we assign exactly one shared trait such that each person only has at most $6$ distinct traits. Since personality is a bit weird, the same trait might not express itself with everyone else, so it could be the case that a boy and a girl have the same trait, but it might not be the trait shared between them. Suppose that there are no traits held by at least three girls and three boys. Split the traits into two disjoint categories such that all boyish traits are held by at most $2$ girls and all girlish traits are held by at most $2$ boys. Number the boys $1$ through $21$ and let $b_i$ denote the number of girlish traits the $i$-th boy has, so he has at most $6-b_i$ boyish traits. If $b_i=0$ for some $i$, then this boy only has boyish traits and thus can only share a trait with at most $6\cdot 2=12$ girls, which is bad (such are the consequences of toxic masculinity), so $b_i \geq 1$ always. Then the number of girls who he shares a girlish trait with is at least $21-2(6-b_i)=9+2b_i \geq 11$. Summing across all boys, we find that at least $11\cdot 21$ boy-girl pairs share a girlish trait. But the analogous argument for girls implies that at least $11\cdot 21$ boy-girl pairs share a boyish trait. Since each boy-girl pair only shares $1$ trait and boyish and girlish traits are disjoint, this easily yields a contradiction. $\blacksquare$

Assassinate all the boys and girls, and buy a $21 \times 21$ grid instead. Fill each element of the grid with the common solves of the $i$th boy and $j$th girl. It then remains to show that some integer must appear in at least $3$ rows and at least $3$ columns. FTSOC suppose not. Now, define the capacity of a row / column as the number of distinct numbers that have appeared in it. Then the net capacity over all rows / columns is $6 \cdot 21 \cdot 2 = 252$. Now consider what happens when we fill some elements of the grid with an integer $a_i$. Let a thin integer be one with a grid which is $1 \times n$. Let a fat one be $2 \times n$. Claim: At least $21$ squares in the grid are thin. Proof. If some integer appears more than three times in a row, then that integer must be thin. This then holds for each row by pigeonhole. $\blacksquare$ Claim: The net capacity used to fill the grid is $\ge 252$ and equality only holds when all integers occur with grid $k \times 21$. Proof. A thin integer which has a $1 \times n$ lattice has a ratio of capacity to cells $\frac{n+1}{n} \ge \frac{22}{21}$, and there are at $n_T \ge 21$ of those. A fat integer which has a $2 \times n$ lattice of $\frac{2 + n}{2n} \ge \frac{23}{42}$, and there are $n_F \le 420$ of these. As such, if $R_T$ is the weighted ratio of thin integers and $R_F$ is the weighted ratio of fat integers, we have that the total cells used is \[ R_T \cdot n_T + R_F \cdot n_F \ge R_T \cdot 21 + R_F \cdot 420 \ge \frac{22}{21} \cdot 21 + \frac{23}{42} \cdot 420 = 252. \]Equality can only hold if the inequalities on all ratios of thin and fat integers holds, as desired. $\blacksquare$ However, the equality case can easily be seen not to work with the initial conditions, contradiction.