Minimum number of sets to guess a natural number from 1 to 100. One set contains up to 5 numbers.

Question

There is a hidden natural number from $1$ to $100$. One can make multiple sets of up to $5$ numbers. Once sets are picked, all the sets containing the hidden number are highlighted. What is the minimum number of such sets that after first try one can surely know the hidden number?

May it be so that the answer is above $20$, since if at least any number is not present in any of the set there is no way for us to know, if it is the hidden one?

Edit: There are $100$ numbers from $0$ to $99$. One number $x$ was picked, and we need to find $x$. To find it, we can choose sets of up to $5$ numbers, and when all sets are chosen we are told which sets contain $x$ and which don't. Problem: Choose a smallest number of sets. Important is that we don't get any information until all sets are chosen.

Answer 1

This is possible using 38 sets:

Arrange the hundred numbers into a rectangle of 5 rows times five columns. 19 sets are each one of the 20 columns of five numbers, except we don't have a set for the last column. This tells us in which column the hidden number is. 19 sets are the five rows of length 20 each split into 4 pieces of length five, except for the last one. This tells us in which horizontal piece of five numbers x is. Together with the column this tells us x.

Actually we can do this with 19 + 16 = 35 sets. Arrange the numbers in five rows with 20 columns. 19 sets let you determine the right column. 16 sets let you determine that x is in one of the first four rows, and if it isn't then it must be in the last row. So 35 sets.

Answer 2

The problem is equivalent to:

Build a $k \times n$ binary ($0/1$) matrix such that each row has weight (number of ones) at most $w\le 5$, and no columns are equal. The number of columns is fixed $n=100$, and we want to minimize the number of $k$ rows.

Consider the $5 \times 15$ matrix $$B = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} $$

This has fixed row weight $w=5$, and all columns are different (and not zero).

Lets build our matrix as

$$M = \begin{pmatrix} B & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & B & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & B & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & B & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & B & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & B & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & C \\ \end{pmatrix} $$

where $B$ is is the previous matrix, and

$$C = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} $$

This gives a $34 \times 100 $ matrix that fullfills the condition. Then, $34$ sets suffice. We could even add 2 more columns (all zeroes and all ones), and the construction would still be valid (so we can guess 102 numbers).

I'm not sure if this is optimal, probably not.

Update: If there exists a semi-regular $33\times 66$ matrix, with column weight $2$ and row weight $4$, then $33$ sets would be enough. I suspect that's not possible, and hence I (wildly) conjecture that $34$ is optimal.

Update 2: Conjecture is false, see Misha Lavrov's answer.

His answer, in this formulation, consists of taking

$$M = \begin{pmatrix} A & I & 0 \end{pmatrix} $$

where $I$ is the $33 \times 33$ identity, $0$ is a column of zeroes, and

$$ A = \begin{pmatrix} A_1 & 0 & 0 & 0 & 0 & 0 \\ 0 & A_1 & 0 & 0 & 0 & 0 \\ 0 & 0 & A_1 & 0 & 0 & 0 \\ 0 & 0 & 0 & A_1 & 0 & 0 \\ 0 & 0 & 0 & 0 & A_1 & 0 \\ 0 & 0 & 0 & 0 & 0 & A_2 \\ \end{pmatrix} $$

with

$$ A_1 = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \end{pmatrix} $$ and

$$ A_2 = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$

It's readily seen (by inspection, or, better, by the geometry) that both $A_1, A_2$ have row weight $4$ and column weight $2$. Hence the matrix $M$ fullfills the conditions: all rows have weight $5$ and all columns are distinct.

Answer 3

The minimum possible number is $33$ sets. First, a proof that we cannot do any better.

There can be at most one number not covered by any sets: we cannot distinguish two such numbers. Also, every set can contain at most one number that is not in any other sets; again, we cannot distinguish two such numbers.

Suppose that there are $k$ sets; let $A_0$, $A_1$, and $A_{\ge 2}$ partition $\{1,2,\dots,100\}$ into the numbers which are contained in $0$ sets, $1$ set, and $2$ or more sets, respectively. Then we must have $5k - |A_1| \ge 2|A_{\ge2}|$, because the $5k-|A_1|$ elements of the $k$ sets not covering $A_1$ must cover each element of $A_{\ge2}$ at least twice. Therefore $$ |A_0| + |A_1| + |A_{\ge 2}| \le 1 + |A_1| + \frac{5k-|A_1|}{2} \le 1 + \frac12|A_1| + \frac52k \le 3k+1. $$ But $|A_0| + |A_1| + |A_{\ge 2}| = 100$, and $3k+1 \ge 100$ only if $k\ge 33$.

To try to achieve exactly $33$ sets, we need every inequality along the way to be tight. So there is one number not in any set, $33$ numbers in exactly one set, and $66$ numbers in exactly $2$ sets. As long as, additionally, no two sets overlap in more than one element, we will be able to identify any number by the set it's in.

At the end of this post is a construction that's self-sufficient, but here is a brief overview of how it's obtained.

We can delete the numbers in fewer than $2$ sets, because those can be put back in arbitrarily at the end. It's enough to describe how to cover $66$ numbers with $33$ sets of $4$ elements, each covering $2$ sets, and with no two overlapping in more than one element.

If we wanted to cover $10$ or $16$ numbers this way, there are two easy-to-visualize configurations (with numbers being points and sets being lines):

To cover $66$ points, just break them up into groups of $10 + 10 + 10 + 10 + 10 + 16$; use a pentagram-shaped construction on the first $5$ and a grid on the last.

This gives us the following $33$ sets, divided into five pentagram-shaped constructions and one grid-shaped construction. The numbers $67, \dots, 99$ were put back in at the end and are only covered by one set; the number $100$ is not covered by any sets.

1  2  3  4  67
4  5  6  7  68
2  7  8  9  69
3  5  9  10 70
1  6  8  10 71  

11 12 13 14 72
14 15 16 17 73
12 17 18 19 74
13 15 19 20 75
11 16 18 20 76

21 22 23 24 77
24 25 26 27 78
22 27 28 29 79
23 25 29 30 80
21 26 28 30 81

31 32 33 34 82
34 35 36 37 83
32 37 38 39 84
33 35 39 40 85
31 36 38 40 86
    
41 42 43 44 87
14 45 46 47 88
42 47 48 49 89
43 45 49 50 90
41 46 48 50 91

51 52 53 54 92
55 56 57 58 93
59 60 61 62 94
63 64 65 66 95
51 55 59 63 96
52 56 60 64 97
53 57 61 65 98
54 58 62 66 99