Many ways to work?

(Use a fixed-width font to view this)

I spent a frozen 15 minute walk yesterday wondering how many different ways I could get to work (I don't get out much). I think it's a lot...

A

S

P

O

I

L

A

G

E

In the single-street case you want to go S blocks south and E blocks east, for a total of S+E blocks. You can choose the E eastward steps from the total in (S+E)!/(S!E!) ways.

For the two-sidewalks-per-street case, you have two ways to traverse each of the S+E steps, so each of the street-oriented routes above corresponds to 2^(S+E) sidewalk-oriented routes.

Puzzle extension: How many routes avoid the wumpus who lurks at one of the intermediate intersections?

Well, now. That really depends on which intersection he is at. And what about the bottomless pits?

Josh

First, reduce the problem to one dimension: Once you've picked the south streets, the east streets are forced, and vice-versa. You must pick a south street from each row. And the south streets you pick must be ordered west to east. Number the columns 0-3, and a path can be described as an ordered triplet of columns (k,l,m), where 0<=k<=l<=m<=3

So the number of different ways is

sum (sum (sum 1)) k=0,3 l=k,3 m=l,3

Suppose the wumpus is at (A,.

The number of routes encountering the wumpus is

(A+! (C+D)!

What a blast from the past! Is there a version of Hunt The Wumpus on the net?

(Wombats! I hate wombats!)

Never mind..found several! Here's one: http://enterprise.sct.gu.edu.au/~anthony/dungeon/wumpus/

The original post is the spoiler

Consider all the different ways to get to each point:

I thought it too obvious to mention that the wumpus is at intersection (x,y).

The single-wumpus variation is really no harder than the original no-wumpus puzzle, but things get interesting (read: 'I don't know a good approach' when you add a few bottomless pits or a few more wumpi, or when you start letting the wumpi move around. (Why are the wumpi on the move? Perhaps they're searching for their wumpae. Or perhaps each wumpus is trying to avoid capture by Native Americans, who would first castrate him and then trade him