Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 IMO Problems/Problem 5"
Line 21: Line 21:
 
   a_i \textrm{ if }  a_i \in A \\
 
   a_i \textrm{ if }  a_i \in A \\
 
   a_i-n \textrm{ if } a_i  \in B
 
   a_i-n \textrm{ if } a_i  \in B
−
\end{array} \right for i=1,2,\ldots,k</cmath>
+
\end{array} \right \textrm{for }i=1,2,\ldots,k</cmath>
  
 
What we want to show now is that each element of <math>\cal{M}</math> is an image of exactly <math>2^{k-n}</math> elements from <math>\cal{N}</math>, which would imply <math>N = 2^{k-n}M</math> and solve the problem.
 
What we want to show now is that each element of <math>\cal{M}</math> is an image of exactly <math>2^{k-n}</math> elements from <math>\cal{N}</math>, which would imply <math>N = 2^{k-n}M</math> and solve the problem.
  
−
Consider an element <math>y</math> of <math>\cal{M}</math> let <math>l_i</math> be the number of apearances of the number <math>i</math> in <math>y</math> for <math>i=1,2,\ldots n</math>. Now consider the set of pre-images of <math>y</math>, that is <math>X_y = \{ x | f(x) = y \}</math>.
+
Consider an arbitrary element <math>y</math> of <math>\cal{M}</math> and let <math>l_i</math> be the number of appearances of the number <math>i</math> in <math>y</math> for <math>i=1,2,\ldots n</math>. Now consider the set of pre-images of <math>y</math>, that is <math>X_y = \{ x | f(x) = y \}</math>.
  
 
It is easy to see that each element <math>x\in X_y</math> is derived from <math>y</math> by ''flipping'' an ''even'' number of its <math>1</math>-s, <math>2</math>-s, and so on, where flipping means changing the number <math>j\in A</math> to <math>j+n\in B</math>. Since each such set of flippings results in a unique <math>x</math>, all we want to count is the number of flippings. We can flip exactly <math>0, 2, 4,\ldots </math> of the <math>1</math>-s, so that results in
 
It is easy to see that each element <math>x\in X_y</math> is derived from <math>y</math> by ''flipping'' an ''even'' number of its <math>1</math>-s, <math>2</math>-s, and so on, where flipping means changing the number <math>j\in A</math> to <math>j+n\in B</math>. Since each such set of flippings results in a unique <math>x</math>, all we want to count is the number of flippings. We can flip exactly <math>0, 2, 4,\ldots </math> of the <math>1</math>-s, so that results in

Revision as of 05:22, 4 September 2008

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} \rightarrow \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 \textrm{for }i=1,2,\ldots,k\] (Error compiling LaTeX. Unknown error_msg)

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

Consider an arbitrary element $y$ of $\cal{M}$ and let $l_i$ be the number of appearances 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 | f(x) = y \}$.

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 $j\in A$ to $j+n\in B$. Since each such set of flippings results in a unique $x$, all we want to count is the number of flippings. We can flip exactly $0, 2, 4,\ldots$ of the $1$-s, 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}2^{l_2-1}\cdots2^{l_n-1} = 2^{l_1+l_2+\cdots+l_n-n} = 2^{k-n}.\] This shows that $|X_y| = 2^{k-n}$ and the proof is complete.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_IMO_Problems/Problem_5&oldid=27757"