I found the following problem at http://www.artofproblemsolving.com/Store/products/intro-counting/posttest.pdf and I think it's great:

Particle Man is at the origin in three-dimensional space. In how many ways can Particle Man take a series of 12 unit-length steps, each step parallel to one of the coordinate axes, from the origin to (3, 4, 5) without passing through the point (2, 3, 2)?

Slightly harder: what if Particle Man also is not allowed to pass through the point (1,1,1)?

No vote yet

4 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestAt first consider the total number of ways Particle Man can take a series of 12 unit-length steps from the origin to \( (3, 4, 5) \), i.e remove the constraint first. Consider a permutation of \( 3 \) identical \( x \)s, \( 4 \) identical \( y \)s, and \( 5 \) identical \( z \)s. For example, \( xxyyyyxzzzzz \) is such a permutation. In each such permutation, a \( x \) corresponds to moving one step along \( x \) axis, a \( y \) corresponds to moving one step along \( y \) axis, and a \( z \) corresponds to moving one step along \( z \) axis. We are talking about moving positively along the axes here, because if a negative step is taken then the total number of steps taken to reach the destination will be more than \( 12 \). The total number of permutations is \( \frac{12!}{3!4!5!} \). Now we find the number of ways Particle Man can reach his destination passing through \( (2, 3, 2) \). Consider the first part of his journey, i.e his journey from origin to \( (2, 3, 2) \). In a similar argument, we can prove that Particle Man can go there in \( \frac{7!}{(2!)^23!} \) ways. Now consider the second part of his journey, i.e his journey from \( (2, 3, 2) \) to the destination. Similarly we can prove that this can be done in \( \frac{ ((3-2) + (4-3) + (5-2))!}{(3-2)! (4-3)! (5-2)!} = \frac{5!}{3!} \) ways. Hence the total number of ways Particle Man can reach his destination via \( (2, 3, 2) \) is \( \frac{7!5!}{(2!)^2(3!)^2} \) (the numbers are multiplied). We have to subtract this from the total number of ways, so the final answer will be \( \frac{12!}{3!4!5!} - \frac{7!5!}{(2!)^2(3!)^2} \).

I will post my answer to the harder part shortly.

Log in to reply

That's a wonderful answer, and it is correct, obviously. On Project Euler (a website with programming challenges) a similar problem was posted, but it is much, much harder: it involves many more points in the grid that have to do with pythagorean triples. :) Here it is: http://projecteuler.net/problem=408

Log in to reply