Maths Olympiad Prep

Library / /53 of 54

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it China

There are nn (n>12n > 12) students participating in a mathematics contest. The examination paper consists of 15 fill-in-the-blank questions. For each question, the score of a correct answer is 1 point, and no point will be awarded if the answer is wrong or left blank. After analyzing all the possible cases of score distributions of these nn students, one finds out that if the sum of total scores of any 12 students is not less than 36 points, then there are at least 3 students among these nn students who answer at least 3 identical questions correctly. Determine the smallest possible value of nn. (Posed by Liu Shixiong)

Solution

The smallest nn is 911. We divide the proof into two parts:

(1) We first prove that n=911n = 911 satisfies the conditions. If each student answers at least 3 questions correctly, then for any student there are (153)=455\binom{15}{3} = 455 ways for him to have exactly 3 correct answers. If there are 911 students participating in the contest, it follows from the pigeonhole principle that there are at least 3 students having 3 identical correct answers.

If there is a student XX whose score is not more than 2, then the number of remaining students with a score not more than 3 cannot exceed 10; otherwise, pick any 11 of these students together with XX, and the sum of their total scores is less than 36 points. Then there are more than 91111=900911 - 11 = 900 students in the rest, such that each of them has a score less than 4. Since (43)=4\binom{4}{3} = 4, and 4×900>455×24 \times 900 > 455 \times 2, there are at least 3 students answering 3 identical questions correctly.

(2) There are 910 students participating in the contest. Divide them into 455=(153)455 = \binom{15}{3} groups, and there are exactly 2 students in each group. In each group, both students have the identical answers with only 3 correct answers indexed by the group label.

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.