The Lamplighter's Manor

1. Nov 6, 2008

Werg22

The Lamplighter's manor is 9 room house, which can be represented as 3x3 grid. Each room has a single lamp.

When a lamp is lit, the lamps in each of the adjacent rooms light up if they are unlit, and darken if they are lit. Likewise, when a lamp is extinguished, the lamps in each of the adjacent rooms darken if they are lit, and light up if they are unlit. This does not include the rooms in diagonal, only those directly to the North, South, West and East, where it applies.

We are allowed to light or darken any room, at any given time. Suppose the manor starts with all of its lights off, expect for the one in the very middle, in the second row and second column. What sequence(s) of action gets us to a fully lit manor? Here an action is to be understood as either lighting or darkening a room.

2. Nov 7, 2008

davee123

Not sure if it's the shortest path, but I got it in 10 steps:

M, NW, SE, NE, SW, M, N, W, S, E

DaveE

3. Nov 7, 2008

Werg22

Hi davee123,

Correct! There is a shorter path though, reexamine your solution and you may find it.

Last edited: Nov 7, 2008
4. Nov 7, 2008

davee123

Ahh, yes. I had just done that one by hand, sort of guessing. Just wrote a program to figure out the shortest path-- one of the shortest is:

S, SE, NW, W, E, SW, N, NE

What surprised me was that no matter the starting orientation, no other orientation is more than 9 moves away-- and there's always only ONE that's 9 moves away. In the case of starting with everything off except the middle, the furthest away is having everything off except the 4 corners.

DaveE

5. Nov 7, 2008

Werg22

In fact,

It's the shortest path.

6. Nov 7, 2008

Werg22

Although your solution is correct, I don't think you've figured out the trick.

The Lamplighter's mansion is made up of 36 rooms, representable by a 6x6 grid. The same rules apply. The lights in the NW and NE corners are lit, and all others are off. How do you get to a fully lit mansion?

Don't try this by hand!

7. Nov 7, 2008

physics girl phd

the three-by-three version of this used to be on the Merlin:

Except it would start with a random configuration of lights. Just random trivia.

8. Nov 7, 2008

davee123

Well, I said one of the shortest since technically, there are 16 variants with rotation and reflection on the path I gave. Admittedly, I didn't know if there were other paths to the solution that weren't variants on what I said, but I knew that there were at least 15 more I could've stated.

I guess not? I'm assuming there's effectively an algorithm for doing this that's applicable at any scale. My quickie program can fully map up to a 4x4 set, and a 5x5 takes a long time (an hour maybe?). As is it can't take a 6x6, but I could probably make a lot of efficiencies-- possibly enough to explore the whole 6x6 grid. I'll have to examine some solutions for the 4x4 and 5x5 grids and see what the "trick" might be.

DaveE

9. Nov 7, 2008

Werg22

There are more than 16 variants to your solution. Far more.

The trick I'm referring to though has more to do with the analysis at the outset rather than any particular algorithm. It's really neat and easy (not computationally easy though). What I said in spoilers is a hint.

10. Nov 7, 2008

davee123

11. Nov 8, 2008

Werg22

S, NW, NE, E, N, W, SE, SW also works.

12. Nov 8, 2008

davee123

I'm not sure I follow-- how is that a rotation or reflection of the method I presented? It looks like a totally different solution. And, if so, I'm also not sure I understand why you very expressly emphasized the word "the" to imply that the solution was unique?

DaveE

13. Nov 8, 2008

Werg22

Does it not work though? Try it.

I reemphasize "the". All the solutions are really essentially the same.

14. Nov 8, 2008

Werg22

Any rearrangement of the moves in your solution works. This why all solutions are essentially the same, they are all permutations of a same set of moves. There are in fact 8! possible solutions if you take order into account. What if you represent a lit lamp with a 1, and an unlit one with a 0? How can you represent the effect of an action with respect to the 0's and 1's, mathematically what is it equivalent to?

15. Nov 14, 2008

Werg22

No progress?

No other takers?

16. Nov 14, 2008

Caracrist

You have 9 lamps total. There is no reason to use one lamp more than once. The question is, which lamps to use, and which not. So there are some 9 variants in using 8 lamps, 9*8/2 = 36 variants of using 7 lamps, and so on. And of course, there is only one variant of using 9 lamps.
And the answer should be described as:
Using all lamps except the middle one

17. Nov 17, 2008

davee123

Sorry-- I haven't been back since my last post. Yeah, I'm not sure why I didn't think about it in those terms. I think the terminology used probably got me stuck-- you started off asking for a sequence, which isn't necessarily applicable, but I think it immediately triggered me thinking that order was important.

DaveE