9
$\begingroup$

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?

$\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$ – greenturtle3141 Sep 25 '16 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 notna Sep 25 '16 at 23:55
17
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ I think the second row should contain digits 2 and 4. Oh, but wait... $\endgroup$ – Matsmath Sep 26 '16 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$ – Bass Dec 15 '17 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 '17 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 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 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.