However, since 7 is odd, the number of off lights cannot be the same as the number of on lights. Therefore, Bart cannot end up with such a decision; for example, if there are 3 lights on and 4 lights off, and Lisa picks three positions, Bart cannot possibly be forced to turn all the lights the same color, because it is not even possible to turn all the off lights on! Thus, for any odd n and not all lights the same color, Bart can prevent Lisa from winning.
In the base case, k = 0, there is one light. If it is on, Lisa wins; if it is off, Lisa requests
to turn it on. That takes only one turn.
Lisa’s aim will be first to get each light the same color as its partner and then to turn all the pairs on. To get each light the same color as its partner, she restricts her choices such that she never chooses both a light and its partner. Since there are 2×2k lights, there are 2k sets of partners. Lisa imagines an equivalent table with 2k lights, where each light corresponds to one set of partners on the big table. For each pair on the big table that has two different colors, their light is off on the small table; for each pair on the big table with the same color, their light is on at the small table. Then she makes each light the same color as its partner in 2k moves, just as she would solve the small table in 2k moves.
Once every light is the same color as its partner, Lisa restricts her choices such that for every light she chooses, she also chooses its partner. This time she imagines another table with 2k lights. On this small table, each light still corresponds to one set of partners on the big table, but this time the light at the small table is the same color as the pair (since the partners now match). She finishes solving the big table in 2k moves, just as she would solve
the small table in 2k moves. Lisa has then solved the big table with 2×2k lights in 2×2k moves. Our induction is complete.
Solution 2 by: Kristin Cordwell (9/NM)
(b) We identify the lights and the switching patterns with polynomials by calling the first of the consecutive eight lights (points) 1, the second x, the third x2, and so on, all the way up to x7. A light will be "on if the coefficient of its respective power of x is 1; otherwise, the light will be "off. We will also think of the switching pattern being rotated, rather than the lights. Similarly, a coefficient of 1 in a switching pattern polynomial will indicate
that that position is to be switched. To rotate a switching pattern n positions, we multiply the corresponding polynomial by xn, and we take this new polynomial mod (x8 + 1), because x8 = 1, having gone all the way around the circle. When we add and multiply polynomials, we take the coefficients mod 2, since switching (adding a power of x, with a coefficient of 1) changes an "off (0) to an "on (1) and vice-versa. (In what follows, we use symbol ≡ to indicate congruence modulo 2 or x8 + 1.)
[Ed: For example, suppose the table has 8 lights, and positions 1, 2, and 6 are on. Then the polynomial corresponding to this set of lights is
x1 - 1 + x2 - 1 + x6 - 1 = 1 + x + x5.
Lisa chooses positions 1, 2, and 6. Suppose Bart rotates the table by five positions. Then the lights in positions 6, 7, and 3 get flipped, so the lights in positions 1, 2, 3, and 7 are on. In terms of the polynomials, we multiply 1 + x + x5 by 1 + x5 to get
(1 + x + x5)(1 + x5) = 1 + x + 2x5 + x6 + x10.
We reduce all coefficients mod 2, because flipping a light twice does nothing. Also, going around the circle, position 10 is the same as position 2, which is the same as reducing the polynomial mod x8 + 1. Hence,
| 1 + x + 2x5 + x6 + x10 | ≡ 1 + x + x2 + x6 |
| | = x1 - 1 + x2 - 1 + x3 - 1 + x7 - 1, |
which confirms that the lights at positions 1, 2, 3, and 7 are on.]
An(x) the polynomial for the lights at the end of the nth round. We claim that if Lisa gives Bart a switching pattern equal to the "on lights at the beginning of that round, then Lisa will win in eight or fewer rounds.
When Lisa gives Bart A0(x) for the switching pattern, we end up with
A1(x) = An(x) + xa1An(x) = (1 + xa1)An(x)
as the new light pattern, where Bart has rotated the switching pattern by a1 positions. Similarly,
A2(x) = (1 + xa2)A1(x),
where Bart rotates the second switching pattern by a2 positions. Continuing, we get
A3(x) = (1 + xa3)A2(x),
A4(x) = (1 + xa4)A3(x),
. . . ,
A8(x) = (1 + xa8)A7(x).
Note that if x = 1, then for any i,
1 + xai = 1 + 1ai = 2 ≡ 0,
so 1 + x is a factor of 1 + xai. Indeed,
| (1 + x)(1 + x + x2 + · · · + xai - 1) |
= 1 + x + x2 + ... + xai - 1 + x + x2 + ... + xai |
| | = 1 + 2x + 2x2 + ... + 2xai - 1 + xai |
| | ≡ 1 + xai |
Thus, setting Pi(x) = 1 + x + x2 + ... + xai - 1, we can write
1 + xai ≡ (1 + x)Pi(x).
So,
| A8(x) | = (1 + xa8)A7(x) |
| | = (1 + xa8)(1 + xa7)A6(x) |
| | = ... |
| | = (1 + xa8)(1 + xa7) ... (1 + xa1)A0(x) |
| | ≡ (1 + x)P8(x)(1 + x)P7(x) ... (1 + x)P1(x)A0(x) |
| | = (1 + x)8P8(x)P7(x) ... P1(x)A0(x). |
Now,
| (1 + x)8 | = 1 + 8x + 28x2 + 56x3 + 70x4 + 56x5 + 28x6 + 8x7 + x8 |
| | ≡ 1 + x8 (reducing the coefficients mod 2) |
| | ≡ 0, (reducing the polynomial mod 1 + x8) |
so A8(x) = 0. Therefore, all lights will always be off after eight rounds. Looking back at the
equation
A8(x) = (1 + xa8)A7(x),
we see that the polynomial A7(x) must then have the property that for any a8, multiplying
A7(x) by 1 + xa8 gives the zero polynomial. The only polynomials A7(x) that have this property are A7(x) = 0 and
A7(x) = 1 + x + x2 + ... + x7.
Thus, after seven turns, the lights are either all on or all off. If the lights are all on, Lisa has won at the end of the seventh round (or sooner, if they were all on sooner). If they are all off, Lisa gives Bart the switching pattern of change everything, and Lisa wins at the end of the eighth round (or sooner, if they were all off sooner). This generalizes to all n that are powers of two, so that Lisa can always win in at most n rounds.
Generating Functions
|Contact|
|Front page|
|Contents|
|Games|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
