Results 1 to 12 of 12

Math Help - Simple, yet hard...

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    3

    Simple, yet hard...

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hello darlove
    Quote Originally Posted by darlove View Post
    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
    Attached Thumbnails Attached Thumbnails Simple, yet hard...-untitled.jpg  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    3
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Grandad View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2009
    Posts
    90
    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}\}
    Last edited by bmp05; March 28th 2009 at 07:53 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Type

    Hello bmp05
    Quote Originally Posted by bmp05 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by bmp05 View Post
    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.

    Quote Originally Posted by Grandad View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Mar 2009
    Posts
    90
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by bmp05 View Post
    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:
    123
    145
    167
    246
    257
    347
    356
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Mar 2009
    Posts
    90
    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.

    Quote Originally Posted by Opalg View Post
    Code:
    123
    145
    167
    246
    257
    347
    356
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Explicit formula

    Thanks Opalg
    Quote Originally Posted by Opalg View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Really simple question too hard for a simple mind
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 5th 2010, 08:03 AM
  2. Probability Question- could be simple/could be hard??
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 7th 2010, 04:56 AM
  3. simple yet hard finding area + volume question
    Posted in the Calculus Forum
    Replies: 0
    Last Post: September 25th 2009, 07:27 PM
  4. Simple for you.. hard for me :(
    Posted in the Algebra Forum
    Replies: 4
    Last Post: January 3rd 2008, 10:53 PM
  5. simple questions hard to get the answer
    Posted in the Statistics Forum
    Replies: 3
    Last Post: May 27th 2005, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum