A looped building with Prime rooms lighted

Question

Imagine a building with 200 consecutive connected rooms as shown below. The shape is not important. It could be a circular loop building.

You do not know the room numbers but you are told that they are in order. You also know that room 200 connects to room 1, making it a fully looped building. You do not know the building shape.

Only the rooms with Prime Numbers are lighted. You have no control over the lights.

You cannot see any other rooms except the one you are in. You can only go to the neighboring rooms.

You are placed in a randomly selected room. Could be any room. You can walk in either direction. You are told the direction of ascending order. If you visit the same room twice it will be counted as 2 rooms visited. You are given a paper and pencil to keep record of lighted/unlighted rooms.

You need to devise a guaranteed strategy for telling the number of the room you started from. What is the SMALLEST POSSIBLE number of room visits such a strategy must have? Why?

Note the spaces between rows of rooms are not significant. I just wanted to complete the loop.

Answer 1

_{(The answer survived a triple check of the logic, mostly by pure luck. The readability of my explanation didn't survive; so here's is a rewrite.)}

The house has two repeating runs of 27 consecutive rooms: the first one starts at room 20 and repeats at room 50, and the other one starts at room 128 and repeats at room 170. However, it's still possible to determine the starting room with only

26 room visits.

Here's how:

We need to start in the ascending direction. If we started in a dark room, and the next rooms are either "dark, light" or "dark, dark, light", we'll turn back. Otherwise we'll just keep going until we've collected a sequence that uniquely defines our starting room.

This method works, because it makes sure we won't hit the worst case scenarios (or even the second worst case scenarios), because all the mutually indistinguishable 27-room repeat sequences happen to begin with "dark-dark-dark-lit", and the method detects and avoids them before it's too late.

On the other hand, even though it "wastes" a visit (or three), we are ok with turning back at the first lit room, if it occurs that early:

All backwards sequences of length 23 that start with "lit-dark-dark-dark" are unique. Here's the program (Try it online!) that I used to verify it.

So if we hit the special case, we visit at most 4 rooms (incl. starting and turning room) going forward, and then at most 22 more going backward.

OTOH, if we don't hit the special case, we know we didn't start at the worst possible spot (20, 50, 128 or 170), and neither did we start at the second worst possible spot (21, 51, 129 or 171), so we are guaranteed to find the solution in 26 visits in that case too.

Note that I didn't use a program to prove optimality (or to find a better answer): this puzzle comes with the no-computers tag, so anything more than proofreading by computer would have felt like cheating.

About the possibility of future improvement: the 27-room runs all end in lit-dark-lit-dark-dark-dark, and any forward sequence starting "lit-dark-lit" becomes uniquely defined in 19 rooms or less. However, there's a 25-room duplicate run (at 42-66 and 162-186) that comes into play if we try to go lower than 26 rooms. Since that run cannot be usefully detected until it's just barely too late to turn away (it seems so, because it ends in lit-dark-lit-5darks, and that just happens to be one of those lit-dark-lits that require all the 19 rooms to solve), it seems that all these attempts must top out at 26 rooms at the minimum, too. Unless I've missed something, of course.

Answer 2

First of all,

the 27-room sequences starting at 128 and 170 have the same lighting pattern, so we must visit at least 27 rooms.

But

28 rooms is enough. If we extend those sequences one step further at either end, they no longer match; both sequences contain a run of exactly 9 primes (with composites at either side) and we can readily check that there are no other such runs.

However,

if we don't know which direction is which then there is a further complication: these two blocks form part of a long palindromic sequence of lights. The runs of composites go ... 3 5 1 9 1 5 5 3 5 5 1 9 1 3 1, which means that we have the palindromic sequence CCCPCPCCCCCCCCCPCPCCCCCPCCCCCPCCCPCCCCCPCCCCCPCPCCCCCCCCCPCPCCC (which is preceded by C and followed by P so doesn't extend any further), of length 63. So if we don't know which direction is which then we need to visit 64 rooms to know where we are.

Answer 3

For a General Case solution (i.e. an guaranteed solve, starting from any room), I'm going to go with an Upper Bound of

28 rooms

This is because

The longest repeated sequence possible is 27 rooms, which appears in 2 different forms:

~ Rooms 20-46 match Rooms 50-76
   Lit/Unlit: (UUULUUUUULULUUUUULUUULULUUU)

~ Room 128-154 match Rooms 170-196
   Lit/Unlit: (UUULUUUUULULUUUUUUUUULULUUU)

So, you add 1 more room to make the sequence unique

As a bonus, here is a practical implementation on how to apply this:

Tear your paper in two, for long/narrow strips. On one, put a column of 227 boxes of equal height, numbered 1-200 and then continuing 1-27. Mark these as either Solid Fill or with a diagonal-strike depending on whether or not they are Prime.
On the other, make 28 boxes the same size as your other sheet. Fill these out in the same way as you walk through rooms in ascending order, depending on whether or not they are Lit.

Once you have filled all 28 boxes out, place the 2 pieces of paper next to each other, and slide them up/down until the pattern matches. The top box that matches will be room 1

Answer 4

Edit : my first answer no longer works because i assumed re-visiting a room that we already explored doesn't count. I deleted that part and went back to solving it. As @DEEM stated, revisiting counts. With these changes, i found :

Going forwards (ascending) or backwards (descending) gives the same result : 28.

The different starting positions i found for this number are :

Forwards : 20, 50, 128, 170
Backwards : 46, 76, 154, 196
turns out these positions are the positions of the 9-gaps + two other positions (gaps : 35153 and 55153)

It turns out the answer is way higher than what I excepted. If i missed some starting positions, please add them. Now i will try to solve it without knowing the direction (i'm very close!), and eventually create some kind of program that will verify my answer.

Answer 5

@Bass just beat me, but I also got a minimum of

26 rooms

But the strategy I checked (manually) was a little bit different:

Start in ascending order. If the starting room was dark and you reach a lit room within the first 3 steps, turn around and do the rest in descending order.

Answer 6

2. Starting from room 2 and proceeding to room 3, you pass through a unique sequence: lit, lit. (This is because you're told which direction is the ascending order of integers.)