Labyrinth

Consider the possible paths from the starting point. At each junction, you have a finite number of choices as to which route to take. Define the length of a route to be the number of junctions met (after the first).

There are a finite number of routs of length $1$ (one for each initial choice of direction). For each of the routes of length $1$ , there are a finite number of routes of length $2$ that start with the route of length one (one for each possible choice of the last direction to take). Thus there are finitely many routes of length $2$ . Similarly, each route of length $n$ can be extended in a finite number of ways to obtain a route of length $n+1$ . Thus, if there are finitely many routes of length $n$ , then there are finitely many routes of length $n+1$ . If we assume that there are at most four choices of direction at each junction, we deduce that there are at most $4^n$ routes of length $n$ .

Since the distance from the start to the end is finite, the way out is a route of length $N$ for some $N$ .

We can try possible routes in some order. If we test a route of length $n$ and do not get out, we backtrack along this route until we get back to the start. I shall call following a route, and backtracking if the route is unsuccessful testing a route.

A route of length $n$ can be described by an $n$ -tuple of the lettters L,F,R,B, where each letter describes which way to turn at each junction. Thus the route $(F,R,B,L)$ is a route of length $4$ which involves going straight on at the start, turning right at the next junction, going back at the next, and then turning left at the final junction. A dull route that gets you back to where you started, but never mind. The point is that these up to $4^n$ routes can be sorted lexicographically, so they can be ordered (without having to know the layout of the labyrinth).

Adopt this strategy. Test the length $1$ routes in order (backtracking to the start if they are unsuccessful). Now test the length $2$ routes in order, then the length $3$ routes, and so on. After testing at most $4 + 4^2 + 4^3 + \cdots 4^N = \tfrac43(4^N-1)$ routes (each of which has length at most $N$ passages, meaning that you will have traversed at most $\tfrac43N(4^N-1)$ passages (twice each, allowing for backtracking), which will take you finite time), you will get out. Thus you will get out in finite time, without needing help from anyone. The answer is $\boxed{1}$ .

The bottom line is that there are countably many paths of finite length, and these can be tested successively. After a finite number of tests, you will be able to get out.

The problem statement and choices reveal the solution. If one person might not ever find it, then how can the communication device help another? Since infinity is not one of the choices, the answer must be one!

The minimum number of required people is $\boxed{1}$ .

If the distance between the entrance and exit is finite, there must also be a finite number of possible paths to take of this exact finite length.

Start by testing all paths of distance $1$ from the entrance. If the exit is not found, increase the distance by $1$ , and test all possible paths of the new length. Repeat until you find the exit.

An easy way to do this would be to follow the left wall, considering any paths beyond the current test length to be blocked off. Once you find yourself back at the entrance, increase the distance and repeat.

As the entrance and exit are located on the labyrinth boundary and the labyrinth is entirely on a single plane, we know we can't accidentally pass around the back of the exit or entrance.

Think about the labyrinth as a graph were the nodes are the squeres and the edges are a possible moves. Do BFS, and becuse the exist is within finite steps, you are certain to find it.

The communication device does not allow you to say where the exit is, hence it is useless. Because of this, a singular person would have the same odds as the whole group working individually. The exit is at a finite distance, meaning it is possible to reach.

It’s a logic problem, not a mathematical one. If no people enter the maze, there is no strategy of finding the exit. Therefore you need at least 1 person for strategy to exist.