2
$\begingroup$

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

  • 0
    No graph algorithm is necessary.2012-05-13
  • 1
    How many steps do you have in each such route? How many of which are down and how many are right?2012-05-13
  • 0
    Ok. Treat me like I know nothing. Why?2012-05-13
  • 1
    Oh, I may have misread the question, I thought only right and down moves are allowed.2012-05-13
  • 0
    Maybe it is the case (only right/down moves)? Otherwise there is at least one more route in the $2x2$ case.2012-05-13
  • 0
    @user3533 I think you read it well.2012-05-13
  • 0
    @gyaresu: Ok. Seems like they really mean only right/down moves are allowed. Try answering my Q in the second comment under this assumption.2012-05-13
  • 2
    Do you have the distances between every 2 nodes in the grid? If so , then you can try using Floyd Algorithm http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm2012-05-13
  • 0
    I'm sitting here with a pad and pen trying to find some commonality between 2sqr grid and a 3sqr grid. Maybe I'll have a eureka moment ;)2012-05-13
  • 0
    If I look at it as a diamond shape then one only need calculate half of the diamond for possible routes.2012-05-13
  • 1
    We have been asked by the Project Euler people not to discuss their problems here.2012-05-13
  • 0
    Gerry, I'm trying to keep the specific question out of it but do you have a suggestion how one should phrase the question regarding the mathematics of it? There's a massive difference between providing the code and providing guidance.2012-05-13
  • 0
    I refer you to the discussion at http://meta.math.stackexchange.com/questions/1090/re-project-euler-questions and the links given there.2012-05-14

1 Answers 1

2

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)!} $$

  • 0
    There may be something to this but I must need to think about it some more. Cheers.2012-05-13
  • 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.2012-05-13
  • 0
    Cool. Any primers on Combinatorics you can recommend? Cheers. I really appreciate any direction on "stuff I don't know".2012-05-13
  • 0
    If I do pascals triangle on a 2*2 grid the bottom corner is 6. If I do it on a 3*3 grid it's 20. I'm on my phone at a restaurant but if this is a correct way to solve the problem. Could you please submit it as an answer Xnyurznaa? I'll carry on with my pen and paper till then :)2012-05-13
  • 0
    I love your answer Xnyurznaa I just don't understand it. The n is over the k in brackets and the equals sign has a preceding colon... Ok then....2012-05-13
  • 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.2012-05-13
  • 0
    I don't mean to sound ungrateful or that I don't appreciate all direction in these matters. I just have no history with maths. I'm not dumb, it's just that on a lot of stuff I need to see the rule book. :)2012-05-13
  • 0
    We have been asked by the Project Euler people not to discuss their problems here.2012-05-13
  • 1
    Well, this crap-easy problem is common knowledge and part of math-currilicum and cant really be attributed to project euler.2012-05-13
  • 0
    @Xnyyrznaa nice answer with the different levels, clever.2012-05-13
  • 1
    @MaoYiyi There is a button next to the answer with the same function as your comment. ;-)2012-05-13