Extremely hard combinations problem.

K

ksmith3894

New member
Joined
Aug 31, 2012
Messages
13
**I am trying to attempt this, but I honestly don't even know where to start. I can't figure out how this applies to section 1 and 2 of my finite mathematics class. If you could possibly just help me to get started. Or if someone wants to attempt this fun problem, could you tell me how you completed it?

An integer lattice contains all the points (x, y) in the plane with both x and y integers. So
points like (3, 5) and (0, 2) are on the lattice, but (1.2, 5) or (3, 5.67) are not.
From any point on the lattice you can move one up, one down, one left or one right. For
example, from (3, 5) you can move up to (3, 6), down to (3, 4), left to (2, 5) or right to (4, 5).
We are trying to count shortest paths between two given points. For example, from (0, 0) to
(2, 3) any shortest path has length 5 (i.e. you need fi ve moves), and an example of two such shortest
paths is (0, 0) to (0, 1) to (1, 1) to (1, 2) to (1, 3) to (2, 3) (there are several shortest paths, this is
just one of them).
(a) What is the length of the shortest path from the point (0, 0) to the point (30, 20)?
(b) How many distinct paths are there (0, 0) to (30, 20) that have as length the shortest length
from part (a)?
(c) How many distinct paths of shortest length from (0, 0) to (30, 20) are there that avoid the
point (15, 10) ?
(d) How many distinct paths of shortest length from (0; 0) to (30; 20) are there that avoid the
points (15, 10) and (25, 5) ?
(e) How many distinct paths of shortest length from (0; 0) to (30; 20) are there that avoid the
points (15, 10) and (20, 14)?

THANK YOU! :D
 
ksmith3894 said:
**I am trying to attempt this, but I honestly don't even know where to start. I can't figure out how this applies to section 1 and 2 of my finite mathematics class. If you could possibly just help me to get started. Or if someone wants to attempt this fun problem, could you tell me how you completed it?
An integer lattice contains all the points (x, y) in the plane with both x and y integers. So
points like (3, 5) and (0, 2) are on the lattice, but (1.2, 5) or (3, 5.67) are not.
From any point on the lattice you can move one up, one down, one left or one right. For
example, from (3, 5) you can move up to (3, 6), down to (3, 4), left to (2, 5) or right to (4, 5).
We are trying to count shortest paths between two given points. For example, from (0, 0) to
(2, 3) any shortest path has length 5 (i.e. you need five moves), and an example of two such shortest
paths is (0, 0) to (0, 1) to (1, 1) to (1, 2) to (1, 3) to (2, 3) (there are several shortest paths, this is
just one of them).
(a) What is the length of the shortest path from the point (0, 0) to the point (30, 20)?
(b) How many distinct paths are there (0, 0) to (30, 20) that have as length the shortest length
from part (a)?
(c) How many distinct paths of shortest length from (0, 0) to (30, 20) are there that avoid the
point (15, 10) ?
(d) How many distinct paths of shortest length from (0; 0) to (30; 20) are there that avoid the
points (15, 10) and (25, 5) ?
(e) How many distinct paths of shortest length from (0; 0) to (30; 20) are there that avoid the
points (15, 10) and (20, 14)?
Click to expand...
Given two points \(\displaystyle (j,k)~\&~ (m,n)\) in the lattice the shortest distance between them is \(\displaystyle |m-j|+|n-k|\).

The number of shortest paths is \(\displaystyle \dfrac{(|m-j|+|n-k|)!}{(|m-j|)!(|n-k|)!}~.\)
 
Avoid certain points?

Well that makes sense...
However, how do you avoid certain points in your lattice? Would you just subtract 1 from each variable for each individual point like instead of 50!, it would be 48! ? I am not sure how to avoid these certain points with this method and use of I guess it would be a permutations. Any Help?
THANK YOU!:D
 
Find the number of paths from the start to the excluded point, find the number of paths from the excluded point to the end.

Lets say we start at (0,0) and end at (3,3) and want to exclude the point (2,2)
20 ways to get from (0,0) to (3,3),
6 ways to get from (0,0) to (2,2),
2 ways to get from (2,2) to (3,3).

How many ways total to get from (0,0) to (3,3) that DO go through the point (2,2)?
Now subtract those off since you don't want them.
 
If the 6 ways to get to (2,2) are 1-6 and the 2 ways to get to (3,3) are A and B, the paths are...
1A, 2A, 3A, 4A, 5A, 6A, ... 5B, 6B How many? (not 8)
 
There are only 20 ways total from 0,0 to 3,3 so taking away some of these ways and getting 30 makes no sense.
1A 2A 3A 4A 5A 6A 1B 2B 3B 4B 5B 6B
This is 12 paths that go through (2,2), or you could have just done 6*2 via counting principle.
Excluding this point we get 20 - 12 = 8 paths that don't go through (2,2)
 
You must log in or register to reply here.
Top