There are $2007$ boys and $2007$ girls in a middle school,every student can attend no more than $100$ academic meetings,if we know any pair of students with different sex attend at least one common meeting.prove that there must be a meeting with at least $11$ boys and $11$ girls attend.
Problem
Source: 2007 HongKong mathematical Olympiad
Tags: combinatorics proposed, combinatorics
31.10.2013 21:08
Say we have set of meetings $\mathcal{M}= \{M_1,M_2,...,M_n\}$. Let $\mathcal{B}$ be set of boys and $\mathcal{G}$ set of girls. Let $d(S)=\#$ of meetings student $S$ attend, thus $d(S)\leq 100$. Let $g_i = \# $ girls attending meeting $M_i$ and $b_i = \# $ boys attending meeting $M_i$. So we have \[\sum_{i=1}^n b_i= \sum _{B\in \mathcal{B}} d(B) \leq 100\cdot 2007 \] and \[\sum_{i=1}^n g_i= \sum _{G\in \mathcal{G}} d(G) \leq 100\cdot 2007 \] Since every pair $(B,G)\in \mathcal{B}\times \mathcal{G}$ has attend at least one common meeting we have $d(B,G)\geq 1$, so we have \[2007^2\leq \sum _{(B,G)\in \mathcal{B}\times \mathcal{G} } d(B,G) = \sum_{i=1}^n g_i\cdot b_i \] Say $g_i\leq 10 $ or $b_i\leq 10$ for all $i$. Then we can split $\mathcal{M}$ in 3 disjoint subsets: Set $\mathcal{A}$ contains meetings with at most 10 boys and at most 10 girls, set $\mathcal{B}$ contains meetings with at most 10 boys and at least 11 girls and set $\mathcal{C}$ contains meetings with at most 10 girls and at least 11 boys. Now let $\mathcal{X}'$ be set of all index of meetings in $ \mathcal{X}$, where $ \mathcal{X}\in \{\mathcal{A}, \mathcal{B}, \mathcal{C}\}$. So we have: \begin{eqnarray*} 2007^2 &\leq & \sum_{i\in \mathcal{A}'} g_i\cdot b_i +\sum_{i\in \mathcal{B}'} g_i\cdot b_i+\sum_{i\in \mathcal{C}'} g_i\cdot b_i \\ &\leq & \sum_{i\in \mathcal{A}'} g_i\cdot b_i +\sum_{i\in\mathcal{B}'} g_i\cdot b_i+\sum_{i\in\mathcal{A}'} g_i\cdot b_i+\sum_{i\in\mathcal{C}'} g_i\cdot b_i\\ &\leq & \sum_{i\in\mathcal{A}'} g_i\cdot 10 +\sum_{i\in\mathcal{B}'} g_i\cdot 10+\sum_{i\in\mathcal{A}'} 10\cdot b_i+\sum_{i\in\mathcal{C}'} 10\cdot b_i\\ &= & \sum_{i=1}^n g_i\cdot 10 +\sum_{i=1}^n 10\cdot b_i\\ &\leq & 100\cdot 2007\cdot 10 + 10\cdot 100\cdot 2007 = 2000\cdot 2007 \end{eqnarray*} Contradiction.
07.03.2021 16:52
Let $B_1,B_2,...,B_{2007}$ the boys and $G_1,G_2,..,G_{2007}$ the girls. Consider a $2007\times 2007$ grid with boys as columns and girls as rows. In the intersection cell of a row and a column we putt the common meeting of the two students. Take an arbitrary row $G_i$ Since this row has at most $100$ differents elements there exist a meeting which is contained at least $\dfrac{2007}{100}>11$ times. So the number of meetings which is contained at most $10$ times in this row is $\leq 99$. This means that there exist $\geq 2007-99\cdot 10>2007/2$ cells in this row which contain meetings which are contained at least $11$ times in this row(we call these cells "nice"). Do the same thing in the all the others rows. Then color all "nice" cells black. Do the same thing in the all columns, and color the "nice" cells red. Since the number of "nice" cells in each row and each column is $>2007/2$ there is a cell which is colored black and red . Take the meeting in this cell and we are done!
02.07.2021 09:42
Solution. The main idea is double counting triples of the form $(boy,girl,club)$. Let there be $T$ such triples. Assume the opposite. Let $X$ be the number of triples such that the clubs contain at most $10$ boys. Let $Y$ be the number of triples such that the clubs contain at most $10$ girls. There are $2007 \times 100$ pairs of the form $(girl, club)$, since there at most $10$ boys, we have that $X\leq 2007 \times 100 \times 10=2007 \times 1000$. Similarly, $Y \leq 2007\times 1000$. We have $$2007^2 \leq T \leq X+Y \leq 2007\times 2000.$$A contradiction.