Labyrinth of Teleporters

Question

You find yourself in an empty room, with a few distinctly numbered elevated platforms on the floor; your only possession is a pebble that can easily be picked up and placed down. You step on one of these platforms only to be teleported to a different, but similar room with another set of distinctly numbered platforms, and after some more investigation you deduce that there's a whole network of similar and possibly indistinguishable rooms all accessible through these consistent one-way teleporters. You hope there's an exit somewhere...

Assuming that this network is finite, and that every room is accessible from every other room (not neccesarily directly), given enough time, should it be possible for you to determine whether an exit exists with complete certainty? If so, how, and if not, why not?

Discussion

This is an original puzzle. While I did post this with the intention of seeing others' solutions (I know there are more than one), I would also be interested to hear about any suggestions for ways I could improve the wording of this puzzle, or potentially alter it to create a more challenging or interesting variation.

Answer 1

Without the pebble...

... it is impossible to conclude there is no exit. Any set of observations is consistent with every room visited having been distinct, so there may be rooms that have not been visited -- the labyrinth is finite, but may be arbitrarily large.

But...

... there is an exploration algorithm that will eventually visit any particular room (equivalently, every room). So, if there is an exit, this algorithm will be guaranteed to find it even without using the pebble.

Practically speaking, moving randomly will visit any particular room (such as the room with the exit) with probability one. Given any fixed finite maze, the probability of random movement reaching the exit in some large fixed number of steps (depending on the size of the maze) for any starting point is bounded below. Thus, in each block of moves of our chosen step count, we have at least that probability of reaching our destination. As we repeat, the probability of repeated failure then goes to zero.

We can also do this deterministically by trying every finite route. To show this works, we must prove that for any possible labyrinth, there is a finite route that will guarantee to find our chosen destination. It must do this no matter what room in starts in, as we can't really be sure what room we'll be in when we start any route. But having shown such a route exists for each labyrinth, by trying every finite route, we will eventually stumble on the route that solves the labyrinth we are in (for our chosen destination).

So, for a chosen particular labyrinth, start our route with a sequence that goes from room 1 to the destination. So, if we started in room 1, this route will work. But, if we were in room 2 to start, we are maybe in the wrong room. So, let us extend our route with a sequence that goes from this wrong room to the destination. Thus, if we started in room 2, we will first go the the wrong room, and then to the destination. (Starting in room 1 continues to work, as we didn't change the initial segment of our route.) But, if we were in room 3 to start, maybe we are in the wrong room. But, we can correct this issue just as we did for room 2 by extending the route again, and so on for each possible starting room. This is a route that is guaranteed to travel through the destination room no matter where it started.

(Regarding how to formalize "try every route"... this relies on the fact that finite sequences of natural numbers are countable and we can choose some enumeration of them. The particular choice of enumeration doesn't really matter. This is a standard result. But, basically, for each $N$ there are only a finite number of sequences where the maximum element plus the length of the sequence is less than or equal to $N$; so we can e.g. sort sequences according to this bound (and e.g. in lexicographic order in case of a tie). We also need to map finite sequences of natural numbers to routes, but it doesn't really matter how we do this. For example, if a natural number doesn't correspond with any teleporter in the room we are in, we could choose to stay in place for that step.)

Using the pebble...

If we place the pebble, we can guarantee eventually finding it again using the above-mentioned algorithm. (Without such an algorithm, placing the pebble might be useless, as it could be as hard to find the pebble again as to find the exit.)

So, we can place the pebble in the starting room, and then use the algorithm to find a route that returns us to the starting room. Remember the sequence of moves that we used. Then, move the pebble to the next room in this loop, and repeat the loop. Do this for each room in the loop. This tells which rooms our loop visits multiple times. We now have a partial map including all the teleporters involved in this loop. Return the pebble to the starting room. If there is some teleporter in a any room that we haven't used yet, go to the room that contains it and then take it. Then use the algorithm to find the starting pebble. Append this new loop to the previous loop to form a new large loop. Repeat the process of moving the pebble to find duplicate rooms in the large loop. Then we will repeat this process of exploring new teleporters until our map includes the entire maze (which must eventually happen because the maze is finite), and we know for sure whether there is an exit.

Note that moving the pebble is required. Without moving the pebble, it is consistent with our observations that every room is distinct unless we reached it in the exact same way from the room with the pebble. This is fine, and we might still be able to explore every route from the pebble room, but if (and only if) there is a loop that doesn't involve the pebble room, then there are arbitrarily long loops from the pebble room back to the pebble room with no way of proving that any rooms are being visited multiple times in such routes.

Answer 2

The answer is:

You can prove that there is no exit even if all rooms are identical.

And here is why.

You can explore the labyrinth and identify all places.

You start by dropping the pebble and start taking teleporters randomly. You might find an exit, if so, good for you. If there is no exit you will eventually return back to the room with the pebble.

You need to teleport randomly or you might end up in an infinite loop. This means there is no upper limit to the time you will need to explore the labyrinth.

Make sure to write down every single choice of teleporter. Oops you have no paper. Well you will need a good memory!

You know that if you follow the same path by making the same choices of teleporter you will revisit the same rooms in the same order. So you can identify each room mentally by assigning an arbitrary ID to it, be it the order of discovery or the sequence of jumps that takes you from the original room to the said room.

But of course, it could be some rooms have been visited twice.

To identify the rooms uniquely, you can retrace the original path repeatedly, moving the pebble one room forward each time. You don't need to leave the pebble in the original room to know where you are as long as you follow the known path. Whenever you encounter the pebble unexpectedly, you can identify the current room as the same as the one where you left the pebble. When you have marked all rooms on the known path you have identified all rooms uniquely.

This gives you a partial map of the maze. Each room you have visited is identified mentally. As long as you follow teleporters you have used before in a room, you know which room you end. So you can navigate the partial map without getting lost and without marking a room with a pebble.

Then, find any room with a teleporter you haven't tried before. Let's call this room R. Drop the pebble in room R and restart a random walk starting with that untried teleporter. When you eventually reach the pebble again, you know you are back to room R. You can either follow the new loop again, or go anywhere else in the known part of the labyrinth, as long as you use known teleporters.

So now, you redo the identification thing by retracing the new loop, dropping the pebble in each room in turn. But this time, each time you reach room R, you must also explore the known part of the labyrinth. This way you identify which rooms in the new loop are already known and which rooms are new.

This extends your knowledge of the maze, you know more rooms and the destination of more teleporters.

As long as there is any teleporter in any room that you haven't tried, repeat this exploring process.

Eventually you will come to the point where you know every room and have tried every teleporter.

It is time to shout loud and clear "OK, I KNOW THERE IS NO EXIT! SO NOW WHAT?".

Answer 3

Strategy that guarantees your exit in finite time (no probabilistic mumbo-jumbo here :P). Drop stone in the first room, obviously.

Suppose you have N rooms with M doors each. M is freely selectable from 2 onwards. If there are some rooms that have fewer than M doors simply pretend there are extra imaginary doors which are all leading back to this same room. If there are some rooms that have more than M doors, pretend they are actually two (or 3, 4, etc) rooms, with M-th door leading towards the "next room" (and increase N accordingly).

.

You don't know N, but you do know that you have NM total doors to travel. How are you going to travel them all? You need a certain pattern of door-picking that guarantees that you have tried them all. One good way is using all possible ordering of NM numbers. With N*M=3 you get 1231321312 (one possibility, there might be a shorter way). This sequence is finite though it does get long. As you don't know N and don't fancy wasting too much time, you can simply iterate: try 1,2 ... M first, then continue with above etc ... until you get back to the original room with the stone or find the exit.

.

So, keep trying doors in the sequence until reaching the original room again. Once we do, we have an insanely complicated list of portals we used. The next step? Move the stone in the next room and simply repeat the list (not trying the new sequences again). All repeated comings to the same room are marked as being just different doors in the room. Keep doing this until all the rooms and doors of the first sequence are mapped. If there are still doors we have not tried, pick any of them, putting the stone there, and repeat the procedure. Keep doing this until you have mapped everything or managed to get out.

Filling up the holes:

You have numbers on teleporter bases. Sort by number so you get them in order 0->X. Also, when you have sequence, you need to perform (modulo M, +1) to get back to the 1->M range of room numbering.

Not shown - proof that the presented sequence actually is guaranteed to work. But considering it is exhaustive, I don't think it can break.

Answer 4

A deterministic algorithm for exploration.

Other answerers have already created solutions for what to do if you have an algorithm that will return you back to the start (and "move randomly" theoretically does indeed do that with probability 1) - but what if you're not capable of producing random numbers? A computerized PRNG has a finite length after which it will repeat values, so a maze with a pathologically chosen size could be designed to trap an explorer dependent on a particular PRNG in an infinite loop.

If you have perfect memory, you can use the following algorithm instead:

Consider each room that you have visited so far as an ordered pair of numbers (n,m) where n is the number of teleporters in the room and m is the number of the teleporter which you took. Keep track of the entire sequence of rooms that you have visited. When you arrive at a room, choose a door which creates the shortest new sequence that is not a repeat of any sub-sequence the previous traversal.

Since we're incapable of producing random numbers, if there are multiple possible doors which would all produce minimal new sub-sequences, choose the one with the lowest number.

A worked example

Let's assume (as a worst-case of this algorithm), that you are in a maze where every room has the same number of doors. Let's say 3.

• In the first room, you choose door #1, because the sequence is empty. The traversal is now [(3,1)]
• In the second room, (3,1) would be a repeat but (3,2) has never been seen before, so you choose door #2. The traversal is now [(3,1), (3,2)]
• In the third room, you choose door #3. The traversal is now [(3,1), (3,2), (3,3)]
• In the fourth room, all of (3,m) have been seen, but the subsequence [... (3,3), (3,m) ...] has never been seen before for any m, so you choose door #1 since it has the lowest number. The traversal is now [(3,1), (3,2), (3,3), (3,1)]
• In the fifth room, all of (3,m) have been seen before, and so has [... (3,1), (3,2) ...], so you choose door #1 again to form [(3,1), (3,2), (3,3), (3,1), (3,1)].
• In the sixth room, you choose door #2, because [... (3,1), (3,1) ...] has already been seen, but [... (3,1), (3,2) ...] has not.

Correctness... maybe?

Any exploration must either explore the whole maze or get caught in a cycle. Thus, it is sufficient to prove that this algorithm will never get caught in a cycle.

I believe it should be possible to prove that if this algorithm traverses a cycle of length k, it guarantees that at some point in the future, there will be a sequence of k steps in the future which is not a repeat of the k steps immediately before it, which will therefore not repeat the cycle, (unless the maze has only one room and one teleporter, in which case this algorithm has already explored the whole maze). However, I don't have a proof of this.

Other sources of randomness

The guaranteed exploration from this algorithm comes from its property of non-repetition. True randomness has this property as well (it is capable of producing sequences not before seen), but so do irrational numbers. If there are fewer than 10 doors in each room, then choosing the n'th digit of pi modulo the number of doors in the room would also guarantee eventual total exploration, because pi does not repeat. However, this requires that the explorer be capable of calculating a decimal value of pi to arbitrary precision.

Conclusion

This algorithm guarantees eventual total exploration of the maze, which is sufficient to find your stone again.

The downside is that the memory requirements are exponential with the size of the maze, but that's table-stakes with the other solutions already.