## The Random Maze

Posted by on Friday, June 5, 2015 Under: Puzzles

Earlier this week I wrote an article about an interesting (and possibly previously unpublished) about a mathematics puzzle that so far as I know does not have a simply solution. Apparently it was popular, and as such I have decided to devote today's article to another interesting puzzle. As with the previous one, I have asked a number of mathematician friends about this one and as yet I have not found a previously published source, or a solution for it. Perhaps one of you reading this will find the answer...

Start with an NxM lattice of points, as shown below.

Now take your favorite random boolean number generator (ie a coin). For each two neighbouring points, either horizontal or vertical, flip the coin. If it comes up heads, leave the space blank and if it comes up tails draw a line between those two points. In the end, you should have something like this:

Start with an NxM lattice of points, as shown below.

Now take your favorite random boolean number generator (ie a coin). For each two neighbouring points, either horizontal or vertical, flip the coin. If it comes up heads, leave the space blank and if it comes up tails draw a line between those two points. In the end, you should have something like this:

The question is, what is the probability that the final figure will be a solvable maze? By solvable here, I mean start in the upper left corner, and draw a path through the figure to the lower right corner without passing through any of the lines. The particular example above is not solvable, whereas the one below is:

The full puzzle though is slightly more complicated. For arbitrary N and M, and for arbitrary probability p of drawing any given line (the example above uses p = 0.5), what is the probability that the final maze has a solution?

This is an interesting question, because it is simple to state and yet so far the mathematicians I have shown it to have not been able to solve it. In fairness, I don't have a really good, simple solution either (It can be solved with more complicated computer algorithms).

So I leave it to the readers of this article to see if they can find a solution. I will be interested to see where this puzzle leads...

The full puzzle though is slightly more complicated. For arbitrary N and M, and for arbitrary probability p of drawing any given line (the example above uses p = 0.5), what is the probability that the final maze has a solution?

This is an interesting question, because it is simple to state and yet so far the mathematicians I have shown it to have not been able to solve it. In fairness, I don't have a really good, simple solution either (It can be solved with more complicated computer algorithms).

So I leave it to the readers of this article to see if they can find a solution. I will be interested to see where this puzzle leads...

In : Puzzles