Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I tend to struggle in counting because I just am not that insightful so I was wondering if someone could help me with a counting problem that I found in a book from Art of Problem Solving. Also, there is an extension to it; if someone can tell me a solution to that I would be grateful! I was thinking of a possible bijection for the extension since the graph is symmetrical.

Part A: Bob starts from a square at one of the top five squares. He then goes down 1 unit OR he can go down 1 and left 1 unit. How many ways can he get to bottom?

http://tinypic.com/r/6560l4/6

Part B: Same directions as above, you can go down 1 unit or down 1 to left 1 unit except the graph is symmetrical this time.

http://tinypic.com/r/3450vfk/6

Thanks for help!

Can't directly post images so the links are the imaegs.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

If the answer for the first problem is $n$, then the answer for the second is $n^2$. This is because for every ordered pair $(p,q)$ of paths that work for the first problem, the path that we get by first doing $p$, then reversing $q$, gives a solution to the second problem. Conversely, any path from the top of the second configuration to the bottom produces an ordered pair $(p,q)$ of paths for the first problem. So there is indeed a bijection from the set of ordered pairs of paths for the first problem and all paths for the second problem.

Now for the first problem, it is probably worthwhile to think in general terms (so $k$ instead of $5$). We will not do that, just begin to deal with the concrete problem. Since $5$ is a pretty small number, we can just list the paths and count. It is useful to do this systematically.

If we start in top row, leftmost square, we can only go down, so there is $1$ path from there.

If we start in top row, the second leftmost square, at some time we will have to take a diagonal step, and then we have to keep going down. A look at the picture shows that there are $4$ places to take the diagonal step, and hence $4$ paths.

If we start in top row, third leftmost square, things are more complicated. We can take an immediate diagonal step, and then by the previous kind of analysis there are $3$ ways to finish. Or we can do down, and take a diagonal step. There are then $2$ ways to finish. Or we can go down, down, giving $1$ way to finish, for a total of $6$ paths.

If we start in top row, fourth leftmost square, we can take an immediate diagonal step, and then there are by the previous analysis $2$ ways to finish. Or else we can go down, giving $1$ way to finish, for a total of $3$.

Finally, if we start in the rightmost square of the top row, there is only $1$ path.

Add up.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.