IMO 2016 Problem 2

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m59s

Problem

Find all integers $n$ for which each cell of $n \times n$ table can be filled with one of the letters $I,M$ and $O$ in such a way that:


- in each row and each column, one third of the entries are $I$, one third are $M$ and one third are $O$; and - in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are $I$, one third are $M$ and one third are $O$.

Note. The rows and columns of an $n \times n$ table are each labelled $1$ to $n$ in a natural order. Thus each cell corresponds to a pair of positive integer $(i,j)$ with $1 \le i,j \le n$. For $n>1$, the table has $4n-2$ diagonals of two types. A diagonal of first type consists all cells $(i,j)$ for which $i+j$ is a constant, and the diagonal of this second type consists all cells $(i,j)$ for which $i-j$ is constant.

Exploration

The constraints impose a rigid global balancing condition. Each row and column of an $n \times n$ array must contain exactly $\frac{n}{3}$ entries of each of the symbols $I,M,O$, so a necessary condition is that $n$ is divisible by $3$.

The diagonal condition applies only to diagonals whose length is a multiple of $3$. A diagonal of either type has length at most $n$, so whenever $n \equiv 0 \pmod 3$, many diagonals must also satisfy the same balance condition. This suggests strong periodic structure, reminiscent of Latin squares with additional diagonal constraints.

For small cases, $n=3$ is feasible by a standard $3 \times 3$ Latin square pattern. For $n=6$, one can suspect a block construction using $3 \times 3$ patterns tiled periodically, preserving row and column balance. This suggests that all multiples of $3$ might work.

A potential obstruction would be compatibility between diagonals of different lengths, especially those of length $3k$ that cut across block boundaries. However, periodic $3 \times 3$ constructions are naturally invariant under shifts along diagonals of slope $1$ and $-1$, so they are promising.

Thus the conjecture is that all positive integers divisible by $3$ work, and no other $n$ do.

Problem Understanding

This is a Type A problem: we must determine all integers $n$ for which a certain $n \times n$ grid can be filled with $I,M,O$ satisfying uniform distribution conditions in every row, column, and in diagonals whose length is divisible by $3$.

Each row and column must contain exactly one third of each symbol, forcing $n$ to be divisible by $3$. The diagonal condition adds a global constraint but is only activated on diagonals of length divisible by $3$.

The expected answer is that exactly those $n$ divisible by $3$ work. The intuition is that a $3 \times 3$ Latin square can be repeated periodically across the grid in a way that preserves all required balances, including on diagonals whose lengths are multiples of $3$.

Thus the goal is to prove two statements: if such a filling exists then $3 \mid n$, and if $3 \mid n$ then such a filling can be constructed.

Proof Architecture

First lemma states that $3$ divides $n$, derived from row counting.

Second lemma constructs a valid filling for $n=3k$ using a periodic assignment $A_{i,j} = f(i+j \bmod 3, i-j \bmod 3)$ induced by a $3 \times 3$ Latin square structure.

Third lemma verifies that every row and column contains exactly $k$ of each symbol.

Fourth lemma verifies that every diagonal of length divisible by $3$ also contains equal numbers of each symbol, using periodicity modulo $3$.

The hardest part is the diagonal verification, since diagonals mix residue classes in a nontrivial way.

Solution

Lemma 1

If the table satisfies the row condition, then $3$ divides $n$.

Each row contains exactly $\frac{n}{3}$ entries of each of $I,M,O$, hence $\frac{n}{3}$ must be an integer. Therefore $n$ is divisible by $3$. ∎

This establishes that any admissible configuration forces a global arithmetic restriction, and no assumption about diagonals is needed for this obstruction.

Lemma 2

For every positive integer $k$, there exists a filling of a $3k \times 3k$ table satisfying all row, column, and diagonal conditions.

Consider a $3 \times 3$ Latin square on symbols $I,M,O$, for example

$$\begin{matrix} I & M & O \ M & O & I \ O & I & M \end{matrix}$$

Define a $3k \times 3k$ table by setting the entry at $(i,j)$ equal to the entry of the above $3 \times 3$ square at position $(i \bmod 3, j \bmod 3)$, where residues are taken in ${0,1,2}$ and matched with indices ${1,2,3}$.

This construction is well-defined for all $k$ and assigns a symbol to every cell of the $3k \times 3k$ grid.

This establishes a globally periodic candidate configuration, whose correctness reduces to verifying uniformity along residue classes.

Lemma 3

In the construction of Lemma 2, every row and every column contains exactly $k$ occurrences of each symbol.

Fix a row index $i$. As $j$ ranges from $1$ to $3k$, the residue $j \bmod 3$ takes each value exactly $k$ times. In the fixed row $i$, the symbol depends only on $j \bmod 3$, and within a full residue class modulo $3$, each symbol $I,M,O$ appears exactly once in the base $3 \times 3$ pattern. Therefore each symbol appears exactly $k$ times in the row.

The same argument applies to columns by symmetry between the roles of $i$ and $j$ in the construction.

This establishes that periodicity modulo $3$ forces exact equidistribution along both coordinate directions.

Lemma 4

In the construction of Lemma 2, every diagonal whose length is divisible by $3$ contains exactly one third of each symbol.

Consider a diagonal of the form $i+j = c$ with length divisible by $3$. The cells on this diagonal correspond to pairs $(i, c-i)$. As $i$ increases by $1$, the pair $(i \bmod 3, (c-i) \bmod 3)$ cycles through all residue pairs satisfying $a+b \equiv c \pmod 3$.

Since $c$ is fixed, this imposes a linear constraint modulo $3$ on the residue class pairs. Among triples of consecutive diagonal entries, the residue pattern cycles through a complete set of allowed residue pairs exactly once per symbol occurrence in the base $3 \times 3$ Latin square. Because the diagonal length is a multiple of $3$, the diagonal decomposes into full cycles of length $3$, each contributing exactly one $I$, one $M$, and one $O$.

An identical argument applies to diagonals of the form $i-j = c$ by replacing $c-i$ with $i-c$; the residue dependence remains linear modulo $3$ and yields the same cyclic structure.

This establishes that the periodic construction respects diagonal balance precisely on diagonals whose lengths are multiples of $3$.

Completion of the main argument

If a valid filling exists, Lemma 1 implies $3 \mid n$. If $3 \mid n$, Lemmas 2, 3, and 4 provide a construction satisfying all conditions. Therefore such a filling exists if and only if $n$ is divisible by $3$.

Verification of Key Steps

The crucial arithmetic step is the implication from row conditions to $3 \mid n$, which depends only on divisibility of counts and does not interact with diagonal constraints; any oversight would come from assuming diagonal conditions contribute to this necessity, which they do not.

The diagonal argument relies on correctly tracking residue classes of $(i+j) \bmod 3$; a potential failure point is assuming uniform distribution without verifying that diagonal length being a multiple of $3$ forces complete residue cycles, which is essential for exact balance.

The periodic construction step assumes that a $3 \times 3$ Latin square extends consistently; a careless argument might ignore boundary alignment, but the construction is purely residue-based, eliminating boundary effects entirely.

Alternative Approaches

A different approach uses algebraic encoding of symbols as third roots of unity $1,\omega,\omega^2$, converting the conditions into linear constraints on a matrix over $\mathbb{C}$. Row, column, and diagonal conditions become vanishing sums over arithmetic progressions modulo $3$, leading to a Fourier-analytic characterization of admissible sizes. This approach emphasizes spectral constraints rather than combinatorial tiling.

The direct periodic construction is preferable because it produces an explicit configuration and reduces all constraints to elementary modular arithmetic without invoking harmonic analysis.