Browse · MathNet

IMO Team Selection Contest

Estonia counting and probability

Problem

A class consists of

7

boys and

13

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.

Solution

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} ∣ \geq ∣ T_{2} ∣ \geq \dots \geq ∣ T_{7} ∣

. Consider two cases.

1. The case

∣ T_{1} ∣ + ∣ T_{2} ∣ + ∣ T_{3} ∣ + ∣ T_{4} ∣ \geq 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 \leq 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} ∣ \geq ∣ T_{1} ∣ + ∣ T_{2} ∣ + ∣ T_{3} ∣ + ∣ T_{4} ∣ - k \geq 20 - 6 = 14

This is a contradiction since there are only

13

girls.

2. The case

∣ T_{1} ∣ + ∣ T_{2} ∣ + ∣ T_{3} ∣ + ∣ T_{4} ∣ \leq 19

. As

∣ T_{5} ∣ + ∣ T_{6} ∣ + ∣ T_{7} ∣ \geq 12

, we have

∣ T_{5} ∣ \geq 4

. Now

∣ T_{4} ∣ \leq 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} ∖ T_{1} ∣ + ∣ T_{3} ∖ (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} ∖ T_{1}

and

T_{3} ∖ (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} ∖ (T_{1} \cup T_{2})

.

---

Alternative solution.

Solution 2: Let

A

be the set of all combinations of two boys,

∣ A ∣ = (2 7) = 21

. Say that girl

t

determines an element

{p_{1}, p_{2}}

A

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

(2 n _{1}) + (2 n _{2}) + (2 n _{3})

elements of

A

. Applying Jensen's inequality for

f (x) = \frac{x ( x - 1 )}{2}

gives

(2 n _{1}) + (2 n _{2}) + (2 n _{3}) \geq 3 \cdot f (\frac{n _{1} + n _{2} + n _{3}}{3}) = 3 \cdot f (\frac{7}{3}) = 4 \frac{2}{3}

. As

(2 n _{1}) + (2 n _{2}) + (2 n _{3})

is an integer,

(2 n _{1}) + (2 n _{2}) + (2 n _{3}) \geq 5

. Hence all girls determine at least

13 \cdot 5 = 65

elements of

A

in total. As

65 \geq 3 \cdot 21 + 1

, an element

{p_{1}^{*}, p_{2}^{*}}

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.

---

Alternative solution.

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

⎩ ⎨ ⎧ g_{2} + 3 g_{3} + 6 g_{4} + 10 g_{5} + 15 g_{6} + 21 g_{7} \leq 21, g_{1} + g_{2} + g_{3} + g_{4} + g_{5} + g_{6} + g_{7} \leq 13, g_{1} + 2 g_{2} + 3 g_{3} + 4 g_{4} + 5 g_{5} + 6 g_{6} + 7 g_{7} \geq 31.

If at least one girl acquainted with

5

or more boys then

g_{5} + g_{6} + g_{7} \geq 1

. The system then reduces to

⎩ ⎨ ⎧ g_{2} + 3 g_{3} + 6 g_{4} + 10 (g_{5} + g_{6} + g_{7} - 1) \leq 11, g_{1} + g_{2} + g_{3} + g_{4} + (g_{5} + g_{6} + g_{7} - 1) \leq 12, g_{1} + 2 g_{2} + 3 g_{3} + 4 g_{4} + 7 (g_{5} + g_{6} + g_{7} - 1) \geq 24.

Summing the first two inequalities gives

g_{1} + 2 g_{2} + 4 g_{3} + 7 g_{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

⎩ ⎨ ⎧ g_{2} + 3 g_{3} + 6 g_{4} \leq 21, g_{1} + g_{2} + g_{3} + g_{4} \leq 13, g_{1} + 2 g_{2} + 3 g_{3} + 4 g_{4} \geq 31.

Suppose that

g_{4} \geq 1

. As in the previous case, this implies

⎩ ⎨ ⎧ g_{2} + 3 g_{3} + 6 (g_{4} - 1) \leq 15, g_{1} + g_{2} + g_{3} + (g_{4} - 1) \leq 12, g_{1} + 2 g_{2} + 3 g_{3} + 4 (g_{4} - 1) \geq 27.

The first two inequalities sum up to

g_{1} + 2 g_{2} + 4 g_{3} + 7 (g_{4} - 1) \leq 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} \leq 12

and

g_{1} + 2 g_{2} \geq 27

, which contradict each other since

g_{1} + 2 g_{2} \leq 2 (g_{1} + g_{2})

.

Hence also

g_{4} = 0

and our system of inequalities reduces to

⎩ ⎨ ⎧ g_{2} + 3 g_{3} \leq 21, g_{1} + g_{2} + g_{3} \leq 13, g_{1} + 2 g_{2} + 3 g_{3} \geq 31.

Subtracting the first inequality from the third one, we obtain

g_{1} + g_{2} \geq 10

. Subtracting twice the second inequality from the third one, we get

g_{3} - g_{1} \geq 5

. The two inequalities obtained sum up to

g_{2} + g_{3} \geq 15

, contradicting the second inequality.

Techniques

Pigeonhole principleInclusion-exclusionJensen / smoothing