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.

Me again "new to maths guy". Please tell me if the substance of my questions are not a good fit for the site.

I'm now onto Question 15 of Project Euler and it seems like there's some mathematical path finding technique I should use.

Looking around I've found graph and tree traversal, djikstras shortest path and some others but none are quite appropriate.

I would be grateful If you would be so kind as to link me to documentation in this regard.

thanks

share|improve this question
    
No graph algorithm is necessary. –  user3533 May 13 '12 at 8:54
1  
How many steps do you have in each such route? How many of which are down and how many are right? –  user3533 May 13 '12 at 8:55
1  
Oh, I may have misread the question, I thought only right and down moves are allowed. –  user3533 May 13 '12 at 8:57
2  
Do you have the distances between every 2 nodes in the grid? If so , then you can try using Floyd Algorithm en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm –  Bhargav May 13 '12 at 9:11
1  
We have been asked by the Project Euler people not to discuss their problems here. –  Gerry Myerson May 13 '12 at 12:39

1 Answer 1

up vote 2 down vote accepted

Minor hint:
You can encode any path uniquely by a sequence of 20 zeros and ones, with 10 zeros and 10 ones. 0 representing down, 1 representing right. And every such sequence determines a valid path.

Level 2 hint:
We are looking for the number of ways to choose 10 elements from a 20 element set. Not too hard to derive the general formula.

Solution:
Use the binomial formula to calculate the number of ways to choose k elements from a set of n,

$$\binom{n}{k}:= \frac{n!}{k!(n-k)!} $$

share|improve this answer
    
There may be something to this but I must need to think about it some more. Cheers. –  gyaresu May 13 '12 at 9:26
1  
It might be hard to figure out if you havent had combinatorics before, but we are looking for the number of ways to choose 10 elements from a 20 element set. –  user1708 May 13 '12 at 9:27
1  
Those brackets are just a way to label the function, instead of writing f(n,k), because its a commonly used function. And that colon means the left side is defined as the right side. –  user1708 May 13 '12 at 10:03
1  
Well, this crap-easy problem is common knowledge and part of math-currilicum and cant really be attributed to project euler. –  user1708 May 13 '12 at 13:11
1  
@MaoYiyi There is a button next to the answer with the same function as your comment. ;-) –  user1708 May 13 '12 at 17:18

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.