I'll edit in a solution later oops

I claim that the answer is $\boxed{\text{all prime n}}$. If $n$ is prime, note that all arithmetic progressions of length $n$ either are all the same $\pmod n$ or contain every residue $\pmod n$. Note that if one row has all the same residues, then no row can contain all the residues, since there are only $n$ numbers with the same residue less than $n^2$. Hence, if one row has all the same residues, then all the rows do. In this case, we can permute the rows such that the columns are (in some order) \[\{k, k + n, k + 2n \cdots k + n^2 - n\}\]for all $0 < k \le n$. Otherwise, all rows have all different residues. In this case, sort all the rows, and the columns are (in some order) \[\{1 + kn, 2 + kn, 3 + kn, \cdots, n + kn\}\]for all $0 \le k < n$. Hence, the statement is true for all prime $n$. If $n$ is composite, write $n = ab$ and consider the construction \[\begin{bmatrix} 1 & a + 1 & 2a + 1 & \cdots & a^2b - a + 1\\ 2 & a + 2 & 2a + 2 & \cdots & a^2b - a + 2\\ 3 & a + 3 & 2a + 3 & \cdots & a^2b - a + 3\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a & 2a & 3a & \cdots & a^2b\\ a^2b + 1 & a^2b + 2 & a^2b + 3 & \cdots & a^2b + ab\\ a^2b + ab + 1 & a^2b + ab + 2 & a^2b + ab + 3 & \cdots & a^2b + 2ab\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a^2b^2 - ab + 1 & a^2b^2 - ab + 2 & a^2b^2 - ab + 3 & \cdots & a^2b^2 \end{bmatrix}\]Suppose for the sake of contradiction that you can rearrange this table to be column-valid. Consider the arithmetic progression in the column containing $a + 1$. Let it's common difference be $d$. Note that for the $(a + 1)$th term to not be in the first row, we require \[(a + 1) + a\cdot d > a^2b \implies d > ab - 1 - \frac 1a \implies d \geq ab - 1\]Since the $n$th term is at most $n^2$, we have \[(a + 1) + (ab - 1) \cdot d \le a^2b^2 \implies d \le ab + 1 - \frac{1}{ab-1} \implies d \le ab\]Note that $d \neq ab$ because otherwise the second term would be in the first row. Hence, $d = ab-1$. However, we now have that the $n$th term is \[(a + 1) + (ab-1)(ab-1) = a^2b^2 - 2ab + a + 2 = a^2b^2 - ab + 1 - (a(b-1) - 1) < a^2b^2 - ab + 1\]but then no terms can be from the last row. Hence, no column-valid rearrangement exists.

I believe the statement should say "permuting the numbers in each row", since that makes much more sense than "permitting the numbers in each row". This was not on the USAJMO though, so I am not aware of the official wording.

vsamc wrote: I believe the statement should say "permuting the numbers in each row", since that makes much more sense than "permitting the numbers in each row". This was not on the USAJMO though, so I am not aware of the official wording. You're right, I made a typo lol

BobsonJoe wrote: Note that for the $(a + 1)$th term to not be in the first row... I strongly believe that a (short) justification of why this term exists is necessary for a solution to be considered complete. In particular, this is because if $n$ is prime then such a term will not actually exist because $b=1$, which turns out to be the only point in most solutions (?) where $b>1$ is actually used. Another issue with the solution: what if some term, like $2$, comes before $a+1$ in its column after rearrangement? If you work with $2$ or $a$ instead, I believe this issue becomes side-steppable if you just take the term $a$ after $2$ or $a$, rather than the $a+1$-th term in general. I would not be surprised to see a similar fix be possible for $a+1$, but currently the step where you obtain $d \leq ab$ is flawed, since the assumption that $a+1$ is the first term in its sequence makes the bound stronger. Edit: to be clear (not saying anyone misinterpreted) the construction itself does work but the proof of why it does is a bit off.

Proof for all $n = p$ prime work (constructions provided above, and I am lazy): Weight cell with $k$ by $x^k$, with $x$ to be varied. Say that row $i$ consists of the arithmetic sequence (without any particular order) $a_i + xd_i$ as $x$ ranges from $0$ to $p-1$. Then, summing across all squares,\[x(1 + x + \ldots + x^{n^2 - 1}) = \sum_{i = 1}^p x^{a_i}(1 + (x^{d_i}) + \ldots + (x^{d_i})^{p-1}).\]Vary $x$ across the $p$th roots of unity that aren't $1$. Then, we have\[0 = \sum x^{a_i}\]across all $i$ for which $p \mid d_i$. Let $b_i$ be $a_i$ mod $p$, and are thus restricted to $< p$, so $0 = \sum x^{b_i}$. This polynomial has roots which are $p$th roots of unity not equal to $1$, hence $1 + x + \ldots + x^{p-1}$ divides this polynomial, which has degree at most $p-1$ since $b_i$ are defined to be modulo values of $a_i$. So, this polynomial is either identically $0$, where each row is complete modulo residue class, or this polynomial is equal to $1 + x + \ldots + x^{p-1}$, where $p$ divides all $d_i$ and hence each row consists of the $p$ unique elements from $1$ to $p^2$ which are $b_i$ mod $p$. So the configurations are actually pretty rigid. In the previous case, we can always rearrange the grid so that column $i$ consists of all numbers $i$ mod $p$ (clearly every column is then an arithmetic sequence with difference $p$), and in the latter case, we can just make column $i$ the consecutive numbers from $1 + (i-1)p$ to $ip$. Construction is not too hard, something along the lines of what post $3$ did should work. BobsonJoe wrote: I claim that the answer is $\boxed{\text{all prime n}}$. If $n$ is prime, note that all arithmetic progressions of length $n$ either are all the same $\pmod n$ or contain every residue $\pmod n$. Note that if one row has all the same residues, then no row can contain all the residues, since there are only $n$ numbers with the same residue less than $n^2$. Hence, if one row has all the same residues, then all the rows do. In this case, we can permute the rows such that the columns are (in some order) \[\{k, k + n, k + 2n \cdots k + n^2 - n\}\]for all $0 < k \le n$. Otherwise, all rows have all different residues. In this case, sort all the rows, and the columns are (in some order) \[\{1 + kn, 2 + kn, 3 + kn, \cdots, n + kn\}\]for all $0 \le k < n$. Hence, the statement is true for all prime $n$. If $n$ is composite, write $n = ab$ and consider the construction \[\begin{bmatrix} 1 & a + 1 & 2a + 1 & \cdots & a^2b - a + 1\\ 2 & a + 2 & 2a + 2 & \cdots & a^2b - a + 2\\ 3 & a + 3 & 2a + 3 & \cdots & a^2b - a + 3\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a & 2a & 3a & \cdots & a^2b\\ a^2b + 1 & a^2b + 2 & a^2b + 3 & \cdots & a^2b + ab\\ a^2b + ab + 1 & a^2b + ab + 2 & a^2b + ab + 3 & \cdots & a^2b + 2ab\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a^2b^2 - ab + 1 & a^2b^2 - ab + 2 & a^2b^2 - ab + 3 & \cdots & a^2b^2 \end{bmatrix}\]Suppose for the sake of contradiction that you can rearrange this table to be column-valid. Consider the arithmetic progression in the column containing $a + 1$. Let it's common difference be $d$. Note that for the $(a + 1)$th term to not be in the first row, we require \[(a + 1) + a\cdot d > a^2b \implies d > ab - 1 - \frac 1a \implies d \geq ab - 1\]Since the $n$th term is at most $n^2$, we have \[(a + 1) + (ab - 1) \cdot d \le a^2b^2 \implies d \le ab + 1 - \frac{1}{ab-1} \implies d \le ab\]Note that $d \neq ab$ because otherwise the second term would be in the first row. Hence, $d = ab-1$. However, we now have that the $n$th term is \[(a + 1) + (ab-1)(ab-1) = a^2b^2 - 2ab + a + 2 = a^2b^2 - ab + 1 - (a(b-1) - 1) < a^2b^2 - ab + 1\]but then no terms can be from the last row. Hence, no column-valid rearrangement exists. A different, working, argument for why your construction works: Focus on the number $a^2b + ab$. If the column it's in has difference $d < ab = n$, then another number in its row, $a^2 + ab - d$, would need to be in its column, which is not possible. If the column has difference $d > ab = n$, then no element in the next row can be in its column. If $d = ab = n$, then $a^2b + ab - 2d = a^2b - ab$ and $a^2 + ab - d = a^2b$, which are both in the row above it, must both be in its column, also impossible Hence this construction works

hi (will edit sol in later )

IAmTheHazard wrote: Another issue with the solution: what if some term, like $2$, comes before $a+1$ in its column after rearrangement? If you work with $2$ or $a$ instead, I believe this issue becomes side-steppable if you just take the term $a$ after $2$ or $a$, rather than the $a+1$-th term in general. I would not be surprised to see a similar fix be possible for $a+1$, but currently the step where you obtain $d \leq ab$ is flawed, since the assumption that $a+1$ is the first term in its sequence makes the bound stronger. OK I guess both bounds need some extra justification (which I don't remember if I wrote on the test oops), but it's pretty easy to fix, since if $a + 1$ is not the first term, then $d < ab$ anyways right? Hopefully just a 1 point dock?

Quite nice! The answer is the prime numbers. Firstly, let us show that composite $n{}$ do not work. Suppose that $n{}$ is composite. Let $p{}$ be a prime factor of $n{}$. On the first $p-1$ rows of the table, arrange the numbers $1,2,\ldots, n(p-1)$ in increasing order, from left to right, hence on the first line we have the numbers $1,2,\ldots,n$. On the last row, place the numbers $n^2-n+1,\ldots n^2$. The remaining $n(n-p)$ numbers are placed on the remaining $n-p$ lines according to their residue class modulo $n-p$. Suppose moreover that we may permute the numbers in each row to get a column-valid configuration. Let $n^2-n+i$ be the number on the same column as $2{}$ and let $r{}$ be the common difference of the progression on that column. Evidently, $2{}$ and $n^2-n+i$ are the smallest and largest numbers on that column, so $n^2-n+i=(n-1)r$ so $i=2$ and $r=n$. Thus, on that column we must have the numbers $2,2+n\ldots, 2+(n-1)n$ but as $2+n$ and $2+n\cdot n/p$ are congruent modulo $n-p$, we get a contradiction, since they must be on the same row, according to our construction. Consequently, all composite $n{}$ fail. Now, let's show that the prime numbers $p{}$ work. Consider a row; its elements are $a,a+b,\ldots, a+(p-1)b$. These are either all congruent modulo $p{}$ or form a complete residue set modulo $p{}$. Hence, we have two cases. The first case is that row $k$ contains all the numbers congruent to $\pi_k$ modulo $p{}$ for some permutation $\pi$ of $1,2,\ldots, p$. In this case, we may permute the numbers on each row so that each column is of the form $pi+1,pi+2,\ldots,p(i+1)$ in some order. The second case is that on each row, the numbers form a complete residue set modulo $p{}$. That is, for each $k{}$ the numbers congruent to $k{}$ modulo $p$ lie on distinct rows. It is easy to observe that we can permute the numbers in each row so that for each index $i{}$ on the $i^{\text{th}}$ column we only have the numbers congruent to $i{}$ modulo $p{}$, done. @below Good point. Anyway, I edited that part out since it wasn’t even necessary.

oVlad wrote: In the terminology of IZHO 2021/3 (which haunts me to this day), call a set of $p{}$ cells, no two of which are on the same row or column a rook. Hehe, I'd really prefer rook set like in the original IZHO problem, a rook would usually refer to just a single one of the cells

Answer is $n$ prime. To show $n=p$ works, note each row must be all the same or all different$\pmod{p}$. If all the rows are homogeneous$\pmod{p}$, just arrange each in increasing order to get a column-valid grid. On the other hand, if all the rows are completely heterogeneous$\pmod{p}$ then we can arrange them so that the columns are homogenous$\pmod{p}$, which makes a column-valid grid. If $n=ab$ is not prime with $a,b>1$, then consider the row-valid grid (for convenience shift all the numbers down by $1$) \begin{tabular}{|ccccc|} \hline $0$&$a$&$2a$&$\cdots$&$(ab-1)a$\\ $1$&$a+1$&$2a+1$&$\cdots$&$(ab-1)a+1$\\ $\vdots$&&&&$\vdots$\\ $a-1$&$2a-1$&$3a-1$&$\cdots$&$a^2b-1$\\ \hline $a^2b$&$a^2b+1$&$a^2b+2$&$\cdots$&$a^2b+ab-1$\\ $a^2b+ab$&$a^2b+ab+1$&$a^2b+ab+2$&$\cdots$&$a^2b+2ab-1$\\ $\vdots$&&&&$\vdots$\\ $a^2b^2-ab$&$a^2b^2-ab+1$&$a^2b^2-ab+2$&$\cdots$&$a^2b^2-1$\\ \hline \end{tabular}The claim is that $a^2b+ab-1$ cannot be part of an arithmetic progression with one person from every row. Indeed, if the common difference was less than $ab$ then there would be someone else in the same row, and if it were greater than $ab$ then we would skip the row below. And if the difference is exactly $ab$, then everything will be $-1\pmod{a}$, so we'll miss the top row.

The answer is $n = p,$ where $p$ is a prime. We first show that it works. Note that the sum of numbers in row-valid arrangement must be divisible by $p.$ Consider a row valid arrangement. The numbers in the row must have same remainder $($mod $ p)$, or $p$ distinct remainders $($mod $ p)$. If one row has same all same residues, then all row must have same residues too. If there is a row where there is at least two and at most $p-1$ values repeated, it is clear that the arrangement is not row- valid as the sum is not divisible by $p$. Hence, one can permute the numbers in each row so that each column has same residue $($mod $ p)$ or $p$ distinct remainders $($mod $ p)$. If $n$ is composite, then let $p$ be a prime dividing $n$. First we prove following lemma: Lemma : Let $a \geq 2$ be a positive integer. Then the arithmetic sequence $\{a, a+d, a+2d,\dots, a+(n-1)d\}$ is row/column valid if $d \leq n.$ Proof: Assume otherwise. Then, $d \geq n+1$, but notice $$a + (n-1)d \geq 2 + (n-1)(n+1) = n^2 + 1 > n^2$$ a contradiction. Hence, the lemma. Now, consider the construction \[\begin{bmatrix} 1 & p + 1 & 2p + 1 & \cdots & np - p + 1\\ 2 & p + 2 & 2p + 2 & \cdots & np - p + 2\\ 3 & p + 3 & 2p + 3 & \cdots & np - p + 3\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ p & 2p & 3p & \cdots & np\\ np + 1 & np + p + 1 & np + 2p + 1 & \cdots & 2np - p + 1\\ np+2 & np + p + 2 & np + 2p + 2 & \cdots & 2np - p + 2\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ n^2 - np + p & n^2 - np + 2p & n^2 - np + 3p & \cdots & n^2 \end{bmatrix}\] Note that each row is row-valid. Assume for contradiction that there is some arrangement where we can transform it into column-valid. Consider the element, $2np - p +1$. Let $d$ be the common difference in the column-valid arrangement of $2np - p +1$. So by the lemma if smallest term of this column is greater than $1$ then $d \leq n$. But, $$2np - p + 1 - d \geq 2np - p + 1 - n = np + (n-1)(p-1) > np.$$ Which is a contradiction, because it would mean $2np - p + 1 - d$ is in the same row as $2np - p + 1.$ If first term is $1$ but $d \leq n$, the above inequality still holds. If first term is $1$ and $d = n+1$, then $$2np - p \equiv 0 \implies 3p \equiv 0 (mod\ n+1) \implies n+1|3p \implies n+1 \in \{1,3,p,3p\}.$$ But note that, as $p|n$ and $n \geq 3$, each of these cases dont work. Thus, the construction works. And we are done.

Full solutions of USAMO 2023: https://www.youtube.com/watch?v=Eqy0345YhoY Full solutions of USAJMO 2023: https://www.youtube.com/watch?v=TyVbbMxe7II

All the constructions for composite above seem roughly similar, I would like to check this much simpler one: Suppose $n=xy$. In the first $y$ rows, we only use numbers which are $\equiv 0 \pmod{x}$. This is possible for example $\{x,\cdots,nx\},\{(n+1)x,\cdots,2nx\},\cdots,\{((y-1)n+1)x,\cdots,ynx\}$. In the next $y$ rows, we only use numbers which are $\equiv 1 \pmod{x}$. We keep going, until the last $y$ rows only use numbers which are $\equiv (x-1)\pmod{x}$. This cannot be permutated to be column valid because any column would be $0,\cdots,0,1,\cdots,1,\cdots,x-1,\cdots,x-1\pmod{x}$, which is not an AP$\pmod{x}$, so it cannot be an AP. Unrelated note: I love the title of this thread.

gghx wrote: All the constructions for composite above seem roughly similar, I would like to check this much simpler one: Suppose $n=xy$. In the first $y$ rows, we only use numbers which are $\equiv 0 \pmod{x}$. This is possible for example $\{x,\cdots,nx\},\{(n+1)x,\cdots,2nx\},\cdots,\{((y-1)n+1)x,\cdots,ynx\}$. In the next $y$ rows, we only use numbers which are $\equiv 1 \pmod{x}$. We keep going, until the last $y$ rows only use numbers which are $\equiv (x-1)\pmod{x}$. This cannot be permutated to be column valid because any column would be $0,\cdots,0,1,\cdots,1,\cdots,x-1,\cdots,x-1\pmod{x}$, which is not an AP$\pmod{x}$, so it cannot be an AP. Unrelated note: I love the title of this thread. It is an AP though? Congruent to 0,1,2,3,…,xy mod x after rearranging

The answer is all prime $n$. Proof that prime $n$ work: Suppose $n=p$ is prime. Then, let the arithmetic progressions in the $i$th row have least term $a_i$ and common difference $d_i$. For each cell with integer $k$, assign a monomial $x^k$. The sum of the monomials is \[ x(1+x+\ldots+x^{n^2-1}) = \sum_{i=1}^n x^{a_i}(1+x^{d_i}+\ldots+x^{(n-1)d_i}), \]where the LHS is obtained by summing over all cells and the RHS is obtained by summing over all rows. Let $S$ be the set of $p$th roots of unity that are not $1$; then, the LHS of the above equivalence vanishes over $S$ and the RHS is \[ \sum_{p \mid d_i} x^{a_i}. \]Reducing the exponents (mod $p$) in the above expression yields \[ f(x) := \sum_{p \mid d_i} x^{a_i \pmod{p}} = 0 \]when $x \in S$. Note that $\prod_{s \in S} (x-s)=1+x+\ldots+x^{p-1}$ is a factor of $f(x)$, and as $f$ has degree less than $p$, $f$ is either identically 0 or $f(x)=1+x+\ldots+x^{p-1}$. If $f$ is identically 0, then $p$ never divides $d_i$. Thus, no two elements in each row are congruent $\pmod{p}$, so all residues are represented in each row. Now we can rearrange the grid so that column $i$ consists of all numbers $i \pmod{p}$, which works. If $f(x)=1+x+\ldots+x^{p-1}$, then $p$ always divides $d_i$. It is clear that each $d_i$ must be $p$, so each row represents a single residue $\pmod{p}$. Thus, we can rearrange the grid so that column $i$ contains all consecutive numbers from $1 + (i-1)p$ to $ip$, which works. All in all, any prime $n$ satisfies the hypotheses of the problem. Proof that composite $n$ do not work: We present a general counterexample that shows that composite $n$ do not work. For composite $n$, let $n=ab$ for $a, b>1$. Construct the row-valid grid where For $1 \le i \le a$, row $i$ consists of an increasing arithmetic progression with starting term $i$ and common difference $a$. For $a+1 \le i \le ab$, row $i$ consists of an increasing arithmetic progression with starting term $(i-1)ab+1$ and common difference $1$. Look at the term $a^2b+ab$; we claim it cannot be part of a column that has cells forming an arithmetic sequence after any appropriate rearranging. After such a rearrangment, if the column it is in has common difference $d<ab=n$, then $a^2+ab-d$ must also be in its column, which is impossible. If the column has difference $d > ab = n$, then no element in the next row can be in its column. If the common difference is $d = ab = n$, then $a^2b + ab - 2d = a^2b - ab$ and $a^2 + ab - d = a^2b$, which are both in the row above it, must both be in its column, which is impossible. Therefore, the grid is not column-valid after any rearrangement, which completes the proof.

Answer is primes. Proof composite fail: Take a prime $p \mid n$. Note that a row-valid grid exists with first row $2, 2 + p, \dots, 2 + (n - 1)p$. A construction is to have the following rows be $$1, 1 + p, \dots, 1 + (n - 1)p$$$\vdots$ $$p, 2p, \dots, np$$ Now, for all numbers from $np + 1$ to $n^2$ simply place them in order in a row from left to right before moving to the next row. Note that this arrangement is not column valid as for this to happen, another arithmetic sequence must exist with 2 that shares none of the terms of $2, 2 + p, \dots, 2 + (n - 1)p$. Note that if such a sequence has common difference $d < n$, note that $2 + pd$ is found in both sequences. (If $d = 1$ it is still found since $p + 2 \le n$) $d = n$, note that $1 + n$ is in both sequences. $d > n$ is impossible by bounding. Therefore, this is impossible. Proof primes work: Consider a row-valid grid. Case 1: Every row arithmetic sequence has common difference not equal to $n$ Note that since $n$ is prime, each sequence will cover all residues mod $n$. We can rearrange to form a column with all $0 \pmod n$ residues, $1 \pmod n$ residues, etc. Case 2: 1 or more sequences have common difference $n$ I claim in this case, every sequence must have common difference $n$, which clearly works (1 through $n$ in column 1, $n + 1$ through $2n$ in column 2, etc.) To prove the claim, consider 1 of these sequences with common difference $d \neq n$: $a, a + d, \dots$. Note that this covers every residue mod $n$ including a term of the row arithmetic sequence with common difference. Therefore, it's not possible to have a sequence with common difference $d \neq n$.

Solved with hint from lrjr24 I think this works. If it doesn't please correct me. We claim that the answer is all $n$ that are primes. First, we prove that all primes work. Note that every single progression in a row, must have the same rate of change (this works for all $n$). For primes, we are forced to choose between two progressions because it's prime. We have either \[\{\{1,2,3,\cdots, p\},\{p+1,p+2,\cdots, 2p\},\cdots, \{p^2-p+1,p^2-p+2,\cdots, p^2\}\}\]or \[\{\{1,1+p,1+2p,\cdots, p^2-p+1\},\{2,2+p,2+2p,\cdots,p^2-p+2\}, \cdots, \{p,2p,\cdots p^2\}\}\]These obviously must both form row-valid and column-valid. Now, FTSOC, all composite $n$ have the given condition. Let $1, n \neq d | n $. Consider the row-valid arrangement. \[\{\{1,1+d,1+2d,\cdots, 1+(n-1)(d))\}, \cdots, \{ (nd)(\frac{n}{d}-1)+d, (nd)(\frac{n}{d}-1)+2d, \cdots, n^2\}\}\}\]where the least value of each row are $\{1,2, \cdots, d, (nd)+1, (nd)+2, \cdots, (nd)+d, (nd)(2)+1, \cdots (nd)(2)+d, \cdots, (nd)(\frac{n}{d}-1)+1, \cdots (nd)(\frac{n}{d}-1)+d \}$. Arrange the rows from least to greatest. Note that $k$-th term of row must form an arithmetic sequence with the $k$-th term of the next sequence. This is because otherwise it wouldn't satisfy the same rate of change rule. But, when we transition from $d \rightarrow e+1$, it must still have the same rate of change but $d \neq e$, so we have a contradiction.

took an embarassingly long amount of time...can't be doing this on the actual usamo The answer is prime $n.$ We first show composite $n$ fail. Pick $p \mid n$ and consider the following construction: \[\begin{bmatrix}1 & 1+p & 1+2p &\dots &1+(n-1)p \\ 2 & 2+p & 2+2p &\dots &2+(n-1)p \\ &\vdots \\ p & 2p & 3p &\dots &np \\ np+1 & np+2 & np+3 &\dots &np+n \\ &\vdots \\ n^2-np+p & n^2-np+2p & n^2-np+3p &\dots &n^2\end{bmatrix}\]Consider an arithmetic sequence with $2.$ Let $d$ be the common difference. Then \[n^2 \leq 2+(n-1)d \implies d \leq \tfrac{n^2-2}{n-1}<n+1,\]so $d \leq n.$ But observe that if there were to be a column-valid arrangement, the term $2+pd$ would have to be contained in both the same row and same column as $2,$ which is absurd. It remains to show prime $n$ work. There are two cases: if there do not exist rows with common difference $d=n,$ and if there do exist rows with common difference $d=n.$ Consider the former case. Since $n$ is prime, each row covers all residues modulo $n.$ Then, rearrange the rows so that each column comprises of numbers that are same modulo $n.$ Consider the latter case. In fact, this case implies that every row must have common difference $n.$ Observe that there are only $n$ numbers less than $n^2$ which have same residues modulo $n.$ Thus, if there is one row with common difference $d=n$ (that is, with all residues identical modulo $n$), than all other rows are also forced to have identical residues modulo $n,$ because it is impossible to generate a row with all different residues.

We claim that only primes work, so let's prove it. First, if $n$ is some prime $p$, then we can take each number mod $p$ and the numbers in each row must be some permutation of $0, 1, \ldots, p-1$, so we can simply rearrange the rows so each column is the same mod $p$, which will make the grid column-valid. Now we show a counterexample for $n$ not prime. Let the first row be $1, 2,\ldots, n$. Choose a proper divisor $d$ of $n$, and let the next $d$ rows have the starting number be $n+1, n+2, \ldots, n+d$ respectively, with common difference $d$, such that each number in each of the $d$ rows are the same mod $d$. Consider the arithmetic sequence with $1$. The common difference must be $\geq n$ and $\leq n+1$ because $1+(n-1)=n$ is in the same row as $1$ and $1+(n+2)(n-1) = n^2 + (n-1) > n^2$ for all $n\geq 3$. Now we will show that the common difference can be neither $n$ nor $n+1$. If the common difference is $n$, then we have $1+2n$ is in the sequence, but $1+n+d(\frac{n}{d})$, which is in the second row since $\frac{n}{d}\leq n-1$, but we can't have both $1+n$ and $1+2n$ in the same row. If the common difference is $n+1$, then the sequence with $1$ works out. So now, we consider the sequence with $2$, where the common difference is either $n$ or $n-1$. The common difference can't be $n$ because the column with $1$ and the column with $2$ would both use $n+2$. Instead, if we choose $n-1$, then $2+(n-1)(d+1) = n+1 + d(n-1)$, which can't happen because $n+1$ and $2+(n-1)(d+1)$ would be in the same row. Since we've checked all the cases, and found none of them possible, we're done.

Our answer is $\boxed{\text{all primes}}$. When $n$ is prime, an arithmetic sequence with $n$ terms must will either contain all distinct or equal residues modulo $n$. Then it becomes clear that, once we select the first row to have either one of these properties, all other rows will share that property. If every row has all distinct residues, we can permute them so that each column has cells of equal residues and vice versa, thus producing a column-valid configuration. We move on to proving $n=pk$ for a prime $p$ and $k>1$ won't hold. Consider a construction where we place the first $p^2k$ numbers in (rightwards) increasing order on rows based on residue modulo $p$, and place the remaining $p^2k^2-pk$ numbers underneath in (downwards) increasing order on columns based on residue modulo $p$. Through contradiction, use a bounding argument on the common difference of a sequence containing $p+1$ to show this arrangement cannot be made column-valid. $\blacksquare$

Great problem! Claim 1: If $n$ is prime, it's satisfied. Firstly, take $k$ where $1 \leq k < n$. Now take the numbers: $$k, k + d, k + 2d, \dots, k + (n - 1)d$$where $d$ denotes the common difference. Observe that $d \leq n$, which we can see by taking extreme ends of a row as $1$ and $n^2$, which yields: $$1 + (n - 1)d = n^2 \implies (n - 1)(n + 1) = (n - 1)d \implies d = n + 1$$For any other arrangement, $d \leq n$. However, say 2 of these, $k + ad$, $k + a_1d$ (where $a_1 > a$, and $a_1 - a < n$) lie in the same row and $d < n$, it would take more than $n$ terms for $d$ to "get to" $a_1$ in time, which means $d \geq n \implies d = n$. So, either $k, k + n, \dots, k + n(n - 1)$ lie in the same row or they all lie in different rows. If they lie in the same row, notice that they all have the same residue $\mod n$ ($k$), and there are $n$ numbers having this residue between $1$ and $n^2$, which means the row is taking up all these numbers, which implies each row will have numbers with the same residue $\mod n$. Rearranging them into columns with each column having the same residue, we are done. If they lie in different rows, each row produces all distinct residues $\mod n$, so we simply rearrange them so that each column once again possesses the same residue $\mod n$. So we are done. Claim 2: It doesn't work for composites. Take a composite number $n$, where $n = ab$, $1 < a \leq b < n$. Take the following construction: \begin{tabular}{|ccccc|} \hline $1$ & $a+1$ & $2a+1$ & $\cdots$ & $(ab-1)a+1$ \\ $2$ & $a+2$ & $2a+2$ & $\cdots$ & $(ab-1)a+2$ \\ $\vdots$ & & & & $\vdots$ \\ $a$ & $2a$ & $3a$ & $\cdots$ & $a^2b$ \\ \hline \end{tabular}We will have $b$ such tables continuing until we reach $a^2b^2$ in the bottom right. Notice that the common difference, $d \leq n$ (as mentioned earlier), and $d \leq n - 1$ as it would cause us to take too many terms in the first table, which means $d = n$. We know the terms are $a \mod{ab} \implies a \mid \text{terms of the A.P}$, however, all the terms in the first row are $1 \mod {a}$, which causes a contradiction. So we are done.

We claim that only primes work. For composites, consider the smallest prime factor of $n$, say $p$. Consider if the first row is $A=\{p,2p,3p,\dots,np\}$. If $a$ is the common difference in the column that $p$ is in after the transformation, then $p+ap>np$ or else $p+ap\in A$ which cannot occur. Hence, $a>n-1$ but note $a=n$ is also bad as $p+n\in A$. Hence, $a\ge n+1$ so the final element of the column is at least $p+(n-1)(n+1)=n^2+p-1>n^2$, absurd. For primes, notice if $a$ and $a+p$ are in a row then the common difference $d$ of this row must divide $p$ so $d=1$ or $d=p$. In the former case the row is $a,a+1,\dots,a+p$ which has too many elements. In the latter case, the row is all numbers congruent to $a$ modulo $p$. Call such rows bland. On the other hand, if all elements of a row are distinct from each other modulo $p$, the row is a complete residue class modulo $p$. Call such rows tasty. Notice if we have a bland row, we cannot have any tasty rows and vice versa. Hence, we either have all bland rows or all tasty rows. Note from a bland configurations we can sort the columns to all be tasty and from a tasty configuration we can sort all columns to be bland. Thus, primes work. $\square$

The answer is $n$ prime only. Construction: Let $n=p$ be prime. We let $S_1, S_2, \dots$ denote the arithmetic progressions formed when row entries are ordered, and let $d_1, d_2, \dots$ be their common differences. Claim. If $d_i = p$ for some $i$, then $d_i=p$ for all $j$. Proof. Suppose $d_j \neq p$ for some $j$. Then there exists some element in $S_j$ that is $i$ mod $p$ as it has $p$ elements. This means $S_i$ and $S_j$ have nonempty intersection, contradiction. $\blacksquare$ In the case where $d_i = p$ for every $i$, we can permute the columns to read $(1, 2, \dots, p)$, $(p+1, p+2, \dots, 2p)$, and so on in some order. If $d_i \neq p$ for all $i$, then we can permute the columns to read $(1, p+1, \dots)$, $(2, p+2, \dots)$ and so on in some order as no two elements in each row will ever differ by a multiple of $p$. Restriction: Suppose that $n$ is composite, and fix some $p \mid n$. Let the rows read \[r_{qp+r} = (qpn+i, qpn+i+p, \dots, qpn+i+(n-1)p)\]for $1 \leq r \leq n$ and $0 \leq p \leq n-1$. Then consider picking the arithmetic sequence that starts with $2$, which is in say row $R$. For any $d \leq n$ relatively prime to $p$, the number $dp + 2$ appears in $R$, implying that $d$ cannot be a common difference for this arithmetic sequence. For any $n \geq d = kp$ for some $k < n/p$, again the number $2+kp$ must show up in $R$, so this $d$ cannot be a valid common difference either. Note that obviously $d < n+1$ by size. So such an arithmetic sequence cannot exist, contradiction.

The answer is $n = p$ for all primes $p$. For our construction, WLOG the common difference for none of the rows is $p$. Then each row has $p$ numbers that are all distinct modulo $p$, from which it is easy to permute the rows so that column $i$ only contains numbers that are $i \pmod p$, done. If the common difference of a row is $p$, then that row contains all numbers from $1$ through $p^2$ that are $k \pmod p$ for some $k$. However, if another row has common difference that is not $p$, then it will contain a number that is $k \pmod p$, which is impossible. So then all rows have common difference $p$, from which it is easy to permute the rows so that the columns are $1 + pm$, $2 + pm$, $\dots$ for some $m < p$. To prove impossibility for $n \neq p$, we consider the following counter-construction. Let $d \mid n$, so that $d \neq 1, n$. Then let the first $d$ columns be $(d - i, 2d - i, \dots, nd - i)$, varying $i$ with $i = 0, 1, \dots, d-1$. Then let the remaining $n - d$ columns be $(n(d+i) + 1, n(d+i) + 2, \dots)$, varying $i$ once again with $i = 0, 1, \dots, n - d - 1$. We show that cell $nd + 1$ cannot belong to a valid column. If $nd + n$ belongs to a column with common difference less than $n$, then it is a clear contradiction. If the common difference is more than $n$ we clearly will not have enough space as $\frac{nd + n - 1}{n+1} < 1$. If the difference is $n$ exactly then clearly this doesn't work as $nd + n - kn$ is $0$ modulo $n$ and some rows obviously do not contain any $0$ modulo $n$ numbers, for example $i = 1$ so we are done.

Let $n$ be \textit{good} if and only if it is possible to transform any row-valid arrangement into a column-valid arrangement by permuting the numbers in each row of an $n \times n$ table. Now, we claim the following. Claim : All composite integers $n \geq 3$ are not good by the following construction. Proof : Let $p$ be the smallest prime factor of $n$. Then, since $n>p$, consider the below construction. Let $d$ be the common difference of the arithmetic progression of a certain row or column. \begin{tabular}{c c c c c| c} 1 & 2 & 3 & $\cdots$ & $n$ & $d = 1$ \\ $n+1$ & $2n-p+1$ & $3n-2p+1$ & $\cdots$ & $n^2 + p-pn + 1$ & $d=n-p$\\ $n+2$ & $2n-p+2$ & $3n-2p+2$ & $\cdots$ & $n^2 + p -pn + 2$ & $d=n-p$\\ $\vdots$ & $\vdots$& $\vdots$& $\vdots$ & $\vdots$ & $d=n-p$\\ $2n-p$ & $3n-2p$ & $4n-3p$ &$\cdots$ & $n^2 + n -pn$ & $d=n-p$ \\ $n^2+n-pn+1$ & $n^2 +n -pn +2$ & $n^2 +n -pn +3$ & $\cdots$ & $n^2 + 2n - pn$ & $d=1$\\ $\vdots$ &$\vdots$ &$\vdots$& $\vdots$ & $\vdots$ & $d=1$\\ $n^2 -2n + 1$ & $n^2 -2n + 2$ & $n^2 -2n +3 $ & $\cdots$s & $n^2 -n$ & $d=1$\\ $n^2 -n +1 $ & $n^2 -n +2$ & $n^2 -n +3$ & $\cdots$ & $n^2$ & $d=1$ \end{tabular} Here, the first row is $1,2,\cdots n$ and the next $n-p$ rows start with $n+1 , n+2 , \cdots 2n-p$ respectively and have common difference $n-p$. Then, the remaining columns fill in the integers from $n^2+n-pn+1$ to $n^2$ with common difference 1 in each row. Now, it is obviously clear that this arrangement is row-valid. If it is column valid then the first column must be an arithmetic progression. Since it is clearly in increasing order in the table from top to bottom, the common difference must be $n+1-1=n$, which is impossible if $n+2$ lies on this column as well. Thus, clearly this arrangement is not column-valid and we are done. Now, we shall show that all primes $p\geq 3$ are indeed good. Consider the following key claim. Claim : We will always have $c,p+c,\cdots, p^2 - p + c$ for all $1\leq c \leq p$ all in the same row or all in $p$ different rows. Proof : Simply notice that if $k_1p+c$ and $k_2p+c$ lie on the same row, they must be members of an arithmetic progression with common difference $d \mid (k_2-k_1)p$ but it is easy to see that each arithmetic progression cannot have a common difference greater than $p+1$ since, $$1 + (p-1)d \geq 1 + (p-1)(p+1) = p^2$$Thus, the common difference must indeed be $p$ which means indeed this row contains $c,p+c,\cdots, p^2-p+1$ as claimed. Now, we proceed by induction say we have that there exists $k<p$ rows which are $1,p+1,\cdots$ , $2,p+2,\cdots,$ and so on up to $k, p+k, \cdots$. Then, consider the row containing $k+1$ (which is the smallest unplaced number). Notice that if this row has common difference $d$, then if $d<k$ $$k+1 + d(p-1)= dp - d + k + 1 \leq dp \leq dp + (d-1)$$also $$k+1+d(p-1)=dp-d+k+1 > dp + d - p -2= (d-1)p + (d-2)$$Thus, we have the sequence $k+1, k+1 + d , \cdots$. We notice that it is impossible to have any two terms which are the same modulo $p$ since $$k+1 +c_1d \equiv k+1 +c_2d \implies (c_2-c_1)d \equiv 0 \pmod{p} $$Thus, since we have exactly $p$ terms in this arithmetic sequence each must be different mod $p$. ($c_2\neq c_1$) unless $d=p$. Thus, there must exist some term which is $1 \pmod{p}$. But since the first row already has all terms which are $1 \pmod{p}$ this is impossible. The case when $d\geq k$ is similar since here too, we have atleast $d$ terms in Row 1 less than the largest term in the row containing $k+1$. This means that no other arithmetic sequence is possible forcing this row also to be $k+1,k+1+p, \cdots$. Thus, indeed the only possible row-valid configuration is the one with rows with minimum elements $1,2,\cdots,p$ with common difference $p$. But then it is easy to see that we have the column-wise arithmetic progressions, $1,2,\cdots,p$ ; $p+1,p+2,p+3,\cdots,2p$ ; $\cdots$ ; $p^-p+1,p^2-p+2,\cdots,p^2$ since we have the modulo classes $\pmod{p}$ is in different rows as shown before. Thus, indeed for $n\geq 3$, every row-valid arrangement is also column-valid if and only if $n$ is a prime.