The 4th Japanese Junior Mathematical Olympiad

Denote by $X_{i,j}$ the entry that lies in the $i$th column. We will prove that $(m,n)$ is a good pair if and only if $m+1$ and $n+1$ are not relatively prime.

First, we prove that $(k,k)$ is a good pair for any integer $k\ge 2$. In fact, given a $k\times k$ grid, write integers as $$X_{i,j}=\{\begin{array}{ll}(-1{)}^i& \text{if }i=j\pm 1\\ 0& \text{otherwise}\end{array}$$ and the desired condition holds.

Next, we prove $(m,n)$ is a good pair if $m+1$ and $n+1$ are not relatively prime. Let $d$ be the greatest common divisor of $m+1$ and $n+1$. Since $(d-1,d-1)$ is a good pair, there exists a $(d-1)\times (d-1)$ matrix $Y=(Y_{i,j})$ which satisfies the required conditions. Then extend the domain of $Y_{i,j}$ (as a function $(i,j)\mapsto Y_{i,j}$) to $\mathbb{Z}\times \mathbb{Z}$ by $$\begin{gathered} Y_{i,j}=Y_{2d+i,j}=Y_{i,2d+j}\text{and} \\ -Y_{i,j}=Y_{i,-j}=Y_{-i,j} \end{gathered}$$ and then $(Y_{i,j}{)}_{1\le i\le m,1\le j\le n}$ satisfies the required conditions.

Therefore, it suffices to prove that $(m,n)$ is not a good pair if $m+1$ and $n+1$ are relatively prime. Assume that we have written integers $X_{i,j}$ in the squares with condition (ii). It suffices to prove $X_{i,j}=0$.

Extend the domain of $X_{i,j}$ (as a function $(i,j)\mapsto X_{i,j}$) to $\mathbb{Z}\times \mathbb{Z}$ by $$\begin{gathered} X_{i,j}=X_{2(m+1)+i,j}=X_{i,2(n+1)+j}\text{and} \\ -X_{i,j}=X_{i,-j}=X_{-i,j} \end{gathered}$$ Then it is clear that $\sigma (S)=0$ holds for all square $S$.

Denote by $S(k,l)$ the square on the $k$th column. $\sigma (S(1,1))=0$ yields $X_{1,2}+X_{2,1}=0$. Then $\sigma (S(2,2))=0$ yields $X_{2,3}+X_{3,2}=0$. It follows that $X_{k,k+1}+X_{k+1,k}=0$ for any integer $k$.

Now, let $i$ and $j$ be integers such that $i-j$ is even. Since $m+1$ and $n+1$ are relatively prime, there exist integers $u,v$ such that $$i-j=2v(n+1)-2u(m+1),$$ or, $$i+2u(m+1)=j+2v(n+1).$$ Then, $0=X_{i+2u(m+1)+1,j+2v(n+1)}+X_{i+2u(m+1),j+2v(n+1)+1}=X_{i+1,j}+X_{i,j+1}$ follows from the periodicity of $X$. Since $X_{0,j}=0$, it follows by induction that $X_{i,j}=0$ for all $i,j$ such that $i+j$ is odd.

Since $m+1$ and $n+1$ are relatively prime, $m$ or $n$ is even. Assume that $m$ is even. Then, by symmetry, $X_{i+1,j}+X_{i,j+1}=0$ for even $i+j$ too, and $X_{i,j}=0$ follows for all $i$ and $j$. Hence $(m,n)$ is not a good pair.

We can solve the problem using the results above.

(1) $(3,n)$ is a good pair if and only if $4$ and $n+1$ are not relatively prime, in other words, if $n$ is odd. So the answer is $n=3,5,7,9$.

(2) One counts the number of pairs $(i,j)$ of integers such that $3\le i,j\le 11$ and $i,j$ not relatively prime, and obtain the answer $29$.