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?

Pawns on infinite chessboard

Let $k$ be a fixed integer. The cells in a $1 \times \infty$ chessboard is colored in the following fashion: ..., red, blue, green, red, blue, green, ... (and so on) There are a number of pawns on the board. At each turn, we are allowed to choose two pawns $A,B$ and make $A$ "jump over" $B$ so that the new distance is $k$ times the old distance. Formally, we may choose $A$ and $B$ with distance $d$ and move $A$ so that the new distance is $kd$ and $A$ is on a different side of $B$. Multiple pawns may occupy a single cell. Determine all values of $k$ such that, regardless of initial configurations, it's always possible to move the pawns to all occupy the same color.

Circles on a sphere

Given a sphere of radius $R$, we draw 2015 circles with radius $R$ on it, such that there are no three circles that all meet in one point. It's easy to see that there will be $2^{2015}$ regions created on the sphere surface. Prove that we can color each region with black or white so that no two adjacent regions are colored the same and the total area painted black is the same as the total area painted white.