wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> GridWork
        
(Message started by: Ant_Man on Jan 23^rd, 2010, 2:23pm)

Title: GridWork
Post by Ant_Man on Jan 23^rd, 2010, 2:23pm

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).

Title: Re: GridWork
Post by towr on Jan 23^rd, 2010, 2:50pm

Let's see, wasn't that [hide](X+Y-2)!/(X-1)!/(Y-1)![/hide]?
[hide]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.[/hide]

Title: Re: GridWork
Post by Ant_Man on Jan 23^rd, 2010, 3:21pm

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 [hide](X+Y)!/(X!Y!)[/hide], but you're right towr.
Another cool way to think of it:
[hideb]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.[/hideb]

@towr: Why are there X vases? Shouldn't it be X-1 with your definition of an X by Y grid?

Title: Re: GridWork
Post by Grimbal on Jan 23^rd, 2010, 4:24pm

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.

Title: Re: GridWork
Post by towr on Jan 24^th, 2010, 9:21am

on 01/23/10 at 15:21:47, 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 :P 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.

Title: Re: GridWork
Post by Ant_Man on Jan 24^th, 2010, 7:30pm

I see now. Thanks.