
10.3. Laura has 2010 lamps connected with 2010 buttons in front of her. For each button, she wants to know the corresponding lamp. In order to do this, she observes which lamps are lit when Richard presses a selection of buttons. (Not pressing anything is also a possible selection.) Richard always presses the buttons simultaneously, so the lamps are lit simultaneously, too.

a) If Richard chooses the buttons to be pressed, what is the maximum number of different combinations of buttons he can press until Laura can assign the buttons to the lamps correctly?

b) Supposing that Laura will choose the combinations of buttons to be pressed, what is the minimum number of attempts she has to do until she is able to associate the buttons with the lamps in a correct way?


Solution. a) Let us say that two lamps are separated, if one of the lamps is turned on while the other lamp remains off. Laura can find out which lamps belong to the buttons if every two lamps are separated. Let Richard choose two arbitrary lamps. To begin with, he turns both lamps on and then varies all the other lamps in all possible ways. There are $2^{2008}$ different combinations for the remaining $2010-2=2008$ lamps. Then Richard turns
the two chosen lamps off. Also, at this time there are $2^{2008}$ combinations for the remaining lamps. Consequently, for the $2^{2009}$ combinations in all, it is not possible to separate the two lamps of the first pair. However, we cannot avoid the separation if we add one more combination. Indeed, for every pair of lamps, we see that if we turn on a combination of lamps $2^{2009}+1$ times, there must be at least one setup where exactly one of the lamps is turned on and the other is turned off. Thus, the answer is $2^{2009}+1$.

b) For every new step with a combination of lamps turned on, we get a partition of the set of lamps into smaller and smaller subsets where elements belonging to the same subset cannot be separated. In each step every subset is either unchanged or divided into two smaller parts, i.e. the total number of subsets after $\mathrm{k}$ steps will be at most $2^{k}$. We are finished when the number of subsets is equal to 2010 , so the answer is at least $\left\lceil\log _{2} 2010\right\rceil=11$. But it is easy to see that Laura certainly can choose buttons in every step in such a way that there are at most $2^{11-k}$ lamps in every part of the partition after $k$ steps. Thus, the answer is 11 .
