Recently one of my friends asked me this deceivingly simple question:

I have a midterm with a predetermined list of 15 possible questions. Out of the 15 questions only 7 will actually appear on the test. Out of the 7 that appear on the test I will only have to answer 5. How many answers should I memorize to make sure I get 100% on the test?

I think I have convinced myself that it is pretty easy to show that he needs to memorize exactly 13 questions - 15-(7-5) - in order to guarantee he will know at least 5 of the questions on the midterm and thus get 100%.

However I am having trouble generalizing the math to answer some more interesting questions. Specifically:

How many answers should I memorize such that 75% of the time I will get 100% on the test?


How many answers should I memorize such that on average I will get at least an 80% on the test?


Let $N = 15$ be the total population of questions, $n = 7$ the number that will appear on the test, and $m = 5$ the number of questions you need to answer. There are $\binom{N}{n}$ possible tests; I'll assume the test is selected uniformly at random without replacement.

Say you memorize $K$ of the questions. Then, the number of questions on the test that you know the answer to, call it $k$, is hypergeometric, with population size $N$, "success" population size $K$, and number of draws $n$ (like the names in the Wikipedia article).

How many answers should I memorize such that 75% of the time I will get 100% on the test?

You get 100% on the test if $k \ge m$, so the probability of doing so is the complement of the CDF at $m-1$. Unfortunately, the expression for this is not pretty:

$$ {{{n \choose {m}}{{N-n} \choose {K-m}}}\over {N \choose K}} \,_3F_2\!\!\left[\begin{array}{c}1,\ m-K,\ m-n \\ m+1,\ N+m+1-K-n\end{array};1\right] \ge .75 $$

where $_3F_2$ is the generalized hypergeometric function.

This probably needs to be solved numerically.

How many answers should I memorize such that on average I will get at least an 80% on the exam?

Your score on the exam can be written as $S := \max\left(1, \frac{k}{m}\right)$. To get rid of the max, you can do: $$ \begin{align*} \mathbb{E}[S] &= \Pr[k \le m] \, \mathbb{E}[S \mid k \le m] + \Pr[k > m] \, \mathbb{E}[S \mid k > m] \\ &= \Pr[k \le m] \, \mathbb{E}[k \mid k \le m] + \Pr[k > m] \end{align*} $$ where the two probability terms are again gross hypergeometric cdfs, and I don't know if there's a nice form for $\mathbb{E}[k \mid k \le m]$. Maybe if you derive it the way you derive $\mathbb{E}[S]$ it'll mostly cancel out with $\Pr[T \le k]$ or something; not sure.

For smallish numbers like the ones given, you could compute $\mathbb{E} S$ exactly based on the hypergeometric pmf, but you'd probably have to do a binary search or something to find the exact cutoff.

  • 2
    $\begingroup$ Thinking a little more about this I think your answer is double counting. Lets say we know 6 answers (1-6 WLOG). Your solution is showing the tests {1,2,3,4,5}U{6,7} and {1,2,3,4,6}U{5,7} as distinct test. I think the solution requires inclusion-exclusion. $\endgroup$
    – Matt
    Jul 23 '14 at 18:14
  • $\begingroup$ Ugh, you're right about the double-counting. I rewrote the answer to make everything in terms of the hypergeometric, which means no closed forms for these two questions. If you can come up with a better form based on inclusion-exclusion, that'd be interesting, but I suspect it'll reduce to the same sum as the $_3F_2$ call in the hypergeometric cdf. $\endgroup$
    – Danica
    Jul 24 '14 at 1:31

The objective of a test is to encourage you to learn and understand the material. If you do that you shouldn't have to memorize anything

  • $\begingroup$ Completely agreed. And that is exactly what I told my friend when he asked. Although I have to admit it is an extremely simple question to ask - and one I think many students can relate to - that leads to some complex ideas in combinatorics and probability. $\endgroup$
    – Matt
    Jul 23 '14 at 16:38

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.