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"

(New page: === Problem 5 === Let <math>n</math> and <math>k</math> be positive integers with <math>k \geq n</math> and <math>k - n</math> an even number. Let <math>2n</math> lamps labelled <math>1</m...)
 
Line 9: Line 9:
  
 
== Solution ==
 
== Solution ==
−
Let us describe all sequences of switching the lamps as a <math>k</math>-dimensional vector
+
For convenience, let <math>A</math> denote the set <math>(1,2,\ldots n)</math> and <math>B</math> the set <math>(n+1,n+2,\ldots,2n)</math>.
−
<math>(a_1, a_2, \ldots, a_k)</math>, where <math>a_i \in (1,2,\ldots,2n)</math> denotes which lamp was switched on the <math>i</math>-th move for <math>i=1,2,\ldots k</math>.  
 
  
−
Let <math>\cal{N}</math> consist of those sequences that contain each of the numbers <math>1,2,\ldots, n</math> an odd number of times and each of the numbers <math>n+1,\ldots,2n</math> an even number of times. Define the following mapping <math>f:\cal{N}->\cal{M}</math> as
+
We can describe each sequences of switching the lamps as a <math>k</math>-dimensional vector
 +
<math>(a_1, a_2, \ldots, a_k)</math>, where <math>a_i \in A \cup B</math> signifies which lamp was switched on the <math>i</math>-th move for <math>i=1,2,\ldots k</math>.
 +
 
 +
Let <math>\cal{N}</math> consist of those sequences that contain each of the numbers in <math>A</math> an ''odd'' number of times and each of the numbers in <math>B</math> an ''even'' number of times. Similarly, let <math>\cal{M}</math> denote the set of those sequences that contain no numbers from <math>B</math> and each of the numbers in <math>A</math> an odd number of times. By definition, <math>M=|\cal{M}</math> and <math>N=\cal{N}</math>.
 +
 
 +
Define the mapping <math>f:\cal{N}->\cal{M}</math> as
 
<cmath>f(a_1, a_2, \ldots, a_k) = (b_1,b_2,\ldots b_k) :  
 
<cmath>f(a_1, a_2, \ldots, a_k) = (b_1,b_2,\ldots b_k) :  
−
b_i = \left{ \begin{array}  
+
b_i = \left\{ \begin{array}{l}
−
   a_i, & a_i \in [1, n] \\
+
   a_i \textrm{ if }  a_i \in A \\
−
   a_i-n, & a_i  \in [n+1,2n]
+
   a_i-n \textrm{ if } a_i  \in B
 
\end{array} \right .</cmath>
 
\end{array} \right .</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> ekements 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> and let <math>B_1,</math>B_2,\ldots,B_n<math> be the sets of </math>1<math>-es, </math>2<math>-es, \ldots and </math>n$-s.

Revision as of 05:44, 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}->\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}$ and let $B_1,$B_2,\ldots,B_n$be the sets of$1$-es,$2$-es, \ldots and$n$-s.

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