Problem

Source: Moscow Olympiad 2018, Grade 11, P6

Tags: combinatorics



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 ?