Trick of Mind

16 Responds so far- Add one»

1. 1. Nathan Said：
   July 13th, 2010 at 6:20 pm

   It looks likes this problem if closely related to the Catalan numbers, though with more possible solutions because of the diagonal movements allowed.
2. 2. John24 Said：
   July 13th, 2010 at 6:50 pm

   3^49 * 2^14 is my guess.

   This is because every square on the board has 3 possible moves except the far right 8 squares and the top 8 squares (which both contain the upper right square, which has no possible moves).
3. 3. slavy Said：
   July 14th, 2010 at 1:30 am

   Hi, Chris. I have a question regarding the diagonal moves – so if we make an up move and then a right move, do we have the freedom to choose whether these are two moves or one diagonal one, or it is always the second type?
4. 4. Chris Said：
   July 14th, 2010 at 1:50 am

   An up followed by a right is distinct from a diagonal.
5. 5. Anonymous Said：
   July 14th, 2010 at 1:54 am

   Chess Moves

   Starting at the bottom left-hand corner of a chessboard, how many different ways are there of moving to the top right-hand corner if

   (a) You can move only one square at a time and
   (b) You can move bottom to top, left to right or a diagonal combination of the two? (Each counts as one move))

   Given an 8×8 board start at 1,1

   it requires 7 Up or “U” moves and 7 right or “R” moves. A diagonal “D” move will replace one U and one R move.

   With 0 D moves UUUUUUURRRRRRR and all it’s permutations get to the “finish”
   #permutations= 14!/(7!*7!*0!)=3432

   With 1 D moves DUUUUUURRRRRR and all it’s permutations get to the “finish”
   #permutations= 13!/(6!*6!*1!)=12012

   With 2 D moves DDUUUUURRRRRR and all it’s permutations get to the “finish”
   #permutations= 12!/(5!*5!*2!)=16632

   with 3 D moves DDDUUUURRRR and all it’s permutations get to the “finish”
   #permutations= 11!/(4!*4!*3!)=11550

   with 4 D moves DDDDUUURRR and all it’s permutations get to the “finish”
   #permutations= 10!/(3!*3!*4!)=4200

   with 5 D moves DDDDDUURR and all it’s permutations get to the “finish”
   #permutations= 9!/(2!*2!*5!)=756

   with 6 D moves DDDDDDUR and all it’s permutations get to the “finish”
   #permutations= 8!/(1!*1!*6!)=56

   with 7 D moves DDDDDDD and all it’s permutations get to the “finish”
   #permutations= 7!/(0!*0!*7!)=1

   Sum of all these results=3432+12012+16632+11550+4200+756+56+1=48639

   Given the choice of U,D,R moves there are 48639 way of going from bottom left corner of a chess board to the upper right corner.

   Cam
6. 6. slavy Said：
   July 14th, 2010 at 2:00 am

   I agree with Cam
7. 7. Chris Said：
   July 14th, 2010 at 2:10 am

   Nice one Cam. I hadn’t expected that analysis. 48639 it is.

   There is another way. It will give all the numbers of paths for all the rectangular chess boards in one table. e.g. for a 2*3 chess board. And it can be readly extended to larger boards.
8. 8. Chris Said：
   July 14th, 2010 at 4:04 pm

   Unless you specify that you can’t touch the same square twice or anything the moves are infinite. You can keep moving around the chess board.
9. 9. Chris Said：
   July 14th, 2010 at 4:08 pm

   @Chris (other). It is not possible to visit a square more than once with the given rules.
10. 10. tullotoe Said：
    July 14th, 2010 at 9:52 pm

    I apologize for being dumb, but I am not seeing how Cam goes from 3432 on an 8×8 board to 12012 on a 7×7 board and 16632 ona 6×6 board.

    Not really appreciating your | notation, and simply contemplating the problem, I find it har to believe the solutions increate as the effective board decreases.

    Could you please be more eplicit with your solution for the slower among us?
11. 11. Chris Said：
    July 14th, 2010 at 10:15 pm

    @tullotoe. Cam was only using a 8×8 board. He was considering all paths across the board when 7 diagonal moves were made, then when exactly 6 diagonal move was made etc., all the way through to 0 diagonal moves were made.

    For 7 diagonal moves there is only 1 path (of 7 steps) and that’s taking the diagonal straight line from the bottom left to the top tight corner.

    If no diagonal moves are made, then each path will have 7 up and 7 right moves to get to the other corner (14 moves in total); they can be taken in any order. If you make 1 diagonal move, then you need 6 up and 6 right moves (13 in moves total). Each diagonal move takes away 1 up and 1 right move. All Cam was doing is calculating the combinations and adding them together.

    If D, U and R are the number of moves of each type taken, then the number of paths that can be chosen is: (14-D)!/(U! * R! * D!). NB U = R = (7-D) in all cases, so you end up with (14-D)!/((7-D)! * (7-D)! * D!). I could have written U+R+D instead of 14-D. e.g. If D = 3, then the total number of paths is 11!/(4! * 4! * 3!)

    That lot has to be summed for D = 0 to 7 to get the grand total number of possible paths. Does that help you?

    PS I have re-examined this page, I think Cam’s explanation is clearer than mine, but ‘ll leave it just in case …
12. 12. Chris Said：
    July 15th, 2010 at 5:21 am

    … taking the case of 6 D, and 1 U and 1 R we have DDDDDDUR, DDDDDDRU, DDDDDRDU, DDDDDRUD, DDDDDURD, DDDDDUDR … and that goes on to give 56 (unique) combinations altogether.
13. 13. Chris Said：
    July 15th, 2010 at 7:17 am

    Another way to do this is to start at the bottom left corner and consider how many ways there are to get to the current square. You can then buid up the number of paths by adding the number of paths from the left, backward diagonal and below square. I’ve padded with 0s to get the layout right.

    1 15 113 575 2241 7183 19825 48639
    1 13 085 377 1289 3653 08989 19825
    1 11 061 231 0681 1683 03653 07183
    1 09 041 129 0321 0681 01289 02241
    1 07 025 063 0129 0231 00377 00575
    1 05 013 025 0041 0061 00085 00113
    1 03 005 007 0009 0011 00013 00015
    1 01 001 001 0001 0001 00001 00001

    The numbers represent the number of paths that can be found to get to the given square.

    These numbers are known as Delannoy numbers. http://mathworld.wolfram.com/DelannoyNumber.html
14. 14. Anonymous Said：
    July 15th, 2010 at 10:22 am

    Wow, I really like that method Chris. It’s a peace of cake to use that on a spreadsheet for any size rectangle, and it’s nice that it’s iterative.

    I don’t think it would be my choice of method by hand, but with a computer, I think I’d use your method. I think being able to see the numbers build up in a meaningful way makes the result easier to understand, and to verify. Nice job.

    Cam
15. 15. Chris Said：
    July 15th, 2010 at 10:36 am

    Hi Cam. Thank you for the compliment. I came up with it as the method by hand.

    Here’s the (copy and pasted) rest of what I know:
    I did a Google with “48639 chess” and came across a paper that showed the expression corresponding to the “squared” Pascal’s triangle is:
    g(n,r) = Sum[a=0 to r, 2^a * c(n,a) * c(r,a)]

    where c(a,b)=a!/((b-a)!b!)

    The result we want is g(7,7)=48639

    The link to the paper is:
    http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1102913231

    There’s a link (near the top left) to a pdf and djvu copy of the paper.

    Here’s my Mathematica code and output (going to 9*9 board):
    For[n = 0, n < 9, n++,
    Print[Table[
    Sum[2^a Binomial[n, a] Binomial[r, a], {a, 0, n}], {r, 0, n}]]]

    {1}
    {1,3}
    {1,5,13}
    {1,7,25,63}
    {1,9,41,129,321}
    {1,11,61,231,681,1683}
    {1,13,85,377,1289,3653,8989}
    {1,15,113,575,2241,7183,19825,48639}
    {1,17,145,833,3649,13073,40081,108545,265729}

    Greetz
16. 16. Chris Said：
    July 16th, 2010 at 5:27 am

    @tullotoe. I just re-read your comment. Cam is using an exclamation mark ! (not a |). ! is the factorial symbol. e.g. 5! = 5*4*3*2*1.

    Special case(s) are 1! = 1 and 0! = 1 (surprisingly).

    This site seems to be using the “MS Reference Sans Serif” font (9 point). It is horrible for maths.

Post a reply