Easy(for many people) but interesting(to me) mathematics question?

Question

The image is at this link:
http://i203.photobucket.com/albums/aa303/mts6b21/question.jpg
It is supposed to be a 5x3 rectangle made up by identical squares.

Find the number of all P-Q routes(move from P to Q)
(i) that do not self-intersect i.e. do not cross over themselves
(ii) that do not pass through any segment more than once (Check and prove that this is not the answer as (i) )

And one question is that what type of question is this or under what topic?

it is supposed to be only one of them for each case

interested to find you how do you do it by the common sense way and the combinatorial and graph theory way

the question is in two parts not combined

ok thanks a lot dw, I also watched your show a long time ago

so you are suggesting systematic labelling or counting but it is sometimes not easy to check whether you have left out one due to carelessness.

Are there other methods like using binary sequence or other methods?

also you say that "There can't be a very big number of them."

However, when I used binary sequence or whatever you call it. There seems to be even 56 routes already.
56= 8!/(5!3!)
shortest route should be 00000111 in all kinds of order if 0 represents moving to the right and 1 represents moving up.

or am i wrong? Then to count all the non overlapping routes one by one would be madness.
it could be 000001(-0)(-0)(-0)(-0)(-0)1000001(-0)(-0)(-0)(-0)(-0)
or am i wrong?

thanks curt for the answer

Answer 1

I don't see how it could be only one route for each case. For the first one you are required that hte routes not cross each other. One possible route is an L through the bottom right corner. ANother is an L through the upper left corner. 2 routes that do not cross.

For the second case, I'm only seeing 2 possible routes at a time. That's because the immediate exit from P has 2 paths: horizontal, vertical. At most there can be 1 path that leave P horizontally, and 1 path that leave P vertically. Anymore, then you cross over either the vertical or horizontal segment more than once.

Answer 2

I guess is a combinatorial and graph theory.
Or just common sense.
I saw this problem but in the form that satisfies both (i) and(ii)
if you want only one of them is harder.

I guess you can start by doing the obvious: count them.
Take all the possible routes. There can't be a very big number of them.
You can start by taking all possibilities of routes by the point where they change direction on first row and column.
Somehow, especially (ii) the procedure is iterative. That means if you are in point B and you know all routes from B to the end, you can count only the routs from start to B.

Answer 3

I got your email and I wish I could remember how to do this. I think it was connected to Graph Theory.
I'd say counting but try drawing it out like a tree. Label each intersection with a number. Have P be the top of the tree and have branches for each one that is possible.
P
/\
12
The find all the possibilities from 1 (making sure you don't count anything there's a direct link to the top of the tree). That may help in keeping track.

Answer 4

Got your E-mail, Pole, and I'm glad to help, but I don't know the answer to this. This is definitely like the problems I did in Graph Theory, but that class was almost thirty years ago! Sorry.

Answer 5

qi
5*3+1 = 16 at most simultaneously.

qii
2 at most at one time.

if the question's asking "the number of distinct pairs of routes" that fulfilling those rule, then i don't know.

Answer 6

I don't know a slick way to do this.

My best idea is to start by looking at m x n rectangles smaller than 5x3, and work your way up.

Answer 7

Sorry, I don"t have ready answer for this problem.