Consider a $6 \times 6$ grid. Define a diagonal to be the six squares whose coordinates $(i,j)$ ($1 \le i,j \le 6)$ satisfy $i-j \equiv k \pmod 6$ for some $k=0,1,\dots,5$. Hence there are six diagonals. Determine if it is possible to fill it with the numbers $1,2,\dots,36$ (each exactly once) such that each row, each column, and each of the six diagonals has the same sum.
Problem
Source: Taiwan 2014 TST3 Quiz 1, P1
Tags: analytic geometry, modular arithmetic, combinatorics proposed, combinatorics
08.10.2014 23:49
The answer is NO. Suppose an arrangement is possible. The equal sum is $ 111 $, hence, the number of odd entries in each row, column and diagonal is odd. For the $ 6 \times 6 $ grid $ G $, let $ [k] = \{ (i,j) \mid (i,j) \in G , i-j \equiv k ( \bmod 6) \} $, $ k \in \{0,1, \ldots ,5 \} $. Define \[ S = \sum_{(i,j) \in G} (i-j) \chi(i,j) \] where $ \chi(i,j) $ is the indicator function. Calculate $ S $ in $ \mathbb{F}_2 $ in two different ways. First, \[ S = \sum_{(i,j) \in G} i \chi(i,j) -j \chi(i,j) = \sum_{i=1}^{i=6} \sum_{j=1}^{j=6} i \chi(i,j) - \sum_{j=1}^{j=6} \sum_{i=1}^{i=6} j \chi(i,j) \] \[ = \sum_{i=1}^{i=6} i \left( \sum_{j=1}^{j=6} \chi(i,j) \right) - \sum_{j=1}^{j=6} j \left( \sum_{i=1}^{i=6} \chi(i,j) \right) = \sum_{i=1}^{i=6} i - \sum_{j=1}^{j=6} j = 0 \] But we also have, \[ S = \sum_{k=0}^{k=5} \sum_{(i,j) \in [k]} (i-j) \chi(i,j) = \sum_{k=0}^{k=5} k \left(\sum_{(i,j) \in [k]} \chi(i,j) \right) = \sum_{k=0}^{k=5} k = 1 \] contradiction.
09.10.2014 01:53
Yep, parity works. Another way to phrase the same ideas: color the grid as follows: ABABAB *C*C*C ABABAB *C*C*C ABABAB *C*C*C Let $A$ be the sum of the guys colored A, and define $B$, $C$ similarly. If the common sum is $111$, then $A+B=333$, $B+C=333$, $C+A=333$, contradiction. And you can get this for any $n \equiv 2 \pmod 4$.
10.04.2020 12:22
Evan whats n?
10.04.2020 18:57
The size of the grid (i.e. the same proof works for a $10 \times 10$, $14 times 14$, etc.)
13.03.2021 02:33
Note the sum of all entries is $1 + 2 + \ldots + 36 = 18 \cdot 37$, covering a total of $6$ nonoverlappig columns. So the common sum is $3 \cdot 37 = 111$. Say we consider the $k = 1, 3, 5$ rows and columns, along with the $k = 1, 3, 5$ diagonals, of whose cells sum (with overlap) to $9 \cdot 111 = 999$. Funnily enough, this sum counts every cell in the union of these $6$ rows/colums and $3$ diagonals twice, so the sum must be even, contradiction. Not possible.
30.12.2022 20:48
I'm not sure if this is the best or the worst problem I've ever seen, but it's definitely one of the two. The answer is no. Suppose it was possible, and view the grid as a torus, so the top and bottom rows are consecutive. The shared sum must equal $\frac{36(37)}{2(6)}=3\cdot37$, which is crucially odd. Consider any three consecutive rows and three consecutive columns. The sum of the row elements is odd, as is the sum of the column elements. Thus the sum of elements in any "diagonal pair of 3x3 squares" is even. An example of what this term means is below (marked by the X's—though the O's also form a diagonal pair) XOOOXX OXXXOO OXXXOO OXXXOO XOOOXX XOOOXX Now consider the diagonal passing through the centers of the squares, as well as the two diagonals next to it. The below grid shows the diagonals marked by X's for the above example. OOOXXX OOXXXO OXXXOO XXXOOO XXOOOX XOOOXX The sum of the elements in these three diagonals is odd. Adding this to the first group of X's gives us that the sum of elements in the X-marked squares is odd: XOOXOO OXOOXO OOOOOO XOOXOO OXOOXO OOOOOO Since we're working on a torus, vertically rotating these X's once and twice, and adding them to the above grid gives us that the sum of elements in X-marked squares below is odd as well: XXOXXO XXOXXO XXOXXO XXOXXO XXOXXO XXOXXO But if we sum these elements directly by column, the sum should be even: contradiction. $\blacksquare$
15.11.2023 18:24
No. Let each sum be $S$ which is odd. Add the odd columns and even rows which sum to $6S$. Then, subtract $3$ diagonals which have sum $3S$ and cover all cells with even coordinate sum. What we are left with is each square with odd $x$ coordinate and even $y$ coordinate being shaded twice. However, this has sum $3S$ which is odd and a contradiction as each cell is counted an even number of times.
07.08.2024 03:37
No. Fill every other row with the letters $ababab$ and for all other rows $cdcdcd.$ The $c$ will be ignored. Let the capital letter denote the sum of all the small letters. Then $A+B=B+D=D+A=333,$ which is not possible for integers$.\blacksquare$
03.10.2024 15:27
06.01.2025 20:18
Honestly surprisingly tricky for a parity argument. The answer is no. Suppose otherwise; then every row, column, and diagonal of the grid has sum $3 \times 35 = 105$, which is odd. Consider the symmetric difference $\mathcal R_{\mathrm{odd}} \Delta \mathcal C_{\mathrm{odd}}$ consisting of all the squares of the grid with row and column indices of differing parity. On one hand, the sum of the numbers in these squares has the same parity as the multiset union $\mathcal R_{\mathrm{odd}} \cup \mathcal C_{\mathrm{odd}}$, which is even. On the other hand, this set consists of three diagonals of the grid, so it should have an odd sum. This yields a contradiction.