Browse · MathNet
PrintEstonian Math Competitions
Estonia counting and probability
Problem
Let be positive integers. In each cell of an grid there is a lamp, which can either be turned on or off. In one switch, we can change the state of five lamps, which are placed in cells forming a cross (see the diagram). Initially all the lamps are turned off. How many possible arrangements of lamps can be formed with these switches? Arrangements obtained from each other by rotations and reflections are considered different.
Solution
Answer: .
For convenience, assume that the switch for any cross is located at the central cell of that cross. Then switches are located in all cells not on the edge of the grid. There are such cells.
The final state of each lamp is determined by whether there have been an even or odd number of switches affecting it, meaning we can cancel out all double presses of the same switch. So any possible arrangement can be achieved by using each switch at most once. There are possibilities for the choice of switches to use.
Consider any two combinations differing by at least one switch used. Let be the leftmost square, whose switch is used in one combination, but not in the other (if there are several options, choose at random). Then the left neighbour of will have a different end state for these arrangements. So different combinations yield different lamp arrangements. Therefore there are exactly possible arrangements.
For convenience, assume that the switch for any cross is located at the central cell of that cross. Then switches are located in all cells not on the edge of the grid. There are such cells.
The final state of each lamp is determined by whether there have been an even or odd number of switches affecting it, meaning we can cancel out all double presses of the same switch. So any possible arrangement can be achieved by using each switch at most once. There are possibilities for the choice of switches to use.
Consider any two combinations differing by at least one switch used. Let be the leftmost square, whose switch is used in one combination, but not in the other (if there are several options, choose at random). Then the left neighbour of will have a different end state for these arrangements. So different combinations yield different lamp arrangements. Therefore there are exactly possible arrangements.
Final answer
2^{(m-2)(n-2)}
Techniques
Invariants / monovariantsColoring schemes, extremal arguments