Browse · MathNet
PrintHong Kong Preliminary Selection Contest
Hong Kong counting and probability
Problem
There are 12 lamps, initially all off, each of which comes with a switch. When a switch is pressed, a lamp which is off will be turned on, and a lamp which is on will be turned off. Now one is allowed to press exactly 5 different switches in each round. What is the minimum number of rounds needed so that all lamps will be turned on?
Solution
Suppose all lamps are turned on after rounds. Then we have pressed the switches times in total. Note that each lamp should change state for an odd number of times. As there are 12 lamps, the total number of times the lamps have changed state is an even number, meaning that is even.
Clearly, , since at most lamps can be turned on in 2 rounds.
On the other hand, we can turn on all lamps in 4 rounds as follows:
Round 1 — Press switches 1, 2, 3, 4, 5 Round 2 — Press switches 6, 7, 8, 9, 10 Round 3 — Press switches 7, 8, 9, 10, 11 Round 4 — Press switches 7, 8, 9, 10, 12
It follows that the answer is 4.
Clearly, , since at most lamps can be turned on in 2 rounds.
On the other hand, we can turn on all lamps in 4 rounds as follows:
Round 1 — Press switches 1, 2, 3, 4, 5 Round 2 — Press switches 6, 7, 8, 9, 10 Round 3 — Press switches 7, 8, 9, 10, 11 Round 4 — Press switches 7, 8, 9, 10, 12
It follows that the answer is 4.
Final answer
4
Techniques
Invariants / monovariants