Advanced Coloring Techniques in Olympiad Problems

When Two Colors Are Not Enough

Consider this problem: Can a 10x10 board be tiled with 1x4 rectangular tiles (tetrominoes)?

Let's try our 2-coloring from the last lesson. A 10x10 board has 100 squares, so it has 50 black and 50 white squares. A 1x4 tile, placed on a checkerboard, will always cover 2 black and 2 white squares. To tile the board with 25 such tiles, we would need 25 * 2 = 50 black squares and 25 * 2 = 50 white squares. The numbers match perfectly!

Does this mean a tiling is possible? Not necessarily. The 2-coloring simply fails to give us a contradiction. This is a sign that we need a more refined tool. When a problem involves a number k (like the 1x4 tile), it's a strong hint that coloring with k colors, or using arithmetic modulo k, might be the key.

Coloring with Modular Arithmetic

Let's generalize. A standard way to color a board with k colors is to assign a color to the square at position (i, j) based on its coordinates. A simple yet effective scheme is to color (i, j) with the color j mod k.

Now, let's go back to the 10x10 board and 1x4 tiles. We'll color the board with 4 colors, labeling them 0, 1, 2, and 3. Let's assign color j mod 4 to each square in column j (for j from 0 to 9).

1. Analyze the Board:

   • Columns 0, 4, 8 will be color 0. Each column has 10 squares. So, 30 squares of color 0.
   • Columns 1, 5, 9 will be color 1. So, 30 squares of color 1.
   • Columns 2, 6 will be color 2. So, 20 squares of color 2.
   • Columns 3, 7 will be color 3. So, 20 squares of color 3.
     The board has an unequal number of colors: (30, 30, 20, 20).

2. Analyze the Tile:

   • If we place a 1x4 tile horizontally, it covers four consecutive columns. Its squares will have colors j, j+1, j+2, j+3 (mod 4), which means it covers exactly one square of each color (0, 1, 2, 3).
   • If we place it vertically, all its squares are in the same column, so they all have the same color.

3. The Contradiction:
   Let's suppose a tiling exists. Let h_i be the number of horizontal tiles and v_i be the number of vertical tiles covering only color i. To cover the entire board, the number of squares of color 2 must equal the number of squares of color 0. But our board has 20 squares of color 2 and 30 squares of color 0. This is a contradiction, so no such tiling is possible.

Wait, the logic is slightly flawed. A horizontal tile covers one of each color. A vertical tile covers four of one color. Let's count the total number of squares of each color covered.
Let $H$ be the number of horizontal tiles and $V_0,V_1,V_2,V_3$ be the number of vertical tiles of each color.

• Total squares of color 0: $H+4V_0=30$
• Total squares of color 1: $H+4V_1=30$
• Total squares of color 2: $H+4V_2=20$
• Total squares of color 3: $H+4V_3=20$

From the first two equations, $4V_0=4V_1$, so $V_0=V_1$. From the last two, $H=20-4V_2$. Substituting this into the first equation gives $20-4V_2+4V_0=30$, which simplifies to $4(V_0-V_2)=10$. This implies $V_0-V_2=10/4=2.5$. But the number of tiles must be an integer. This is a contradiction. Therefore, the tiling is impossible.

This technique of coloring with k colors is a powerful generalization of the checkerboard pattern.

Assigning "Weights" Instead of Colors

We can take this idea even further. Instead of abstract "colors," we can assign numbers—or "weights"—to each square. This allows us to use arithmetic to find invariants. A common strategy is to choose weights such that any tile placed on the board covers a total weight of 0. If the total weight of the entire board is not 0, then a tiling is impossible.

A beautiful demonstration of this is using complex numbers, specifically roots of unity.

The core idea from the reading is:

• Let $\omega =e^{2\pi i/k}$ be a primitive $k$-th root of unity. A key property is that $1+\omega +{\omega }^2+\cdots +{\omega }^{k-1}=0$.
• To test if an m x n board can be tiled by 1 x k tiles, assign the weight ${\omega }^{i+j}$ to the square at (i, j).
• A horizontal 1 x k tile starting at (i, j) covers squares with weights whose sum is ${\omega }^{i+j}+{\omega }^{i+j+1}+\cdots +{\omega }^{i+j+k-1}={\omega }^{i+j}(1+\omega +\cdots +{\omega }^{k-1})=0$. A similar argument holds for vertical tiles.
• Therefore, any tile covers a total weight of 0. If the board can be tiled, the sum of all weights on the board must be 0.
• The total weight of the board is the product of two geometric sums: $$\left(\sum _{i=0}^{m-1}{\omega }^i\right)\left(\sum _{j=0}^{n-1}{\omega }^j\right)$$
• This product is zero if and only if one of the sums is zero. The sum ${\sum }_{i=0}^{m-1}{\omega }^i=0$ if and only if k divides m.
• This gives us the famous result: an m x n rectangle can be tiled by 1 x k tiles if and only if k divides m or k divides n.

This is a quintessential Olympiad-level proof: it uses a more advanced mathematical structure (complex numbers) to find a simple and elegant solution.

Modular Arithmetic as a General Heuristic

The principle of using modular arithmetic isn't confined to grid problems. It's a fundamental problem-solving technique for finding constraints in equations involving integers. The strategy is to choose a modulus that makes parts of an expression simpler—often reducing terms to 0, 1, or -1.

This video analyzes a Putnam exam problem and provides a masterclass in how to strategically choose your "colors" (moduli) to crack an equation.

The strategy here is identical to our coloring approach. In the mutilated chessboard problem, we chose 2 colors because the tile had length 2. Here, we choose mod a and mod (a+1) because the equation's bases are a and a+1. We choose mod 3 because the constant term is divisible by 3. The underlying principle is to choose a structure (a coloring scheme, a modulus) that interacts neatly with the constraints of the problem.

Practice Problems

Now it's your turn to apply these more advanced coloring methods. Think about what property you want to use as your "color" — remainders mod k? Powers of 2? Coordinates?

1. Revisiting a Classic: Prove that a 6x6 board cannot be tiled by 1x4 tiles.
   (Hint: Use a 4-coloring. You can do this with numbers 0,1,2,3 or with roots of unity. Try to write down the argument formally.)

2. (Russia 1996) A 5x7 board is covered by L-trominoes (3 squares in an L-shape) in several layers, such that each square of the board is covered by the same number of trominoes. Prove this is only possible if the number of layers is a multiple of 3.
   (Hint: Color the board with 3 colors. A standard c(i,j) = (i+j) mod 3 coloring won't work for an L-tromino. Try a coloring where c(i,j) = i mod 3. How many squares of each color does an L-tromino cover, regardless of orientation?)

3. (Another Tiling Problem) Is it possible to tile a 4x4 grid using one 2x2 square tile and four L-shaped tetrominoes? An L-tetromino is a 2x2 square with one 1x1 square removed.
   (Hint: Consider a non-standard 2-coloring. Try coloring some rows black and others white.)

Tackle these problems by first identifying the "board" and the "tiles." Then, ask yourself: What coloring scheme will reveal an invariant property of the tiles?

Conclusion

Today, we've elevated coloring from a simple trick to a versatile and powerful method. The main takeaway is that "coloring" is the art of assigning properties to elements of a set to reveal hidden structures. These properties don't have to be limited to just two colors; they can be integers mod k, real-numbered weights, or even complex numbers. By carefully choosing a coloring that simplifies the action of our "tiles" (or algebraic terms), we can often transform a difficult combinatorial problem into a simple counting argument or an algebraic contradiction.

This concludes our module on invariants, monovariants, and coloring. You now have a formidable set of tools for proving possibility or impossibility. In our next module, we will shift gears. We'll move from questions of existence to questions of enumeration by introducing Recurrence Relations and Generating Functions, which will allow us to start tackling problems like the "pizza cutting problem" you mentioned at the beginning of the course.