IMO 2008 Shortlist C4
Let n and k be fixed positive integers of the same parity, k ≥ n. We are given 2n lamps numbered 1 through 2n; each of t...
Category: Combinatorics
Problem
Let n and k be fixed positive integers of the same parity, k ≥ n. We are given 2n lamps numbered 1 through 2n; each of them can be on or off. At the beginning all lamps are off. We consider sequences of k steps. At each step one of the lamps is switched (from off to on or from on to off). Let N be the number of k-step sequences ending in the state: lamps 1,...,n on, lamps n+1,...,2n off. Let M be the number of k-step sequences leading to the same state and not touching lamps n+1,...,2n at all. Find the ratio N/M.