pigeonhole principle problem 2

Question

Every year the teacher write 4 tests with 6 questions, from a list of 10 different questions, Is it certain that after 8 years, theres 3 different tests with the same 4 questions?

how do i show that with the pigeonhole principle?

Answer 1

Here's a line of thinking to consider. I have no idea if it is correct.

8 years of tests is 32 tests. So we are looking at 32 tests, each with 6 questions. Is it possible for at most only 2 tests have the same set of 4 questions (4-tuples)?

Each test contains ${6\choose4}=15$ 4-tuples. So 32 tests contain $32*15=480$ total 4-tuples.

There are a total of ${10\choose4}=210$ 4-tuples able to be created from the bank of 10 total questions.

So if each of the $210$ 4-tuples gets used twice, you have filled $420$ of the $480$ slots. Leaving 60 free.

I'm not sure where to go from here. Can we say that $210$ easily covers those $60$ so we can fill all the tests with no 4-tuple being used 4 times (only some of them were used 3 times even)? I'm not sure.

Answer 2

There are $n!= n\times\ldots\times 1$ ways to arrange n things. There are then, $6\times5\times4\times3\times2\times1=720$ ways, to rearrange the 6 questions, once chosen. The number of combinations ( as opposed to permutations), of y distinct things from z is $\frac{z!}{(z-y)!\times y!}$ . We have 10 things to choose from, and 6 to choose. We can then plug these into the expression given and simplify , and get that the ways to choose 6 questions without caring about order (aka combinations, not permutations) , is $\frac{10!}{4!6!} = \frac{3628800}{24\times720}=210$. So, There are really only 210 distinct tests. We can then deduce that there are $4\times 8=32$ tests given in 8 years. The number of 4 question distinct tests, as part of the 6 question test, are $\frac{6!}{2!4!} = \frac{720}{2\times 24} = 5 \times 3 = 15 $. Using the math from above, there are 210 distinct, 4 question sets, from the 10 questions. $\lceil{210\over15}\rceil=15$ is the minimum number distinct of 6 question sets that can cover it So 2 overlap. Fifteen and then 14 more more to go over them all again = 29 tests needed for 3 to overlap as 29<32 the statement is guaranteed.