That sort of reminds me of my solution to the “nine dots, four lines” puzzle, which is usually presented in such a way that it can actually be solved in three lines.
The solution to the equivalent 7 x 7 puzzle is symmetric any way you could like (see below). What’s the difference between that and the 5 x 5 case?
A1, B1, D1, F1, G1
A2, B2, C2, E2, F2, G2
B3, C3, E3, F3
A4, D4, G4
B5, C5, E5, F5
A6, B6, C6, E6, F6, G6
A7, B7, D7, F7, G7
(I’m using the solver here. The largest puzzle they can solve is 7 x 7, so if you want a larger puzzle solved, it’ll take a little while.)
In the 7 by 7 case, the buttons are all linearly independent, so one must have a solution for every configuration and also a symmetric solution for every symmetric configuration. The number of dimensions of possible configurations equals the number of dimensions of possible actions.
In the 5 by 5 case, the buttons are not all linearly independent, so not every configuration has a solution; indeed, even symmetric combinations of buttons can demonstrate linear dependence (e.g., clicking every button not on one of the large diagonals is the same as doing nothing), so not every symmetric configuration has a symmetric solution. The number of dimensions of possible configurations exceeds the number of dimensions of possible actions.
Just to be more explicit as to why this entails symmetric solutions to symmetric configurations: This means each configuration has a unique solution, and thus the unique solution to a configuration must in itself contain all the same symmetries as the configuration. (That is, the map sending button combinations to their cumulative actions always sends symmetric button combinations to symmetric actions; in the 7 by 7 case, this map is a bijection, so we have conversely that every symmetric action comes from a symmetric button combination)
When I learned it, the lesson was that it was unsolvable. That was shown only after we had spent time trying to solve it. One of the rules was that a line couldn’t go under a house or a utility. Obviously that’s one solution if the puzzle is presented without that limitation, but I think the whole point of the exercise is to show that some things are unsolvable and can be proven so.
Well, I solved it but darned if I used a system.
One point which hasn’t been remarked upon, incidentally, is that ultrafilter’s solution does have one symmetry (reflection across the diagonal from E1 to A5).
With regard to the houses/utility puzzle, this is a good lesson in how different models give different results. To recap:
[ol]
[li]If you model the houses and utilities as points in a plane, then there’s no solution as described above.[/li][li]If you model the houses and utilities as sets of nonzero area in the plane, there is a solution, but you have to run one line through a house or utility that it’s not serving to get it.[/li][li]If, on the other hand, your model incorporates a third dimension, the problem is trivial: simply run one utility cable under another.[/li][/ol]
Take the piece of paper, and roll it into a tube. Now draw your final line.
I think the point of this exercise was to get a third grade class to sit down and be quiet which is the goal of any substitute teacher.
The thing that kept me at it was that some of my classmates claimed to have solved it, but they would never tell me how. So another point of this exercise was to prove that some of my classmates were lying sacks of shit, which I had always suspected.
This doesn’t help… if you could draw it on the sides of a cylinder, you could draw it on the surface of the Earth, which, as above noted, is impossible.
Put another way, all folding the paper into a tube lets you do for the final line is have it exit out one side of the paper and re-enter on the opposite side. But you can already accomplish the same thing without having to fold the paper: once you get to the one side of the paper, just run around the margins till you make it to the other side.
Or, looking at it another way: Stretch the bottom circle of your cylinder out, and maybe shrink the top circle, until it’s a flat disk with a hole in the middle. If you can solve it on a flat piece of paper with a hole, then surely you can solve it on one without a hole.
Now, if you also attach the ends of your cylinder to make a torus, that might help.
Oh, and I figured out why my intuition was that the lights-on puzzle should be symmetrical. The existence of an asymmetrical solution implies the existence of many identities (sets of switches you can flip to leave the state the same), and I wasn’t expecting any nontrivial identities. Take the original solution, rotate it in some way in which it doesn’t have a symmetry, and XOR the two together, and you’ll get an identity.
Right; the existence of nontrivial identities is what I meant by saying the buttons’ actions weren’t linearly independent (as vectors in the 5 by 5 dimensional space over the field of integers modulo 2). As you note, if you have linear independence, the unique solution to any particular starting configuration must itself have all the same symmetries as that configuration.
The solution is astonishingly simple: click randomly for about 30 seconds without any logic or pattern: voilà!
Ah, I understand what you’re saying now. Yeah, we’re on the same page.
Ooh, yeah, that’s a much nicer description.
Indeed; here’s an illustration from MathWorld of how it can be done on a torus.
