1
$\begingroup$

Let $a_1<a_2<\ldots<a_{n+1}$ different integers. Prove that $$n!\Big|\prod_{1\leq i< j\leq n+1}{(a_j-a_i)}$$Here's my proof:

Let $k\in\bigl\{1,2,\ldots,n\bigr\}$. $k<n+1$ and using the Pigeonhole Principle, there are $0\leq i<j\leq n+1$ (but $0\leq i<j\leq k+1$ is enough) such that $$a_i \equiv a_j\pmod{k}$$Thus, $$k\big|(a_j-a_i)$$Every $k\in\bigl\{1,2,\ldots,n\bigr\}$ satisfies this, and we are done.

Is the proof correct? I couldn't find a mistake myself but it seemed weird that the use of the Pigeonhole Principle had $n+1$ pigeons and only $k$ holes (when $k$ can be as little as $1,2,3$). Am I missing something?

$\endgroup$
6
  • $\begingroup$ what do you mean by $k\in[n]$? What is $[n]$? $\endgroup$ Oct 18, 2020 at 22:35
  • $\begingroup$ It's a symbol for $\bigl\{1,2,\ldots,n\bigr\}$. I thought about changing it before as I wasn't sure if it's a known symbol or not. I changed it now though. $\endgroup$
    – Guy
    Oct 18, 2020 at 22:42
  • $\begingroup$ It is very common, at least in combinatorics. $\endgroup$ Oct 18, 2020 at 22:48
  • 1
    $\begingroup$ Then I guess $k<n+1$ is redundant. $\endgroup$ Oct 18, 2020 at 22:54
  • 1
    $\begingroup$ Your proof is not sufficient : you need to prove that the pair $(i,j)$ such that $k\mid (a_j-a_i)$ is different for every $k$. Otherwise with the same reasoning, you could prove that $2^{10} | 2$. $\endgroup$ Oct 18, 2020 at 22:56

1 Answer 1

1
$\begingroup$

It seems to me that your argument shows that $$ \prod_{1\leq i<j\leq n+1}(a_j-a_i) $$ (you shouldn't allow $i=j$), which is actually a Vandermonde determinant, is divisible by all $k\leq n$.

This is not (yet) enough to conclude that $n!$ divides it: $3\cdot4\cdot 5=60$ has this property but is actually smaller than $5!$.


But it is possible that the argument can be improved upon.

Given a prime $p\leq n<n+1$ there are always $\lfloor\frac n{p^k}\rfloor+1$ elements among the $a_i$'s that give the same class modulo $p^k$ as long as $p^k\leq n$. This should account for the $$ \lfloor\frac n{p}\rfloor+\lfloor\frac n{p^2}\rfloor+\lfloor\frac n{p^3}\rfloor+\cdots $$ factors of $p$ that occur in $n!$.

(I leave to you to fill the details)

$\endgroup$
1
  • 1
    $\begingroup$ +1 Very nice elegance. $\endgroup$ Oct 18, 2020 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.