Assume we can fill a table $n\times n$ with all numbers $1,2,\ldots,n^2-1,n^2$ in such way that arithmetic means of numbers in every row and every column is an integer. Determine all such positive integers $n$.
Problem
Source: Czech and Slovak Olympiad 2019, National Round, Problem 6
Tags: Combinatorial Number Theory, numbers in a table, national olympiad, number theory
07.06.2019 19:50
Partial solution: I show that all integers except for $4k+2$ work. Claim $1$: All odd integers work. Proof: Put them in the "regular" way, i.e. first row being $1,2,....n$, second one being $n+1,n+2,...2n$, and so on till we reach the last row being $n^2-n+1,n^2-n+2,....n^2$ and check that this works. Claim $2$: $2^k$ works for $k \geq 2$ Proof: Use the following tiling: $1,3,5,7….2^{k+1}-1$ $2*2^{k+1}-1,2*2^{k+2}-3,...2^{k+1}+1$ and make similar "pairs" of numbers at each two rows, until all odd numbers are exhausted( which is exhausting half of the rows) and then use this tactic: $2,4,6,8.....2^{k+1}$ $2*2^{k+1}-2,2*2^{k+1}-4,.....2^{k+1}-2,2*2^{k+1}$ again making similar pairs like this in each two rows, until all numbers are exhausted. One can easily check that this works, and see why this isn't applicable for $2^1=2$ Claim 3:$2^nr$ works where $n \geq 2$ and $r$ is odd. Proof: Call $k$ the strategy we used in the $2^n*2^n$ cells . For a number $q$, $k+q$ is that same strategy applied except the numbers are added by $q$ in each cell. Then use the following tactic: $k,k+2^{2n},k+2*2^{2n},...k+(r-1)2^{n}$ $k+2^{2n}r,k+2^{2n}(r+1),....k+2^{2n}(2r-1)$ $...………………………………………………………………$ $...……………………………………..k+2^{2n}(r^2-1)$ and check that this works.
29.06.2019 17:32
The answer is all positive integers except 2.
14.07.2019 13:17
Ok, so any proof for integers of the form $4k+2$ but which are greater than $2$? I couldn't prove it for that case.
27.09.2019 02:26
First of all, notice that we essentially just need to make all row and column sums divisible by $n.$ Hence, we can go ahead and reduce all entries of the grid modulo $n$. Therefore, let's replace $1, 2, \cdots, n^2$ with $n$ copies of $0$, $n$ copies of $1$, $n$ copies of $2$, $\cdots$, and $n$ copies of $n-1.$ For odd $n$, simply place the $0$'s in the first row, the $1'$ in the second row, etc. For $4 | n$, let $n = 4k.$ Then, for $i \neq k, 3k$, we will let the $(i+1)$th row consist of only $i$'s. The $k$th and $3k$th rows will read $k, 3k, k, 3k, \cdots, k, 3k$ from left to right. It's easy to check that this grid works. For $4| n-2$, let $n = 4k+2.$ Then, begin by letting the $(i+1)$th row consist of only $i$'s, for $0 \le i < n.$ Now, we'll make the following edits. For $1 \le i \le 2k$, add $2k+1$ to the $i$th and $(i+1)$th entries in the $i$row. For $i = 2k+1$, add $2k+1$ to the first and $(2k+1)$th entries in the $i$th row. For $2k+2 \le i \le 4k+2$, add $2k+1$ to the $2(i - 2k-1)$th and $(2(i-2k-1)-1)$th entries in the $i$th row. It can be checked that this grid now works, and has exactly $n$ things which are $0, 1, 2, \cdots, n-1$ modulo $n$. $\square$
24.04.2020 20:09
as others said n odd is trivial now suppose n=2k it makes that only remainders by 2k are important i make a Latin square by 0,1 , ...., k-2 and what is needed in order to 2k divides each column , name this square S then suppose 2^a<2k<2^a+1 now S , S+2^a S+2^a-1 , T which T is the Latin square made by others reminders work . you can prove details your self
02.07.2024 21:14
official solution: https://www.matematickaolympiada.cz/media/3459596/a68angl.pdf#page=22