# An old and interesting problem in combinatorics from Russia Mathematics Olympiad

Can the numbers from $$1$$ to $$81$$ be written on a $$9 \times 9$$ board, so that the sum of the numbers in each $$3\times 3$$ square is the same?

I believe I have not made much progress and am missing the key insight here. Any advice?

• One insight is that each 3x3 block's numbers have to add up to the sum of all the numbers divided by 9: $\sum_{k=1}^{81} k /9$. That's not enough to solve the problem but it reduces the number of cases that need to be considered. Jan 14, 2020 at 17:42
• Do you mean all the $3\times 3$ squares in the $9\times 9$ grid (of which there are $49$, I think)? Jan 14, 2020 at 17:43
• @StinkingBishop Yes, all the $3\times 3$ squares.
– kora
Jan 14, 2020 at 17:46
• I may have misunderstood the question, but I was considering a partition into nine disjoint 3x3 blocks, no overlap allowed. Jan 14, 2020 at 17:46
• @StinkingBishop There are $49$, but they overlap, so you'd be double counting. You can divide the big square into $9$ disjoint $3\times3$ squares, though. The sum in each square is $369$, if I divided correctly. Jan 14, 2020 at 17:46

I believe if you take the following matrix:

$$\left[\begin{array}{ccccccccc}0&3&6&0&3&6&0&3&6\\1&4&7&1&4&7&1&4&7\\2&5&8&2&5&8&2&5&8\\3&6&0&3&6&0&3&6&0\\4&7&1&4&7&1&4&7&1\\5&8&2&5&8&2&5&8&2\\6&0&3&6&0&3&6&0&3\\7&1&4&7&1&4&7&1&4\\8&2&5&8&2&5&8&2&5\end{array}\right]$$

it already satisfies the conditions, and so does the transpose $$A^T$$:

$$A^T=\left[\begin{array}{ccccccccc}0&1&2&3&4&5&6&7&8\\etc.\end{array}\right]$$

and so does an affine combination $$B=A+9A^T+1$$, where "$$1$$" is the matrix filled with "all ones". One should verify that the resulting matrix $$B$$ has all the different values from $$1$$ to $$81$$. It begins something like this:

$$B=\left[\begin{array}{ccccccccc}1&13&25&28&40&52&55&67&79\\etc.\end{array}\right]$$

• There are, I believe, some minor typos in the matrix. A 9 in the row seven column eight. An 8 in the row 8 column 4. It's a simple typo, but I can't make an edit because it's less than 6 characters. Jan 14, 2020 at 19:12
• @ACheca Thanks, fixed Jan 14, 2020 at 19:15
• I check this, and it seems to be a correct solution. Can you explain your thought process on coming up with this, and how you can tell that the final matrix has all of the numbers from 1 to 81 present in it? Jan 15, 2020 at 4:56
• @Geoffrey If you decrement all the numbers by $1$ (to get to range $0-80$, and then represent every number in base $9$, you get an array of $2$-digit (at most) numbers. You want them to be all different, but then I went off to try to separately "fit" the first digit and the second digit (knowing that each has to appear $9$ times). Matrix $A$ was pretty much the first fit I tried, and then matrix $A^T$ just did the rest of the job. A bit lucky, I guess. To check, I just wrote all those base-$9$ numbers by superimposing matrices $A$ and $A^T$ and checked that they were all different $00-88$. Jan 15, 2020 at 6:15