EPTOK, question reads:
Sung (nice name btw) is 5blocks east and 4 blocks south of her friend's home. How Mmany different routes are possible if she walks only west or north?
Math Question?
| Blogs > Salv |
|
Salv
Canada3083 Posts
OK, question reads: Sung (nice name btw) is 5blocks east and 4 blocks south of her friend's home. How Mmany different routes are possible if she walks only west or north? | ||
|
BottleAbuser
Korea (South)1888 Posts
Err, I guess not. My noob stab at it: The path will always be 9 blocks long (displacement is 5 + 4). There will be only 2 choices at most for each step (N or W?). Therefore, an upper limit will be 2^9 routes. However, at the 4 spots South of Sung's friend's house, there is only 1 choice (go North), and same with the 5 spots East of the house (go West). Dunno how to account for those. | ||
|
Salv
Canada3083 Posts
| ||
|
Salv
Canada3083 Posts
Not sure ;S | ||
|
ShaLLoW[baY]
Canada12499 Posts
1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 I think that's how pascal's triangle goes? | ||
|
BottleAbuser
Korea (South)1888 Posts
| ||
|
Salv
Canada3083 Posts
It is hard to explain, but I am fairly certain this is correct? Any verification? | ||
|
fusionsdf
Canada15390 Posts
I remember this problem. If you cant figure it out, draw out a grid and list the various paths. Theres a pattern, but I forget how it goes. but if you do the diagram it should be obvious | ||
|
Salv
Canada3083 Posts
On January 29 2008 13:40 ShaLLoW[baY] wrote: I'm not sure how to explain it, but it's a Pascal's Triangle variation I think? I suck though, so don't quote me on that. I think it ends up being 126. 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 I think that's how pascal's triangle goes? I think I remember the answer actually being 126 :O, could you explain this further? | ||
|
ShaLLoW[baY]
Canada12499 Posts
![[image loading]](http://img209.imageshack.us/img209/893/lolwutjc7.png) You start by placing a 1 next to each intersection at the bottom and right sides as there is only one possible way to reach each of those squares. You then add the numbers on either side of the intersection to get how many possible ways there are to reach that intersection. (bit confusing, look at how I did 1 + 1 = 2 for the bottom right, then 2 + 1 = 3 for the one above it, cont. until you reach the end) Man I'm bad at explaining things :p Obviously you start at the bottom right, and only add upwards and leftwards as you can only walk west and north. | ||
|
imDerek
United States1944 Posts
the method I would use is called block-walking. so consider a coordinate system where (0,0) is where you start from and (5,4) is your ending location. the south direction is set to the +y direction for convinience. since the person can only walk east or south, the calculation is nice. observe that there is only 1 way to walk from (0,0) -> (1,0) and only 1 way to walk from (0,0) -> (0,1). now note that you can only go to (1,1) from either (0,1) or (1,0). and since there is only 1 way to get to (0,1) and 1 way to get to (1,0), there is a total of 1+1=2 ways to get to (1,1). in general, the number of ways to get to (m,n) = number of ways to get to (m-1,n) + number of ways to get to (m, n-1). So this is a recursion. just make a 4x5 grid and do it real quick, and you should get 126. | ||
|
BottleAbuser
Korea (South)1888 Posts
| ||
|
ShaLLoW[baY]
Canada12499 Posts
| ||
|
Salv
Canada3083 Posts
 .Mad props to you both! :D | ||
|
imDerek
United States1944 Posts
let x be the vector <0,1> and y be the vector <1,0>. you will need 5 y's and 4 x's to get to the point (5,4) and you can arrange them any way you like. so the answer is precisely 9! / (5!*4!). | ||
|
FieryBalrog
United States1381 Posts
So yea its 126. | ||
|
Day[9]
United States7366 Posts
you can view your path as a series of W (west) and N (north) moves. For example, a legit enumeration of a path would be " W W W N N W W N N ". Or, we could go "N N N N W W W W W ". We are happy with both because (in the end) there are 5 west moves total and 4 north moves total. So, lets count the total number of enumerated paths! Since we have NINE TOTAL MOVES, we can simply CHOOSE when to take our FIVE WEST MOVES and the north moves are fixed. For example, if we decided to go "W W W _ _ W W _ _ " we know that all the underscores MUST be north moves (as we have performed all our west moves). Therefore, the total number of unique paths is (9 choose 5) = 9! / (4!5!). (if you didn't know the binomial coefficient (9 choose 5) is the 5th element on the 9th row of pascals triangle). tada! god damn i'm good | ||
|
ShaLLoW[baY]
Canada12499 Posts
+ Show Spoiler + <3 | ||
|
Day[9]
United States7366 Posts
| ||
|
ShaLLoW[baY]
Canada12499 Posts
On January 29 2008 13:36 Salv wrote: I was thinking it was 9factorial divided by 5factorial times 4factorial? Not sure ;S I just realized that you had it right from the very beginning O_o | ||
|
GeneralStan
United States4789 Posts
| ||
|
Saracen
United States5139 Posts
| ||
|
Day[9]
United States7366 Posts
On January 29 2008 13:28 BottleAbuser wrote: Pretty sure it has to do with the Catalan numbers. I'll go look. if sung was disallowed from ever having more north moves than west moves, then yeah it would relate to the catalan numbers. woooo | ||
|
Slithe
United States985 Posts
BTW Day[9], if you think you've got the skills, you should take a crack at the problems in my blog. | ||
|
Day[9]
United States7366 Posts
induction is INSANELY powerful and can provide a REALLY easy way of cracking some extremely difficult problems. however, its such a boring mechanical process. i like pure combinatorics 8] | ||
|
Polemarch
Canada1564 Posts
| ||
|
ShaLLoW[baY]
Canada12499 Posts
| ||
| ||
