(This actually is a question in coding theory.) Let $L_1,L_2,\ldots,L_n$ be the corresponding sets of lamps that are lit by Richard in the first $n$ rounds. ============================================ LEMMA: The following two statements are equivalent: (1) For any two distinct lamps $x$ and $y$, there exists some set $L_r$ that contains exactly one of $x$ and $y$. (2) Laura can correctly assign all buttons. ============================================ Proof of the lemma. (1) => (2): Consider some fixed lamp $x$, and let $R$ denote the set of all rounds $r=1,\ldots,n$ with $x\in L_r$. First, assume that $R$ is non-empty. Then the intersection of all $L_r$ over all $r\in R$ consists of the single lamp $x$. Hence there is a unique button that was pressed during the rounds in $R$, and this button switches $x$. Next assume that $R$ is empty. Then $x$ is the unique lamp that does not show up in any set $L_r$, and it is switched by the unique button that Richard has not pressed. not (1) => not (2): If two lamps $x$ and $y$ are always lit simultaneously or unlit simultaneously, then Laura cannot decide which of the corresponding two buttons switches $x$ and which one switches $y$. ============================================ The answer to (a) is $2^{2009}$: Richard arbitrarily presses the buttons for the first $2009$ lamps ($2^{2009}$ possibilities), and presses the button for the last lamp $x$ if and only if the button for the first lamp $y$ is pressed. By the lemma, Laura cannot distinguish $x$ from $y$. But if Richard goes through $2^{2009}+1$ rounds, then there must exist one round in which exactly one of $x$ and $y$ is lit. Hence Laura can identify all lamps by the lemma. ============================================ The answer to (b) is $11$: Laura associates every button with a unique bit-string of length $11$; this is possible, as $2^{11}=2048>2010$. In round $r=1,\ldots,11$, Laura simply presses the buttons for which the $r$-th bit in the bit-string equals $1$. If there are only $10$ rounds, then the $10$ sets $L_1,\ldots,L_{10}$ yield only $2^{10}=1024<2010$ patterns, so that some pair $x$ and $y$ of lamps must violate condition (1) in the lemma.

djb86 wrote: 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? For part $a$, note that if Richard picks the $2^{2009}$ combinations that include an even number of the first $2$ lamps, Laura will have no way of telling which of the first $2$ lamps is which. However, I claim she always will know which is which after $2^{2009}+1$ combinations. Why? Given any two switches $a$ and $b$, one cannot tell them apart in terms of which lightbulb they correspond to unless $a$ is pressed exactly when $b$ is pressed. However, there are only $2^{2009}$ sets of lights to pick when an even number of $a$ and $b$ are pressed. So for each lamp, the set of the numbered computations, a subset of ${1,...2^{2009}}$, for which the lamp is turned on, is distinct. This enables Laura to easily figure out which light controls which switch. Part $b$ involves powers of $2$ also, but in a different direction. All she needs is $11$ attempts. Why don't $10$ attempts suffice? Because then for each lightbulb we can make a subset of ${1,...10}$ that corresponds to which trials it turned on on. For instance if some light was on on the first, fourth, and fifth trials only the subset would be ${1,4,5}$. For two lightbulbs these subsets would be the same because $2010>1024$, and it would be impossible to tell which of $2$ switches controlled which of two lightbulbs, because one lightbulb would be on exactly when the other is on. For $11$ tries, just assign each of the $2010$ switches a unique subset of ${1,...11}$. If a switch gets ${1,2,5}$, turn it on exactly on the first, second, and fifth triangles, and similar for the others. Clearly then any given lightbulb will turn on on trials $a_1$ through $a_n$, and no other lightbulb would turn on on those same trials. Then we can clearly uniquely find the switch that controls the lightbulb from the lightbulb. So the answers are $2^{2009}+1$ and $11$, and we're done. Q.E.D.

woe wrote: (1) => (2): Consider some fixed lamp $x$, and let $R$ denote the set of all rounds $r=1,\ldots,n$ with $x\in L_r$. First, assume that $R$ is non-empty. Then the intersection of all $L_r$ over all $r\in R$ consists of the single lamp $x$. Hence there is a unique button that was pressed during the rounds in $R$, and this button switches $x$. Next assume that $R$ is empty. Then $x$ is the unique lamp that does not show up in any set $L_r$, and it is switched by the unique button that Richard has not pressed. This part of the proof is false. Since we can find an example contrary to the explanation. Assuming we have only 3 lamps. We can have set $L_1=\{1\},L_2=\{1,2\},L_3=\{1,2,3\}$, which enables Laura to distinguish 3 buttons. However, when we look at lamp 2, in the three sets, there are only two sets that includes lamp 2. The intersection of these two sets are $\{1,2\}$, which includes two but not one elements. ===================================================== I believe that we can do a minor adjustment to the solution, so that we consider about the intersection of $L_r$ that include $x$ and the complements of $L_s$ that exclude $x$. (e.g. In the example we proposed before, we consider the intersection of: $\{1,2,3\},\{1,2\}$, since they are the sets that include lamp 2; $\{2,3\}$, since it is the complement of the set that excludes lamp 2. Thus we get the intersection $\{2\}$, which fulfills our will.) I hope this can help solve the problem.