Maths Olympiad Prep

Library / /12 of 33

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Turkey

In the round robin chess tournament organized in a school every two students played one match among themselves. Find the minimal possible number of students in the school if each girl student has at least 21 wins in matches against boy students and each boy student has at least 12 wins in matches against girl students.

Solution

The answer is 6565. Suppose that there are xx girl and yy boy students in the school. Obviously xy21x+12yxy \ge 21x + 12y is a necessary condition for the existence of the tournament with given conditions. Let us show that this inequality is also a sufficient condition for the existence of the tournament. Let us consider x×yx \times y score table of the tournament. We put 11 (alternatively \emptyset) in the intersection of mm-th row and nn-th column if mm-th girl wins (alternatively loses) the match with nn-th boy. Let us prove that there is a table in which each row contains at least 2121 entries 11 and each column contains at least 1212 entries \emptyset.

We start with the table where each entry of the first 2121 columns is 11 and each other entry is \emptyset and step by step move to the table satisfying the conditions. Suppose that kk-th column contains less than 1212 \emptyset's. Since the total number of \emptyset's is not less than 12y12y then some ll-th column should contain more than 1212 \emptyset's. In this case we choose a row such that the intersection of this row with kk-th and ll-th columns are 11 and \emptyset, respectively and switch these two entries. After each move some column with \emptyset shortage gains one \emptyset and the total number of 11 entries of each row does not change. Therefore after finite number of moves we will get the desired table. Done.

Now let us find the minimal value of x+yx + y. The inequality (x12)(y21)1221(x - 12)(y - 21) \ge 12 \cdot 21 is equivalent to xy21x+12yxy \ge 21x + 12y. By AM-GM inequality we get
(x12)+(y21)2(x12)(y21)21221>31. (x-12) + (y-21) \ge 2\sqrt{(x-12)(y-21)} \ge 2\sqrt{12 \cdot 21} > 31.
Thus, x+y12+21+32=65x + y \ge 12 + 21 + 32 = 65. Any pair out of (26,39)(26,39), (27,38)(27,38), (28,37)(28,37), (29,36)(29,36), (30,35)(30,35) with sum 6565 satisfies the condition xy21x+12yxy \ge 21x + 12y. Done.

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.