All roads lead to Rome
Consider a chessboard. For those that might not be familiar with chess, a (classic) chessboard is made out of 64 squares (8 rows and 8 columns).
Suppose that the board is clear of any piece, except for the king, which you place at the lowest left corner (the red square A1). You goal is to move around the king to get to the upper right corner (the red square H8). But there are rules: you are only allowed to move either to the right or up (and hence, never diagonally or to the left or down).
How many different paths are there that satisfy those constraints and travel from A1 to H8?
Bonus : Can you generalize to an m × n chessboard?
The answer is 3432.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I, too, used the binomial coefficient to solve it. However, as a chess hobbyist, the first thing I noticed is that you refer to the corners as 1a and 8h. I have exchanged match histories with people from around the world, but have always seen squares notated by file first, rank second (e.g. f7, c5, a8, etc.). Are squares notated by rank first, file second in some parts of the world?
Also, your general solution is slightly off: instead of
(
n
m
+
n
)
, it should be
(
n
−
1
m
+
n
−
2
)
.
This is because if the board is
n
×
m
, then there are
(
n
−
1
)
moves in one direction and
(
m
−
1
)
moves in the other. This is verified by the
8
×
8
case in the problem.
Log in to reply
yep, my apologies. I will correct it straight away!
Hi Patrick, I think there is still an error in the last line of you solution , I think you mean ( n − 1 m + n − 2 ) instead of ( n − 1 m + m − 2 ) , right ?
Log in to reply
It actually says ( n − 1 n + m − 2 ) now, just the top-right edge of the C is very close to the n , so it looks like an m . If you zoom in very very close to the C , you can see that it is actually an n .
Log in to reply
Yeah, you are right .
Log in to reply
@A Former Brilliant Member – i put a little space. it's clearer now ;)
Good solution. I posted a variation of this question some time ago, in which the playing piece can also be moved diagonally upward as well. (I probably should have made the playing piece a king rather that a pawn; some chess aficionados took exception to having a pawn moving this way.) Give it a try if you're interested. :)
Evidently, to reach both corners, we will need by the end of the day to move the king 7 times to the right and 7 times up. So, it will take 14 steps to connect both corners.
Hence, we simply need to determine when we will move the king up (to the right works as well!). Hence, the number of possibilities is : C 7 1 4 = 7 ! 7 ! 1 4 ! = 3 4 3 2 .
In general, the answer is : C n − 1 n + m − 2 ( = C m − 1 n + m − 2 )