How many definitions of a list of 30 would I need to know so that I could answer at least 10 from any 18?

Question

While studying for my English exam, I noticed that the way the definitions portion of the final is set up posed an interesting problem. While I will study all the definitions, I thought trying to solve this might be fun and just got totally stuck.

Given a list of 30 possible terms, 18 of them will be on the final exam; the final exam requires that I choose and define 10 of them. What is the minimum number of the terms I need to know so that for any 18 chosen, I know at least 10 words.

So far, I have found $$\alpha ={30 \choose 18}\cdot{18 \choose 10}$$ where $\alpha = 3.7847705 \times 10^{12}$.

My best guess for how to continue would be to find a number $$\beta = {30 \choose 18}\cdot{18 \choose k}$$ with $k \gt 10$ such that $$\frac{\beta}{\alpha} \le C$$ for some $C$.

My problem is that the discrete math I've seen thus far hasn't really told me how to proceed with a question like this, if there is a method, as I learned mostly about identities.

Answer 1

The problem can be answered simpler than that. The answer is that you need to learn $22$ words in order to guarantee knowing 10 in any selection of $18$.

We need to show that $22$ is sufficient and that anything less than $22$ won't always work.

To show that $22$ is sufficent, consider the worst case scenario: all $30 - 22 = 8$ words that you didn't study are part of the test. Then that means you know the remaining $10$ of those $18$ words, so you can pick those $10$ and all is well.

To show that anything less than $22$ isn't enough, consider this worst case scenario again. If you only learn $N$ terms, where $N < 22$, then the worst case scenario has $30 - N$ words you didn't study among the $18$ words, so $18- (30 - N) = N - 12$ words that you do know. You need $N - 12 \geq 10$, thus $N \geq 22$.

Answer 2

Worst case scenario: the $30-18=12$ words not on the test are all ones that you know. In that case, you would need to know an additional $10$ from the remaining to be able to get a perfect score. This means you could get away with a minimum of $22$ words.

Answer 3

If there are more than $18-10=8$ words whose definitions you don't know, and they are all on the final, you're out of luck. If there are $8$ or fewer that you don't know, you're in the clear, even if every single unknown word shows up on the final! So, at most, you may neglect $8$ of the $30$ words, meaning you must know at least $30-8=22$ words.