In chess, a knight moves in L-shaped jumps consisting of two squares along a row or column plus one square at a right angle. If it can only move up the board, how many routes can it take to reach any square on the top row of the board?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ So the knight starts where it usually starts, and you want the number of ways it can reach the top row? $\endgroup$– greenturtle3141Sep 25, 2016 at 23:47
-
$\begingroup$ Yes, the knight starts at the second square of the bottom row and all the ways it can reach the top row. Thanks. $\endgroup$– wohc notnaSep 25, 2016 at 23:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
The easiest way to do this, I think, is
just to fill in the number of routes from the top row (where the number is already 1: you're on the top row and there's only one way to get to the top row, namely by making no moves) downward: at each stage, you put in each square the sum of the numbers in the squares you can move to from there. It's quicker and more reliable to do it with a computer, but it's well within the range of reasonable hand calculation.
The answer is
269
and here are the calculations:
1 1 1 1 1 1 1 1 1 1 2 2 2 2 1 1 3 4 5 5 5 5 4 3 6 8 11 13 13 11 8 6 15 21 28 29 29 28 21 15 36 46 65 73 73 65 46 36 86 116 159 168 168 159 116 86 205 269 373 413 413 373 269 205
answered Sep 26, 2016 at 2:17
-
$\begingroup$ I think the second row should contain digits 2 and 4. Oh, but wait... $\endgroup$– MatsmathSep 26, 2016 at 6:44
-
$\begingroup$ In the calculation diagram, each number seems to be roughly 2.5 times the one above it, maybe just a little less. Do you think there's some definite value the ratio might be approaching, given a larger board? $\endgroup$– BassDec 15, 2017 at 10:16
-
3$\begingroup$ Yes, there will certainly be some such value. If we represent two successive rows by an 8-element vector (we only need 8 elements, not 16, because of symmetry) then moving down one row is achieved by multiplying that vector by a certain 8x8 matrix. Then, barring improbable coincidences, everything will grow at a rate given by the largest eigenvalue of that matrix. $\endgroup$– Gareth McCaughan ♦Dec 15, 2017 at 14:21
-
$\begingroup$ Oh, I realise that that assumes the board is only getting larger in one dimension, so it's 8xn and n is increasing. If we consider an nxn board, I bet some limit-y thing is still true, but it's not so straightforward. $\endgroup$– Gareth McCaughan ♦Feb 19, 2021 at 16:26
-
2$\begingroup$ If my calculations are correct (which they might be), then for an 8-wide board the actual ratio approaches a root of a degree-7 polynomial which is approximately 2.39, versus 1+sqrt(3) ~= 2.73. Numerical experimentation suggests that for the limit of large square boards the edge effects do go away and you get 1+sqrt(3). $\endgroup$– Gareth McCaughan ♦Feb 20, 2021 at 1:51