13
$\begingroup$

A group of students have taken an exam. We have the following information:

  • Every student answered at most 15 questions.
  • Every question is answered by at least 1 and at most 3 students.
  • Every three students answered at least 1 common question.

At most how many questions could be there in this exam?

$\endgroup$
  • 3
    $\begingroup$ Do we need to know how many students there are? $\endgroup$ – EKons Aug 7 '18 at 20:51
  • 2
    $\begingroup$ @ΈρικΚωνσταντόπουλος no $\endgroup$ – Oray Aug 7 '18 at 20:52
  • $\begingroup$ Can we assume that the number of students is at least 3? Otherwise, "every three students" doesn't make sense. (Not knowing the exact number.) $\endgroup$ – EKons Aug 7 '18 at 21:47
  • $\begingroup$ What if it is just 15 because no one yet can predict the future then there is no need for any other knowledge $\endgroup$ – Duck Aug 7 '18 at 21:49
  • $\begingroup$ @Randal'Thor people were voting for the other answer, so I thought it was the right and better one, that's why I deleted it :D I undeleted it... $\endgroup$ – Oray Aug 8 '18 at 13:22
9
$\begingroup$

We can start by combining rules 2 and 3 to say that each group of 3 students has exactly one question that is unique to that group.

If there are n students, there are $_nC_3$ groups of 3 students, so the same number of questions that are part of shared groups. Additionally, each student is part of $_{n-1}C_2$ different groups of 3 students (the same as all possible groups of 2 students not including that student). Each student has a limit of 15 questions, and of those, $_{n-1}C_2$ will be shared with other students, while the rest of their 15 will be unique to them.

To get the total number of questions for a given number of students, add the number of questions shared between students and the number of students times the number of unique questions per student. This gives us the equation for the total number of questions for n students: $$_nC_3 + n \times(15 - _{n-1}C_2)$$

Plugging this into excel gives us the maximum value of

55 questions, which happens with 5 students.

$\endgroup$
  • $\begingroup$ Would be interesting if there was a proof for the highest possible $n$ as well...JK, have a +1. :P $\endgroup$ – EKons Aug 7 '18 at 22:16
  • $\begingroup$ I added another answer that doesn't do much else than elaborate on yours; I was hoping the solution is a bit easier to follow in a table format. I didn't want to add such a major edit to your answer without asking first, but if you think it might be a good idea to combine the answers, I'll be happy to delete mine. $\endgroup$ – Bass Aug 8 '18 at 2:24
  • $\begingroup$ @ΈρικΚωνσταντόπουλος the table in the answer below will also give that. $\endgroup$ – Bass Aug 8 '18 at 3:15
4
$\begingroup$

@DqwertyC's answer is correct and thorough. Maybe it's because I just woke up, but it took me some effort to follow through all the maths notation in the explanation, so here's the same answer in tabular form:

We want to maximise the number of questions, so every student will have answered 15 questions. Also, we will never want to have any two students answering the same question, unless it is required by the third constraint in the question.

    How many  | How many    | Memberships   | Non-shared Q | Max total
    students  | groups of 3 | per student   | per student  | questions
  ------------+-------------+---------------+--------------+----------
  1 student   | 0           | 0             | 15           | 15
  2 students  | 0           | 0             | 15           | 30
  3 students  | 1           | 1             | 14           | 43
  4 students  | 4           | 3             | 12           | 52
  5 students  | 10          | 6             |  9           | 55
  6 students  | 20          | 10            |  5           | 50
  7 students  | 35          | 15            |  0           | 35
 (8 students  | 56          | 21 (> 15)     | -6 (< 0)     | N/A )
  ------------+-------------+---------------+--------------+----------
       N      | G = C(N, 3) | M = C(N-1, 2) | P = 15 - M   | N * P + G 

On the last line, C(n,k) is the "from n, choose k" function. It counts the number of different ways it's possible to choose a combination of k items from a total of n items. It can be calculated as

$C(n,k) = \frac{n!}{k! (n-k)!}$

where the exclamation point is the factorial function. @DqwertyC uses the notation $_nC_k$ for this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.