Room count of the cross-wired tower.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Room count of the cross-wired tower.

Postby emlightened » Thu Oct 29, 2015 9:45 pm UTC

Extension to this puzzle.

(Bolded texts are changes to the orginal's rules.)


Imagine a cylindrical tower with an unknown number of indistinguishable, which form a ring around a central (inaccessible) circular area. Each room has two doors, both leading to the next room in either direction. Furthermore, each room has a light switch button which can turn on/off the light in the same room. However, it also turns on/off the light in exactly one other room. The button in that room also turns on/off the light in the other of the two rooms. Note that this may either switch both lights on/off, or change which light is on.

One day you find yourself in one of the rooms, with knowledge of the above paragraph. Your goal is to find out how many rooms are there. You can go from room to room and turn on/off lights. You have no other means to interact with the world. You cannot rely on observing anything other than the current state of the light in the room you are currently in. Oh, and of course you can not assume anything about the initial condition of the lights in any room.


I have come up with a solution, but I'm interested in others.

Extension: The number of rooms on the same circuit is unknown. (And you may assume that the gcd of the set of number of rooms in any given circuit is 1, for uniqueness. This prevents the case of a tower with MN rooms, and each switch also changes the light N rooms in front of it, 2N rooms, 3N rooms ahead, etc.)

"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Room count of the cross-wired tower.

Postby Cauchy » Fri Oct 30, 2015 8:32 am UTC

Spoiler:
Pick a starting room, and choose one direction as "forward". We say that two rooms are linked if their light switches toggle the other room's state.

For each positive integer N, in sequence:

Note the state of the starting room. Walk forward N rooms, flip the light switch, and walk backward N rooms to the starting room.

If the state is the same, then the tower does not have N rooms, and the starting room is not linked to the room N rooms forward. We note that the room N rooms forward is not linked to the starting room, and we check the next integer.

If the state is different, then either the tower has N rooms, or the starting room and the room N rooms forward are linked. In the case that the tower has N rooms, then we've now visited all of them, and the starting room must be linked to one of them. We've already compiled a list of whether the starting room is linked to each room before this one (with one possible exception, which will be addressed at the end). If the starting room is linked to one of these other rooms, then it's not linked to the one N rooms forward, and hence we've found the width of the tower. Otherwise, it's not linked to any of the rooms, so the tower cannot be only N rooms around. Then, the room N rooms forward is not the same as the starting room, and so it must be linked to the starting room. We note that the room N rooms forward is linked to the starting room, and we check the next integer.

tl;dr: The first time we find that toggling a light somewhere far away changes the starting room's state, it'll be a red herring caused by linked rooms. We resolve this by noting that the starting room has to be linked to something, so if it's not anything else in the tower up to that point it must be the room we just found. The second time we find what we're looking for, it'll be because we've actually circumnavigated the tower.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
Elvish Pillager
Posts: 1009
Joined: Mon Aug 04, 2008 9:58 pm UTC
Location: Everywhere you think, nowhere you can possibly imagine.
Contact:

Re: Room count of the cross-wired tower.

Postby Elvish Pillager » Sat Oct 31, 2015 9:48 pm UTC

Solution to the first puzzle:
Spoiler:
Like the original puzzle, this one has a solution that is O(n).

1. Set i=1
2. Walk and memorize the current states of rooms until you have memorized 2^i rooms in a row.
3. Toggle the switch of the current room.
4. Walk back along the rooms you memorized. The second time you encounter a light different than the one you remember, you've found the answer. If you only encounter 0 or 1 changed lights, increment i and repeat from 2.

Just like my first answer to the original puzzle, this takes no more than 5n moves, which I believe is nearly optimal (the best being around 4.83n).

And about the extension:
Spoiler:
This is impossible. Even if you visit, say, 1 billion rooms, you can never be sure whether you're in a loop of 6 rooms or a loop of 1,000,000,001 rooms where only the first billion are tricky and the last one only toggles itself.

You'll need to come up with a more strict rule to prevent "tricky" circuits.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests