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.

Coins in equilateral lattice

$n(n+1)/2$ coins are placed on an equilateral lattice with side $n$, such that all but one coin are showing heads.

At each step, one is allowed to choose two adjacent coins $A$ and $B$, and then flip all coins on the line $AB$ (and its extension).

Characterize all starting configuration such that it's always possible to get all tails.

Triangular (and tetrahedral) lattice

An equilateral triangle $ABC$ with side $n$ a positive integer is divided into triangular lattice consisting of unit triangles.

Each point on the lattice is colored red, white, or blue such that:
1. No point on $AB$ is colored red
2. No point on $BC$ is colored blue
3. No point on $AC$ is colored white

Prove that there exists a unit triangle whose vertices are colored with 3 different colors.

Challenge problem: Same problem but for tetrahedron and four colors.

Solution

We first state the one-dimensional version of this problem:

Given a sequence of points on a line colored red or blue, and the first point must be colored red, and the last point must be colored blue, then we have an ODD number of segments that has two differently-colored end points.

This one-dimensional version is trivial to prove.

Now we turn to the 2-dimensional version as stated in the problem.
For each side that has both red and blue endpoints, we "mark" that side.
Then for each unit triangle, we give it a score based on how many marked sides it has. Now, if we consider the "outside" area as another "surrogate unit triangle", then we can also give it a score based on how many marked sides are facing the outside.

First, note that the total score of all areas must be even, since any marked side contribute one score to two areas.

Now, applying the 1-dimensional version of the problem, we know that side AC has an odd number of marked sides. Side AB and BC does not have any marked sides. So the outside area has an odd score. Thus, there is an odd number of unit triangles that has an odd score. In order for a unit triangle to have an odd score, it must have three differently-colored vertices.

Chess Board Coloring

Each cell in an infinite chess board is colored with one of the $n$ available colors. Prove that we can always find a rectangle such that all four corners have the same color.

Advanced version: Suppose not all cells are colored, but only some of them. Furthermore, for any circle with radius R, we can always find a colored cell in that circle. Prove that we can still find a monochromatic rectangle.

Divide Colored Balls

There are $2n$ balls of each color: red, green, and blue. How many ways are there to divide them into two groups such that each group has $3n$ balls?

First Solution

It is the same as the coefficient of $3n$ in the expansion $(1+x+x^2+x^3+\cdots+x^{2n})^3$. The proof is left to the readers as an exercise.


Note that $(1+x+\cdots+x^{2n})^3 = \frac{(1-x^{2n+1})^3}{(1-x)^3} = (1 - 3x^{2n+1} + 3x^{4n+2} - x^{6n+3})(1-x)^{-3}$

But $(1-x)^{-3} = (1+3x + 6x^2 + 10x^3 + \cdots + \frac{(k+2)(k+1)}{2}x^k + cdots)$

So the coefficient of $3n$ in that expansion is:

$\frac{(3n+2)(3n+1)}{2} - 3\frac{n(n+1)}{2} = 3n^2 + 3n + 1$

Second Solution

We shall prove that there are $3n^2+3n+1 = (n+1)^3 - n^3$ ways, which has striking geometrical interpretations.

Create an equilateral triangle with altitude $3n$, and mark all the points that has integer distance to all the sides. These points will form a triangular lattice

It is a well-known fact that for any point in an equilateral triangle, the sum of distances to the sides is constant. Since the altitude of the triangle is $3n$, then for any point in that triangular lattice, the sum of distance to the sides is $3n$. Furthermore, the distances are integers. Thus, these points represent the number of ways to choose $3n$ balls from 3 colors.

However, the constraint that we only have $2n$ supply of each color is not yet enforced. We examine the points in the lattice whose distance to any of the sides is greater than $2n$, and we eliminate them. So we are left with a hexagonal lattice of side $n+1$. This is the projection of a half-shell of an $n+1$-cube that has $n$-cube carved out of it.

KBB2 Problem 3

Suppose the Cartesian plane is tiled with infinitely many square tiles such that:

1. The square tiles must have the same size and form a chessboard-like formation.

2. Each tile corner must lie on a point with integer x-coordinate and y-coordinate

3. The tile sides need not be parallel to the X or Y axis.

Given that the points $(0,0)$ and $(3,1)$ are both tile corners (not necessarily of the same tile), determine all the possible tile sizes.