UKC

Given a chessboard (8 x 8 square grid) and a piece which is only allowed to move one square upwards or rightwards (it cannot move diagonally, downwards or left).

The piece starts in the bottom left corner of the board and you have to move it to the top right corner. There are clearly lots of ways to do this, and they all require 14 moves.

The question is: Exactly how many different paths may be taken by this piece to get from the bottom left corner of the board to the top right?

In reply to Paul Robertson:

This is a 3d chessboard then?

In reply to Paul Robertson:
1000000000000
in binary

In reply to elsewhere:

Are you sure? Seems high, I had a much smaller number in mind but haven't sorted a proof yet.

In reply to Paul Robertson:
3432

lcb

In reply to JJL:


Yup. 14 choose 7.

In reply to Ramblin dave:


Agreed.

There must be exactly 7 up moves and 7 right moves.

The up moves can be on any 7 of the fourteen moves. So it's the number of ways you can choose 7 numbers from the numbers 1 - 14. No repeated numbers allowed, and the order in which they appear doesn't matter.

http://www.mathsisfun.com/combinatorics/combinations-permutations-calculato...

Martin

In reply to Martin Hore:

Ok, Well done.

So what if the grid measures 10 x 8 squares?

The puzzle was inspired by the headstone of John Renie in Monmouth Churchyard. Three websites give three different answers to what is essentially this puzzle. One is correct but none of them offer a proof.

In reply to Reach>Talent:
14 moves, each move is a binary choice between "go right" or "go up".

2^14 is 100000000000000 in binary (I counted the zeroes incorrectly earlier)

I calculate 16384 in decimal.

In reply to elsewhere:

No, because once you've gone "up" seven times your remaining choices all have to be "go right".

Martin's explanation is spot on.

In reply to Ramblin dave:
That makes sense.

In reply to elsewhere:

You can only "go right" seven times. Likewise you can only go up "seven times".

In reply to Paul Robertson:


16 choose 7 or 16 choose 9, I guess. Should give the same answer - 16!/(7!*9!) I think . Quick reply before I exit to climb some gritstone this weekend - a fair drive from Ipswich!

Thanks for getting us thinking.

Martin

In reply to Martin Hore:

That's a really elegant and simple explanation, thanks!

In reply to Paul Robertson:




11440