This looks silly, but...

My solution is essentially the same as above. Let $V$ be the vector space over $Z/2Z^n$ and let $+$ (or addition) be done component wise in modulo 2 and the string $(0,0,...,0)$ be the null vector. Let the $i$th lamp be On iff the $i$ th bit is 1 and Off otherwise. To $i$th state we assign an element $s_i$ of $V$.If $(s_1+...+s_k)$ is $(1,1,...,1)$(Call it $1_n$) for some $k$ less than ${2^{n-1}-1}$ we are done. Otherwise let $s=s_1+...+s_{2^{n-1}-1}$. If $s$ is $1_n$ we are done. If $s+s_i$ is $1_n$ (for $i=1,...,{2^{n-1}-1}$) we are done. Otherwise let us choose another subset which contributes $s'$. Now if $s+s'$ is $1_n$ we are done. Otherwise since the empty set is not there we have an $i$ with $i\le 2^{n-1}-1$ such that $s+s'+s_i$ is $1_n$(using a simple counting argument). Hence the conclusion.

Can someone kindly explain the last step of the above solutions?

cba wrote: Can someone kindly explain the last step of the above solutions? X is the buttons you have already chosen ( |X|=$2^{n-1}-1$ ) Y is the buttons you don't know if $s' \in X$ ,then choose it , we consider the case $s' \in Y $ if you can find $s_i, s_j \in X$, that $s_i +s_j =s'$,we make $s_i, s_j $ to be the last two bottons, we notice that for the $2^{n}-2$ subsets ( except s' and the empty one ), we can make $2^{n-1}-1$ pairs of $(i,j)$ such that $s_i +s_j =s'$ each pair of $(i,j)$ can't belong to X or Y, in another word, it must be one in X and the other one in Y

hajimbrak wrote: There are $n\ge 2$ lamps, each with two states: $\textbf{on}$ or $\textbf{off}$. For each non-empty subset $A$ of the set of these lamps, there is a $\textit{soft-button}$ which operates on the lamps in $A$; that is, upon $\textit{operating}$ this button each of the lamps in $A$ changes its state(on to off and off to on). The buttons are identical and it is not known which button corresponds to which subset of lamps. Suppose all the lamps are off initially. Show that one can always switch all the lamps on by performing at most $2^{n-1}+1$ operations. Consider the space of all subsets of $A$ as a vector space $V$ over $\mathbb{F}_2$. One basis of it may be $v_i=(0,0,\dots,1,0,\dots,0),i=1,2,\dots,n$ ($1$ is at the $i$-th place and can be interpret as a subset that contains only the $i$-th element of $A$). Clearly $V$ has dimension $n$. Now we begin to push different buttons, interpret as picking distinct vectors from $V$, until the span of the vectors picked is the entire $V$. It happens no later than at the $2^{n-1}$-th pick and may be attained if we have first picked up all $2^{n-1}-1$ non zero vectors from some $n-1$ dimensional subspace of $V$. Now, suppose we span the entire $V$ at the $2^{n-1}-r$-th vector, $r\ge 0$. Thus, the first $2^{n-1}-r-1$ vectors span some $n-1$ dimensional subspace $V_0$ of $V$. The number of all non zero vectors of $V_0$ is $2^{n-1}-1$, so let $u_1,u_2,\dots,u_r$ be the missing ones. The sum of the first $2^{n-1}-r-1$ vectors is exactly $u:=u_1+u_2+\dots+u_r\in V_0$. Let the last picked up vector is $v$. Then $(1,1,\dots,1)=v'+v$, where $v'\in V_0$ implying $(1,1,\dots,1)=u+(-u+v')+v$. The dimension of the subspace $V_0'$ of $V_0$ spanned by $u_1,u_2,\dots,u_r,v'$ is at most $r+1$ and we can choose a basis of $V_0'$ which does not contain $u_1,u_2,\dots,u_r$ (easy to prove). Pushing some of the buttons corresponding to that basis, we can construct the vector $(-u+v')$ with at most $r+1$ operations. Hence, all operations needed to construct $(1,1,\dots,1)$ are at most $2^{n-1}-r+(r+1)=2^{n-1}+1$.