Maths Olympiad Prep

Library / /3 of 14

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Estonia

A class consists of 77 boys and 1313 girls. During the first three months of the school year, each boy has communicated with each girl at least once. Prove that there exist two boys and two girls such that both boys communicated with both girls first time in the same month.

Solutions — 3

Solution 1

Solution 1: Call the first communication between a boy and a girl their acquaintance. During the 33 months, there are 713=917 \cdot 13 = 91 acquaintances in total. Thus there exists a month when there was at least 3131 acquaintances. Let the boys be denoted by p1p_1 through p7p_7 and let TiT_i, i=1,,7i = 1, \dots, 7, be the set of girls to whom pip_i acquainted in this month. We have to show that there exist distinct ii and jj such that TiTjT_i \cap T_j contains at least 22 girls. W.l.o.g., assume the inequalities T1T2T7|T_1| \ge |T_2| \ge \dots \ge |T_7|. Consider two cases.

1. The case T1+T2+T3+T420|T_1| + |T_2| + |T_3| + |T_4| \ge 20. Suppose that all intersections T1T2T_1 \cap T_2, T1T3T_1 \cap T_3, \dots, T3T4T_3 \cap T_4 contain at most one girl. Let k6k \le 6 be the number of non-empty intersections. Then the first four boys acquainted with
T1T2T3T4T1+T2+T3+T4k206=14 |T_1 \cup T_2 \cup T_3 \cup T_4| \ge |T_1| + |T_2| + |T_3| + |T_4| - k \ge 20 - 6 = 14
This is a contradiction since there are only 1313 girls.

2. The case T1+T2+T3+T419|T_1| + |T_2| + |T_3| + |T_4| \le 19. As T5+T6+T712|T_5| + |T_6| + |T_7| \ge 12, we have T54|T_5| \ge 4. Now T44|T_4| \le 4 implies T4=T5=4|T_4| = |T_5| = 4 and hence also T6=T7=4|T_6| = |T_7| = 4. Now T1+T2+T3=15|T_1| + |T_2| + |T_3| = 15 in order to get 3131 in total.
Suppose that all intersections TiTjT_i \cap T_j, i,j=1,,7i, j = 1, \dots, 7, contain at most one girl. If boys p1,p2p_1, p_2 and p3p_3 altogether acquainted with all girls in this month then at least one intersection TiT4T_i \cap T_4, i=1,2,3i = 1, 2, 3, contains at least two girls. Otherwise, T1+T2T1+T3(T1T2)=1512=12|T_1| + |T_2 \setminus T_1| + |T_3 \setminus (T_1 \cup T_2)| = 15 - 1 - 2 = 12 (Fig. 33 shows all possibilities), since only then there is a girl, say t13t_{13}, with whom none of p1,p2,p3p_1, p_2, p_3 acquainted. Clearly all boys p4,p5,p6,p7p_4, p_5, p_6, p_7 must have acquainted with her, and each of them also acquainted with one girl from sets T1T_1, T2T1T_2 \setminus T_1 and T3(T1T2)T_3 \setminus (T_1 \cup T_2). As the last set contains at most three elements, two of the four boys acquainted with the same girl from T3(T1T2)T_3 \setminus (T_1 \cup T_2).

Solution 2

Solution 2: Let AA be the set of all combinations of two boys, A=(72)=21|A| = \binom{7}{2} = 21. Say that girl tt determines an element {p1,p2}\{p_1, p_2\} of AA if tt acquainted with p1p_1 and p2p_2 in the same month. If in the iith month a girl tt acquainted with exactly nin_i boys, where i=1,2,3i = 1, 2, 3, then tt determines (n12)+(n22)+(n32)\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2} elements of AA. Applying Jensen's inequality for f(x)=x(x1)2f(x) = \frac{x(x-1)}{2} gives (n12)+(n22)+(n32)3f(n1+n2+n33)=3f(73)=423\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2} \ge 3 \cdot f(\frac{n_1+n_2+n_3}{3}) = 3 \cdot f(\frac{7}{3}) = 4\frac{2}{3}. As (n12)+(n22)+(n32)\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2} is an integer, (n12)+(n22)+(n32)5\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2} \ge 5. Hence all girls determine at least 135=6513 \cdot 5 = 65 elements of AA in total.
As 65321+165 \ge 3 \cdot 21 + 1, an element {p1,p2}\{p_1^*, p_2^*\} of AA is determined by at least 44 girls by the pigeonhole principle. Consequently there exists a month in which this couple of boys is determined by at least two girls.

Solution 3

Solution 3: Suppose that there is no required pairs of boys and girls. Like in Solution 1, consider a month with 3131 or more acquaintances. Let gig_i be the number of girls who acquainted with exactly ii boys in this month, i=0,1,,7i = 0, 1, \dots, 7. We get a system of inequalities
{g2+3g3+6g4+10g5+15g6+21g721,g1+g2+g3+g4+g5+g6+g713,g1+2g2+3g3+4g4+5g5+6g6+7g731. \left\{ \begin{array}{l} g_2 + 3g_3 + 6g_4 + 10g_5 + 15g_6 + 21g_7 \le 21, \\ g_1 + g_2 + g_3 + g_4 + g_5 + g_6 + g_7 \le 13, \\ g_1 + 2g_2 + 3g_3 + 4g_4 + 5g_5 + 6g_6 + 7g_7 \ge 31. \end{array} \right.
If at least one girl acquainted with 55 or more boys then g5+g6+g71g_5 + g_6 + g_7 \ge 1. The system then reduces to
{g2+3g3+6g4+10(g5+g6+g71)11,g1+g2+g3+g4+(g5+g6+g71)12,g1+2g2+3g3+4g4+7(g5+g6+g71)24. \left\{ \begin{array}{l} g_2 + 3g_3 + 6g_4 + 10(g_5 + g_6 + g_7 - 1) \le 11, \\ g_1 + g_2 + g_3 + g_4 + (g_5 + g_6 + g_7 - 1) \le 12, \\ g_1 + 2g_2 + 3g_3 + 4g_4 + 7(g_5 + g_6 + g_7 - 1) \ge 24. \end{array} \right.
Summing the first two inequalities gives
g1+2g2+4g3+7g4+11(g5+g6+g71)23, g_1 + 2g_2 + 4g_3 + 7g_4 + 11(g_5 + g_6 + g_7 - 1) \leq 23,
which contradicts the third inequality.
Thus g5=g6=g7=0g_5 = g_6 = g_7 = 0 and the system of inequalities reduces to
{g2+3g3+6g421,g1+g2+g3+g413,g1+2g2+3g3+4g431. \left\{ \begin{array}{l} g_2 + 3g_3 + 6g_4 \le 21, \\ g_1 + g_2 + g_3 + g_4 \le 13, \\ g_1 + 2g_2 + 3g_3 + 4g_4 \ge 31. \end{array} \right.
Suppose that g41g_4 \ge 1. As in the previous case, this implies
{g2+3g3+6(g41)15,g1+g2+g3+(g41)12,g1+2g2+3g3+4(g41)27. \left\{ \begin{array}{l} g_2 + 3g_3 + 6(g_4 - 1) \le 15, \\ g_1 + g_2 + g_3 + (g_4 - 1) \le 12, \\ g_1 + 2g_2 + 3g_3 + 4(g_4 - 1) \ge 27. \end{array} \right.
The first two inequalities sum up to g1+2g2+4g3+7(g41)27g_1 + 2g_2 + 4g_3 + 7(g_4 - 1) \le 27. In the light of the third inequality, this is possible only if g3=0g_3 = 0 and g4=1g_4 = 1. Then the second and third inequalities give g1+g212g_1 + g_2 \le 12 and g1+2g227g_1 + 2g_2 \ge 27, which contradict each other since g1+2g22(g1+g2)g_1 + 2g_2 \le 2(g_1 + g_2).

Hence also g4=0g_4 = 0 and our system of inequalities reduces to
{g2+3g321,g1+g2+g313,g1+2g2+3g331. \left\{ \begin{array}{l} g_2 + 3g_3 \le 21, \\ g_1 + g_2 + g_3 \le 13, \\ g_1 + 2g_2 + 3g_3 \ge 31. \end{array} \right.
Subtracting the first inequality from the third one, we obtain g1+g210g_1 + g_2 \ge 10. Subtracting twice the second inequality from the third one, we get g3g15g_3 - g_1 \ge 5. The two inequalities obtained sum up to g2+g315g_2 + g_3 \ge 15, contradicting the second inequality.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.