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

Let us describe all sequences of switching the lamps as a $k$ -dimensional vector $(a_1, a_2, \ldots, a_k)$ , where $a_i \in (1,2,\ldots,2n)$ denotes 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 $1,2,\ldots, n$ an odd number of times and each of the numbers $n+1,\ldots,2n$ an even number of times. Define the following 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} 
   a_i, & a_i \in [1, n] \\
   a_i-n, & a_i  \in [n+1,2n]
\end{array} \right .\] (Error compiling LaTeX. Unknown error_msg)

Page

Toolbox

Search

2008 IMO Problems/Problem 5

Problem 5

Solution