Maths Olympiad Prep

Library / /60 of 520

Combinatorics Difficulty 6.4 National olympiad Find the answer

Find the number of ways to color n×mn \times m board with white and black
colors such that any 2×22 \times 2 square contains the same number of black and white cells.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to ensure that any 2×22 \times 2 square on the n×mn \times m board contains exactly two black cells and two white cells. This constraint implies that the coloring must follow a specific pattern.

1. Identify the possible patterns:
- The 2×22 \times 2 square constraint can be satisfied by alternating colors in a checkerboard pattern. There are two basic checkerboard patterns:
- Pattern 1: Start with a black cell in the top-left corner.
- Pattern 2: Start with a white cell in the top-left corner.

2. Extend the patterns to the entire board:
- For Pattern 1, the board will look like:
BWBWWBWBBWBWWBWB \begin{array}{cccc} B & W & B & W & \cdots \\ W & B & W & B & \cdots \\ B & W & B & W & \cdots \\ W & B & W & B & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}
- For Pattern 2, the board will look like:
WBWBBWBWWBWBBWBW \begin{array}{cccc} W & B & W & B & \cdots \\ B & W & B & W & \cdots \\ W & B & W & B & \cdots \\ B & W & B & W & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{array}

3. Count the number of ways to alternate colors:
- There are 2 ways to alternate colors vertically (starting with either black or white in the first row).
- There are 2 ways to alternate colors horizontally (starting with either black or white in the first column).
- There are 2 ways to alternate colors diagonally (starting with either black or white in the first cell).

4. Combine the patterns:
- However, the vertical and horizontal alternations are not independent. The diagonal alternation is also not independent of the vertical and horizontal alternations. Therefore, we need to consider the unique patterns that satisfy the 2×22 \times 2 constraint.
- The two basic checkerboard patterns (Pattern 1 and Pattern 2) are the only valid patterns that satisfy the 2×22 \times 2 constraint.

Thus, there are only 2 valid ways to color the n×mn \times m board such that any 2×22 \times 2 square contains the same number of black and white cells.

The final answer is 2\boxed{2}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.