Mathematically Absurd
by SomeonecoolLovesMaths, Jan 3, 2025, 6:52 PM
Prove that for any positive integers 
,
![\[ \prod_{1 \leq i < j \leq n} \frac{a_i-a_j}{i-j} \in \mathbb{Z} .\]](//latex.artofproblemsolving.com/4/3/0/4302b6638b7ebd13c28130e7a969c6284f4ad531.png)
Proof:
We shall show that for any prime
![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) \geq v_p \left( \prod_{1 \leq i < j \leq n} (i-j) \right). \]](//latex.artofproblemsolving.com/3/b/5/3b5f9deb6b391a9640fe8b64eeedc99d5461365f.png)
The divisibility immediately follows. Indeed, the problem statement is equivalent to showing that the quantity
![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) \]](//latex.artofproblemsolving.com/4/d/d/4dd9b4d8d8e1c2a25d85f65cbcf7ae6c93494baf.png)
is minimised when 
for all 
. To prove this we find some reasonable way of computing the above quantity.
Denote
. Then
![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) = \sum_{1 \leq i < j \leq n} v_p \left( a_i-a_j \right) = \sum_{k \geq 1} |A_{p^k}| .\]](//latex.artofproblemsolving.com/a/b/0/ab0f0f9cb159fd1e74f090806a247af3a3618832.png)
We proceed by computing the size of each individual set 
. I claim the cardinality of this set is minimised when for all . Indeed, let
![\[ A_{(p^k, x)} = \left\{ a_i \mid a_i \equiv x \pmod{p^k} \right\} \]](//latex.artofproblemsolving.com/4/4/d/44d0b55326b872421bba03c8d6a3cfbd6cd01cf4.png)
for 
. We remark that the union of 
partitions the set 
because modular congruence is an equivalence relation. Moreover, 
if and only if 
for some 
. Thus
![\[ |A_{p^k}| = \sum_{x=0}^{p^k-1} \binom{|A_{(p^k,x)}|}{2} .\]](//latex.artofproblemsolving.com/4/2/b/42bef1bec3b07afbf989781b632bb981634d5aae.png)
I claim that the above sum is minimised if there exists an integer 
such that 
for all . (Note that this is very close to Jensen's Inequality.) Suppose for the sake of contradiction that the function
![\[ f(a_0, a_1, \dots, a_{p^k-1} )=\sum_{x=0}^{p^k-1} \binom{a_x}{2} \]](//latex.artofproblemsolving.com/e/9/2/e92723c09356b1b4e16b7b31c9aa665c403a053f.png)
has minimal value at 
that does not satisfy the above claim. Then there exists 
such that 
.
Rearrange to
and rewrite as
Then
![\[ \binom{a_i-1}{2} + \binom{a_j+1}{2} < \binom{a_i}{2}+\binom{a_j}{2} .\]](//latex.artofproblemsolving.com/c/a/4/ca43f8e5daed4c375e4074f6bb83a70fa9c3236e.png)
Finally, if we assume without loss of generality that 
we conclude
![\[ f(a_0, a_1, \dots ,a_{p^k-1} ) > f(a_0, a_1, \dots , a_i-1, \dots, a_j+1, \dots, a_{p^k-1} ) \]](//latex.artofproblemsolving.com/0/b/b/0bb27c918147a6c68f5a678dc2aa55a2f79bde46.png)
contradicting the minimality of 
.
Because
is partitioned by the 
, we have that
![\[ |A_{(p^k,0)}|+|A_{(p^k,1)}|+\dots+|A_{(p^k,p^k-1)}|=n . \]](//latex.artofproblemsolving.com/6/e/5/6e53d1469796e1ef9f30a2605911e2780d22681c.png)
We may say that 
has remainder 
upon Euclidean division by 
. Then from our above work it follows that,
![\[ |A_{p^k}|=f \left( | A_{(p^k,0)}|, |A_{(p^k,1)}|, \dots, |A_{(p^k,p^k-1)}|\right) \geq r\binom{\left\lfloor \frac{n}{p^k}\right\rfloor +1 }{2} + (p^k-r)\binom{\left\lfloor \frac{n}{p^k}\right\rfloor}{2}. \]](//latex.artofproblemsolving.com/9/e/a/9ead7efbb8cdeb6060c191544c535d9ba4b1f334.png)
It remains to show that this value is taken when . For that case, we define 
and 
. It's fairly easy to see that
![\[ |A_{(p^k,x)}|= \space
\begin{cases}\left\lfloor \frac{n}{p^k}\right\rfloor +1 &\text{ if } 0 \leq x \leq r \\
\left\lfloor \frac{n}{p^k}\right\rfloor & \text{ if } r < x \leq p^k-1.
\end{cases} \]](//latex.artofproblemsolving.com/f/c/c/fcc79b5842c90c1046bc8cc68124c8d6e002c7ed.png)
Then
![\[ |A_{p^k}^{\star}|=f \left( | A_{(p^k,0)}^{\star}|, |A_{(p^k,1)}^{\star}|, \dots, |A_{(p^k,p^k-1)}^{\star}|\right) = \sum_{x=0}^{p^k-1} \binom{|A_{(p^k,x)}^{\star}|}{2} = r\binom{\left\lfloor \frac{n}{p^k}\right\rfloor +1 }{2} + (p^k-r)\binom{\left\lfloor \frac{n}{p^k}\right\rfloor}{2} \]](//latex.artofproblemsolving.com/7/8/1/78194a51e45e422000a8a9bc5a335c348490b39a.png)
when . Thus 
.
![\[ v_p \left( \prod_{1 \leq i < j \leq n} (i-j) \right) = \sum_{1 \leq i < j \leq n} v_p \left( i-j \right) = \sum_{k \geq 1} |A^{\star}_{p^k}|. \leq \sum_{k \geq 1} |A_{p^k}|= v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) ,\]](//latex.artofproblemsolving.com/c/1/1/c11b062e0185af7cfb058d01beb910f3caf84c0e.png)
completing the proof.
Thanks to HKIS200543
,![\[ \prod_{1 \leq i < j \leq n} \frac{a_i-a_j}{i-j} \in \mathbb{Z} .\]](http://latex.artofproblemsolving.com/4/3/0/4302b6638b7ebd13c28130e7a969c6284f4ad531.png)
Proof:
We shall show that for any prime
![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) \geq v_p \left( \prod_{1 \leq i < j \leq n} (i-j) \right). \]](http://latex.artofproblemsolving.com/3/b/5/3b5f9deb6b391a9640fe8b64eeedc99d5461365f.png)
The divisibility immediately follows. Indeed, the problem statement is equivalent to showing that the quantity![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) \]](http://latex.artofproblemsolving.com/4/d/d/4dd9b4d8d8e1c2a25d85f65cbcf7ae6c93494baf.png)
is minimised when 
for all 
. To prove this we find some reasonable way of computing the above quantity.Denote
. Then![\[ v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) = \sum_{1 \leq i < j \leq n} v_p \left( a_i-a_j \right) = \sum_{k \geq 1} |A_{p^k}| .\]](http://latex.artofproblemsolving.com/a/b/0/ab0f0f9cb159fd1e74f090806a247af3a3618832.png)
We proceed by computing the size of each individual set 
. I claim the cardinality of this set is minimised when for all . Indeed, let![\[ A_{(p^k, x)} = \left\{ a_i \mid a_i \equiv x \pmod{p^k} \right\} \]](http://latex.artofproblemsolving.com/4/4/d/44d0b55326b872421bba03c8d6a3cfbd6cd01cf4.png)
for 
. We remark that the union of 
partitions the set 
because modular congruence is an equivalence relation. Moreover, 
if and only if 
for some 
. Thus![\[ |A_{p^k}| = \sum_{x=0}^{p^k-1} \binom{|A_{(p^k,x)}|}{2} .\]](http://latex.artofproblemsolving.com/4/2/b/42bef1bec3b07afbf989781b632bb981634d5aae.png)
I claim that the above sum is minimised if there exists an integer 
such that 
for all . (Note that this is very close to Jensen's Inequality.) Suppose for the sake of contradiction that the function![\[ f(a_0, a_1, \dots, a_{p^k-1} )=\sum_{x=0}^{p^k-1} \binom{a_x}{2} \]](http://latex.artofproblemsolving.com/e/9/2/e92723c09356b1b4e16b7b31c9aa665c403a053f.png)
has minimal value at 
that does not satisfy the above claim. Then there exists 
such that 
.Rearrange to
and rewrite as
Then![\[ \binom{a_i-1}{2} + \binom{a_j+1}{2} < \binom{a_i}{2}+\binom{a_j}{2} .\]](http://latex.artofproblemsolving.com/c/a/4/ca43f8e5daed4c375e4074f6bb83a70fa9c3236e.png)
Finally, if we assume without loss of generality that 
we conclude![\[ f(a_0, a_1, \dots ,a_{p^k-1} ) > f(a_0, a_1, \dots , a_i-1, \dots, a_j+1, \dots, a_{p^k-1} ) \]](http://latex.artofproblemsolving.com/0/b/b/0bb27c918147a6c68f5a678dc2aa55a2f79bde46.png)
contradicting the minimality of 
.Because
is partitioned by the 
, we have that![\[ |A_{(p^k,0)}|+|A_{(p^k,1)}|+\dots+|A_{(p^k,p^k-1)}|=n . \]](http://latex.artofproblemsolving.com/6/e/5/6e53d1469796e1ef9f30a2605911e2780d22681c.png)
We may say that 
has remainder 
upon Euclidean division by 
. Then from our above work it follows that,![\[ |A_{p^k}|=f \left( | A_{(p^k,0)}|, |A_{(p^k,1)}|, \dots, |A_{(p^k,p^k-1)}|\right) \geq r\binom{\left\lfloor \frac{n}{p^k}\right\rfloor +1 }{2} + (p^k-r)\binom{\left\lfloor \frac{n}{p^k}\right\rfloor}{2}. \]](http://latex.artofproblemsolving.com/9/e/a/9ead7efbb8cdeb6060c191544c535d9ba4b1f334.png)
It remains to show that this value is taken when . For that case, we define 
and 
. It's fairly easy to see that![\[ |A_{(p^k,x)}|= \space
\begin{cases}\left\lfloor \frac{n}{p^k}\right\rfloor +1 &\text{ if } 0 \leq x \leq r \\
\left\lfloor \frac{n}{p^k}\right\rfloor & \text{ if } r < x \leq p^k-1.
\end{cases} \]](http://latex.artofproblemsolving.com/f/c/c/fcc79b5842c90c1046bc8cc68124c8d6e002c7ed.png)
Then![\[ |A_{p^k}^{\star}|=f \left( | A_{(p^k,0)}^{\star}|, |A_{(p^k,1)}^{\star}|, \dots, |A_{(p^k,p^k-1)}^{\star}|\right) = \sum_{x=0}^{p^k-1} \binom{|A_{(p^k,x)}^{\star}|}{2} = r\binom{\left\lfloor \frac{n}{p^k}\right\rfloor +1 }{2} + (p^k-r)\binom{\left\lfloor \frac{n}{p^k}\right\rfloor}{2} \]](http://latex.artofproblemsolving.com/7/8/1/78194a51e45e422000a8a9bc5a335c348490b39a.png)
when . Thus 
.![\[ v_p \left( \prod_{1 \leq i < j \leq n} (i-j) \right) = \sum_{1 \leq i < j \leq n} v_p \left( i-j \right) = \sum_{k \geq 1} |A^{\star}_{p^k}|. \leq \sum_{k \geq 1} |A_{p^k}|= v_p \left( \prod_{1 \leq i < j \leq n} (a_i-a_j) \right) ,\]](http://latex.artofproblemsolving.com/c/1/1/c11b062e0185af7cfb058d01beb910f3caf84c0e.png)
completing the proof.Thanks to HKIS200543
March 2025
February 2025