4
$\begingroup$

First of all, I don't know the answer to this question; I have some ideas, but nothing rigorous. Apologies if it's not on-topic. I have solved the puzzle now.

Suppose there is a light switch in a room. You are with $n-1$ other people, each of whom has an (unchanging) operation on the switch out of four possible operations: They can turn it on no matter what, off no matter what, flip the switch, or do nothing.

You don't know what the other people's operations are. To gain information, you perform "rounds" in which all $n$ people go into the room in some order, one by one, and perform their operation. You choose the order after each round. On your turn, you may observe the current state of the switch, and set the switch to whatever you like. Before the first round, the switch begins in an unknown state.

In the worst case, how many rounds does it take to determine everyone's operation?

Example: Suppose $n=3$, we label ourselves as $P$, and label the other two players as $A$ and $B$. Let the on state be denoted $1$ and the off state as $0$. If we perform the following rounds:

(1)         | (2)            | (3)           | (4)        
BPA         | PAB            | PAB           | BPA        
 ^ set to 1   ^ observe x      ^ observe y      ^ observe z
                set to 1         set to 1         set to 0

| (5)           | (6)              | (7)
| PAB           | APB              | PAB
  ^ observe w      ^ set to (not y)  ^ observe u

Together, $(x,y,z,w,u)$ is enough to construct $A$ and $B$'s operations.

Explanation:

Observations in rounds 2 and 4 determine $A$, because we know the result after $0$ and $1$. The observation in round 3 determines the result of applying $AB$ to $1$, namely $y$. The observation in round 4 tells us the result of applying $y$ to $B$. The observation in round 7 tells us the result of applying $\lnot y$ to $B$. Together, 4 and 7 determine $B$.

Crude upper and lower bounds:

Each round gives us $1$ bit of information, and since there are $4^{n-1}$ possibilities, it must take at least $2n-2$ rounds by the pigeonhole principle. The above example can be relatively easily extended to any $n$, giving an upper bound of $4n-1$.

$\endgroup$
2
  • $\begingroup$ The title sounds like you only need to determine those who perform the flipping operation. $\endgroup$
    – WhatsUp
    Jan 4, 2022 at 23:35
  • $\begingroup$ @WhatsUp adjusted accordingly, though I'm not sure of the most efficient phrasing $\endgroup$ Jan 4, 2022 at 23:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.