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 == | ||
− | + | 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> | ||
− | Let <math>\cal{N}</math> consist of those sequences that contain each of the numbers <math> | + | 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 \textrm{ if } a_i \in A \\ |
− | a_i-n | + | 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 04:44, 4 September 2008
Problem 5
Let and be positive integers with and an even number. Let lamps labelled , , ..., 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 be the number of such sequences consisting of steps and resulting in the state where lamps through are all on, and lamps through are all off.
Let be number of such sequences consisting of steps, resulting in the state where lamps through are all on, and lamps through are all off, but where none of the lamps through is ever switched on.
Determine .
Solution
For convenience, let denote the set and the set .
We can describe each sequences of switching the lamps as a -dimensional vector , where signifies which lamp was switched on the -th move for .
Let consist of those sequences that contain each of the numbers in an odd number of times and each of the numbers in an even number of times. Similarly, let denote the set of those sequences that contain no numbers from and each of the numbers in an odd number of times. By definition, and .
Define the mapping as
What we want to show now is that each element of is an image of exactly ekements from , which would imply and solve the problem.
Consider an element of and let B_2,\ldots,B_n12n$-s.