Problem 2

Find all 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 on that diagonal are

I

, one third are

M

, and one third are

O

. (Note that an

n\times n

table has

4n-2

diagonals in total, in both directions.)

Step 1 of 5: Construction: an explicit valid

9\times9

tile

Previous step Next step

In plain words

The following tile can be checked directly: every row, column, and diagonal whose length is a multiple of three has one third of each letter. Repeating the tile periodically gives every multiple of $9$ .

\text{A valid }9\times9\text{ tile, repeated periodically}

Detailed analysis

Use the $9\times9$ tile IOMOMIMOI IOMOIMOIM IMIMOMIOO OIOIOMMIM MOIIMOIOM MIMOIOOMI OIOMMIMIO MMOIIOOMI OMIMOIIMO. A direct count along the nine rows, nine columns, and every diagonal of length $3$ , $6$ , or $9$ verifies the required one-third counts. Repeat this tile with period $9$ in both directions. Any diagonal segment of length divisible by $3$ then decomposes into complete three-step residue classes of the same periodic check, so it also has one third of each letter.