Mr Geometry is at the origin in three-dimensional space. How many ways can Mr Geometry 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,1,2)?

hehehe Mr Geometry

dek likes!

ooh, a combinitorics puzzie.

lesse.  I think it's (12 : 3 4 5) - (5 : 2 2 1)

no, wait, it's (12 : 3 4 5) - (5 : 2  1 2)(7 : 1 3 3)

No to the first.

wait, you're actually deciphering my notation? It was supposed to be secret, so I could be smug and reveal that I knew the answer all along! 

Please finish with the actual number...

For those who don't know the secret notation..

... gotta get my calculator...

And give an explanation so everyone knows you know why, and newbies can understand the reasoning... if that's okay.

I step away for 5 mins and when I get back, nothing makes sense....

You GUYS!!

hm... that doesn't make sense.  calculator says it's 27714.2

that doesn't make sense....

Try those buttons again...

here we go: 23520. (I dropped a factorial)

Yes. And the explanation?

... or would you prefer if I gave it?

P.S. +1 point for Duke Jake.

I'll do it. maybe starting from the Binomial Theorem.

No no!

Withhold the point till he gives the explanation!!

He got the point - as soon as I saw his notation I knew he knew why. But for the record, it would be better if there was a plain English explanation here.

shhhh..... play along will ya?

hehehe
 

Hey DJ, don't start with the Binominal Theorem, you joker! Just about why there can't be any back-tracking, how you work out the number of possible paths from one point to another, ... why the three factorials in the denominator.

...and the reasoning behind the second term being a product.

It provides a good background.  some people might not know this.

Anyway.  The Binomial Coefficent: The binomial coefficient is the number of ways of organizing n items in a row when k of them are all identical.  Like having 5 white socks in a drawer with 20 socks in it (the rest are black).

It turns out that

Since there are 20! ways to take the socks in order.  But once you have them in order, you can take the white socks in any of 5! ways and the black socks in any of 15! ways

[edit: added link]

Okay, nice intro.

For pacing's sake, I want to have a few posts between this post and the next.  Math is really annoying when it's lumped too close together.

(also gives me time to compose next message)

..

...

..

So is the number of ways to select two distinct types of things.

What if we had red socks, too?

Then we have the Multinomial Coeffiecent: the multinomial coeffiecent is the number of ways of choosing from a group with ANY NUMBER of different things.

the multinomial coefficent looks very familar:

Imagine if we had 5 white socks, 5 red socks, and 10 black socks (for a total of 20 socks).  There are 20! ways to take the socks in order.  But once you have them in order, you can take the white socks in any of 5! ways, the red socks in any of 5! ways, and the black socks in any of 10! ways

the multinomial coeffiecent is (20 : 5 5 10) = 20! / (5! * 5! * 10!)

... and now you see why I used the notation that I did.

...

...

...

And we're back to the original problem.

You are taking 12 steps in one of three directions, 3 x-axes, 4 y-axes, and 5 z-axes.  These steps are all identical, so there are (12 : 3 4 5) ways of selecting them.

To get to (2,1,2), you need to make 5 steps in one of three directions, 2 x-axes, 1 y-axes, and 2 z-axes.  These steps are all identical, so there are (5 : 2 1 2) ways to get to (2,1,2).

From there, you still have to hit (3,4,5), which is (3,4,5)-(2,1,2) = (1,3,3) from here for a total of 7 steps in one of three directions, 1 x-axes, 3 y-axes, and 3 z-axes.  These steps are all identical, so there are (7 : 1 3 3) ways to get from (2,1,2) to (3,4,5).

If we multiply those together, we get the number of paths that pass through (2,1,2) on their way to (3,4,5), for a total of (5 : 2  1 2)*(7 : 1 3 3) paths

So (12 : 3 4 5) paths of which  (5 : 2  1 2)*(7 : 1 3 3) are invalid, gives us (12 : 3 4 5) - (5 : 2  1 2)*(7 : 1 3 3) valid paths.

Thanks DJ!

*suffers from flashbacks of uni maths class*

yep, that's where I got all of this.

oh, and some calculator results: (12 : 3 4 5) = 27720

(5 : 2  1 2)(7 : 1 3 3)  = 4200

27720 - 4200 = 23520

wow.  that took an hour? daaaamnnn!

That's great! All I would add is that in general, getting to a point could involve steps in either direction along each of the three axes, that is, backtracking is in general possible, where Mr Geometry sets out in the x direction, say, then takes a step in the y direction, then goes BACK say two steps in the x direction, etc. This makes it far more complicated. He could even overshoot the destination along any or all of the axes, then come back to it.

Thankfully, in this problem, 12 steps is the minimum required to get to (3,4,5) from the origin walking parallel to the axes, and so there can't be any backtracking. All steps must be in the +ve direction along each of the three axes. Only the axis-order of the steps can vary.

yes, and I appreciate neither having to solve that, nor explain the solution.

i'm glad i missed this one.....i would never have got that.

Yeah... I'd probably have pulled up a paint window, sketched out a 3d grid and started counting...