Author |
Topic: GridWork (Read 453 times) |
|
Ant_Man
Newbie
Gender: 
Posts: 23
|
This seems like it should I have been posted already, but searching turned up nothing. Should be a piece of cake for many on this site though.
How many ways are there to get from the lower left corner of an X by Y grid to the top right corner if you are only allowed to move up or right at each intersection. (You are moving along the grid lines).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: GridWork
« Reply #1 on: Jan 23rd, 2010, 2:50pm » |
 Quote  Modify
|
Let's see, wasn't that (X+Y-2)!/(X-1)!/(Y-1)!?
You can see it as the number of ways of dividing Y-1 balls over X vases. Where putting a ball in vase is equivalent to moving up that many gridpoint in a column before moving (right) to the next column.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ant_Man
Newbie
Gender:
Posts: 23
|
|
Re: GridWork
« Reply #2 on: Jan 23rd, 2010, 3:21pm » |
Quote Modify
|
I guess I should have said that X, Y are the lengths of the sides of the grid (i.e. an 2 by 2 grid has 3 rows and 3 columns). It makes the answer nicer looking (X+Y)!/(X!Y!), but you're right towr.
Another cool way to think of it:
| hidden: | | Orient the grid so that the starting corner is at the top of the page and the ending corner is at the bottom (the grid will be angled). Recursively, we know that the way to reach one vertex is to add the number of ways to reach the two vertices above that one together. Write the number of ways to reach a specific vertex on that vertex and the grid looks like Pascal's triangle. The answer follows from the binomial coefficient formula. |
@towr: Why are there X vases? Shouldn't it be X-1 with your definition of an X by Y grid?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: GridWork
« Reply #3 on: Jan 23rd, 2010, 4:24pm » |
Quote Modify
|
Considering that you have X horizontal and Y vertical moves, it is just the number of ways to place the X horizontal moves among the X+Y moves.
That is Comb(X+Y,X), same solutions as everybody.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: GridWork
« Reply #4 on: Jan 24th, 2010, 9:21am » |
Quote Modify
|
on Jan 23rd, 2010, 3:21pm, Ant_Man wrote:| @towr: Why are there X vases? Shouldn't it be X-1 with your definition of an X by Y grid? |
|
No, it should be X, if only because that gives the same answer  But also because you can move up along all X columns. However, you can only move up Y-1 times, so you distribute those Y-1 steps up over the X columns.
|
| « Last Edit: Jan 24th, 2010, 9:22am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ant_Man
Newbie
Gender:
Posts: 23
|
|
Re: GridWork
« Reply #5 on: Jan 24th, 2010, 7:30pm » |
Quote Modify
|
I see now. Thanks.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print