I have been recently taking course on Combinatorics and landed on following problem, Here is the formal statement of problem:
A room contains a single bulb and $(2^{2^{10}}+2^{2^9})$ identical switches, out of these switches, exactly one switch will operate the bulb, in each attempt by a person, Any number of switches can be triggered on/off simultaneously only, find least number of attempts required to identify correct switch for bulb in "all possible scenarios", note: All switches are turned off initially
Here is my first Attempt: I thought If they are just asking minimum possible attempts so that correct switch can be identified, Why not trigger all buttons on first attempt, and find out which button triggered the bulb on, but later realised that multiple switches can only be triggered simultaneously, from which one cannot uniquely identify which switch worked, Hence Discarded the idea, then Thought switch on all switches one by one, But its feasibility will depend on where the correct switch is, If bulb glows on first attempt, It would be minimum, if it glows for last attempt, It will be the maximum number of attempt, Hence I need to find some another mechanism to reduce number of Attempts so that they are minimum for all cases, Any ideas to Carry Forward? My intuition says it has something to do with problems where we switch half of them on and continue the cycle, But cannot grasp the logic
Also What will the minimum number even intuitively "mean" after finding the solution?
For each natural $n$ let $f(n)$ be the number of steps to identify the correct switch among $n$ switches in the worst case. I claim that $f(n)=\lceil \log_2 n\rceil$, that is $f(n)$ is the smallest nonnegative integer $k$ such that $2^k\ge n$. We prove the claim by on induction on $n$ as follows. Clearly, $f(1)=0$. Suppose that $n\ge 2$ is a natural number and $f(k)=\lceil \log_2 k\rceil$ for all integer $k<n$.
To prove the induction hypothesis for $n$ suppose that the switches are numbered from $1$ to $n$. Trigger any $\lceil n/2 \rceil$ switches, say, from $1$ to $\lceil n/2 \rceil$. If the bulb state was switched then one of these switches operates with the bulb, but if the bulb state was not switched then one of the remaining switches operates with the bulb. In the former case it remains to check switches from $1$ to $\lceil n/2 \rceil$, whereas in the latter case it remains to check switches from $\lceil n/2 \rceil+1$ to $n$. Note that in any of these cases there remain at most $\max\{\lceil n/2 \rceil,n-\lceil n/2 \rceil\}=\lceil n/2\rceil$ switches to check. By the induction hypothesis, this can be done in at most $\lceil \log_2 \lceil n/2\rceil\rceil=\lceil \log_2 n\rceil-1$ steps.
On the other hand, suppose that at the first step we triggered exactly $k$ switches, say, from $1$ to $k$. If the bulb state was switched then one of these switches operates with the bulb, but if the bulb state was not switched then one of the remaining switches operates with the bulb. In the former case it remains to check switches from $1$ to $k$, whereas in the latter case it remains to check switches from $k$ to $n$. Thus after the first step in the worst case there can remain at least $\max\{k,n-k\}\ge \lceil n/2\rceil$ switches which can operate with the bulb so they have to be checked. Again by the induction hypothesis, they can be checked in at least $\lceil \log_2 \lceil n/2\rceil\rceil=\lceil \log_2 n\rceil-1$ steps.
Consider the following example of the proposed algorithm. Let $n=10$ and the switches are numbered from $1$ to $10$. Thus initially we have $10$ switches to check.
At the first step we trigger the switches from $1$ to $5$. Suppose that the bulb state was changed. Thus the switch operating with the bulb is one of switches $1,\dots, 5$. Thus there remains five switches to check.
At the second step we trigger the switches from $1$ to $3$. Suppose that the bulb state was not changed. Thus the switch operating with the bulb is either switch $4$ or switch $5$. Thus there remains two switches to check.
At the second step we trigger switch $4$. Suppose that the bulb state was not changed. Thus the switch operating with the bulb is switch $5$.