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

 Going North-East (Posted on 2014-12-05)
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: 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:

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

 Search: Search body:
Forums (0)