There are 8 rooms, one containing a pot of gold. You know which room the gold is in, but your partner does not. The task is to inform your partner which room the gold is in under the following condition.
There is a switch board with 40 up/down switches, all randomly set. You must pass on the room number to your partner using this switch board while only being able to flick one switch.
How can this be done?
On
We can consider bit sums mod 2. Number all switches, starting at 0, ending 39, their bit values being $d[i]$ for index $i$. Take relative prime number "steps", for example 2,3,5 calculate initial arithmetic bit sum for these subsets
$$b = [2,3,5]$$
$$a_i= \sum_{k=0}^{\lfloor39/b_i\rfloor} d[k \cdot b_i] \hspace{1cm} \text{ where } a_i,d[j] \in \mathbb{Z}_2 \hspace{0.5cm} \forall i,j\in\mathbb{Z}$$
Denote the truth value for the need to switch bit $a_k$ by $s_k$. An index is then given by: $$\mod\left(\prod_{i=0}^{\text{len(b)}}(s_i \cdot (b_i-1)+1) , \prod_{i=0}^{\text{len}(b)}b_i\right)$$
We can convince ourselves the minimum index strategy works by evaluating in Octave (or Matlab if it ever implements automatic broadcasting):
mod(prod((mod([0:7]',[8,4,2])>=[4,2,1]).*([5,3,2]-1)+1,2),30)'
ans = [ 1 2 3 6 5 10 15 0 ]
As we can see for all of the eight cases there will be unique ID to switch so no space for confusion.
Next step if we need efficiency would be to let both sender and receiver implement a number of sieves.
There will be redundancy as prime number positions larger than the largest number ($5$ in our example) will be redundant. This would let us skip $7,11,13, 2 \cdot 7 = 14$ and we're down to needing $16-4 = 12$ switches.
Another sieve would be to remove indexes which have any prime in $b$ occuring more than once. This lets us weed out $4=2^2,8=2^3,9=3^2,12=2^2\cdot 3$, then we're down to $12-4=8$ switches required.
And if we are obliged to flick a switch there is still no problem as $1$ not divisible by any prime in $b$. And if we are not obliged we can remove index 1 too. Finally the solution should not be worse than Ross's ;)
Implementation wise we can do this with bit masking with and followed by hamming distances ( population count ) and then xoring with 1 in the desired position. ( Just in case Alice and Bob have access to bit logic assembly in the dungeon. )
I can do it with only seven switches. I need to transmit three bits to my friend. Bit one is the parity of the number of switches up among $1,3,5,7$. Bit two is the parity of the number of switches up among $2,3,6,7$. Bit three is the parity of the number of switches up among $4,5,6,7$. I examine the initial setting, find the bits that are wrong, if any, and there is one switch I can flip to make the parities right. If none are wrong, I leave well enough alone as OP said was allowed. The switch to flip is found by reading the set of errors in binary.