IMO 2016 · Problem 2

Find all positive integers \(n\) for which each cell of an \(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 integers \((i,j)\) with \(1\le i,j\le n\). For \(n>1\), the table has \(4n-2\) diagonals of two types. A diagonal of the first type consists of all cells \((i,j)\) for which \(i+j\) is constant, and a diagonal of the second type consists of all cells \((i,j)\) for which \(i-j\) is constant.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{n=9k\quad\text{for every positive integer }k.} \]

Solution

The row condition implies \(3\mid n\). Write \(n=3m\).

A diagonal \(i-j=d\) has length \(n-|d|\), so its length is divisible by three exactly when \(d\equiv0\pmod3\). Similarly, a diagonal \(i+j=s\) has length \[ n-|s-(n+1)|, \] which is divisible by three exactly when \(s\equiv1\pmod3\).

Necessity. Suppose a valid filling exists. For \(r,s\in\{1,2,3\}\), let \(a_{rs}\) be the number of entries \(I\) in cells satisfying \[ i\equiv r\pmod3,\qquad j\equiv s\pmod3. \] Consider the \(3\times3\) matrix \(A=(a_{rs})\).

There are \(m\) actual rows in each residue class, and each contains \(m\) entries \(I\). Thus every row sum of \(A\) is \(m^2\). Likewise, every column sum is \(m^2\).

The cells with \(i-j\equiv0\pmod3\) form a disjoint union of diagonals whose lengths are divisible by three. They comprise three residue classes of cells, each containing \(m^2\) cells. Exactly one third of their entries are therefore \(I\), giving \[ a_{11}+a_{22}+a_{33}=m^2. \] Applying the same argument to the cells with \(i+j\equiv1\pmod3\) gives \[ a_{13}+a_{22}+a_{31}=m^2. \]

Now add the middle row, the middle column, and the two diagonals of \(A\). Their sums total \(4m^2\). Every entry of \(A\) is counted once, except \(a_{22}\), which is counted four times. Since all entries of \(A\) sum to \(3m^2\), we obtain \[ 4m^2=3m^2+3a_{22}. \] Hence \(m^2=3a_{22}\), so \(3\mid m\). Consequently \(9\mid n\).

Sufficiency. Let \(n=9k\), where \(k\ge1\). Repeat the following \(3\times9\) pattern \(k\) times horizontally and \(3k\) times vertically: \[ \begin{array}{ccc|ccc|ccc} I&I&I&M&M&M&O&O&O\\ M&M&M&O&O&O&I&I&I\\ O&O&O&I&I&I&M&M&M \end{array}. \] Every row contains \(3k=n/3\) copies of each letter. Every column also contains \(3k\) copies of each letter, since each successive group of three rows contains one of each.

Partition the table into \(3\times3\) blocks. Within every block, each of its two diagonals contains one \(I\), one \(M\), and one \(O\). We show that every diagonal whose length is divisible by three is a union of such complete block diagonals.

Write the coordinates within a block as \[ i=3a+r,\qquad j=3b+s,\qquad r,s\in\{1,2,3\}. \]

For a qualifying diagonal \(i-j=d\), we have \(d\equiv0\pmod3\), hence \(r-s\equiv0\pmod3\). Since \(-2\le r-s\le2\), this forces \(r=s\). Thus, whenever the diagonal meets a block, its intersection is the block’s complete main diagonal.

For a qualifying diagonal \(i+j=t\), we have \(t\equiv1\pmod3\), hence \(r+s\equiv1\pmod3\). Since \(2\le r+s\le6\), this forces \(r+s=4\). Thus its intersection with any block it meets is the block’s complete other diagonal.

Every qualifying diagonal is therefore partitioned into triples containing one of each letter. This verifies the remaining condition and completes the construction.

The solution was checked against the official IMO shortlist solutions.