Very nice problem. The answer is $n$ divisible by 9. For the construction that it works, you can consider a 3*3 table with arbitrary I's, O's, and M's so that both diagonals have one of each. Then you can consider the "cyclic" tables and alternate. To prove that $n$ must be divisible by 9, you can notice that if you take the rows equivalent to 2 mod 3, the diagonals whose number of entries is a multiple of three, minus the columns not equivalent to 2 mod 3 will have an equal number of I's, O's, and M's. It is also the squares $(3i+2, 3j+2)$. However, if 9 did not divide $n$, then the number of such squares is $\frac{n^2}{9}$, which is not divisible by 3 and a contradiction to the fact that there are equal numbers of I, O, and M. This completes the proof.

I spend my time by filling 9to9

Indeed, it suffices, and it is required to have $9|n$. First, we introduce some notations. Let $(P)$ equal to $1$ if $P$ is correct, and $0$ if it is not. We denote $(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9)$ is in an IMO-state if the following holds true. The value $$\sum_{i=1}^9 a_i \cdot \sum_{0 \le j \le \frac{n}{3}-1} \sum_{0 \le k \le \frac{n}{3}-1} (\text{The letter in }(3j+\lceil \frac{i}{3} \rceil , 3k+ i-3\lfloor \frac{i-1}{3} \rfloor) \text{ is X})$$is equal for all $X=I,M,O$. Note that a linear combination of IMO-states gives you another IMO-state. Now summing all rows numbered $2 \pmod{3}$ gives $A=(0,0,0,1,1,1,0,0,0)$ is in an IMO-state. Summing all columns numbered $2 \pmod{3}$ gives $B=(0,1,0,0,1,0,0,1,0)$ is in an IMO-state. Finally, summing all diagonals gives $C=(1,0,1,0,2,0,1,0,1)$ is in an IMO-state. Summing every row, we have $D=(1,1,1,1,1,1,1,1,1)$ is in an IMO-state. Now by making an linear combination, i.e. $A+B+C-D$, we get that $(0,0,0,0,3,0,0,0,0)$ is an IMO-state. Therefore, there are equal number of letters in coordinates $(3j+2,3k+2)$, so $\frac{n^2}{9}$ is a multiple of $3$. This forces $9|n$. Now for the construction. Clearly, if we make a table for $n=9$, we can just repeatedly use it to make one for $n=9k$. If we just take $k*k$ of these tables, each row and column are guaranteed to have same number of $I, M, O$. Also, if we take a diagonal, each "segments" formed with the diagonal and tables have the same number of $I, M, O$. Therefore, in total, the diagonal itself has the same number of $I, M, O$ as well. Now let's make one table for $n=9$. We are done. $\blacksquare$ $$\begin{array}{|ccc|ccc|ccc|} \hline I & M & O & M & O & I & O & I & M \\ O & M & I & I & O & M & M & I & O \\ I & M & O & M & O & I & O & I & M \\\hline M & O & I & O & I & M & I & M & O \\ I & O & M & M & I & O & O & M & I \\ M & O & I & O & I & M & I & M & O \\\hline O & I & M & I & M & O & M & O & I \\ M & I & O & O & M & I & I & O & M \\ O & I & M & I & M & O & M & O & I \\\hline \end{array}$$

I think the construction is more straightforward than it looks: \[ \begin{array}{|ccc|ccc|ccc|} \hline 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 \\\hline 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 \\\hline 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 \\\hline \end{array} \] As for the proof that $9 \mid n$, my solution is the same as MathPanda: Let $n = 3k$, which divides the given grid into $k^2$ sub-boxes (of size $3 \times 3$ each). Consider All columns indexed $2 \pmod 3$, All rows indexed $2 \pmod 3$, and All $4k-2$ diagonals mentioned in the problem. This covers the center of each box four times, and every other cell exactly once. Consequently the letters $I$, $M$, $O$ occur with equal frequency on these $k^2$ over-counted cells, so $3 \mid k^2 \implies 9 \mid n$.

Oh hey I actually managed to solve this. Let $n = 3k$. Call a diagonal good if its number of cells is a multiple of three. Call a cell lucky if it is in two good diagonals, and unlucky if it is in none. Assume that $t$ lucky cells contain an $I$, then there are exactly $2k^2 - t$ letters $I$ in non-unlucky cells, and therefore there are $k^2 + t$ letters $I$ in unlucky cells. Now, add up the number of $I$'s which are in rows or columns that are $2$ modulo $3$ (possibly both, in which case they are counted twice). This number is equal to $2k^2$ by hypothesis. On the other hand, it is easy to check that the cells in these rows and columns are exactly the lucky and unlucky cells, and that the total number of $I$'s in these cells is equal to $k^2 + 3t$. Therefore $t = \frac{k}{3}$ and $k$ is a multiple of 3. The construction is straightforward. The diagram shows the lucky ($\times$) cells and the unlucky ($\circ$) cells. \[ \begin{array}{|c|c|c|c|c|c|} \hline & \circ & & & \circ & \\\hline \circ & \times & \circ & \circ & \times & \circ\\\hline & \circ & & & \circ & \\\hline & \circ & & & \circ & \\\hline \circ & \times & \circ & \circ & \times & \circ\\\hline & \circ & & & \circ & \\\hline \end{array} \]

OK so this was a beautiful problem. @MathPanda my solution is quite the same as yours. Btw this was my favourite problem on the test.

My construction was to replace $I,M,O$ with $1,\omega ,\omega^2$ and then put $\omega^{i+j +\lfloor \frac{i}{3} \rfloor -\lfloor \frac{j}{3} \rfloor}$ in cell $(i,j)$ And my calculations seem to point out this works...but still can anybody plz verify it Btw was this inspired by a sudoku type thing?

Well sure there'll be someone to verify it.. after you write it

Hmm...if you are referring to me then i couldnt actually verify this as i wrote it up in last 5 min. Anyway i got it verfied by an aopser. Thanks to him

Yeah Kapil it works. I think maybe this was inspired by sudoku because every condition almost matches. This was thee motivation behind my sol tho.

Denote by $a_1,...,a_9$ the proportion of $I$'s in squares which are $(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)$ modulo $3$. Let $S_1=a_1+a_3+a_7+a_9$ and $S_2=a_2+a_4+a_6+a_8$. Rows and columns not $2$ modulo $3$ give $2S_1+S_2=4$. Diagonals give $S_1+2a_5=2$ and rows and columns $2$ mod $3$ give $S_2+2a_5=2$. Combining $4+6a_5=6$ or $a_5=1/3$ hence $n^2/9$ is divisible by $3$ hence $n=9k$. Construction by v_Enhance is simplest

Construction for multiples of 9: use this BBBAAACCC ACBBBCAAC AAACCCBBB CAACCBBBA ABCBACACB CCACBBBAA BBBAAACCC BACACACBB CCCBBBAAA Now assume n is not a multiple of 9, then change notation and let it be 3nx3n with n not divisible by 3. I prove it's not even possible to put the letter M alone such that all rows, all columns have n Ms and all divisible-by-3 diagonals have a third Ms. Collapse all squares equivalent mod 3 into a single square, so that we obtain a 3x3 board where each square has some integer number of Ms. In each row there's n Ms, in each column there's n Ms, and in both diagonals there's n Ms (coming from the identity $1+2+...+(n-1)+n+(n-1)+...+2+1=n^2$). This is a straightforward system of equations which yields that in the center square there's n/3 Ms. Contradiction.

The answer is $9\mid n$ and can be achieved as described in above posts. Clearly, $3\mid n$, so set $n=3k$. Now, color the board like 123123123... 456456456... 789789789... 123123123... ... Let $a_i$ be the number of $I$'s with color $i$. We clearly have $a_1+a_2+a_3=a_4+a_5+a_6=a_7+a_8+a_9=a_1+a_4+a_7=a_2+a_5+a_8=a_3+a_6+a_9=a_1+a_5+a_9=a_3+a_5+a_7=k^2$ so $k^2=a_7+a_8+a_9=k^2-a_5-a_3+k^2-a_5-a_2+k^2-a_5-a_1=3k^2-3a_5-k^2\implies k^2=3a_5$ so $3\mid k$ as desired.

Why has no one so far posted Day 2 IMO problems ?

kk108 wrote: Why has no one so far posted Day 2 IMO problems ? Perhaps they have not finished testing yet? Yesterday they were posted about an hour from now, I wouldn't expect them until around that time. Be patient please.

aiyer12 wrote: kk108 wrote: Why has no one so far posted Day 2 IMO problems ? Perhaps they have not finished testing yet? Yesterday they were posted about an hour from now, I wouldn't expect them until around that time. Be patient please. Ok thanks !

Can someone solve it using $-1,0,1$ in place of the roots of unity (or similar replacements) please?

My solution We will replace $I$ with $-1$, $M$ with $0$ and $O$ with $1$ It's obvious that $3|n$ so let $n = 3m$ Then $\sum_{all \ the \ cells} = 0$ We devides the board into $m^2$ small $3 \times 3$ boxes. Now consider all the rows. collumns and diagonals which passes through the centers $\implies$ each center is counted $4$ times and each cell is counted $1$ time Note that those rows, collumns and diagonals all have the number of cells divisible by $3$ So $0 = \sum_{all \ counted \ cells} = \sum_{all \ the \ cells} + 3 \sum_{all \ the \ centers } = 3 \sum_{all \ the \ centers}$ $\implies \sum_{all \ the \ center} = 0$ . . Then in those $m^2$ cells, the number of $I's$ = number of $O's$ $(1)$ But on the other hand, if we replace $I$ with $0$, $M$ with $-1$ and $O$ with $1$. the sum is also equal to $0$ so number of $M's$ in those $m^2$ cells = number of $O's$ So, the number of centers is divisible by $3$ or $3 | m^2$. Then, $9 | n$

Here is a solution using counting in two ways. It's obvious that $3 \mid n$. We consider all the squares indexed $(3k+2,3l+2)$ and call it good square. Let $a$ be number of good squares that are filled with $I$. We can see that every good square lies on both type of diagonals. So if we call $D_1,D_2$ be the set of all squares in first type, second type of diagonal that are filled with $I$, respectively. We will have $|D_1 \cap D_2|=a$ and $|D_1|=|D_2|= \tfrac 19 n^2$. Hence, $$|D_1 \cup D_2|=|D_1|+|D_2|+|D_1 \cap D_2|= \tfrac 29 n^2-a.$$Hence, number of squares filled with $I$ that either lie on first type of diagonal or second type but not in both is $\tfrac 29 n^2-2a$. Now, these squares counted above doesn't fill the columns indexed $3k+2$ and rows indexed $3k+2$. So we need to fill these squares with $I$. Let $C$ be the set of squares in columns indexed $3k+2$ that are filled with $I$, similar to set $R$ of rows indexed $3k+2$. We have $$|C \cup R|=|C|+|R|-|C \cap R|= \tfrac 29 n^2-a.$$ From these, we find that the total number of squares filled with $I$ is $\tfrac 49 n^2-3a$. Note that this is also equal to $\tfrac 13 n^2$ so this means $3a= \tfrac 19 n^2$ implies $9 \mid n$, which is the final answer. This argument gives us a way to construct a $9 \times 9$ table, which is first we fill all the good squares in a way such that one third of them are $I$, one third are $O$ and one third are $M$. After that, we fill all the diagonals and then fill the remain squares.

Best notation ever! Answer is $9\mid n,$ construction (which easily generalizes) is \[ \begin{array}{|ccccccccc|} \hline 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 \\ 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 \\ 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 \\\hline \end{array} \]Let $n=3k.$ consider the rows and columns $\equiv 2\pmod{3}.$ The intersections are precisely the points where two diagonals with the number of entries divisible by three intersect. Summing these rows/columns with the previously mentioned diagonals and subtracting the total grid, we have \[2k^2(i+m+o)+2k^2(i+m+o)-3k^2(i+m+o)=k^2(i+m+o).\]But this is $3$ times the sum of the intersections of the $2\pmod{3}$ rows/columns, so their sum is $\frac{k^2}{3}(i+m+o),$ and as the coefficients are integers, $3\mid k.$

Clearly, $3\mid n$ so let $n=3m$. In the $n\times n$ grid set up a coordinate grid with the lower left square being $(0,0)$. If we color all the diagnolas and the $1$ modulo $3$ rows and columns (here the rows are labeled starting from $0$ from the left), then all the squares are colored exactly once except the ones with both coordinates $1$ modulo $3$ which are colored four times. Hence, the number of $M$s colored (where a square can be counted multiple times) is \[\frac{2\cdot 3(1+2+\dots+m+m-1+\dots+2+1)+m\cdot 3m+\cdot 2}{3}=4m^2\]where we are counting by rows/columns/diagonals. On the other hand if we count by squares, our sum is \[\frac{(3m)^2}{3}+3\ell\]where we are counting a third of the total number of squares and adding in three times the number of squares that are counted four times and are $M$s (suppose there are $\ell$ such squares). Notice the second count is divisible by $3$ so the first one must be. Hence, $3\mid 4m^2$ so $3\mid m$. $\square$

A Sudoku-like configuration suffices for $n=9$, and this can be iterated for the rest of the cases where $9|n$. I believe the faksolve stems from the fact that it is implied that $3|n$, so a natural step to make would be to turn this into a $3^2 \times 3^2$ grid of letters.

We claim that $n$ which are multiples of $9$ work. Claim: If there is a valid table for $n$, then $9 \mid n$. Proof. Evidently $3 \mid n$. Tile the $n \times n$ grid with $3 \times 3$ subtables. If we take the multiset consisting of rows and columns that go through the center of each subtable, and every diagonal, then it follows that one third of these are each letter. However, this is also just the entire grid with the centers counted an extra $3$ times. This can only occur if the $\frac{n^2}{9}$ centers are evenly distributed among the three letters, which implies that $9 \mid n$. $\blacksquare$ Claim: There exists a valid table when $9 \mid n$. Proof. Consider the $3 \times 3$ table where each row is a different letter. Note that the diagonals of this table have one of each letter. By cyclically permuting the letters in each row, we end up with three different tables. Then, we can cover a $n \times n$ table with these three different subtables such that each type of table is one third of each row and column by taking a stripe configuration. Furthermore, diagonals follow as they go through the diagonals of each $3 \times 3$ subtable. $\blacksquare$

The answer is all multiples of $9$. An arrangement as such works for $n=9$ \[ \begin{array}{|ccc|ccc|ccc|} \hline 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 \\\hline 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 \\\hline 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 \\\hline \end{array} \] Let $n=3k$ and then partition into $k^2$ boxes (of size $3 \times 3$). Consider the rows with indices $2 \pmod 3$, columns indexed $2 \pmod 3$ and all $4n-2$ diagonals. The center of each of the $k^2$ boxes has been covered $4$ times and the rest $1$ time. Thus, the $k^2$ center squares are equally distributed amongst $I$, $M$, and $O$, implying $9 \mid n$. $\square$

The answer is $9 \mid n$, by tiling the following construction. IMOIMOIMO IMOIMOIMO IMOIMOIMO MOIMOIMOI MOIMOIMOI MOIMOIMOI OIMOIMOIM OIMOIMOIM OIMOIMOIM Obviously $3 \mid n$, so let $n=3k$. I will show that $3 \mid k$. Weight $I$ with $1$, $M$ with $e^{2\pi i/3}$, $O$ with $e^{4\pi i/3}$. Thus the sum of every row, column, and diagonal with length divisible by $3$ is $0$. Conversely, it is clear that if some subset of cells has sum $0$, it must have an equal number of each letter. Partition the grid into $k^2$ $3 \times 3$ squares. Add (meaning sum together the corresponding statements, yielding a statement where some weighted linear combination of row weights equals $0$) every diagonal, as well as the rows and columns passing through the center of some square. Then subtract every row once. The result is that $3$ times the sum of the $k^2$ weights at the center of every square equals $0$, so there must be an equal number of each letter among these $k^2$ cells, i.e. $3 \mid k^2$ as desired. $\blacksquare$

I claim that the answer is all $n$ such that $n$ is a multiple of $9$. Label the columns from left to right as $1$, $2$, $\dots$, $n$, and the rows from bottom to top as $1$, $2$, $\dots$, $n$ also. Define $S_{(i,j)}$ to be the square in column $i$ and row $j$. Let $A$ be the set of all squares $S_{(i,j)}$ such that both $i$ and $j$ are $2$ mod $3$, and let $X$ be the set of all squares. Then let $B=X-A$. Notice that since each row has $\frac{1}{3}$ of its entries as $I$, this implies that $n$ must be a multiple of $3$. Let $n=3k$. I claim that if $3$ does not divide $k$, then there is no way to fill in the grid with $I$'s, $M$'s, and $O$'s such that it satisfies problem conditions. FTSOC, assume that there is such a way to fill in the grid. Now let sets $C$, $D$, $E$, and $F$ be defined as follows - $C$ is the set of all squares $S_{(i,j)}$ such that $i\equiv 1 \mod 3$, - $D$ is the set of all squares $S_{(i,j)}$ such that $j\equiv 2 \mod 3$, - $E$ is the set of all squares $S_{(i,j)}$ such that $i-j\equiv 0 \mod 3$ (AKA the set of all squares on a diagonal with a number of squares that is a multiple of $3$ that goes in the same direction as the diagonal from the bottom left corner to the top right corner), - and $F$ is the set of all squares $S_{(i,j)}$ such that $i+j\equiv 1 \mod 3$ (AKA the set of all squares on a diagonal with a number of squares that is a multiple of $3$ that goes in the same direction as the diagonal from the bottom right corner to the top left corner). Note that we then have that, \[C+D+E+F=4A+B,\]and by problem conditions, since we summed together diagonals that had numbers of squares that were multiples of $3$, columns, and rows, the set $C+D+E+F$ must have equal numbers of squares that have $I$'s, $M$'s, and $O$'s. This implies that the set $4A+B$ must satisfy the same condition. Since $A+B$ is the set of the entire grid, by problem conditions, this implies that the set $A+B$ must also have equal numbers of squares that have $I$'s, $M$'s, and $O$'s. Therefore, subtracting $A+B$ from $4A+B$, we have that the set $3*A$ must have equal numbers of $I$'s, $M$'s, and $O$'s also, which is equivalent to the set $A$ having equal numbers of $I$'s, $M$'s, and $O$'s, implying that $3\mid |A|$. Since $n=3k$, we have that \[3\mid|A|=\frac{(3k)^2}{9}=k^2 \iff 3\mid k^2 \iff 3\mid k,\]meaning that $3\mid k$, and therefore $9\mid n$, as we wished to prove. Now I claim that all $n$ such that $9\mid n$ have constructions. If $n=9m$, we can "tile" the $9m\times 9m$ grid with $m^2$ times with the following $9\times 9$ tile to get our construction. [asy][asy] size(300,300); draw((0,0)--(9,0)--(9,9)--(0,9)--(0,0)); draw((1,0)--(1,9)); draw((2,0)--(2,9)); draw((3,0)--(3,9)); draw((4,0)--(4,9)); draw((5,0)--(5,9)); draw((6,0)--(6,9)); draw((7,0)--(7,9)); draw((8,0)--(8,9)); draw((0,1)--(9,1)); draw((0,2)--(9,2)); draw((0,3)--(9,3)); draw((0,4)--(9,4)); draw((0,5)--(9,5)); draw((0,6)--(9,6)); draw((0,7)--(9,7)); draw((0,8)--(9,8)); label("$O$", (0.5,0.5)); label("$O$", (0.5,1.5)); label("$O$", (0.5,2.5)); label("$M$", (0.5,3.5)); label("$M$", (0.5,4.5)); label("$M$", (0.5,5.5)); label("$I$", (0.5,6.5)); label("$I$", (0.5,7.5)); label("$I$", (0.5,8.5)); label("$O$", (3.5,0.5)); label("$O$", (3.5,1.5)); label("$O$", (3.5,2.5)); label("$M$", (3.5,3.5)); label("$M$", (3.5,4.5)); label("$M$", (3.5,5.5)); label("$I$", (3.5,6.5)); label("$I$", (3.5,7.5)); label("$I$", (3.5,8.5)); label("$O$", (6.5,0.5)); label("$O$", (6.5,1.5)); label("$O$", (6.5,2.5)); label("$M$", (6.5,3.5)); label("$M$", (6.5,4.5)); label("$M$", (6.5,5.5)); label("$I$", (6.5,6.5)); label("$I$", (6.5,7.5)); label("$I$", (6.5,8.5)); label("$I$", (1.5,0.5)); label("$I$", (1.5,1.5)); label("$I$", (1.5,2.5)); label("$O$", (1.5,3.5)); label("$O$", (1.5,4.5)); label("$O$", (1.5,5.5)); label("$M$", (1.5,6.5)); label("$M$", (1.5,7.5)); label("$M$", (1.5,8.5)); label("$I$", (4.5,0.5)); label("$I$", (4.5,1.5)); label("$I$", (4.5,2.5)); label("$O$", (4.5,3.5)); label("$O$", (4.5,4.5)); label("$O$", (4.5,5.5)); label("$M$", (4.5,6.5)); label("$M$", (4.5,7.5)); label("$M$", (4.5,8.5)); label("$I$", (7.5,0.5)); label("$I$", (7.5,1.5)); label("$I$", (7.5,2.5)); label("$O$", (7.5,3.5)); label("$O$", (7.5,4.5)); label("$O$", (7.5,5.5)); label("$M$", (7.5,6.5)); label("$M$", (7.5,7.5)); label("$M$", (7.5,8.5)); label("$M$", (2.5,0.5)); label("$M$", (2.5,1.5)); label("$M$", (2.5,2.5)); label("$I$", (2.5,3.5)); label("$I$", (2.5,4.5)); label("$I$", (2.5,5.5)); label("$O$", (2.5,6.5)); label("$O$", (2.5,7.5)); label("$O$", (2.5,8.5)); label("$M$", (5.5,0.5)); label("$M$", (5.5,1.5)); label("$M$", (5.5,2.5)); label("$I$", (5.5,3.5)); label("$I$", (5.5,4.5)); label("$I$", (5.5,5.5)); label("$O$", (5.5,6.5)); label("$O$", (5.5,7.5)); label("$O$", (5.5,8.5)); label("$M$", (8.5,0.5)); label("$M$", (8.5,1.5)); label("$M$", (8.5,2.5)); label("$I$", (8.5,3.5)); label("$I$", (8.5,4.5)); label("$I$", (8.5,5.5)); label("$O$", (8.5,6.5)); label("$O$", (8.5,7.5)); label("$O$", (8.5,8.5)); [/asy][/asy]

The answer is when $\boxed{9\mid n}$. Clearly $3\mid n$. If $9\nmid n$, sum over all diagonals with number of cells a multiple of $3$, then also sum over every $2$ mod $3$ column. Then subtract every $0$ or $1$ mod $3$ row. Example for $n=6$: 101101 020020 101101 101101 020020 101101 111111 030030 111111 111111 030030 111111 000000 030030 000000 000000 030030 000000 Therefore, the cells with row and column that are both $2$ mod $3$ must have an equal number of I,M,O between them. This is clearly impossible if $9\nmid n$. For $9\mid n$, we will provide an explicit construction for $n=9$ that can simply be used to tile any $n$ by $n$ grid when $9\mid n$: IIIMMMOOO MMMOOOIII OOOIIIMMM IIIMMMOOO MMMOOOIII OOOIIIMMM IIIMMMOOO MMMOOOIII OOOIIIMMM We are done. $\blacksquare$

Our answer is $\boxed{\text{all multiples of 9}}$. Note $n=9$ can be constructed with first row $IIIMMMOOO$, second row $MMMOOOIII$, and so on, and other mutliples of 9 can be constructed by stacking these $9 \times 9$ squares. Note the following count the same set: The numbers in the desired diagonals plus numbers in rows $2 \pmod 3$ plus numbers in columns $2 \pmod 3$. All cells in the grid plus 3 times the squares in row and column $2 \pmod 3$. Each of $I$, $M$, and $O$ is guarenteed to appear the same number of times in every subcategory besides the squares in row and column $2 \pmod 3$. Thus we require $\frac{n^2/9}{3}$ to be an integer, so $9 \mid n$. $\blacksquare$

Solved with SigmaPiE. A beautiful problem! We claim the answer is all positive integers $n$ where $9 \mid n$. To demonstrate a construction, let $n = 9j$ and consider the following $9 \times 9$ grid: \[\begin{matrix} I & M & O & I & M & O & I & M & O\\ I & M & O & I & M & O & I & M & O\\ I & M & O & I & M & O & I & M & O\\ M & O & I & M & O & I & M & O & I\\ M & O & I & M & O & I & M & O & I\\ M & O & I & M & O & I & M & O & I\\ O & I & M & O & I & M & O & I & M\\ O & I & M & O & I & M & O & I & M\\ O & I & M & O & I & M & O & I & M\\ \end{matrix}\]Then consider the above as a singular unit and duplicate it as a $j \times j$ array which yields a valid construction for $9j \times 9j$. To show that $9 \mid n$, let $n = 3k$ and define the cells that lie on exactly $1$ diagonal with a multiple of $3$ amount of cells as hot, and cells that lie on exactly $2$ cold. The main idea is to consider the rows and columns not passing through the cold cells. We claim that these rows and columns intersect precisely at the hot cells, as outlined in the diagram below for $n = 6$. To prove this, partition the grid into $3 \times 3$ subgrids. In each subgrid, there are hot cells at each corner, which the rows/columns not passing through the center intersect at. Hence this easily generalizes to the whole grid. Now suppose that $a$ cold cells contain an $I$. In each set of diagonals with a multiple of $3$ amount of cells parallel to a particular direction, there exists $\frac{1}{3} \cdot 3 \cdot (1 + 2 + \dots + k + \dots + 1) = k^2$ cells with an $I$ in it. Then the number of hot cells containing an $I$ is $2k^2 - 2a$. Now the total number of cells with $I$ among the rows/columns not passing through a cold cell is $\frac{1}{3} \cdot 2 \cdot 2k \cdot 3k = 4k^2$, but we overcount at the hot cells so we have $4k^2 - (2k^2 - 2a) = 2k^2 + 2a$ cells with $I$ along these rows/columns. Adding the number of $I$ in the cold cells gives $2k^2 + 3a$, which also equals $3k^2$, the total number of $I$ in the grid. Then $k^2 = 3a$ implying $3 \mid k$ as desired. Our proof is complete!

wait I proved that all multiples of 9 work but how do you prove all other numbers dnot work

We claim the answer is $n$ works if and only if $9 \mid n$. $9\times 9$ construction attached, $9a \times 9a$ construction is tiling an $a\times a$ grid with the $9\times 9$ construction. To prove $n \not \equiv 0 \pmod{9}$ doesn't work first observe $n \not \equiv 0 \pmod{3}$ doesn't work because you can't have an equal amount of $I$s, $M$s and $O$s in each row. So let $n=3m$ with $m \not \equiv 0 \pmod{3}$, let $I_0$, $I_1$, and $I_2$ denote the number of $I$s that appear in $0$, $1$, and $2$ multiple of $3$ diagonals respectively. Define $M_0$, $M_1$, $M_2$, $O_0$, $O_1$, and $O_2$ similarly. Summing the number of $I$s, $M$s, and $O$s in diagonals with a multiple of $3$ amount of elements gives: $I_1 +2 I_2 = M_1 + 2M_2 = O_1 + 2 O_2 =2m^2$. Considering the total amount of $I$s, $M$s, and $O$s gives: $I_0+I_1+I_2 = M_0 + M_1 + M_2 = O_0+ O_1 + O_2 =3m^2$. Subtracting the first equation from the second gives us $ I_0 -I_2 = M_0 - M_2 = O_0 - O_2=m^2$. Now summing over multiple of $3$ diagonals, and rows/collumns not containing intersections of multiple of $3$ diagonals gives : $I_0+M_0+O_0+ 3(I_1+M_1+O_1)+ 2(I_2+M_2+ O_2) =11n^2$ or $(I_0-I_2)+(M_0-M_2)+(O_0-O_2) \equiv 2 \pmod{3}$. However $(I_0-I_2)+(M_0-M_2)+(O_0-O_2)= 3m^2 \not \equiv 2 \pmod{3}$ a contradiction. $\square$

Attachments:

We claim that $n=9k$, $k\in\mathbb{N}$ works. for the construction, consider a $3\times 3$ block with the columns $YZY$, $XXX$, $ZYZ$ in that order. Let $b_1$, $b_2$, and $b_3$ be the $3\times 3$ blocks with $(X,Y,Z)$ being $(O, M, I)$, $(M, I, O)$, and $(I, O, M)$ respectively. Notice that both diagonals of each $3\times 3$ contains $I, M, O$ so the diagonal condition is satisfied. Each of the rows also contains $I,M,O$ so the row condition is satisfied. Finally, if we let each column of the $9k\times 9k$ have an equal number of $b_1$, $b_2$, and $b_3$ blocks, the column condition is also satisfied. Hence, all $n=9k$, $k\in\mathbb{N}$ works. Now, we'll show that if $n\not\equiv 0\pmod 9$, then no construction works. It's clear that the only other possibilities are $n\equiv 3,6\pmod 9$, since we need $3\mid n$. Now, for each diagonal in the $n\times n$ grid, add up the number of squares that are $I$, $M$, and $O$ separately. Then, For each row that is the $3i+2$th row for some $i$, add up the number of squares that are $I$, $M$, and $O$, and do the same for the columns. So, because of our conditions, the total count for the number of $I$, $M$, and $O$ squares must be equal. However, notice that we have counted each square except the squares that are an intersection of two diagonals exactly $1$ time, and the rest have been counted $4$ times. Notice that the number of such squares is $t^2$, where $n=3t$, and $3\nmid t$ when $n\equiv 3,6\pmod 9$. So, when $3\cdot i$, $3\cdot m$, and $3\cdot o$ is subtracted, where $i$, $m$, $o$ are the number of $I$s, $M$s, and $O$s that are at an intersection of two diagonals respectively, the counts for the number of $I$, $M$, and $O$ squares are now unequal because $3\nmid t^2$. However, this gives a contradiction, since summing up the number of squares that are $I$, $M$, and $O$ separately for each row in the grid, there clearly must be an equal number of $I$, $M$, and $O$ squares.

We claim $9\mid n$ works. First clearly notice $3\mid n$. Next add every diagonal divisible by $3$, add every $1\pmod 3$ row and column (zero-indexed) and subtract the entire grid. We get that there are the same number of $I,M,O$ in the $(\tfrac n3)^2$ squares that are $\equiv (1,1)\pmod 3$. This implies $9\mid n$. To construct, label $(a,b)$ with $\bmod(a+\lfloor\tfrac b3\rfloor,3)$.

This problem was proposed by Trevor Tao (the brother of Terence Tao) and was indeed inspired by Sudoku! We claim the answer is all $9 \mid n$. For the construction, take the grid \[\begin{matrix} 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 \\ 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 \\ 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{matrix}\]and loop it. For the bound, note that $3 \mid n$ obviously. Hence, define the function $I \colon \{1, 2, \dots, 9\} \to \mathbb Z_{\geq 0}$ so that $I(x)$ count the number of $I$'s in the position marked $x$ in the grid below, extended to fill the whole $n \times n$ grid. Define functions $M$ and $O$ similarly. \[\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}\]Impose coordinates by letting the bottom-left corner be $(1, 1)$, the bottom-right corner be $(n, 1)$, the top-right corner be $(n, n)$ and interpolating. By summing over the diagonals of first type with number of cells divisible by three we get that \[I(1) + I(5) + I(9) = M(1) + M(5) + M(9) = O(1) + O(5) + O(9).\]Similarly, by summing over the diagonals of second type with number of cells divisible by three we get that \[I(3) + I(5) + I(7) = M(3) + M(5) + M(7) = O(3) + O(5) + O(7).\]Additionally, we have that \[I(2) + I(5) + I(8) = M(2) + M(5) + M(8) = O(2) + O(5) + O(8)\]and \[I(4) + I(5) + I(6) = M(4) + M(5) + M(6) = O(4) + O(5) + O(6)\]by summing over specific columns and rows. Hence, \[\sum_{i = 1}^9 I(i) + 3I(5) = \sum_{i = 1}^9 M(i) + 3M(5) = \sum_{i = 1}^9 O(i) + 3O(5).\]But \[\sum_{i = 1}^9 I(i) = \sum_{i = 1}^9 M(i) = \sum_{i = 1}^9 O(i)\]by summing over all columns, so it follows that \[3I(5) = 3M(5) = 3O(5)\]by subtracting. This is only possible if $3 \mid \left(\frac n3\right)^2$ and hence if $9 \mid n$.