, 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.