All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Going North-East (Posted on 2014-12-05) Difficulty: 3 of 5
On a 10x10 "chessboard" a token is placed on the leftmost square of the bottom line a.k.a. a1.
You can move said token either one step to the right or one step up within the same column or one step diagonally (combining right and up).
To make it clear from c4 you may advance in one step to c5, c6 or d6.

How many distinct routes exist to reach the top line's rightmost square (i.e. j10?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution: computer used, to avoid tedium | Comment 1 of 4
There's only one way to start out: in the lower left corner. Expanding outward from there, the number of ways of getting to each square is the sum of the ways of getting to the square to the left, the square diagonally to the lower left, and the square below:

       1      19     181    1159    5641   22363   75517  224143  598417 1462563
       1      17     145     833    3649   13073   40081  108545  265729  598417
       1      15     113     575    2241    7183   19825   48639  108545  224143
       1      13      85     377    1289    3653    8989   19825   40081   75517
       1      11      61     231     681    1683    3653    7183   13073   22363
       1       9      41     129     321     681    1289    2241    3649    5641
       1       7      25      63     129     231     377     575     833    1159
       1       5      13      25      41      61      85     113     145     181
       1       3       5       7       9      11      13      15      17      19
       1       1       1       1       1       1       1       1       1       1
       
       
There are thus a total of 1,462,563 ways to get to the northeast corner.

Rather than tediously doing the additions:

Private Sub Form_Load()
 ChDir "C:\Program Files (x86)\DevStudio\VB\projects\flooble"
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
 DoEvents
 
 gr(0, 0) = 1
 For row = 1 To 10
 For col = 1 To 10
   gr(row, col) = gr(row - 1, col) + gr(row, col - 1) + gr(row - 1, col - 1)
   Text1.Text = Text1.Text & mform(gr(row, col), "#######0")
   
 Next
 Text1.Text = Text1.Text & crlf
 Next
   
 Text1.Text = Text1.Text & " done"
End Sub

which goes from top-left to bottom-right, but the output was sorted in reverse order to fit the puzzle's direction of travel.

  Posted by Charlie on 2014-12-05 09:40:23
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information