Lets assume we have a rat maze as represented by the following NxM matrix
where S is the start location and F is the end location.

S    0    0    0    0    0
1    1    0    0    0    0
1    0    1    0    0    0
1    0    1    0    0    0
0    1    0    1    0    0
1    0    0    0    1    0
0    1    1    1    1    F

The idea (as with any rat maze) is to traverse from S to F. The matrix can
have only 0 and 1 as values. 1 represents a path that can be taken and 0
represents a blocked path.

We can make the following assumption:
S will always be (0,0) and F will always be (N,M).

As seen from above, there can be many paths from S to F.

How do we find the shortest (or longest) path from S to F without actually
traversing all the possible paths.

Please post (with proof/explantion) your algorithms. Also can you then think
of ways to optimize the algo?

  I. The chicken came first.
 II. The egg came first.
III. Statement I is false and Statement II is true.

If two of the above statements are false, what chance is there that the egg
came first?

Here is an interesting sequence..
1 20 33 400 505 660 777 8000 9009 10100 11121
What are the next few numbers in the above sequence?

You are travelling in the jungles of Africa, when you are caught by a
tribe of barbarians. They allow you to choose between death or solving
their great challenge. You know what you will choose ;)

You are blindfolded and taken to a room, where you are asked to kneel.
You feel hundreds of circular discs lying in front of you. You are told
that one side of each disc is painted red, and the other, green. There
are exactly 129 discs that currently are red side up. You have to
divide the discs into two groups, such that each group has the same
number of discs showing the red colour. Obviously, no peeking allowed.