Mongolian Mathematical Olympiad

Question

Five girls and five boys participate in a tournament. Suppose that it is possible to number the girls from 1 to 5 and also the boys from 1 to 5 so that for all 1 i, j 5, the number of students that the i-th girl and the j-th boy both know is exactly |i - j|. Let S denote the maximum of the sum of the number of students that each girl knows and the sum of the number of students that each boy knows. What is the minimum possible value of S? Here we assume that the relationship of knowing is directional, that is, A knows B does not mean B knows A. We also do not consider students to know themselves.

Accepted Answer

Answer: 19. For 1 i 5, let a_i denote the i-th girl and let A_i denote the set of students that a_i knows. Similarly let b_i denote the i-th boy and let B_i denote the set of students that b_i knows. Since |A_i B_1| = i - 1, |A_i B_5| = 5 - i, we have |A_1| 4, |A_2| 3, |A_3| 2, |A_4| 3, |A_5| 4. Similarly for |B_i|. First suppose |A_1| = 4. Since |A_1 B_5| = 4, we have A_1 B_5, thus A_1 A_5 B_5 A_5 = . It follows that |B_i| |(A_1 A_5) B_i| = |A_1 B_i| + |A_5 B_i| = 4. Hence |B_i| 20. Similarly, if |A_5| = 4, then |B_i| 20. Now suppose |A_3| = 2. Then |A_3 B_1| = |A_3 B_5| = 2 implies that A_3 B_1 B_5. Hence |B_1| |A_5 B_1| + |B_5 B_1| 6. Analogously, we have |B_5| 6, therefore |B_i| 6 + 3 + 2 + 3 + 6 = 20. Finally, if |A_1| 5, |A_3| 3, |A_5| 5, then we have |A_i| 5 + 3 + 3 + 3 + 5 = 19. T…