Problem 5

Let

n

and

k

be positive integers with

k \ge n

and

k - n

an even number. Let

2n

lamps labelled

1, 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

N

be the number of such sequences consisting of

k

steps and resulting in the state where lamps

1

through

n

are all on, and lamps

n+1

through

2n

are all off. Let

M

be the number of such sequences consisting of

k

steps, resulting in the state where lamps

1

through

n

are all on, and lamps

n+1

through

2n

are all off, but where none of the lamps

n+1

through

2n

is ever switched on. Determine

\dfrac{N}{M}

Step 2 of 3: Define the folding map f from N-sequences to M-sequences

Previous step Next step

In plain words

Folding every switch of lamp $n+i$ onto lamp $i$ adds an even number of switches to lamp $i$ , keeping its total count odd while eliminating all switches in $B$ .

f(a_1,\ldots,a_k) = (b_1,\ldots,b_k), \qquad b_r = \begin{cases} a_r, & a_r \in A \\ a_r - n, & a_r \in B \end{cases}

Detailed analysis

Define $f: \mathcal{N} \to \mathcal{M}$ by replacing each entry $n+i \in B$ with $i \in A$ . Because $n+i$ appears an even number of times in any $(a_1,\ldots,a_k) \in \mathcal{N}$ and $i$ appears an odd number of times, the image $f(a_1,\ldots,a_k)$ has each $i \in A$ appearing an odd-plus-even = odd number of times and no entries from $B$ , so $f(\mathcal{N}) \subseteq \mathcal{M}$ .