Simple, yet hard...

**darlove** · March 27th 2009, 03:41 AM

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?

**Grandad** · March 27th 2009, 08:49 AM

Hello darlove

Originally Posted by darlove

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?

This 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.

Initially, I tried to get a feel for how this works by trying consecutive values of $n (=3, 4, 5, ...)$ , and allocating the questions as logically as possible. This is what I have come up with. $n =$ number of questions; $p =$ number of participants.

$\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 $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 $i, j$ and $k$ - involves the elimination of 3 pairs - $ij, jk, ik$ - from the $\tfrac{1}{2}n(n-1)$ pairs that can be chosen from the $n$ questions. This is because no other participant can be given any other pair of questions from $i, j$ and $k$ once this group of three has been allocated to someone.

A discernible pattern is starting to emerge. The consecutive differences in $p$ are $0, 1, 2, 3, 0, 1, 2, 3, 4$ .

The attached file shows the situation up to $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 $n = 3$ to $n = 12$ , together with the corresponding values of $n$ and $p$ .

Whether you can generalize this, and show how $n = k+1$ can be derived from $n = k$ , and thence to a formula for $p$ in terms of $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

**darlove** · March 27th 2009, 09:18 AM

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 $i$ , then we put $1$ if they have got question $q_j$ , and 0, if not. For each row in the matrix we have $\sum_j a_{i,j}=3$ and for any two participants we have $\sum_j a_{i_1,j}a_{i_2,j}<=1$ . That is, $\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?

**Opalg** · March 27th 2009, 02:50 PM

Originally Posted by Grandad

What also became clear, is that each selection of 3 questions - call them questions $i, j$ and $k$ - involves the elimination of 3 pairs - $ij, jk, ik$ - from the $\tfrac{1}{2}n(n-1)$ pairs that can be chosen from the $n$ questions. This is because no other participant can be given any other pair of questions from $i, j$ and $k$ once this group of three has been allocated to someone.

Following up on that insight of Grandad, each triple that is selected eliminates 3 pairs of questions. Since there are $\tfrac{1}{2}n(n-1)$ pairs, the maximum possible number of participants is $\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 $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:

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

I suspect that the maximum is not going to be attained except at numbers of the form $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.

**Grandad** · March 28th 2009, 08:01 AM

Hello everyone

Opalg has highlighted the significance of $n=2^k - 1$ as being a value of $n$ for which all the 'slack' is taken up. (I had found that this was true for $n = 7$ ; he has demonstrated it to be so when $n = 15$ .)

This confirms the pattern of differences that I had noted. 3 questions permits just one participant: $n=3,p = 1$ . Then, taking $n = 3$ as the starting point, the next few values of $p$ , when $n = 4$ to $7 (= 2^3 - 1),$ are $1 + 0, 1+0 + 1, 1+0+1+2, 1 + 0+1 + 2 + 3$ , which is the next point where the maximum number $(n= 7,p=7)$ is achieved.

The next set starts at $p=7$ , and, for values of $n$ from $8$ to $15 (=2^4 -1)$ , we get values of $p$ from $7 + 0$ to $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 $n = 3, 7, 15$ ) then adding one extra question will not allow any further participants. This is because, for the new value of $n$ , all the new pairs will be in the form $(i,n), i = 1 \dots (n-1)$ , and there are therefore no 'triples-of-pairs' of the form $\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 $n$ to $(n+1)$ , we can now form one and only one new triple. (If we choose, for example, $\Big((1, n), (1, n+1), (n, n+1)\Big)$ , there are now no further triples that can be formed.)

And so on: when $n$ is increased further to $(n+2)$ , there will be $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 $p_k(n)$ in terms of $p_{k-1}(n)$ :

When $n = 3, p = 1$ . This could be denoted as $p_1(3) = 1$ .

For $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 $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 $n = 2^k \dots(2^{k+1}-1), p_k(n) = ...$ (Can you complete this? Express $p_2$ in terms of $p_1$ , and $p_3$ in terms of $p_2$ first.)

I'm not sure about an explicit formula for $p$ in terms of $n$ , but I think it would probably involve the floor function, and $\log_2(n)$ .

Grandad

**bmp05** · March 28th 2009, 08:28 AM

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?

$P_1:=\{Q_1,Q_2,Q_3\}$
$P_2:=\{Q_2,Q_4,Q_5\}$
$P_3:=\{Q_3,Q_4,Q_6\}$
$P_4:=\{Q_1,Q_5,Q_6\}$
.
.
.
$P_8:=\{Q_7,Q_{11},Q_{12}\}$

**Grandad** · March 28th 2009, 09:07 AM

Hello bmp05

Originally Posted by bmp05

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?

I 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 common

But isn't the question that no 2 participants share more than 1 Question?

Correct.

This is a difficult English lesson- the personal pronoun 'them' refers to the questions or the participants?

To the participants: no two participants have more than 1 question in common.

Grandad

**Opalg** · March 28th 2009, 10:27 AM

Originally Posted by bmp05

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?

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.

Originally Posted by Grandad

For $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 $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 $n = 2^k \dots(2^{k+1}-1), p_k(n) = ...$ (Can you complete this? Express $p_2$ in terms of $p_1$ , and $p_3$ in terms of $p_2$ first.)

I'm not sure about an explicit formula for $p$ in terms of $n$ , but I think it would probably involve the floor function, and $\log_2(n)$ .

I think that looks very much like the complete answer. So if $k = \lfloor\log_2n\rfloor$ and $r = n-2^k$ then $p(n) = \tfrac16(2^k-1)(2^k-2)+\tfrac12r(r+1)$ .

**bmp05** · March 28th 2009, 12:23 PM

Sorry, but I still can't convince myself that 7 participants can share an exam of 7 questions in such a way that each participant recieves 3 questions of which only 1 question is shared by any (single) other participant. How does this work?

**Opalg** · March 28th 2009, 12:55 PM

Originally Posted by bmp05

sorry, but i still can't convince myself that 7 participants can share an exam of 7 questions in such a way that each participant receives 3 questions of which only 1 question is shared by any (single) other participant. How does this work?

Code:

**bmp05** · March 28th 2009, 01:13 PM

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.

Originally Posted by Opalg

Code:

**Grandad** · March 28th 2009, 01:27 PM

Thanks Opalg

Originally Posted by Opalg

So if $k = \lfloor\log_2n\rfloor$ and $r = n-2^k$ then $p(n) = \tfrac16(2^k-1)(2^k-2)+\tfrac12r(r+1)$ .

That looks good. I'd overlooked the $\tfrac16n(n-1)$ way of expressing the 'key' values, and I ran out of time - so I posted what I'd got up to then!

Grandad

Thread: Simple, yet hard...

LinkBack

Thread Tools

Display

Simple, yet hard...

Type

Explicit formula

Similar Math Help Forum Discussions

[SOLVED] Really simple question too hard for a simple mind

Probability Question- could be simple/could be hard??

simple yet hard finding area + volume question

Simple for you.. hard for me :(

simple questions hard to get the answer

Search Tags