A total of $n$ people compete in a mathematical match which contains $15$ problems where $n>12$. For each problem, $1$ point is given for a right answer and $0$ is given for a wrong answer. Analysing each possible situation, we find that if the sum of points every group of $12$ people get is no less than $36$, then there are at least $3$ people that got the right answer of a certain problem, among the $n$ people. Find the least possible $n$.
Problem
Source: 2009 China Western Mathematic Olmpiad
Tags: pigeonhole principle, floor function, combinatorics proposed, combinatorics
28.02.2012 20:08
We find that if the sum of points every group of $12$ people get is no less than $36$, then there are at least $3$ people that got the right answer of a certain problem, among the $12$ people. Because with more than $36$ points on $15$ questions ,there is a question with at least $3$ points scored on it (by different people) hene done. If you mean for each problem it is possible: take $n$ people all finding the first until the tenth question. Then no three people found the thirtteenth one. Seems to be stupid interpretations by me. Someone can tell me what is the exact meaning or say sth more?
20.10.2014 09:13
lssl wrote: 2009 Western China Olympiad 3. $n$ ( $ n > 12 $ ) students take part in a math competition , there are $15$ problems for the students to solve , If you solve one problem , then you get $1$ point , if you give up or get the wrong result , then you get $0$ point .After analyzing all the conditions of the mark , we find that : if the sum of any $12$ students' marks is not lower than $36$ points , then there are at least $3$ students who have solved at least $3$ same problems . Find the mininum possible value of $n$ . I think horizon meant that $3$ people got the right answer for $3$ same problems, from http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1971683 Assume all students solved $3$ problems, since$\binom{15}{3}=455$, we will show that the minimum is $455\times2+1=911$. The number of ways $3$ problems is solved out of the $15$ is $\binom{15}{3}=455$. If all students solved $3$ problems, from above $3$ students will solve $3$ same problems. If one student solved at most $2$ problems, then there must be $911-11=900$ students who solve at least 4 problems. Then by pigeonhole, among these $900$ students, there will be at least $\left\lfloor\frac{\binom{4}{3}\times900-1}{455}\right\rfloor=8$ students who solved $3$ same problems. Thus the minimum n is $911$.
31.10.2022 20:10
This problem is terribly worded. Here's what it actually means: Problem wrote: $n$ people compete in a math competition, which contains $15$ problems. Each student earns $1$ point for a problem they answered correctly and $0$ points otherwise. Suppose that the sum of the scores of any $12$ students is at least $36$, and for any three problems, there are at least three students who answered all three problems correctly. Find the minimum possible value of $n$. The answer is $2 \cdot {15 \choose 3} + 1 = 911$ students. If there are only $910$ students, we may partition them into $455$ groups of two students such that each triple of problems is solved only by the two students in a given group. Suppose there are $911$ students. If each student solved at least $3$ problems, both conditions are obviously satisfied. Else, if there exists a student who solved $2$ problems, we must have at least $911 - 11 = 900$ students who solved $4$ problems (to compensate for that student when selecting some $12$ students). This means that there are ${4 \choose 3} \cdot 900$ sets of three problems that were solved by an individual. Obviously, in this case, there must exist some three students who solved the same set of three problems, as required.