0
$\begingroup$

For what $n$s is it possible to write a $1$, $2$ or a $3$ into each cell of a $n\times n$ square, such that each of the three numbers appears equal number of times in every row, column, and diagonal, only if the number of cells of the diagonal is divisible by 3?

I think it appeared in an IMO contest or shortlist about year 2006, but I couln’t find or solve it.

$\endgroup$
3
  • $\begingroup$ So you are asking for which $n$ divisible by $3$ is this possible? $\endgroup$ – Jens Aug 10 '18 at 0:48
  • $\begingroup$ Exactly. For $n=9$ i found a solution $\endgroup$ – Leo Gardner Aug 10 '18 at 5:59
  • $\begingroup$ Well, it's also possible for $n=6$ and therefore for $n=6k, k \in \Bbb N$. Seems to me the only case it's not possible if for $n=3$. $\endgroup$ – Jens Aug 10 '18 at 12:54
0
$\begingroup$

This came from IMO Question 2. I'll summarise the official solution here:

We show that a table exists for $n=9$: $$ \begin{array}{|ccc|ccc|ccc|} \hline 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 \\ 2 & 2 & 2 & 3 & 3 & 3 & 1 & 1 & 1 \\ 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 & 2 \\\hline 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 \\ 2 & 2 & 2 & 3 & 3 & 3 & 1 & 1 & 1 \\ 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 & 2 \\\hline 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 \\ 2 & 2 & 2 & 3 & 3 & 3 & 1 & 1 & 1 \\ 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 & 2 \\\hline \end{array} $$ For any $n=9k$ where $k$ is a positive integer, we can simply take $k\times k$ copies of the above table. It's easily seen that these new tables still satisfy the original condition.

So consider an $n\times n$ table where the requirements are met. Since the number of entries of each row are a multiple of $3$, we let $n=3k$ where $k$ is a positive integer. Then divide the whole table into $k\times k$ copies of $3\times 3$ blocks. We call the entry at the centre of such a $3\times 3$ square a vital entry and we call any row, column, or diagonal that contains at least one vital entry a vital line. We compute the number of pairs $(\ell, c)$ where $\ell $ is a vital line and $c$ is an entry belonging to $\ell$ that contains the numeral $2$. Let the number of pairs be $N$.

Since each vital line contains the same number of each numeral, each vital row and column contains $k$ occurrences of $2$. For vital diagonals in either direction, we count there are exactly $$1+2+\dots+(k-1)+k+(k-1)+\dots+2+1=k^2$$ occurrences of $2$. Therefore, $N=4k^2$. But there are $3k^2$ occurrences of $2$ in the whole table, and each entry belongs to exactly $1$ or $4$ vital lines. So $N\equiv 3k^2\pmod 3$, so $4k^2\equiv 3k^2\pmod 3$ which means $k$ is a multiple of $3$. Thus, $n$ must be a multiple of $9$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.