MathLabs

Problem 5

Let nn and kk be positive integers with k≥nk \ge n and k−nk - n an even number. Let 2n2n lamps labelled 1,2,…,2n1, 2, \ldots, 2n be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on). Let NN be the number of such sequences consisting of kk steps and resulting in the state where lamps 11 through nn are all on, and lamps n+1n+1 through 2n2n are all off. Let MM be the number of such sequences consisting of kk steps, resulting in the state where lamps 11 through nn are all on, and lamps n+1n+1 through 2n2n are all off, but where none of the lamps n+1n+1 through 2n2n is ever switched on. Determine NM\dfrac{N}{M}.
Step 1 of 3: Characterize N-sequences and M-sequences by switch-count parities
Previous stepNext step
In plain words

Starting from all lamps off, a lamp ends on if and only if it is switched an odd number of times, and off if and only if it is switched an even number of times.

A={1,…,n}, B={n+1,…,2n};N:odd on A, even on B;M:odd on A, 0 on BA = \{1,\ldots,n\},\ B = \{n+1,\ldots,2n\}; \quad \mathcal{N}: \text{odd on } A,\ \text{even on } B; \quad \mathcal{M}: \text{odd on } A,\ 0 \text{ on } B
Detailed analysis

Write a kk-step sequence as (a1,…,ak)∈(A∪B)k(a_1,\ldots,a_k) \in (A \cup B)^k where A={1,…,n}A=\{1,\ldots,n\} and B={n+1,…,2n}B=\{n+1,\ldots,2n\}. The set N\mathcal{N} (of size NN) consists of sequences in which every i∈Ai \in A appears an odd number of times and every n+i∈Bn+i \in B appears an even number of times; the subset M\mathcal{M} (of size MM) consists of sequences in which every i∈Ai \in A appears an odd number of times and no element of BB appears at all (with M>0M > 0 since k≥nk \ge n and k−nk - n is even).