Technology Review March/April 2011 Problem 2

On an infinite chessboard an Obamaknight can move six spaces in any direction, then turn left and move one space. For example, from (5,-3) he can move to N-W to (4,3) followed by two moves E-N ending at (16,5). Place a finite number of Obamaknight on the board so that (allowing an arbitrary number of moves):
i. no one of them can reach any other one of them
ii. any position on the board can be reached by one of them

Extension: a modern Obamaknight moves six spaces in any direction, then turns left or right and moves one space. Place a finite number of modern Obamaknights with the above properties.

Solution to original problem:

We begin by noticing that the moves are commutative. When two moves are swapped, the ending position is still the same. There are only four possible moves: N-W, E-N, S-E, and W-S. Furthermore, each pair of N-W and W-S "cancel out", and so do E-N and W-S. So each sequence of moves is equivalent to $a$ moves of N-W followed by $b$ moves of $E-N$ for some integers $a,b$.

If we start at $(0,0)$, and make $a$ moves of $N-W$ + $b$ moves of $E-N$, we will end up at $(-a+6b ,6a+b)$. If we vary $a,b$ over all possible integers, we will get a grid of parallelograms, where one parallelogram has vertices at cells $(0,0), (-1,6), (6,1), (5,7)$. Any cell in this grid (that is, any cell that serves as a vertex of a parallelogram in this grid) can be reachable from $(0,0)$ with proper choice of $a$ and $b$. Conversely, the knight can only reach those cells that are part of the grid.

If we start at $(1,0)$ and repeat the process above, we get a similar grid, except everything is shifted one cell to the east.

Thus, the answer to the original problem is simply how many cells are in the one parallelogram described above. If we put the knights to fill up that parallelogram, they will all reach different cells, and collectively able to reach any cell.

I can't draw the grid and the cells here, but there are 30 such cells. You can convince yourself by drawing the grid, but the cells in the rectangle with vertices $(0,1),(5,1),(0,5),(5,5)$ cover them all. Each cell in that rectangle is not reachable from any other cell in that rectangle, and collectively those cells cover the entire board, since the rectangle can be "copied and stamped" around.

Solution to the extension problem:

One crucial fact about the original problem is that the number of elementary moves are the same as the dimensionality of the board. The board is in 2-D, while there are 2 elementary moves. In the extension problem, we now have four elementary moves (N-W, N-E, E-N, E-S). So the same analysis won't work.

Instead, we attempt to reconstruct a move of "one to the right" by using a finite number of those four moves. Indeed, we could.

$$3 \times (6,1) -3 \times(6,-1) - (-1,6) = (1,0)$$

Thus, 3 moves of E-N followed by 3 moves of W-N followed by S-E results in one move to the right. Using similar technique, one can construct a move of one to the top/left/bottom, and then reach any position on the board. Therefore, one Obamaknight is enough.

Solution: Coupon drawing

Original problem here: http://dharmath.thehendrata.com/2010/01/12/coupon-drawing/

A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?

Challenge: what is the probability that the process ends after exactly $M$ draws?

Stones and Marbles

There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.

At each step, Bob is allowed to either:

1. take a stone from one box, a marble from another box, and put them on the third box

2. add or subtract all boxes by the same number of stones

3. add or subtract all boxes by the same number of marbles

Prove or disprove, that by repeating these steps, Bob can empty all three boxes.

Coin Toss

A boy tosses a fair coin repeatedly. Every time he gets a Head, he earns 1 penny, and every time he gets a Tail, he earns 2 pennies. He starts with no money. Prove that the probability of him at one time having exactly $n$ pennies is $\frac{2+(-\frac{1}{2})^n}{3}$