Room and Lights Game

This problem is identical to this one but reworded for better clarity.

Alice is playing a game against Bob and Charlie. In a room, there are 27 lights with individual switches, some of them could be turned on or off. Bob enters the room while Charlie waits outside. Alice will tell Bob a number from 1 to 27. Bob then is allowed to flip at most 3 switches if he wishes. Then Bob exits and Charlie enters the room. He has to, upon examining the lights, guess the number that Alice told Bob. Neither Bob nor Charlie knows the configuration of the lights before Bob entered the room.

How can Bob and Charlie agree on a strategy to win this game?

Harder version: 15 lights, but Alice tells Bob a number from 1 to 16, and Bob can only flip at most one switch.

Solution

Credit goes to Boon Leong Ng and David Rager for the first part of the solution.

Let us consider the case of 3 lights, and the number ranges from 1 to 4, and he is allowed to flip one switch. Bob and Charlie can agree on the following scheme:

Number the light from 1 to 3 and observe their configuration. Whichever is the "odd one out", that is the number. So, ON ON OFF would mean the number is 3. ON OFF OFF would mean the number is 1. If all three lights are all ON or all OFF, then the number is 4. It is possible to achieve any desired configuration from the original configuration within 1 flip.

For example, if Bob finds that it's ON OFF OFF but the number is 2, he flips the third switch. If the number is 3, he flips the first switch instead. If the number is 1, then that configuration is already correct, and he doesn't need to flip.

Now, let us consider the case of 9 lights, number ranges from 1 to 16, and he is allowed to flip two switches.

Express the number 1 to 16 as a two digit quaternary numbers, where 16 is expressed as 00 instead (so 8 would be 20, 14 would be 32, and so on).

Then let A be the parity of the lights 1,2,3. That is, A is 1 if an odd number of them is ON, and A is 0 if an even number of them is ON. B be the parity of lights 4,5, and 6, and C be the parity of lights 7,8,9. We can apply the same strategy, using A,B, and C to decode the first digit in the quaternary numbers. Suppose our algorithm requires us to flip C from 1 to zero, then we can slip the switch of any light in C and that would flip the parity of C. We expend a total of 1 flip in encoding the first digit.

The second flip can be spent on the lights 1,2,3 themselves to encode the second quarternary digit, again using the same strategy as above.

When Charlie enters the room, he reconstructs both quaternary digits from the lights and would be able to get the number that Alice mentioned.

This concept can be generalized to $3^k$ lights, $4^k$ choice of numbers, and $k$ flips.

Harder Version

With 1 flip, 16 numbers, 15 lights, things get a little bit more complicated.

Express the numbers as 4 digit binary numbers from 0000 to 1111. And give each light an ID number from 1 to 15, and again express them as 4 digit binary numbers from 0001 to 1111. (Note that no light has ID 0000)

Let $S$ be the XOR of the IDs of the lights that are ON. Bob's job is to flip one switch such that when Charlie enters the room, $S$ would point to the number that Alice mentioned.

Suppose originally it's $S_1$ and the desired configuration would yield $S_2$. We wish to prove that $S_1$ and $S_2$ is just within one flip from another. In fact, flipping the light whose ID is $S_1 \oplus S_2$ would do the job.

If $x = S_1 \oplus S_2$, flipping $x$ would either add $x$ to the XOR sum, or "take away" from it. But since $x \oplus x = 0$, then "taking away" $x$ from the sum is also the same as adding $x$ to the sum. So if the original configuration is $S_1$, after we flip $x$, we have $S_1 \oplus x = S_1 \oplus (S_1 \oplus S_2) = (S_1 \oplus S_1) \oplus S_2 = S_2$.

If $x$ happens to be zero, then $S_1$ and $S_2$ are identical, in which case Bob simply does not flip.

Furthermore, this operation is relatively efficient to perform, since XOR is associative and commutative. Bob can start with $S_2$ (the number that Alice mentioned), and XOR it with the IDs of the lights that he sees ON, one by one.