21 people take a test with 15 true or false questions. It is known that every 2 people have at least 1 correct answer in common. What is the minimum number of people that could have correctly answered the question which the most people were correct on?
Problem
Source: China TST 1995, problem 3
Tags: vector, combinatorics unsolved, combinatorics
18.05.2005 03:38
suppose question i was answered correctly by ti students, we must have: \sum\binom{t_i}{2} is at least 210=\binom{21}{2}, so let T=max(t_1,t_2...,t_{15}), then 15\binom{T}{2} is at least 210. So \binom{T}{2} is at least 14, so T is at least 6. I dont find a construction right now....
18.05.2005 14:00
I don't think T=6 is possible. Assume each question was solved by at most 6 people. Then each person must have solved at least 4 questions (since each correct question is shared with at most 5 other people). Furthermore, if anyone solved exactly 4 questions there must be 20 other solvers of those questions and they must all be distinct. Since there are 15 questions, there were at most 90 correct answers total by all participants on all questions, so at least 15 people must have solved exactly 4 questions. Let A_1, A_2, \dots A_{15} be 15 people answering only 4 questions. Each pair of them must have solved exactly one question together. If any question was solved by 5 of the A_i, then those 5 people would have had to solve 15 other questions between them, which would all have to be distinct. This is impossible, so each question was solved by at most 4 of the A_i. We now have that A_1 solved exactly 4 questions, each of which was solved by at most 3 other A_i. Thus A_1 solved questions with at most 12 other A_i, contradicting that every pair of people solved a common problem.
18.05.2005 15:56
I also realised that during the night: Like we have equality every where, we must have every pair appears together in exactly 1 problem, and also, every one appears in exactly 5 problems, Now to everyone asign a vector with 1 in the jth place if he solved problem j, and 0 otherwise. Call this vectors v_1,v_2...,v_{21} and v_iv_j=1 and v_iv_i=5. Now there is a linear combination of them that sum 0, taking products wit all vectors we find a contradiction!
20.05.2005 10:55
To finish things off, here's a construction with T=7 and 14 questions overall Label the contestants by points (i,j), 1 \leq i \leq 7, 1 \leq j \leq 3 Let one question be solved by all contestants of the form (i, ai+b) for each 1 \leq a \leq 3, 1 \leq b \leq 3. The 10th question is solved by all contestants where i \in \{2, 5\} The 11th question is solved by all contestants where i \in \{3, 6\} The 12th question is solved by all contestants where i \in \{1, 4\} The 13th question is solved by all contestants where i \in \{1, 7\} The 14th question is solved by all contestants where i \in \{4,7\}
16.12.2010 16:34
T=7,13 questions is enough. {1,2,3,4} {1,5,6,7} {1,8,9,10} {1,11,12,13} {2,5,8,11}*2 {2,6,9,12}*2 {2,7,10,13}*2 {3,5,9,13}*2 {3,6,10,11}*2 {3,7,8,12}*2 {4,7,9,11}*2 {4,6,8,13}*2 {4,5,10,12}
13.08.2017 08:48
kevinatcausa wrote: Since there are 15 questions, there were at most 90 correct answers total by all participants on all questions, so at least 15 people must have solved exactly 4 questions. I don't understand this
07.08.2018 20:30
Pascual2005 wrote: I also realised that during the night: Like we have equality every where, we must have every pair appears together in exactly 1 problem, and also, every one appears in exactly 5 problems, Now to everyone asign a vector with 1 in the jth place if he solved problem j, and 0 otherwise. Call this vectors v_1,v_2...,v_{21} and v_iv_j=1 and v_iv_i=5. Now there is a linear combination of them that sum 0, taking products wit all vectors we find a contradiction! It is impossible for everyone to be in exactly 5 problems.