Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The Lamplighter's Manor

  1. Nov 6, 2008 #1
    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. jcsd
  3. Nov 7, 2008 #2
    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
     
  4. Nov 7, 2008 #3
    Hi davee123,

    Correct! There is a shorter path though, reexamine your solution and you may find it.
     
    Last edited: Nov 7, 2008
  5. Nov 7, 2008 #4
    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
     
  6. Nov 7, 2008 #5
    In fact,

    It's the shortest path.

    :smile:
     
  7. Nov 7, 2008 #6
    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!
     
  8. Nov 7, 2008 #7
    the three-by-three version of this used to be on the Merlin:

    [​IMG]

    Except it would start with a random configuration of lights. Just random trivia.
     
  9. Nov 7, 2008 #8
    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
     
  10. Nov 7, 2008 #9
    There are more than 16 variants to your solution. Far more.

    :smile:


    Good luck with your approach.


    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.
     
  11. Nov 7, 2008 #10
     
  12. Nov 8, 2008 #11
    S, NW, NE, E, N, W, SE, SW also works.

    :smile:
     
  13. Nov 8, 2008 #12
    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
     
  14. Nov 8, 2008 #13
    Does it not work though? Try it. :smile:

    I reemphasize "the". All the solutions are really essentially the same.
     
  15. Nov 8, 2008 #14
    Maybe I've made this too difficult. Here's a helpful hint:

    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?
     
  16. Nov 14, 2008 #15
    No progress?

    No other takers?
     
  17. Nov 14, 2008 #16
    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
     
  18. Nov 17, 2008 #17
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?