Anna colors exactly 30 numbers to red from the numbers $1,2,\dots, 36$. Then Peter is able to choose six numbers from the 36 (this is called a step).
After $n$ steps, for each of the steps, Anna tells if all the chosen numbers (the six chosen numbers) are red.
Find the minimum value of $n$, such that in (at least) one of the steps, Peter’s six chosen numbers are all red, i.e. for any 30 red numbers, at least one of the guesses (the six chosem numbers) contain six red numbers. (Peter doesn’t know the colored numbers.)
This problem is from Brilliant.org, the answer is 9. But why? Thanks in advnace (please help)!
See it this way: Peter in fact chooses $30$ numbers, and his $30$ numbers have to contain all $6$ non-red numbers.
We are looking for a collection of $n$ subsets of size $30$ such that any subset of size $6$ is contained in one of our $n$ subsets. This is called a $(36,30,6)$-covering design. The smallest size of a $(v, k, t)$ covering design is denoted by $C(v,k,t)$. The problem is to show that $$C(36,30,6)=9.$$
There is no simple recipe to compute the smallest value of $n$ for a given set of parameters, although there are theorems that allow one to find bounds and even exact values in some cases.
One of the results that are the easiest to understand (it results from a greedy/bruteforce reasoning) is known as the Schönheim lower bound, obtained by repeatedly applying the inequality: $$C(v,k,t) \geq \left\lceil \frac vk C(v-1,k-1,t-1) \right\rceil$$ until the third argument is $1$, where $C(v,k,1)=\left\lceil \frac vk\right\rceil$. In your case: $$C(36, 30, 6)\geq \left\lceil \frac {36}{30} \left\lceil \frac {35}{29} \left\lceil \ldots\right\rceil\right\rceil\right\rceil=9$$
So all you have to do is find one solution in $9$ steps, then the theory tells you that this is optimal.
See e.g. Asymptotically optimal covering designs by Gordon, Kuperberg, Patashnik and Spencer.
Also, a SAGE command to compute Schönheim bounds: visit sagecell.sagemath.org and type in the two lines
from sage.combinat.designs.covering_design import schonheim schonheim(36,30,6)then click
Evaluate.