Maths Olympiad Prep

Library / /327 of 520

Combinatorics Difficulty 5.4 AIME, harder Find the answer

7. There are n(n>12)n (n>12) people participating in a mathematics invitational competition. The test consists of fifteen fill-in-the-blank questions, with each correct answer worth 1 point and no answer or a wrong answer worth 0 points. Analyzing every possible score situation, it is found that as long as the sum of the scores of any 12 people is no less than 36 points, then among these nn people, at least 3 people have answered at least three of the same questions correctly. Find the minimum possible value of nn.
(Liu Shixiong provided)

A number or a short expression. Spacing and $ signs are ignored.

Solution

7. The minimum possible value of nn is 911.
(1) First, prove: 911 satisfies the condition.
If each student answers at least three questions correctly, since the number of different ways a student can answer three questions correctly is C153=455\mathrm{C}_{15}^{3}=455, then if there are 911 students participating, by the pigeonhole principle, at least 3 students must have answered the same three questions correctly.

If a student answers no more than 2 questions correctly, then among the remaining students, the number of students who answer no more than three questions correctly cannot exceed 10 (otherwise, the total score of these students and the first student would be less than 36 points). For the remaining 91111=900911-11=900 students, each student answers at least 4 questions correctly.

Since C43×900>455×2\mathrm{C}_{4}^{3} \times 900 > 455 \times 2, there must be at least 3 students who answered the same three questions correctly.
(2) If there are 910 students participating, these students can be divided into 455 groups, with each group consisting of two students who answered the same three questions correctly. In this case, the condition of the problem is not satisfied.
In conclusion, nmin=911n_{\min }=911.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.