Hi there. I have come across such a simple problem: There are n questions in an exam. The participants are handed in 3 questions in such a way that no two of them have more than 1 question in common. Question: How many participants at most can sit the exam? I've tried different paths but have failed so far. Any ideas, please?
Hello darloveThis is one of those apparently straightforward questions that turn out to be very difficult. I'm afraid I don't have a formal answer as yet, but let me share my thoughts so far. Maybe you've been down these roads, so it may not be of any help.Originally Posted by darlove
Initially, I tried to get a feel for how this works by trying consecutive values of $\displaystyle n (=3, 4, 5, ...)$, and allocating the questions as logically as possible. This is what I have come up with. $\displaystyle n =$ number of questions; $\displaystyle p =$ number of participants.
$\displaystyle \begin{matrix}n=\\p=\end{matrix}\,\begin{matrix}3& 4&5&6&7&8&9&10&11&12\\1&1&2&4&7&7&8&10&13&17\end{m atrix}$
As I listed the possible allocations for each successive value of $\displaystyle n$, it became clear that I could use the allocations for the previous value, and add extra allocations, rather than starting from scratch each time.
What also became clear, is that each selection of 3 questions - call them questions $\displaystyle i, j$ and $\displaystyle k$ - involves the elimination of 3 pairs - $\displaystyle ij, jk, ik$ - from the $\displaystyle \tfrac{1}{2}n(n-1)$ pairs that can be chosen from the $\displaystyle n$ questions. This is because no other participant can be given any other pair of questions from $\displaystyle i, j$ and $\displaystyle k$ once this group of three has been allocated to someone.
A discernible pattern is starting to emerge. The consecutive differences in $\displaystyle p$ are $\displaystyle 0, 1, 2, 3, 0, 1, 2, 3, 4$.
The attached file shows the situation up to $\displaystyle n = 12$. I have used the numbers 1 - 12 to denote the 12 different questions. The unused pairs (as referred to above) are shown in red. These are the pairs that cannot be allocated because no suitable partner pairs exist to make another triple. The column on the right shows how the possible allocations of sets of three questions develops from $\displaystyle n = 3$ to $\displaystyle n = 12$, together with the corresponding values of $\displaystyle n$ and $\displaystyle p$.
Whether you can generalize this, and show how $\displaystyle n = k+1$ can be derived from $\displaystyle n = k$, and thence to a formula for $\displaystyle p$ in terms of $\displaystyle n$, I don't know. I may be going in completely the wrong direction, but I hope it may help to shed a little light!
Grandad
Hi there. Thanks for your thoughts. Unfortunately, I have tried something similar. I don't know whether induction is the right tool for the job here. I have no idea how one would argue that in passing from n to n+1 one gets the optimal number based on the previous optimal number (you know what I mean, hopefully). Maybe the optimal arrangement for n is completely wrong for n+1? I have tried something different. I will state it here briefly and maybe someone will be able to do anything useful with it.
Say that you have n questions and arrange them in a sequence. We are constructing a matrix. Each column corresponds to a question. Now, if we have a participant number $\displaystyle i$, then we put $\displaystyle 1$ if they have got question $\displaystyle q_j$, and 0, if not. For each row in the matrix we have $\displaystyle \sum_j a_{i,j}=3$ and for any two participants we have $\displaystyle \sum_j a_{i_1,j}a_{i_2,j}<=1$. That is, $\displaystyle \vec{a}_{i_1}\cdot\vec{a}_{i_2}<=1$. The question is: how many rows at most can you have in such a matrix?
Following up on that insight of Grandad, each triple that is selected eliminates 3 pairs of questions. Since there are $\displaystyle \tfrac{1}{2}n(n-1)$ pairs, the maximum possible number of participants is $\displaystyle \tfrac{1}{6}n(n-1)$. Grandad's computations show that this maximum is attained when n=3 and when n=7. I believe that the maximum can be attained whenever n is of the form $\displaystyle n=2^k-1$. (In fact, I'm sure of that.) I don't have a neat way of describing the construction, but I have written it out in detail for n=15, using these 35 triples:
I suspect that the maximum is not going to be attained except at numbers of the form $\displaystyle n=2^k-1$, and I would guess that there will not be a simple formula for the answer at a general value of n.Code:1 2 3 2 4 6 3 4 7 4 8 12 6 8 14 1 4 5 2 5 7 3 5 6 4 9 13 6 9 15 1 6 7 2 8 10 3 8 11 4 10 14 6 10 12 1 8 9 2 9 11 3 9 10 4 11 15 6 11 13 1 10 11 2 12 14 3 12 15 5 8 13 7 8 15 1 12 13 2 13 15 3 13 14 5 9 14 7 9 12 1 14 15 5 10 15 7 10 13 5 11 12 7 11 14
Hello everyone
Opalg has highlighted the significance of $\displaystyle n=2^k - 1$ as being a value of $\displaystyle n$ for which all the 'slack' is taken up. (I had found that this was true for $\displaystyle n = 7$; he has demonstrated it to be so when $\displaystyle n = 15$.)
This confirms the pattern of differences that I had noted. 3 questions permits just one participant: $\displaystyle n=3,p = 1$. Then, taking $\displaystyle n = 3$ as the starting point, the next few values of $\displaystyle p$, when $\displaystyle n = 4$ to $\displaystyle 7 (= 2^3 - 1),$ are $\displaystyle 1 + 0, 1+0 + 1, 1+0+1+2, 1 + 0+1 + 2 + 3$, which is the next point where the maximum number $\displaystyle (n= 7,p=7)$ is achieved.
The next set starts at $\displaystyle p=7$, and, for values of $\displaystyle n$ from $\displaystyle 8$ to $\displaystyle 15 (=2^4 -1)$, we get values of $\displaystyle p$ from $\displaystyle 7 + 0$ to $\displaystyle 7 + 0 + 1 + 2 + ... + 7 = 35$.
I don't have a complete, formal argument to prove that this will continue. However, what is clear is that when all the 'pairs' that I mentioned have been used, and there is no 'slack' (e.g. at $\displaystyle n = 3, 7, 15$) then adding one extra question will not allow any further participants. This is because, for the new value of $\displaystyle n$, all the new pairs will be in the form $\displaystyle (i,n), i = 1 \dots (n-1)$, and there are therefore no 'triples-of-pairs' of the form $\displaystyle \Big((i,j), (j,k), (k,i)\Big)$ to allow another participant. (NB although these look like ordered pairs and triples as I have written them here, the order within each pair and triple is irrelevant.)
However, when the next set of pairs is added, by increasing $\displaystyle n$ to $\displaystyle (n+1)$, we can now form one and only one new triple. (If we choose, for example, $\displaystyle \Big((1, n), (1, n+1), (n, n+1)\Big)$, there are now no further triples that can be formed.)
And so on: when $\displaystyle n$ is increased further to $\displaystyle (n+2)$, there will be $\displaystyle 2$ further triples possible; and so on ...
So what about a formula, based on these findings? In fact, it's not too difficult to find a recursive formula for $\displaystyle p_k(n)$ in terms of $\displaystyle p_{k-1}(n)$:
When $\displaystyle n = 3, p = 1$. This could be denoted as $\displaystyle p_1(3) = 1$.
For $\displaystyle n = 2^2 \dots (2^3-1), p_2(n) = 1 + \sum_{i=0}^{n - 4}i = 1 + \tfrac{1}{2}(n-3)(n-4)$.
For $\displaystyle n = 2^3\dots (2^4-1), p_3(n) = 7 + \sum_{i=0}^{n-8}i = 7 + \tfrac{1}{2}(n-7)(n-8)$
...
For $\displaystyle n = 2^k \dots(2^{k+1}-1), p_k(n) = ...$ (Can you complete this? Express $\displaystyle p_2$ in terms of $\displaystyle p_1$, and $\displaystyle p_3$ in terms of $\displaystyle p_2$ first.)
I'm not sure about an explicit formula for $\displaystyle p$ in terms of $\displaystyle n$, but I think it would probably involve the floor function, and $\displaystyle \log_2(n)$.
Grandad
I think I haven't understood the problem correctly- What does, "The participants are handed IN 3 questions" mean? Is 'in' a typo or relevant? But isn't the question that no 2 participants share more than 1 Question? This is a difficult English lesson- the personal pronoun 'them' refers to the questions or the participants?
$\displaystyle P_1:=\{Q_1,Q_2,Q_3\}$
$\displaystyle P_2:=\{Q_2,Q_4,Q_5\}$
$\displaystyle P_3:=\{Q_3,Q_4,Q_6\}$
$\displaystyle P_4:=\{Q_1,Q_5,Q_6\}$
.
.
.
$\displaystyle P_8:=\{Q_7,Q_{11},Q_{12}\}$
Hello bmp05I have assumed that this 'in' is a typo, and should not be there. The question should read
The participants are handed 3 questions in such a way that no two of them have more than 1 question in commonCorrect.But isn't the question that no 2 participants share more than 1 Question?
To the participants: no two participants have more than 1 question in common.This is a difficult English lesson- the personal pronoun 'them' refers to the questions or the participants?
Grandad
You are quite right to query this. In British English at any rate, the question papers would be handed OUT to the participants! But the meaning here has to be that each participant gets a different sheet of three questions, with no two participants sharing more than one question.
I think that looks very much like the complete answer. So if $\displaystyle k = \lfloor\log_2n\rfloor$ and $\displaystyle r = n-2^k$ then $\displaystyle p(n) = \tfrac16(2^k-1)(2^k-2)+\tfrac12r(r+1)$.
Oh- so, Participants P1, P2 and P3 have all got Question N1? I thought that N1 could only be given 1 other Participant? "no 2 shall have more than 1 in common..." This was a very cool question- although I would hate to get it in an exam.
  |
LinkBack URL
About LinkBacks