Ten test papers are to be prepared for the National Olympiad. Each paper has 4 problems, and no two papers have more than 1 problem in common. At least how many problems are needed?
Problem
Source: Taiwan NMO 2006
Tags: combinatorics proposed, combinatorics
Adunakhor
22.03.2006 02:41
To minimize the number of unique problems, we want as many as possible to be shared. To do this, we have a problem be shared by only one pair.
The 1st test shares P1 with the 2nd test.
The 2nd test shares P2 with the 3rd test.
The 3rd test shares P3 with the 4th test.
continuing
The 9th test shares P9 with the 10th test. The 1st and 10th test then have two unique problems, followed by 20 more unique ones to fill the other half of each test.
Summing them all up $\Longrightarrow 31$
e.lopes
22.03.2006 05:12
Let $n$ the minimal number of problems, and $P_1$, ... , $P_n$ the problems. Let $A_1$, .. , $A_{10}$ the sets of problems in each test. We have $|A_i \cap A_j| \leq 1$, so, each pair ($P_i$, $P_j$) can't occur more than one time in this sets. now, we have ${n \choose 2} \geq \sum{|A_i| \choose 2} = 10 . {4 \choose 2} = 60$ so, $n \geq 12$. see that the projective plane of order 3 satisfy the conditions (for n = 13): http://home.wlu.edu/~mcraea/Finite_Geometry/NoneuclideanGeometry/Prob14ProjPlane/problem14.html now, we have to prove that n = 12 can't occur.
ThAzN1
22.03.2006 08:38
From above, $n \geq 12$. We show that $n = 12$ cannot work. (Let #s be problem #s.) Some problem, say 1, must occur at least 4 times. Then, the other three problems on each of these tests must be distinct. so we must have 12 distinct problems in addition to 1, showing $n \geq 13$ contradiction. Here's an explicit construction for $n = 13$: 1,2,3,4 1,5,6,7 1,8,9,10 1,11,12,13 2,5,8,11 2,6,9,12 3,5,9,11 3,6,8,12 4,5,10,12 4,6,11,9
Naphthalin
22.03.2006 08:46
If I understand you correctly, you have proved the fact that one problem is there 4 times. I want to give the trivial prove for this: Imagine you have only 12 different problems and each problem is there max. 3 times. So you would have a number of problems less than 37 but you have 40 problems. So there are 13 different problems or one problem is there at least 4 times. Naphthalin
Adunakhor
22.03.2006 13:03
Missed it completely, barely reduced the # at all Thanks for the explanations
tim26270746
17.12.2008 03:28
ThAzN1 wrote: From above, $ n \geq 12$. We show that $ n = 12$ cannot work. (Let #s be problem #s.) Some problem, say 1, must occur at least 4 times. Then, the other three problems on each of these tests must be distinct. so we must have 12 distinct problems in addition to 1, showing $ n \geq 13$ contradiction. Here's an explicit construction for $ n = 13$: 1,2,3,4 1,5,6,7 1,8,9,10 1,11,12,13 2,5,8,11 2,6,9,12 3,5,9,11 3,6,8,12 4,5,10,12 4,6,11,9 I think you did this wrong. Note that you have two sets: 2,6,9,12 3,6,8,12 these two sets appear to have two common problems.
HARDMATH
04.01.2014 06:20
1,2,3,4 1,5,6,7 1,8,9,10 1,11,12,13 2,5,8,11 2,6,9,12 2,7,10,13 3,7,9,11 3,5,10,12 4,6,8,13
DPD1
24.02.2017 15:29
HARDMATH wrote: 1,2,3,4 1,5,6,7 1,8,9,10 1,11,12,13 2,5,8,11 2,6,9,12 2,7,10,13 3,7,9,11 3,5,10,12 4,6,8,13 How did you begin to construct such sequences, is there a technique I am missing?? Thanks