## Wednesday, April 8, 2015

### chessboard manhattan move

Given a $2015 \times 2015$ chessboard, a pawn is placed at the bottom left corner. At each turn, the pawn may move one, two, or three squares to the right or to the top, and the goal is to reach the top right corner. The rules are: If the previous move was to the top, then the next move must be to the right. If the previous move was to the right, then the next move must be to the top. The pawn may not move to the left or to the bottom at any point. The difference of length between each two adjacent moves must be exactly 1. How many legal paths are there for the pawn to reach the top right corner?