Problem 2217

Solution 1: Call the first communication between a boy and a girl their acquaintance. During the $3$ months, there are $7 \cdot 13 = 91$ acquaintances in total. Thus there exists a month when there was at least $31$ acquaintances. Let the boys be denoted by $p_1$ through $p_7$ and let $T_i$, $i = 1, \dots, 7$, be the set of girls to whom $p_i$ acquainted in this month. We have to show that there exist distinct $i$ and $j$ such that $T_i \cap T_j$ contains at least $2$ girls. W.l.o.g., assume the inequalities $|T_1| \ge |T_2| \ge \dots \ge |T_7|$. Consider two cases.

1. The case $|T_1| + |T_2| + |T_3| + |T_4| \ge 20$. Suppose that all intersections $T_1 \cap T_2$, $T_1 \cap T_3$, $\dots$, $T_3 \cap T_4$ contain at most one girl. Let $k \le 6$ be the number of non-empty intersections. Then the first four boys acquainted with
$$|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 $13$ girls.

2. The case $|T_1| + |T_2| + |T_3| + |T_4| \le 19$. As $|T_5| + |T_6| + |T_7| \ge 12$, we have $|T_5| \ge 4$. Now $|T_4| \le 4$ implies $|T_4| = |T_5| = 4$ and hence also $|T_6| = |T_7| = 4$. Now $|T_1| + |T_2| + |T_3| = 15$ in order to get $31$ in total.
Suppose that all intersections $T_i \cap T_j$, $i, j = 1, \dots, 7$, contain at most one girl. If boys $p_1, p_2$ and $p_3$ altogether acquainted with all girls in this month then at least one intersection $T_i \cap T_4$, $i = 1, 2, 3$, contains at least two girls. Otherwise, $|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 $t_{13}$, with whom none of $p_1, p_2, p_3$ acquainted. Clearly all boys $p_4, p_5, p_6, p_7$ must have acquainted with her, and each of them also acquainted with one girl from sets $T_1$, $T_2 \setminus T_1$ and $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 $T_3 \setminus (T_1 \cup T_2)$.

Solution 2: Let $A$ be the set of all combinations of two boys, $|A| = \binom{7}{2} = 21$. Say that girl $t$ determines an element $\{p_1, p_2\}$ of $A$ if $t$ acquainted with $p_1$ and $p_2$ in the same month. If in the $i$th month a girl $t$ acquainted with exactly $n_i$ boys, where $i = 1, 2, 3$, then $t$ determines $\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2}$ elements of $A$. Applying Jensen's inequality for $f(x) = \frac{x(x-1)}{2}$ gives $\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 $\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2}$ is an integer, $\binom{n_1}{2} + \binom{n_2}{2} + \binom{n_3}{2} \ge 5$. Hence all girls determine at least $13 \cdot 5 = 65$ elements of $A$ in total.
As $65 \ge 3 \cdot 21 + 1$, an element $\{p_1^*, p_2^*\}$ of $A$ is determined by at least $4$ 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: Suppose that there is no required pairs of boys and girls. Like in Solution 1, consider a month with $31$ or more acquaintances. Let $g_i$ be the number of girls who acquainted with exactly $i$ boys in this month, $i = 0, 1, \dots, 7$. We get a system of inequalities
$$\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 $5$ or more boys then $g_5 + g_6 + g_7 \ge 1$. The system then reduces to
$$\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
$$g_1 + 2g_2 + 4g_3 + 7g_4 + 11(g_5 + g_6 + g_7 - 1) \leq 23,$$
which contradicts the third inequality.
Thus $g_5 = g_6 = g_7 = 0$ and the system of inequalities reduces to
$$\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 $g_4 \ge 1$. As in the previous case, this implies
$$\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 $g_1 + 2g_2 + 4g_3 + 7(g_4 - 1) \le 27$. In the light of the third inequality, this is possible only if $g_3 = 0$ and $g_4 = 1$. Then the second and third inequalities give $g_1 + g_2 \le 12$ and $g_1 + 2g_2 \ge 27$, which contradict each other since $g_1 + 2g_2 \le 2(g_1 + g_2)$.

Hence also $g_4 = 0$ and our system of inequalities reduces to
$$\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 $g_1 + g_2 \ge 10$. Subtracting twice the second inequality from the third one, we get $g_3 - g_1 \ge 5$. The two inequalities obtained sum up to $g_2 + g_3 \ge 15$, contradicting the second inequality.