2008 IMO Problems/Problem 5

Problem 5

Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number. Let $2n$ lamps labelled $1$ , $2$ , ..., $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 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 $\frac {N}{M}$ .

Solution

For convenience, let $A$ denote the set $(1,2,\ldots n)$ and $B$ the set $(n+1,n+2,\ldots,2n)$ .

We can describe each sequences of switching the lamps as a $k$ -dimensional vector $(a_1, a_2, \ldots, a_k)$ , where $a_i \in A \cup B$ signifies which lamp was switched on the $i$ -th move for $i=1,2,\ldots k$ .

Let $\cal{N}$ consist of those sequences that contain each of the numbers in $A$ an odd number of times and each of the numbers in $B$ an even number of times. Similarly, let $\cal{M}$ denote the set of those sequences that contain no numbers from $B$ and each of the numbers in $A$ an odd number of times. By definition, $M=|\cal{M}$ and $N=\cal{N}$ .

Define the mapping $f:\cal{N}->\cal{M}$ as $f(a_1, a_2, \ldots, a_k) = (b_1,b_2,\ldots b_k) : b_i = \left\{ \begin{array}{l} a_i \textrm{ if } a_i \in A \\ a_i-n \textrm{ if } a_i \in B \end{array} \right .$

What we want to show now is that each element of $\cal{M}$ is an image of exactly $2^{k-n}$ ekements from $cal{N}$ , which would imply $N = 2^{k-n}M$ and solve the problem.

Consider an element $y$ of $\cal{M}$ let $l_i$ be the number of apearances of the number $i$ in $y$ for $i=1,2,\ldots n$ . Now consider the set of pre-images of $y$ , that is

\[X_y = \{ x \in \cal{N} | \math{f(x) = y }\}.\] (Error compiling LaTeX. Unknown error_msg)

It is easy to see that each element $x\in X_y$ is derived from $y$ by flipping an even number of its $1$ -s, $2$ -s, and so on, where flipping means changing the number $k\in A$ to $k+n\in B$ . Since each such flipping results in a unique $x$ , all we want to count is count the flippings. We can flip $0, 2, 4,\ldots$ of the $1$ -s and choose which ones, so that results in $\binom{l_1}{0} + \binom{l_1}{2}+\binom{l_1}{4}+\cdots+ = 2^{l_1-1}$ flippings. Combine each of them with the $2^{l_2-1}$ , $2^{l_3-1}$ , etc. ways of flipping the $2$ -s, $3$ -s etc. respectively to get the total number of flippings $2^{(l_1-1)+(l_2-1)+\cdots+(l_n-1)} = 2^{l_1+l_2+\cdots+l_k-n} = 2^{k-n}.$ This shows that $|X_y| = 2^{k-n}$ and the proof is complete.

Page

Toolbox

Search

2008 IMO Problems/Problem 5

Problem 5

Solution