Since I seem to be getting this question a lot lately: yes, I'm still alive! But I am writing a dissertation. (And waiting to hear back from places where I applied for jobs, but that is not an excuse because those applications are already out there.)
Here's a puzzle I heard a couple weeks ago. You have a 10-by-10 grid of lights. Some of them are on, some are off. You are allowed to make the following moves:
(a): you pick one of the lights which is the center of some 3-by-3 square (i. e. it is not on the edge of the grid) and switch all the lights in that 3-by-3 square (on becomes off, off becomes on).
(b): like in (a), but with a 5-by-5 square.
Is it possible to get from an arbitrary starting position to the all-off position?
A random walk through mathematics -- mostly through the random part.
Blog Archive
-
►
2011
(46)
- December (3)
- November (3)
- October (1)
- September (2)
- August (6)
- July (1)
- June (2)
- May (3)
- April (5)
- March (8)
- February (10)
- January (2)
-
►
2009
(122)
- December (3)
- October (2)
- September (7)
- August (5)
- July (9)
- June (7)
- May (6)
- April (7)
- March (18)
- February (27)
- January (31)
Contributors
Other blogs
- An American Physics Student in England
- Anarchaia
- Arcadian Functor
- Ars Mathematica
- Brown Sharpie
- Casting Out Nines
- Confessions of a Mathematician
- Data Mining: Text Mining, Visualization and Social Media
- Freakonomics
- Game Theorist
- Good Math, Bad Math
- Gooseania
- Gowers's Weblog
- http://mathnotations.blogspot.com
- Information Aesthetics
- Information Processing
- Junk Charts
- Language Log
- Learning Curves
- Machine Learning (Theory)
- Math Notations
- MathTrek
- Science After Sunclipse
- Scientific Curiosity
- SciTalks
- Secret Blogging Seminar
- Sentient Developments
- Statistical Modeling, Causal Inference, and Social Science
- Statistics Consulting Blog
- Terence Tao's blog
- The Everything Seminar
- The Narrow Road
- The Unapologetic Mathematician
- The Universe of Discourse
- Vlorbik on Math Ed
- WebDiarios de Motocicleta
- Wingie
- Wolfram Blog
- WSJ.com: The Numbers Guy
22 comments:
(a) For a given starting arrangement which can be turned all off, there is a sequence of switches abcd...z which turns all lights off.
The action of the switches is commutative. If any switch is used two or more times in the sequence (i.e, the sequence is of the form ...a...a..., then there is an equivalent sequence of the form aa.... The action of the switches is self-inverse, so any sequence of the form aab... has an equivalent sequence of the firm b....
Because of this, any sequence which turns an initial state to all-off has reduced equivalent form in which each switch is used at most once. As such, there are at most 2^64 equivalence classes of sequences. While I believe this reduction is unique up to ordering, I do not need to prove it.
In the case of a 10x10 array of switches, there are 2^100 initial positions, which is larger than the number of possible reduced sequences. Therefor not all initial positions can be turned off.
There are 64 3x3-square switches and 36 5x5-square switches, so you actually do have 100 switches, for a total of 2^100 possibilities.
I suppose that that means that the answer to the question is yes if and only if every combination of switches produces a unique result.
Blaise: you forgot the 5-by-5 squares.
dfan: yes.
OK, and that's equivalent to "there is no combination of switches that results in a blank grid."
Which is equivalent to "there is no combination of purely 3x3 switches that produces the same result as a combination of purely 5x5 switches."
Which I am pretty sure is true (there is no such set of two combinations), but I don't have a proof yet.
Ah, OK, I misread the problem. I had thought (a) and (b) were two different puzzles (both "no"), not two different moves in the same puzzle.
I think the answer is no, because there is a combination of 3x3 blocks you can switch which is the same as switching *every* 5x5 block.
Numbering the lights (i,j) in {1,...,10}^2, consider the 3x3 blocks centered at (i,j) in {2,3,4,7,8,9}.
So the question is whether the set consisting of the 64+36 = 100 matrices is a basis for the Z/2Z-vector space of 10 by 10 matrices. Row-reduction says no, they span a space of dimension 84. (Although the 64 coming from 3x3 squares are independent and the 36 coming from 5x5 squares are also independent).
I should give this problem to my linear algebra students.
Omar, I hadn't actually done the row reduction, so I'm interested to hear the result. I thought that it could be solved that way, but didn't want to actually carry it out (or, more accurately, tell my computer to carry it out).
Omar is right about linear algebra. The problem is essentially a linear system to be solved in $\mathbb{Z}_2^{100}$. I had a Maple algorithm that would solve the "Lights-Out" behavior for me (selected square and all squares distance 1 from it) at one point...
I agree that linear algebra is the way to go for this kind of problem. I did an REU project on this a few years ago. The only thing you have to watch out for is that you can't use the edges. So that might (and most likely will I believe) change a few things.
Nice find, George!
In case anyone is interested, here's the Mathematica (7) code I used. For this specific puzzle the call would be lightPuzzle[10,{3,5}]. (As usual for Mathematica it's short and a little cryptic.)
lightPuzzle[n_, sqSizes_] :=
MatrixRank[
Flatten[Table[
Flatten[Array[
Boole[i <= #1 < i + k && j <= #2 < j + k] &, {n, n}]],
{k,sqSizes}, {i, n - k + 1}, {j, n - k + 1}], 2],
Modulus -> 2]
The point of this problem is to not use a computer, so either you actually do the row reduction by hand or come up with something more clever. (Choose a different problem if you're keen on using computers.)
Not sure whether George did it by hand, but the idea is right: show that the 3x3 and 5x5 matrices are not linearly independent by exhibiting a linear combination of them that equals zero.
The smallest such combination is probably the following: consider a blank 7x7 area and switch its four "cornermost" 3x3 squares as well as its four "cornermost" 5x5 squares. This will look like a cross in between and then blank again. No computer needed to find this, just a pen and the back of an envelope.
It appears that the 16 possible 7x7 squares are exactly the missing dimensions from Omar's remark. Incidentally, 5^2-3^2 = 16 = 4^2, but I don't know what to make of this.
Heinrich,
I'm not seeing how your 7-by-7 configuration equals zero. To equal zero each cell has to be flipped an equal number of times, which is not true in your example. (It's possible that I'm misunderstanding you, though.)
However, an 8-by-8 configuration very much like yours works. Given the eight-by-eight square {1,2,...,8} x {1,2,..., 8}, with (1,1) in the upper left corner, flip the 3-by-3 squares with their upper left corners at (1, 1), (6, 1), (1, 6), and (6, 6), and the 5-by-5 squares with their upper left corners at (1, 1), (4, 1), (1, 4), and (4, 4).
I'm not sure if this is the smallest configuration that equals zero. Since I couldn't figure out the version of the question that was originally posed to me, I changed the numbers, replacing the triple (10, 3, 5) by (5, 2, 3); in that case there's a configuration that ``looks like'' the one above, but with 2-by-2 and 3-by-3 squares in a 5-by-5 square, not 3-by-3 and 5-by-5 in an 8-by-8.
I agree that the problem is better done by trying to find the relation; this is why I didn't use a computer to do it. But I also think that the computer is useful in showing that there should be a total of sixteen independent relations. In particular, I know I haven't found them all, since there are only nine 8-by-8 squares.
Oops, sorry, I indeed meant 8x8. Mea culpa! :-O
That would mean 16-9=7 kernel relations remaining. That's a weird number! For symmetry reasons, I'd expected it to be divisible by 4 (rotations) or 8 (rotations and reflections along the diagonals). Some of them must be highly symmetric and involve the whole board.
The way I picked my example is just to try cases with lots of symmetry, and that can be done in your head.
If you switch blocks with centers in a regular grid arrangement of the form {i_1,...,i_n}^2 then the number of times the light at point (i,j) is switched is equal to the number of i_k with |i_k-i|<=1 (for the 3x3 block, or <=2 for the 5x5 block) multiplied by by the number of i_k with |i_k-j|<=1. Write x[i] = #{i_k:|i_k-i|<=1} (resp. <=2). Then, the number of times light (i,j) is switched is x[i]x[j].
If we switch every 5x5 block, this gives x=(1,2,3,4,5,5,4,3,2,1) or, mod 2, (1,0,1,0,1,1,0,1,0,1).
Similarly, switching every 3x3 block gives x=(1,2,3,3,3,3,3,3,2,1)=(1,0,1,1,1,1,1,1,0,1) mod 2. The 6 consecutive 3s means that this isn't going to be the same as the 5x5 case. However, if you don't choose any 3x3 blocks crossing the half-way lines, you get x=(1,2,3,2,1,1,2,3,2,1)=(1,0,1,0,1,1,0,1,0,1) mod 2, giving my example.
The 8x8 cross idea also fits into the same idea as I was using. with the 3x3 blocks centered at {2,7}^2 you have x=(1,1,1,0,0,1,1,1,0,0). The 5x5 blocks centered at {3,6}^2 gives x=(1,1,1,2,2,1,1,1,0,0), which is the same mod 2.
Shifting these solutions in the x and y directions gives 3^2=9 solutions. Combining this method in the x direction with mine in the y direction gives 3x1=3 solutions. Switching x & y dimensions gives another 1x3 solutions. Then, using my method gives another 1 solution. So, that gives a total of 9+3+3+1=(3+1)^2=16 solutions.
That's probably all of them, but I haven't checked linear independence.
Damn, those aren't linearly independent. Summing all the 8x8 cross methods gives mine.
However, there is one more. Consider centering the 5x5 blocks at {3,4,8}^2, giving x=(1,2,2,2,2,2,1,1,1,1). Similarly, centering the 3x3 blocks at {2,3,5,6,9}^2 gives the same x. This cannot be a linear combination of the 8x8 cross methods, because they all involve an even number of x-positions for the 5x5 blocks, whereas this has an odd number. Combining this solution alternately in the x and y dimensions with the 8x8 cross idea gives the full (3+1)^2 linearly independent solutions.
I admit - didn't do that in my head. Still, just writing down a few dots on a piece of paper is enough to find the solutions.
Sorry about keep coming back to this one with yet more posts, but I just had more thoughts about this (hope my html math works...).
We were given a vector space V =(F_2)^10, and the 2d array of lights can be thought of as the tensor product V⊗V. Then, there are subspaces W1 (vectors with 3 consecutive 1s) and W2 (vectors with 5 consecutive 1s), with dim(W1)^2=dim(W2)^2=8^2+6^2=10^2=dim(V)^2. W1⊗W1 is the space generated by the 3x3 blocks and W2⊗W2 is the space generated by the 5x5 blocks. The question is if W1⊗W1 + W2⊗W2 = V⊗V.
As the dimensions add up correctly, it seemed like a possibility at first, but that was an incorrect guess. By rank nullity, the difference in dimensions of the two sides is dim( (W1⊗W1)∩(W2⊗W2) ). ie, intersection of spaces formed by 3x3 and 5x5 blocks.
The solutions we found in (W1⊗W1)∩(W2⊗W2) were all in the subspace (W1∩W2)⊗(W1∩W2). As W1+W2=V (easy to verify), dim(W1∩W2)=dim(W1)+dim(W2)-dim(V)=8+6-10=4. So, that gave a 4^2=16 dimensional space of solutions. The only remaining question if that is all. Is (W1∩W2)&otimes(W1∩W2)=(W1⊗W1)∩(W2⊗W2).
The answer is yes. Write W1 = W1∩W2+V1, W2 = W1∩W2+V2 (direct sums). Then, V=W1∩W2+V1+V2. As a tensor product of direct sums expands to the direct sum of the tensor products of the subspaces, you can take the tensor product of these and verify that the only terms appearing in both W1⊗W1 and W2⊗W2 is (W1∩W2)⊗(W1∩W2).
Heinrich wrote: "The point of this problem is to not use a computer, so either you actually do the row reduction by hand or come up with something more clever. (Choose a different problem if you're keen on using computers.)"
In my comments I was insinuating that the problem was not terribly interesting (to me) as it was about row-reducing one specific matrix. I apologize first for missing the point and second for disobedience: I will neither row-reduce by hand nor spend time coming up with a "clever" way of showing that a specific 100x100 matrix defined in an arbitrary way is not of full rank.
I prefer to think about things that I can't program a computer in 3 minutes to do, rather than spend an hour figuring out how to do 3-minute-computer-things by hand --but that's a matter of personal preference and it is perfectly reasonable to disagree. Doron Zeilberger's opinions are too radical for me but I do agree with him in part.
Other commenters already established that switch pressing is commutative and each switch press is the inverse to itself so I'll build on that. Since switch presses are self-inverses each switch press will appear in the solution sequence exactly once and the order that they appear in doesn't matter. I'm going to assign coordinates to each light/switch (I'm thinking the old Lights Out game here, where each light is a switch) like a matrix so the top-left one is (1,1) and the bottom right is (100,100). First number is row, second col.
For the 3x3 case:
Claim: It is impossible to get from the state where only (1,1) is lit to a completely unlit state.
1 - Obviously you need to switch (2,2) since that is the only switch that will light (1,1).
2 - In order for (n, 1) for 1 < n < 100 to be unlit at the end exactly two switches out of (n-1, 2), (n, 2) and (n+1,2) must be switched. Since (2,2) has already been switched you'll need (3,2) to unlight (2,1). Now (2,1) and (3,1) have an even number of switches flipped to their right so they're okay. But (4,1) needs (5,2) flipped, then (5,1) needs (6,2) flipped, (7,1) needs etc. etc. etc. in the end to make sure (2,1) to (99,1) are unlit all switches in the form (k,2) where k is not 1 mod 3 must be flipped. So (99,2) must flipped however you decide to proceed elsewhere.
3 - Since (99,2) is the only switch controlling (100,1) the bottom left corner light is lit no matter what else happens. So by turning (1,1) off you have to light up (100,1). Hence you'll never get to an unlit state.
This solution takes a while to describe but I decided to stick it here because it doesn't involve linear algebra or computers. I think it probably extends to the 5x5 case by analyzing (n,3) for 2<n<98 (an even number of those switches must be flipped for every 5 consecutive one and the first two must be flipped) but I really don't have the time to figure that out.
Post a Comment