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?
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 |
solution: computer used, to avoid tedium
