2

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)!

Arnaud Mortier
  • 27,276
Pet123
  • 1,252
  • I can do $10$. Peter guesses $1-6,7-12$ and on for the first six. If he fails on those, each block of six contains one non-red number. Now one of $1,2,3$ or $ 4,5,6$ is all red, as is one of $7,8,9$ and $10,11,12$ Four more guesses will get you there. Maybe this will help your thinking. – Ross Millikan May 12 '18 at 23:32
  • Sorry about the silly edit, that is necessary to avoid confusion with the parameter $k$ which is kind of universally used in covering desing theory. – Arnaud Mortier May 12 '18 at 23:53

1 Answers1

1

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.

Pang
  • 399
  • 5
  • 8
Arnaud Mortier
  • 27,276