Monday, July 22, 2013

How many ways can you cross a game board?

Let's say you're on the top right corner of a chess board, and you want to cross to the bottom right corner.  You've discovered a new chess piece that can only move right or down each move.  How many different ways are there to get from the top right to the bottom left?


Well, let's look at a few obvious solutions:
You could go all the way to the right border, then down:
RRRRRRRDDDDDDD

You could go all the way down then right across the bottom border:
DDDDDDDRRRRRRR

You could go stair-shaped:
DRDRDRDRDRDRDR

But because you can't go up or right, every solution is 14 steps long, and every solution is just a reordering of seven Down moves and seven Right moves.

So naively, the solution is 14! : 14 moves, in any order. The problem with that solution is, you can't tell down-number-three from down-number-six.

So, to take out the different (equivalent) ways you could order the downs, you get:
14! / 7!

Then to take out the equivalent ways you can order the rights, you get:
14! / 7! / 7!

The solution holds for any board size greater than 1x1:
(width - 1 + height - 1)! / (width - 1)! / (height - 1)!