Let $p$ be a prime. We arrange the numbers in ${\{1,2,\ldots ,p^2} \}$ as a $p \times p$ matrix $A = ( a_{ij} )$. Next we can select any row or column and add $1$ to every number in it, or subtract $1$ from every number in it. We call the arrangement good if we can change every number of the matrix to $0$ in a finite number of such moves. How many good arrangements are there?
Problem
Source: 2012 China Mathematical Olympaid P2
Tags: linear algebra, matrix, geometry, geometric transformation, symmetry, algebra, polynomial
14.01.2012 22:20
I think at first, we have to find some conditions of the way to arrange the numbers. And then, count the ways satisfy theses conditions. Let $K = \sum_{1 \le i \le p, 1 \le j \le p} (-1)^{i+j} a(ij) $ with $a(ij)$ denotes the number in row $i$, column $j$. With the given operations, the value of K is not change. The final state corresponds with $K = 0$ then the begin state must have that value. So we have to find the ways to arrange the numbers satisfy that condition. This is my idea and I can't finish my work. Hope someone solve this soon. I think this is a nice problem.
14.01.2012 23:25
its obvious that $K$ changes with this operator(except for $P=2$)
14.01.2012 23:45
i change the problem into this problem: in how many ways we can choose $0<r_{1}<...<r_{p}$ and $a_{0}=0<a_{1}<...<a_{p-1}$ such that the set $A=\left \{ r_{i}+a_{j}\mid i\in \left \{ 1,2,...,p \right \} , j\in \left \{ 0 , 1, ... , p-1 \right \} \right \}=\left \{ 1,2,...,p^{2} \right \}$ i will post my solution tomorrow
14.01.2012 23:52
I think the answer is $2(p!)^2$ . Assume we start with a Good matrix and let $a_i , b_j$ numbers of operation ("numbers add one" $-$ "number of subtract one" ) on $i^{th}$ row and $j^{th}$ column to get into zero matrix.Then we should have $A_{ij} + a_i + b_j =0$ . Sum up all these equation , we obtain $a_1 + a_2 + ... a_p + b_1 + ...+b_p = - p(\frac{p^2 +1}{2})$
Compare these two equation for example : $A_{1 1} + A_{2 2} + ....+ A_{p p} = A_{1 2} + A_{2 1} + ... + A_{p p}$ You'll get $A_{2 2} - A_{21}=A_{12} - A_{11}$ ,go in the same manner to get first row of matrix is just a translation of second row i.e $A_{1i} - A_{2i}$ is constant for $1 \leq i \leq p$ . Obviously it's true for any two other rows. So problem boils down to find ${a_1 , a_ 2 ,...a_p \in \{1,2,\ldots ,p^{2}}\} $ and $0=x_1 , x_2 , ..., x_{p-1} \in \mathbb Z$ such that ${B_i = \{a_1 + x_i , a_2 + x_i , ... , a_p + x_i}\} $ as $i^{th}$ row of matrix $M$ for $1 \leq i \leq p$ represent a partition of ${ \{1,2,\ldots ,p^{2}}\} $ . WLOG we can assume $1=a_1 < a_2 < ...< a_p$ , and $0=x_1 < x_2 < ...< x_{p-1} $ . We try to prove that either $x_i = i-1$ (first column is ${1,2,\ldots ,p}\}$) or $a_i = i$ (first row is ${1,2,\ldots ,p}\}$) . If $a_2 > 2 , x_2 >1$ then neither first row nor any other rows contain $2$ . So we have 2 cases to chase : 1) $x_2=1$ This is easy case , if $x_3 >2$ then there is no possible position for $3$ so $x_3=2$ . Continue in same way (following position of $4,5,...$) You'll see $x_i =i-1$ . 2) $a_2=2$ Let $k$ be greatest number that $a_i=i $ for all $1 \leq i \leq k$ , Then Where is the $k+1$ ? Yes ! $x_2=k$ and $k+1 , ...,2k$ lie below the $1 , 2,...,k$ . Playing around possible position to arrive this matrix : $M= \begin{bmatrix} 1 &2 &... &k &2k+1 & 2k+2&...&3k &4k+1& ... \\ k+1 &k+2 &... &2k &3k+1&3k+2 &...&4k &5k+1 &... \\ & & & && \\ & & & & & \end{bmatrix}$ Above matrix $\implies$ $k \mid p$ contradiction ! (here we use the fact that $p$ is prime) Now we win in both cases .We can suppose that $a_i=i$ (case 1) is actually case $2)$ when we look at problem from transpose of $A$ ) Then it's easy to see $x_i=(i-1)p$ (start with chasing position of $p+1$...) and so every other rows of $M$ uniquely determined by first row . Now to construct $A$ from $M$ we have $p!$ possibilities to order elements of each $B_i$'s in rows and $p!$ for index of $B_i$'s themselves. Because of symmetry , this argument works also for column and because this two case don't overlap each other , answer to this problem is $2 (p!)^2$ .
15.01.2012 00:49
mahanmath wrote: 1) $x_2=1$ This is easy case , if $x_3 >2$ then there is no possible position for $3$ so $x_3=2$ . Continue in same way (following position of $4,5,...$) You'll see $x_i =i-1$ . i think you made a mistake what if $a_{2}=3$
15.01.2012 01:23
mlm95 wrote: mahanmath wrote: 1) $x_2=1$ This is easy case , if $x_3 >2$ then there is no possible position for $3$ so $x_3=2$ . Continue in same way (following position of $4,5,...$) You'll see $x_i =i-1$ . i think you made a mistake what if $a_{2}=3$ It becomes like this , which is impossible because $p$ is odd . $\begin{bmatrix} 1 &3 &5 &7 &\cdots &2p-1 \\ 2&4 &6 &8 & \cdots &2p \\ 2p+1 &2p+3 &2p+5 & 2p+7 &\cdots & 4p-1\\ 2p+2& 2p+4 & 2p+6 & 2p+8 & \cdots &4p \\ \vdots &\vdots & \vdots &\vdots & &\vdots \\ & & & & & \end{bmatrix}$
15.01.2012 01:34
case 1) need more work : If $a_1=1 $ and $a_2=k$ then you can boxed every $2(k-1)$ consecutive numbers like below, which contradicts oddness of $p$ (or you can say it implies $k-1 \mid p$ , Contradiction ) $\begin{bmatrix} 1 &k & & & \\ 2& k+1 & & & \\ \vdots &\vdots & & & \\ k-1&2k-2 & & & \\ --------- &------- & & & \\ 2k-1&3k-2 & & & \\ \vdots &\vdots & & & \\ \end{bmatrix}$ Because every numbers among $1,2,..,2k-2$ has been appear , $x_k $ should be at least $2k-2$ and if it be more than it then $2k-1$ never appear , it means $x_k = 2k-2$ .So below the $k-1$ we see $2k-1$ and same story goes again ....
15.01.2012 10:33
this is my solution: step 1: change the problem to this problem: mlm95 wrote: i change the problem into this problem: in how many ways we can choose $0<r_{1}<...<r_{p}$ and $a_{0}=0<a_{1}<...<a_{p-1}$ such that the set $A=\left \{ r_{i}+a_{j}\mid i\in \left \{ 1,2,...,p \right \} , j\in \left \{ 0 , 1, ... , p-1 \right \} \right \}=\left \{ 1,2,...,p^{2} \right \}$ i do this step as same as <mahanmath> do now another solution for step 2: let $P(x)=(x^{r_{1}-1}+x^{r_{2}-1}+...+x^_{r_{p-1}-1})$ and $Q(x)=(x^{a_{0}}+x^{a_{1}}+...+x^{a_{p-1}})$ then $P(x).Q(x)=1+x+x^{2}+...+x^{p^{2}-1}$ and use the fact that $1+x+...+x^{p^{2}-1}=S(x) .R(x)$ where $S(x)=1+x+...+x^{p-1}$ and $R(x)=1+x^{p}+x^{2p}+...+x^_{p(p-1)}$ notice that $S(x)$ and $R(x)$ are irreducible over Z[x] then the rest is obvious
17.01.2012 01:25
mlm95 wrote: this is my solution: step 1: change the problem to this problem: mlm95 wrote: i change the problem into this problem: in how many ways we can choose $0<r_{1}<...<r_{p}$ and $a_{0}=0<a_{1}<...<a_{p-1}$ such that the set $A=\left \{ r_{i}+a_{j}\mid i\in \left \{ 1,2,...,p \right \} , j\in \left \{ 0 , 1, ... , p-1 \right \} \right \}=\left \{ 1,2,...,p^{2} \right \}$ i do this step as same as <mahanmath> do now another solution for step 2: let $P(x)=(x^{r_{1}-1}+x^{r_{2}-1}+...+x^_{r_{p-1}-1})$ and $Q(x)=(x^{a_{0}}+x^{a_{1}}+...+x^{a_{p-1}})$ then $P(x).Q(x)=1+x+x^{2}+...+x^{p^{2}-1}$ and use the fact that $1+x+...+x^{p^{2}-1}=S(x) .R(x)$ where $S(x)=1+x+...+x^{p-1}$ and $R(x)=1+x^{p}+x^{2p}+...+x^_{p(p-1)}$ notice that $S(x)$ and $R(x)$ are irreducible over Z[x] then the rest is obvious This is very clever. Was this the official solution, or was there an intended combinatorial approach to this problem?
18.01.2012 08:56
SnowEverywhere wrote: Was this the official solution, or was there an intended combinatorial approach to this problem? i don't know the official solution and about an intended combinatorial approach : i think after step 1 the problem occur in number theory's problems
18.01.2012 17:27
yunxiu wrote: Let $p$ be a prime. We arrange the numbers in ${\{1,2,\ldots ,p^2} \}$ as a $p \times p$ matrix $A = ( a_{ij} )$. Next we can select any row or column and add $1$ to every number in it, or subtract $1$ from every number in it. We call the arrangement good if we can change every number of the matrix to $0$ in a finite number of such moves. How many good arrangements are there? My Result =8. $A=\begin{pmatrix} 1 & ... & p\\ ... & ... & ...\\ p(p-1)+1 & ... & p^2 \end{pmatrix}$ and $A^T$. $A=\begin{pmatrix} p & ... & 1\\ ... & ... & ...\\ p^2 & ... & p(p-1)+1 \end{pmatrix}$ and $A^T$. $A=\begin{pmatrix} p(p-1)+1 & ... & p^2\\ ... & ... & ...\\ 1 & ... & p \end{pmatrix}$ and $A^T$. $A=\begin{pmatrix} p^2 & ... & p(p-1)+1\\ ... & ... & ...\\ p & ... & 1 \end{pmatrix}$ and $A^T$.
25.01.2012 07:30
the answer is $2(p!)$. let $u,v$ be the $p-$ and $p^2-$ unitary roots we know that in the $(i,j)th$ place of the matrix,the number is $r_i+c_j$ so $\sum_{i=1}^{p}u^{r_i}*\sum_{i=1}^{p}u^{c_j}=\sum_{(i,j)}u^{r_i+c_j}=\sum_{i=1}^{p^2}u^{i}=0$(similar for $v$) consider the polynomial $f(x)=\sum_{i=1}^{p}x^{r_i}$ and $g(x)=\sum_{i=1}^{p}x^{c_j}$ we know that either $f(u)=0$or$f(v)=0$;either$g(u)=0$or$g(v)=0$ let us suppose $f(u)=0$ then $u$ is a root of $f(x)$ but consider the irreducible polynomial $f_p(x)=x^{p-1}+...+x^{0}$,we get that $f(x)$ is a multiple of $f_p(x)$ when indices consider modulo $p$ ,$degf(x)\le p-1$ hence $f(x)=f_p(x)$ we obtain that all $r_i$ modp are distinct. if $f(v)=0$,then$v$ is a root of $f(x)$ similarly,consider the irreducible polynomial $f_{p^2}(x)=x^{p^2-p}+x^{p^2-2p}+...+x^{0}$,we get $f_{p^2}(x)|f(x)$ it's then easy to get $r_i$ modulo $p$ are all congruent but modulo $p^2$ all distinct,contradiction so $g(v)=0$,yielding $c_j$modulo $p$ are all congruent but modulo $p^2$ all distinct. then by a series of ineq we can get the answer.
30.01.2012 07:42
SnowEverywhere wrote: Was this the official solution, or was there an intended combinatorial approach to this problem? An other solution in Chineseļ¼ http://room-365.com/bbs/forum.php?mod=viewthread&tid=582&extra=page%3D1
04.08.2014 19:27
12.11.2020 17:40
i also arrived to .$2 (p!)^2$