There is house with $2^n$ rooms and every room has one light bulb and light switch. But wiring was connected wrong, so light switch can turn on light in some another room. Master want to find what switch connected to every light bulb. He use next practice: he send some workers in the some rooms, then they turn on switches in same time, then they go to master and tell him, in what rooms light bulb was turned on. a) Prove that $2n$ moves is enough to find, how switches are connected to bulbs. b) Is $2n-1$ moves always enough ?
Problem
Source: Moscow Olympiad 2018, Grade 11, P6
Tags: combinatorics
ThE-dArK-lOrD
07.04.2018 21:57
Label each of $2^n$ rooms by distinct number from $S=\{ 0,1,2,...,2^n-1\}$.
For each room number $d\in S$, consider its binary representation, which contains at most $n$ digits.
For each $i\in \{ 0,1,2,...,n\}$, let $A_i$, and $B_i$, denote the set of all $d\in S$ that the $i^{th}$ digit (say, from the left) is zero, and one, respectively.
Then, in $2n$ moves, send workers to rooms whose number from the set $A_i$ or $B_i$ where $i\in \{ 1,2,...,n\}$.
Not hard to check that, for each $d\in S$ and for all $i\in \{ 1,2,...,n\}$, we can determine the $i^{th}$ digit of the number of room whose switch control the bulb in room number $d$ using information we know from sending $A_i$ and $B_i$.
The answer is yes. We use the same method in a) to determine, in first $2n-2$ moves, for each $d\in S$, the $i^{th}$ digit of the number of room whose switch control the bulb in room number $d$ but only for all $i\in \{ 1,2,...,n\}$ but one choice.
At this stage, we already get that, for each one of $2^{n-1}$ choices of the determined $n-1$ positions, there're exactly two distinct rooms that the switches in those two rooms control the light bulbs in the two rooms whose the room number appear that fixed $n-1$ positions.
So, our objective for the last moves is so that, for every one of $2^{n-1}$ choices of the $n-1$ positions, the following conditions are fulfilled:
Exactly one of two rooms whose number contain those $n-1$ positions was chosen, and
Exactly one of two rooms whose switch control light bulbs in two rooms in the above condition was chosen.
Now this is obvious, view these two conditions as two perfect matching of graph with $2^n$ vertices.
Those two perfect matching combined (multiple edge allowed) gives us a graph $G$ such that every vertex has degree $2$.
So, $G$ is nothing but union of disjoint cycles. Moreover, all of those cycles are even cycle (why?)
For every edge of $G$ connect two vertices $v,w$, we want exactly one of them to be chosen.
This can be done easily by just alternatively select and discard vertices along those even cycles, done!
dgrozev
09.04.2018 16:11
Just a comment: The statement of the problem, as written, is ambiguous: " ...then they turn on switches in same time, then they go to master and tell him, in what rooms light bulb was turned on." It's not clear whether the workers check all the rooms, after pushing the switches, or they check only the rooms they were sent in. Because in the former case only $n$ moves would have been enough. Of course, seeing what should be proven, one could guess the meaning.
But anyway, it made me search for the original Russian text, here is the beginning: "Euro construction repairs(евроремонт) took place in a building with $2^n$ rooms,...". That term is commonly used in Russia for construction repairs complying with EU standards and using imported European materials. Of course it's much more expensive. So, after such an repair, all things are messed up.
I'm far from being paranoid, it's a kind of a joke, but nevertheless it shows some attitude towards EU standards/materials/style of life, etc.