Let $n \ge 2$ be a positive integer. Suppose $a_1, a_2, \dots, a_n$ are distinct integers. For $k = 1, 2, \dots, n$, let \[ s_k := \prod_{\substack{i \not= k, \\ 1 \le i \le n}} |a_k - a_i|, \]i.e. $s_k$ is the product of all terms of the form $|a_k - a_i|$, where $i \in \{ 1, 2, \dots, n \}$ and $i \not= k$. Find the largest positive integer $M$ such that $M$ divides the least common multiple of $s_1, s_2, \dots, s_n$ for any choices of $a_1, a_2, \dots, a_n$.
Problem
Source: Indonesia National Mathematics Olympiad (INAMO) 2024 Problem 8
Tags: number theory, least common multiple, Indonesia, Indonesia MO, LCM
29.08.2024 09:43
Answer. $(n - 1)!$. First choose $a_k = k$ for each $k$. Then $s_k = (n - k)! (k - 1)! \mid (n - 1)!$ for each $k$ and $s_1 = (n - 1)!$, so $\text{lcm}(s_1, s_2, \ldots, s_n) = (n - 1)!$. It remains to show the following claim: $(n - 1)!$ must divide $\text{lcm}(s_1, s_2, \ldots, s_n)$. To prove the claim, it suffices to prove that $\nu_p((n - 1)!) \leq \max_k \nu_p(s_k)$ for any prime $p$. Note that by Legendre's formula, \[ \nu_p((n - 1)!) = \sum_{j = 1}^{\infty} \left\lfloor \frac{n - 1}{p^j} \right\rfloor. \]To prove the inequality, we repeatedly go greedy! Let $A_0 = \{a_1, a_2, \ldots, a_n\}$. By pigeonhole principle, there exists an integer $d_0 \in A$ such that $A_1 = \{x \in A_0 : x \equiv d_0 \pmod{p}\}$ has size at least $\lceil n/p \rceil = \lfloor (n - 1)/p \rfloor + 1$. By pigeonhole principle, there exists an integer $d_1 \equiv d_0 \pmod{p}$ such that $A_2 = \{x \in A_1 : x \equiv d_1 \pmod{p^2}\}$ has size at least $\lfloor (n - 1)/p^2 \rfloor + 1$. Continuing this process, we can show inductively that there exists a chain of integers $d_0, d_1, \ldots$ in $A$ such that: 1. $d_{i + 1} \equiv d_i \pmod{p^{i + 1}}$ for each $i$; and 2. for each $n \geq 1$, the set $A_n = \{x \in A_0 : x \equiv d_{n - 1} \pmod{p^n}\}$ has size at least $\lfloor (n - 1)/p^n \rfloor + 1$. For $i$ large enough (such that $|x - y| < p^i$ for all $x, y \in A_0$), we have $A_i = \{d_i\}$. Furthermore, condition 1 ensures that $A_{n + 1} \subseteq A_n$ for all $n \geq 1$. Thus, the sequence $(d_i)_{i \geq 1}$ is eventually constant, say converging to $d$, and we have $d \equiv d_i \pmod{p^{i + 1}}$ for each $i$. As a result, $A_n = \{x \in A_0 : x \equiv d \pmod{p^n}\}$ for each $n \geq 1$. Finally, write $d = a_k$ for some $k \leq n$. Pick $N$ large enough such that $|A_{N + 1}| = 1$; we then get \begin{align*} \nu_p(s_k) &= \sum_{i \neq k} \nu_p(a_k - a_i) \\ &= \sum_{n = 1}^N n \# (A_n \setminus A_{n + 1}) \\ &= \sum_{n = 1}^N n(|A_n| - |A_{n + 1}|) \\ &= \sum_{n = 1}^N |A_n| - N |A_{n + 1}| \\ &\geq \sum_{n = 1}^N \left(\left\lfloor \frac{n - 1}{p^n} \right\rfloor + 1\right) - N \\ &= \nu_p((n - 1)!). \end{align*}
30.08.2024 15:09
Here is a more algebraic proof that $(n-1)!\mid M$. Define $$ t_k := \prod_{\substack{i \not= k, \\ 1 \le i \le n}} (a_k - a_i),$$so that we ignore absolute values. Define a polynomial $$P(x) :=\binom{x}{n-1}.$$in $\mathbb R[x]$. Then $P(x)$ is an integer for each integer $x$. Moreover $\deg P(x)=n-1$ so by Lagrange's interpolation formula we have $$P(x)=\sum_{k=1}^n \frac{P(a_k)}{t_k}\prod_{\substack{i \not= k, \\ 1 \le i \le n}}(x-a_i).$$Taking the coefficient of $x^{n-1}$ implies that $$\sum_{k=1}^n \binom{a_k}{n-1}\frac{1}{t_k}=\frac{1}{(n-1)!}.$$Multiplication by $M$ makes $LHS$ integer, so it also makes $RHS$ integer. Hence $(n-1)!\mid M$, as desired.
30.08.2024 16:10
In the book "Number Theory Concepts and Problems", this problem from "Saint Petersburg 2004" is given as Example 3.106 with the same solution as #3.