2008 IMO Problems/Problem 5
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
\[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 is an image of exactly elements from , which would imply and solve the problem.
Consider an arbitrary element of and let be the number of appearances of the number in for . Now consider the set of pre-images of , that is .
It is easy to see that each element is derived from by flipping an even number of its -s, -s, and so on, where flipping means changing the number to . Since each such set of flippings results in a unique , all we want to count is the number of flippings. We can flip exactly of the -s, so that results in flippings. Combine each of them with the , , etc. ways of flipping the -s, -s etc. respectively to get the total number of flippings: This shows that and the proof is complete.