Browse · MathNet
PrintChina Western Mathematical Olympiad
China counting and probability
Problem
There are () 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 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 students who answer at least 3 identical questions correctly. Determine the smallest possible value of . (Posed by Liu Shixiong)
Solution
The smallest is 911. We divide the proof into two parts:
(1) We first prove that satisfies the conditions. If each student answers at least 3 questions correctly, then for any student there are 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 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 , and the sum of their total scores is less than 36 points. Then there are more than students in the rest, such that each of them has a score less than 4. Since , and , there are at least 3 students answering 3 identical questions correctly.
(2) There are 910 students participating in the contest. Divide them into 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.
(1) We first prove that satisfies the conditions. If each student answers at least 3 questions correctly, then for any student there are 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 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 , and the sum of their total scores is less than 36 points. Then there are more than students in the rest, such that each of them has a score less than 4. Since , and , there are at least 3 students answering 3 identical questions correctly.
(2) There are 910 students participating in the contest. Divide them into 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.
Final answer
911
Techniques
Pigeonhole principleColoring schemes, extremal arguments