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 3 of 3: Count the preimages of each M-sequence and conclude N/M = 2^(k-n)

Previous step Next step

In plain words

For each $y \in \mathcal{M}$ in which lamp $i$ is switched $l_i \ge 1$ times, choosing any even-sized subset of those $l_i$ switches to lift to $n+i$ gives $2^{l_i-1}$ choices for each $i$ , and multiplying over $i=1,\ldots,n$ gives $2^{k-n}$ .

|f^{-1}(y)| = \prod_{i=1}^n \left(\binom{l_i}{0}+\binom{l_i}{2}+\cdots\right) = \prod_{i=1}^n 2^{l_i-1} = 2^{\sum_{i=1}^n l_i - n} = 2^{k-n} \implies \frac{N}{M} = 2^{k-n}

Detailed analysis

Fix $y \in \mathcal{M}$ where each $i \in A$ appears $l_i \ge 1$ times (with $\sum_{i=1}^n l_i = k$ ). A sequence $x \in \mathcal{N}$ satisfies $f(x) = y$ if and only if, for each $i \in A$ , $x$ is obtained by replacing an even number of the $l_i$ occurrences of $i$ in $y$ by $n+i$ . Since a set of size $l_i \ge 1$ has $\binom{l_i}{0}+\binom{l_i}{2}+\cdots = 2^{l_i-1}$ subsets of even size, and the choices for $i = 1,\ldots,n$ are independent, $|f^{-1}(y)| = \prod_{i=1}^n 2^{l_i-1} = 2^{\sum_{i=1}^n l_i - n} = 2^{k-n}$ . Summing over all $y \in \mathcal{M}$ gives $N = 2^{k-n} M$ , so $\dfrac{N}{M} = 2^{k-n}$ .