IMO 2006 Shortlist C1
We have n ≥ 2 lamps L1,...,Ln in a row, each of them being either on or off . Every second we simultaneously modify the ...
Category: Combinatorics
Problem
We have n ≥ 2 lamps L1,...,Ln in a row, each of them being either on or off . Every second we simultaneously modify the state of each lamp as follows: — if the lamp Li and its neighbours (only one neighbour for i = 1 or i = n, two neighbours for other i) are in the same state, then Li is switched off; — otherwise, Li is switched on. Initially all the lamps are off except the leftmost one which is on. (a) Prove that there are infinitely many integers n for which all the lamps will eventually be off. (b) Prove that there are infinitely many integers n for which the lamps will never be all off. (France)