Argentine National Olympiad 2015

The least number of subsets is 28. Suppose that Bibi has 3 lists 1, 2, 3 which enable her to find $N$ with certainty. Let the lists contain $a_1,a_2,a_3$ subsets respectively. For list $i=1,2,3$ Alex announces the number $x_i$ of subsets in the list that contain $N$, and the ordered triple $x_1,x_2,x_3$ is the only information Bibi obtains. So being able to guess $N$ with certainty means that each triple $x_1,x_2,x_3$ yields a certain $N\in \{1,2,...,1001\}$ as a solution. Because there are 1001 possible numbers $N$ and Alex can choose any of them, it is then necessary that the number of different triples $x_1,x_2,x_3$ is at least 1001. This number equals $(a_1+1)(a_2+1)(a_3+1)$ as there are $a_i+1$ possible values of $x_i$, namely $0,1,...,a_i$ ($i=1,2,3$). Hence we must have

$$(a_1+1)(a_2+1)(a_3+1)\ge 1001.$$

Now use the AM-GM inequality to estimate the total number $a_1+a_2+a_3$ of subsets used by Bibi:

$$1001\le (a_1+1)(a_2+1)(a_3+1)\le {\left(\frac{a_1+a_2+a_3}{3}+1\right)}^3$$

It follows from here that $a_1+a_2+a_3\ge 28$. Indeed if $a_1+a_2+a_3\le 27$ then the right-hand side of the displayed inequality is at most ${\left(\frac{27}{3}+1\right)}^3=1000$.

Now we show that 3 lists with a total of 28 sets suffice. Use the factorization $1001=7\cdot 11\cdot 13$, consider a $7\times 11\times 13$ parallelepiped with the numbers $1,2,...,1001$ written in its unit cubes. Let the vertical dimension be 13, then there are 13 horizontal layers of unit cubes (of dimensions $7\times 11$). For $i=1,2,...,12$ let $S_i$ be the union of the first $i$ horizontal layers. Let list 1 consist of the 12 sets $S_1,S_2,...,S_{12}$, and let Alex say that $x_1$ of them contain $N$. Observe that this answer enables Bibi to determine the horizontal layer containing $N$, whatever the announced value $x_1\in \{0,1,...,12\}$. Indeed, since $S_1\subset S_2\subset ...\subset S_{12}$, the answer $x_1=0$ means that $N$ is in layer 13, $x_1=1$ means that it is in layer 12, etc. In general $x_1=i\in \{0,1,...,12\}$ implies that $N$ is in horizontal layer $13-i$. Thus a list of 12 sets is enough to single out the necessary layer out of 13 possible ones. Analogous lists in the other two directions, with $7-1=6$ sets and $11-1=10$ sets, can determine the layers in those directions that contain $N$.

As a result $N$ becomes known with $12+6+10=28$ sets, with 3 lists used. If Bibi uses 2 lists with $a_1$ and $a_2$ sets then by the same reasoning it is necessary that

$$1001\le (a_1+1)(a_2+1)\le {\left(\frac{a_1+a_2}{2}+1\right)}^2,\text{ hence }{a}_1+a_2\ge 61.$$

Finally it is clear that one list alone would require at least 1000 sets.