Double dose of cyanide on day 2

Art of Problem Solving

AoPS Online

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

Contests & Programs AMC and other contests, summer programs, etc.

AMC and other contests, summer programs, etc.

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Double dose of cyanide on day 2

G H J

Reveal topic tags

arithmetic sequence

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: USAMO 2023/5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1201 posts

#1 h Mar 23, 2023, 10:20 PM • 2 Y

Y by v4913, kred9

Let $n\geq3$ be an integer. We say that an arrangement of the numbers $1$ , $2$ , $\dots$ , $n^2$ in a $n \times n$ table is row-valid if the numbers in each row can be permuted to form an arithmetic progression, and column-valid if the numbers in each column can be permuted to form an arithmetic progression. For what values of $n$ is it possible to transform any row-valid arrangement into a column-valid arrangement by permuting the numbers in each row?

This post has been edited 1 time. Last edited by brianzjk, Mar 23, 2023, 11:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1201 posts

#2 h Mar 23, 2023, 10:23 PM • 1 Y

Y by centslordm

The answer is Click to reveal hidden text

I'll edit in a solution later oops

This post has been edited 1 time. Last edited by brianzjk, Mar 23, 2023, 10:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

811 posts

#3 h Mar 23, 2023, 10:46 PM • 1 Y

Y by rayfish

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3789 posts

vsamc

#4 h Mar 23, 2023, 11:26 PM • 1 Y

Y by centslordm

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1201 posts

#5 h Mar 23, 2023, 11:35 PM • 1 Y

Y by vsamc

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5005 posts

#6 h Mar 24, 2023, 12:36 PM • 1 Y

Y by centslordm

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.

This post has been edited 5 times. Last edited by IAmTheHazard, Mar 24, 2023, 2:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2725 posts

#7 h Mar 24, 2023, 1:21 PM • 1 Y

Y by sargamsujit

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

This post has been edited 2 times. Last edited by jj_ca888, Mar 24, 2023, 2:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

579 posts

#8 h Mar 24, 2023, 2:59 PM

Y by

hi (will edit sol in later

)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

811 posts

#9 h Mar 24, 2023, 4:32 PM

Y by

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1746 posts

oVlad

#10 h Mar 25, 2023, 2:04 PM • 1 Y

Y by gvole

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.

This post has been edited 3 times. Last edited by oVlad, Mar 27, 2023, 5:06 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#11 h Mar 26, 2023, 12:10 AM • 4 Y

Y by oVlad, HamstPan38825, gvole, mathmax12

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

626 posts

#12 h Mar 28, 2023, 11:29 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

68 posts

#13 h Mar 29, 2023, 5:44 PM • 2 Y

Y by surpidism., ABYSSGYAT

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.

This post has been edited 5 times. Last edited by Thapakazi, Mar 29, 2023, 7:31 PM
Reason: Error

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

#14 h Mar 30, 2023, 12:25 AM

Y by

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

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1072 posts

gghx

#15 h Apr 2, 2023, 5:48 AM • 1 Y

Y by sabkx

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.

This post has been edited 1 time. Last edited by gghx, Apr 2, 2023, 5:49 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5005 posts

#16 h Apr 8, 2023, 11:39 PM • 1 Y

Y by centslordm

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#17 h Apr 18, 2023, 9:46 PM

Y by

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.

This post has been edited 2 times. Last edited by Leo.Euler, Apr 19, 2023, 1:01 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1437 posts

#18 h Apr 29, 2023, 12:37 AM

Y by

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$ .

This post has been edited 3 times. Last edited by pi_is_3.14, Apr 29, 2023, 1:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

657 posts

#19 h May 6, 2023, 3:32 AM • 1 Y

Y by KevinYang2.71

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.

remarks

This post has been edited 2 times. Last edited by Spectator, May 6, 2023, 5:06 PM
Reason: wrong construction

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1032 posts

#20 h May 24, 2023, 6:48 AM • 2 Y

Y by ike.chen, crazyeyemoody907

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1417 posts

Jndd

#21 h Aug 27, 2023, 4:02 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5443 posts

#22 h Oct 8, 2023, 7:11 PM

Y by

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

806 posts

#23 h Dec 22, 2023, 5:35 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2502 posts

ATGY

#24 h Feb 11, 2024, 1:43 PM

Y by

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.

This post has been edited 1 time. Last edited by ATGY, Feb 11, 2024, 1:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#25 h Feb 26, 2024, 4:33 AM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8877 posts

#26 h Mar 17, 2024, 1:26 AM

Y by

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.

This post has been edited 1 time. Last edited by HamstPan38825, Mar 17, 2024, 1:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1329 posts

#27 h Jul 3, 2024, 12:18 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

661 posts

cursed_tangent1434

#28 h Jan 18, 2025, 3:47 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1930 posts

#29 h Feb 25, 2025, 2:29 PM • 1 Y

Y by peace09

I'm lazy so you get a direct copy-paste from my DMs.

BLUE LIN FISH
is it n prime
if n is composite then take smallest p|n
then consider the rows
1,p+1,...,p(n-1)+1
2,p+2,...,p(n-1)+2
...
p,2p,...,pn
pn+1,pn+2,...,(p+1)n
(p+1)n+1,(p+1)n+2,...,(p+2)n
...
consider the column containing 1
if its common difference is less than n
then within 1...pn it gets more than p numbers
contradiction since there's only p colors in that range
so the common difference is n
but then it also gets 1+n which is the first color
contradiction

if n is prime
then i claim that coloring mod p works most of the time
indeed the only time it won't work is if one group has two things the same mod p, which can only happen if that group is just a residue mod p
in which case, any other group to not overlap with this group must be a different residue mod p
so then my colors will just be ceil(x/p)
\blacksquare

Edit:
cluelinfish — Today at 11:17 AM
correct
jatloe12345 — Today at 12:07 PM
XOOOOOOOO
XOOOOOOOOOOOOO
XOOOOOOOOOOOOOOOOO
XOOOOOOOOOOOOOOOOOOOOOOOO
XOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

This post has been edited 1 time. Last edited by cj13609517288, Feb 25, 2025, 5:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

648 posts

#30 h Mar 28, 2025, 3:48 PM

Y by

The answer is $n=p$ prime only.

Let two numbers in the same row of a row-valid arrangement be $a$ and $b$ , with $a<b$ . Note that the common difference $d$ of the arithmetic progression must divide $b-a$ .

If $n\mid b-a$ , and let $b-a=nk$ . Note that either $d=n$ or $d\mid k$ . However, if $d\mid k$ , then we must have exactly $\frac{nk}{d}-1\ge n-1$ numbers between $a$ and $b$ . This implies that there are at least $n+1$ numbers in the row, a contradiction. Thus, henceforth assume $d=n$ .

We can now show that the common difference in all of the rows must also be $n$ . First, let the starting term be $c\not\equiv a\pmod n$ . AFTSOC that the difference $d$ is less than $n$ . Then, there must exist some nonnegative $k\le n-1$ such that $c+dk\equiv a\pmod n$ , which implies that $c+dk$ was in the (earlier) sequence with $a$ and $b$ , a contradiction. Therefore, each of arithmetic progressions in the rows have common difference $n$ .

From here, it's easy to see that we can permute the numbers in each row such that $1, 2\dots, n$ are all in a column, $n+1, n+2, \dots, 2n$ are all in a column, and so on. This new rearrangement is clearly column-valid. $\square$

Next, we will deal with the case with $n\nmid b-a$ . Note that $n$ cannot be the common difference in any of the rows (as shown above). However, this implies that two numbers $a\equiv b\pmod n$ cannot be in the same row. Therefore, we can permute the numbers in each row such that $1, n+1, 2n+1, \dots, (n-1)n+1$ are all in a column, $2, n+2, 2n+2, \dots, (n-1)n+2$ are all in a column, and so on (numbers that are the same modulo $n$ are all in the same column). This new rearrangement is clearly column-valid. $\square$

If $n$ is composite, then let $p$ be the smallest prime divisor of $n$ . Fill the first row with $1, 2, \dots, n$ . Fill the second row with $n+1, n+1+p, n+1+2p,\dots, n+1+(n-1)p$ . Fill the third row with $n+2, n+2+p, \dots, n+2+(n-1)p$ . In general, for $1<i\le p+1$ , fill the $i$ -th row with $n+i-1, n+i-1+p, n+i-1+2p, \dots, n+i-1+(n-1)p$ . Fill the remaining rows with the rest of the integers in increasing order (left to right, top to bottom).

AFTSOC that this grid can be rearranged into a column-valid arrangement; clearly, $1$ must be the smallest element in its column (in the new column-valid arrangement). However, all of the integers from $2$ to $n$ are all in the same row as $1$ , so the second-largest element in $1$ 's column must be $n+1$ (otherwise, the sequence's largest term will be too big). Thus, the arithmetic progression in $1$ 's column must have a common difference $n$ . However, note that there exists number not equal to $n+1$ in the second column that is also congruent to $1\pmod n$ (namely, $2n+1=n+1+\frac{n}{p}\cdot p$ ). This is a contradiction, so row-valid arrangements cannot be rearranged into column-valid arrangements when $n$ is composite. $\blacksquare$

This post has been edited 1 time. Last edited by gladIasked, Mar 28, 2025, 3:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1803 posts

akliu

#31 h Apr 2, 2025, 8:27 PM

Y by

Claim: When $n$ is prime, it is always possible.

Proof:
Any arithmetic progression when $n$ is prime either cycles through all the modulo residues mod $n$ exactly once, or stays the same modulo residue.

In the former case, all rows will have an arithmetic progression where every modulo residue mod $n$ appears exactly once. Thus, we can permute each row so that each column corresponds to a modulo residue mod $n$ .

In the latter case, all rows will be assigned a specific modulo residue mod $n$ , and sorting in increasing order gives us a column-valid arrangement. For example: $147$ , $258$ , and $369$ .

There are a lot of configurations that can be used to show that composite $n$ don't work. The one I used in particular was the 20th post in the thread.

This post has been edited 1 time. Last edited by akliu, Apr 2, 2025, 8:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

684 posts

#32 h Apr 25, 2025, 7:45 AM

Y by

We claim that only prime $n$ work.

For composite, let $p$ be a prime dividing $n.$ We claim the construction:
\begin{center} $\begin{bmatrix} 1 & p + 1 & 2p + 1 & \cdots & (n - 1)p + 1 \\ 2 & p + 2 & 2p + 2 & \cdots & (n - 1)p + 2 \\ 3 & p + 3 & \ddots \\ \vdots & \vdots & & \ddots & \vdots\\ p & 2p & & \cdots & np \\ np + 1 & np + 2 & \cdots & & np + n \\ n(p + 1) + 1 & n(p + 1) + 2 & \cdots & & n(p + 1) + n \\ n(p + 2) + 1 & n(p + 2) + 2 & \cdots & & n(p + 2) + n \\ n(p + 3) + 1 & n(p + 3) + 2 & \ddots \\ n(p + 4) + 1 & n(p + 4) + 2 & & \ddots & \vdots \\ n^2 - n + 1 & n^2 - n + 2 & & \cdots & n^2 \end{bmatrix}$
\end{center}
will disprove composite $n.$ No matter how you arrange the rows, note that the first $p$ rows will always be $1, 2, \cdots, p - 1, 0 \pmod p,$ in that order. Thus, the difference is $1\pmod p.$ However, in the $p + 1$ row, notice there is only 1 value that is $1\pmod p.$ Thus, no composite will work.

Now, assume $n = p$ where $p$ is a prime. There are two cases:
\begin{enumerate}
\item If all of the multiples of $p$ are in the same row, then we know that each row has common difference of $p.$ From here, we can just rearrange it so that the common difference in each column is 1.
\item If all of the multiples of $p$ are in a different row, we can arrange it so that the same values modulo $p$ are in the same column. Thus, the difference is $p.$
\end{enumerate}

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a