Fatima and Asma are playing the following game. First, Fatima chooses pairwise different numbers, called . Then, Asma tries to know the value of each number . At each time, Asma chooses and asks Fatima "What is the set ?" (For example, if Asma asks what is the set , and and , Fatima will answer ). Find the least number of questions Asma needs to ask, to know the value of all the numbers .
Solution
Let be the number of different questions Asma asks to know the values of each number . Let us make the following remarks:
a. Because Asma needs to know the value of each number , each number must appear at least in one of the sets that Asma chooses to ask about.
b. If Asma chooses a set , she needs to choose another set that contains only one of the numbers , so that she can distinguish between the values of and .
c. If Asma asks about the sets and , for different indices , she will deduce the value of each number , by taking the intersection of the two sets and their differences.
d. If for some , Asma asks about the sets , for different indices , she will deduce the value of each number and does not need to ask after this about the set since she already knows the answer.
From now on, we assume, without loss of generality, that Asma never asks about a set that she already knows.
According to these remarks, we can make a partition of the set into non-empty disjoint subsets such that two numbers are in the same subset if and only if there exist sets that Asma has asked about each one of them, and such that . Notice that if are different, because of remark (d) they are unique.
For each , there are exactly sets in that Asma has asked about. To see this, fix , and for each with , associate the unique set in the previous paragraph when and are different. It is not hard to see from remark (d) that this map is a bijection between and the set of subsets of in the questions of Asma.
Because each set in the questions of Asma is contained exactly in one of the subsets , we have
Because each set must contain at least elements (remarks (a) and (b)),
This proves that .
Conversely, if Asma asks about the sets
she will know the values of all the numbers .