Colored chessboard

An $n \times n$ chessboard is put on the table such that its sides are facing the North, East, South, and West. Each cell is then colored either with red, green, blue, or yellow paint such that:
1. The North-most cells are colored only with red or green
2. The East-most cells are colored only with green or blue
3. The South-most cells are colored only with blue or yellow
4. The West-most cells are colored only with yellow or red

Prove that there is a point that serves as a vertex to at least three squares of different colors.

Solution


For each cell that has color red, green, blue, and yellow, give it a rank of 1,2,3, and 4 respectively.

Then for each "side" (a segment of line between two cells), mark it if:
1. It delineates two cells. That is, sides that coincides with the sides of the large chess board cannot be marked.
2. Those two cells have a rank differing by exactly 1.

Now, for each vertex, give it a score as follows:
1. The score of each vertex is the number of marked sides that border it. Thus, each cell might have a score of 0, 1, 2, 3, or 4.
2. Vertices that lie on the sides of the large chess board also get their own score. These vertices cannot have a score of 4 of course, but give it a score regardless. Call these vertices the "border vertices" as opposed to "inner vertices"

We assert the following: if an inner vertex has an odd score, then it serves as a vertex to at least three squares of different colors. In other words, an inner vertex with an odd score is the vertex whose existence we seek to prove.

Indeed, it is impossible to form an inner vertex with a score of 1 or 3 with merely one or two colors. For example, if the four squares surrounding the vertex has colors R,G,G,R, then the squares would have ranks of 1,2,2,1, and there are two marked sides. The other combinations are left to the reader as an exercise.

Now, let $A$ be the sum of scores among the inner vertices, and $B$ be the total number of scores among the border vertices. $A+B$ must be even since each marked side contributes two points of score to that total.

We will show that $B$ is odd. The Northwest (NW) corner must be colored red, and the NE corner must be colored green, and the North side must be colored only red or green. Thus, the North side changes color an odd number of times, and each change of color is between a red and a green, producing an odd number of marked sides in the process. These marked sides contribute 1 point each to $B$.

The same argument can be made to the East side and the South side, but not the West side. In fact, none of the color changes on the West side contribute to $B$ at all since they're between a cell of rank 1 and rank 4. So in total, $B$ is a sum of three odd numbers, which means $B$ is odd.

Since $A+B$ is even, then $A$ is odd. That means there must be at least one inner vertex that has an odd score, showing the existence of our desired vertex.

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.