7
$\begingroup$

In chess, a knight moves in L-shaped jumps consisting of two square along a row or column plus one square at a right angle. It can only move upwards. How many routes can it take to any square on the top row of the board?

$\endgroup$
  • 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
14
$\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$
  • $\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
  • 1
    $\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

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.