Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-02-12 22:51:13

fusilli_jerry89
Member
Registered: 2006-06-23
Posts: 86

Hard Maze Problem agh help!

An n by n maze is randomly generated with numbers from 1 to n. Fo example: a 5 by 5 maze might look like the following:

23125
55132
54214
13542
14341

In order to solve the maze, you have to start from one of the top numbers, and get to one of the bottom numbers in n-1 steps (4 in this case). (You can only move down, and diagonal downwards). In addition, you must visit each number from 1 to n once and only once. (You must visit 1,2,3,4,5 in the example above). For example, a solution in the example above might be 2,5,4,3,1 or 5,2,1,4,3.

What is the possibility of a maze with no solutions?

I know that in order to get the answer to this we have to take (1/n)^n² (probability for each maze) and multiply it by the total of number of mazes without solutions. I can see that we can add up all the mazes without a certain number (i.e. a maze with no 2's will yield no solutions), but how do I find out how many mazes there are with no solutions otherwise?


Thanks!

Offline

#2 2009-02-13 14:23:56

John E. Franklin
Member
Registered: 2005-08-29
Posts: 3,588

Re: Hard Maze Problem agh help!

Why not just stick with one number and go with it, it's more fun, and
get's the same answer probably.  Like follow the "1's" down a path.
Also, I think a larger matrix like a 8x8 and use only numbers from
1 to 3, so you have a chance of getting through it.


igloo myrtilles fourmis

Offline

Board footer

Powered by FluxBB