13
$\begingroup$

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.

$\endgroup$
7
  • 8
    $\begingroup$ "You are in a maze of twisty little passages, all alike." $\endgroup$
    – Florian F
    Sep 18 at 15:02
  • $\begingroup$ But a difference here, is whether can you be certain that the destination is always the same. $\endgroup$ Sep 18 at 17:00
  • 4
    $\begingroup$ You say the platforms are distinctly numbered. Does that mean uniquely numbered? Or can the same number occur multiple times, and does it indicate anything (like the same number teleports to the same room)? $\endgroup$
    – john16384
    Sep 19 at 8:10
  • 2
    $\begingroup$ @SwissFrank the (directional) graph of all rooms is connected, which means there will always be a path from any room to any room. This is a given, we don't need to determine it. $\endgroup$
    – justhalf
    Sep 19 at 18:10
  • 1
    $\begingroup$ There's a puzzle very much like this (without the pebble, but with a few of the rooms having recognisable landmarks) in the Lucid Nightmare quest chain in World of Warcraft. $\endgroup$
    – Ross Smith
    Sep 19 at 23:43

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
28
  • $\begingroup$ I was busy writing my answer when you posted yours. It seems we had the same idea. But you were faster... $\endgroup$
    – Florian F
    Sep 18 at 18:06
  • $\begingroup$ Well done! That was pretty fast. This is essentially correct, and really close to the solution I originally came up with. About your pebble-finding procedure, it's worth noting that you aren't really trying every finite route; rather you are producing a route between room $A$ and room $B$ for every hypothetical combination of network, room $A$, and room $B$. Therefore you should recursively extend your route based on a hypothesis that you are in a given hypothetical combination of network, room $A$, and room $B$ ($A$ being your starting room, and room $B$ the pebble room). $\endgroup$
    – C-RAM
    Sep 18 at 18:08
  • $\begingroup$ I'll accept your answer by tomorrow. I'd like to encourage others to post (possibly different) solutions. $\endgroup$
    – C-RAM
    Sep 18 at 18:08
  • 1
    $\begingroup$ @C-Ram: I understand what you are saying, and I think it also works and it is very similar to what I argued, but I think what I argued is slightly different and also correct. The route I constructed is not used per se, I only observe that it exists, and the route I actually choose (the concatenation of every finite route) contains it (no matter the network). Also, although it doesn't contain your route (because it is infinite), it contains every finite prefix of your route which means it also works by your argument :) $\endgroup$
    – tehtmi
    Sep 18 at 18:17
  • 1
    $\begingroup$ @C-RAM These solutions determine whether there is an exit almost surely, but not surely. It is definitely possible to get stuck in a loop if you choose teleporters randomly, even though that has probability 0. I think calling this "with complete certainty" in the question is kind of cheating: the certainty is not complete. As the Wikipedia article states, "almost sure" and "sure" are different things when the sample space is uncountable, and the number of possible countably infinite sequences of choices of teleporters is uncountable. $\endgroup$
    – wimi
    Sep 19 at 8:59
5
$\begingroup$

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?".

$\endgroup$
16
  • 1
    $\begingroup$ I have read through your answer in part, but for now, I have a nitpick. Though it will almost surely terminate, your method for finding the pebble after you have dropped it is not guaranteed to terminate. Would you believe me if I told you there was a way to guarantee you find the pebble? $\endgroup$
    – C-RAM
    Sep 18 at 18:17
  • 1
    $\begingroup$ I don't hold with the idea that randomness must eventually return you to the original room. It might never return you to the original room. Statistically it does with a certainty approaching 1.0 but it is 0.999999... $\endgroup$ Sep 18 at 18:46
  • 3
    $\begingroup$ @WeatherVane This isn't quite right. I'm not a mathematician, but I do have a degree in pure math, and have taken rigorous classes on measure theory and probability/statistics. Mathematics has a very rigorous treatment of these concepts (you're free to disagree that their treatment of these topics is justified, if that's where your skepticism originates), but under the standard mathematical treatment, the associated probability is precisely $1$, because the measure of the set of events where the path returns to its origin is $1$ with respect to the most reasonable probability measure. $\endgroup$
    – C-RAM
    Sep 18 at 19:47
  • 2
    $\begingroup$ @WeatherVane I guess your contention is that the standard mathematical formalisms don't describe reality? In this case, I have no argument but to point out that in reality, you cannot traverse a maze for infinite time, so we must choose to either admit that the issue cannot be discussed in any real sense, or adopt the standard mathematical conventions (which are really our only option when dealing with infinities like this) to discuss it. $\endgroup$
    – C-RAM
    Sep 18 at 20:05
  • 4
    $\begingroup$ @WeatherVane In any case, I think we're clogging up the comments of this poor post with arguments about math. All I can say is that if you were to ask a mathematician, they would say it occurs with probability $1$. Whether or not mathematicians are "correct" in any sense is a debate I'll leave to the mathematical philosophers. $\endgroup$
    – C-RAM
    Sep 18 at 20:12
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @C-RAM if the new network has another room, sequence would have more elements. Assuming there are N rooms with M doors each, you try all ways to get N*M sequences - so, 12345...NM, then 12345...NM,NM-1 etc etc. After you fail with N rooms, you attempt sequences with N+1. All of these will produce an instance of sequence along "door X in room 1, door Y in room 2, door Z in room 1 again" - no matter where you are initially and where you need to go. Sure, this sequence is a huge overkill, it will try all combinations of all doors in all rooms. But it is finite and deterministic. $\endgroup$ Sep 19 at 20:06
  • $\begingroup$ I might have misread your post originaly, and you're right; my argument doesn't fully disprove this method. However, whether or not the presented sequence actually works doesn't seem obvious to me (though I too would be surprised if it failed for some reason). To my somewhat trained eye, this looks like a really hard statement to rigorously prove. $\endgroup$
    – C-RAM
    Sep 19 at 21:55
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is interesting. I will however say that just because a sequence does not explore the whole maze doesn't mean it will necessarily end in a cycle. It could get stuck in some subsection of the maze making some horrible sequence of moves that constitute an infinite squarefree word. As I said in another comment, I would be surprised if a sequence like this did fail to traverse the whole network, but actually proving that it will seems like a really hard problem; possibly PHD level research hard. $\endgroup$
    – C-RAM
    Sep 19 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.