Let $n\ge 2$ be an integer. Given numbers $a_1, a_2, \ldots, a_n \in \{1,2,3,\ldots,2n\}$ such that $\operatorname{lcm}(a_i,a_j)>2n$ for all $1\le i<j\le n$, prove that $$a_1a_2\ldots a_n \mid (n+1)(n+2)\ldots (2n-1)(2n).$$
Problem
Source: Baltic Way 2021, Problem 20
Tags: number theory, number theory proposed, Divisibility, least common multiple
timon92
15.11.2021 22:14
This problem was proposed by Burii.
pi_quadrat_sechstel
15.11.2021 22:41
rafaello wrote: Let $n\ge 2$ be an integer. Given numbers $a_1, a_2, \ldots, a_n \in \{1,2,3,\ldots,2n\}$ such that $\operatorname{lcm}(a_i,a_j)>2n$ for all $1\le i<j\le n$, prove that $$a_1a_2\ldots a_n \mid (n+1)(n+2)\ldots (2n-1)(2n).$$ Any $n\in\{1,2,\cdots 2n\}$ divides a number $m\in\{n+1,n+2,\cdots,2n\}$. For any $m\in\{n+1,n+2,\cdots,2n\}$ there can't be different $i,j$ with $a_i\mid m,a_j\mid m$. Thus there is a bijektion $\phi:\{1,2,\cdots,n\}\to\{n+1,n+2,\cdots,2n\}$ with $a_{i}\mid\phi(i)$ and $a_1a_2\ldots a_n \mid (n+1)(n+2)\ldots (2n-1)(2n)$.
hakN
04.12.2021 22:38
Here is a much less elegant one.
Let $a_i = 2^{b_i} \cdot c_i$ with $c_i$ odd. Then since $a_i \nmid a_j$ for $i \neq j$ we obtain $\{1,3,5, \dots ,2n-1\} = \{c_1 , c_2 , \dots , c_n\}$.
Thus, $a_1a_2 \dots a_n = 2^{\sum_{i=1}^{n} b_i} \cdot \prod_{j=1}^{n} (2j-1) = 2^{\sum_{i=1}^{n} b_i} \cdot \frac{(2n)!}{n! \cdot 2^n}$.
So it suffices to show $\sum_{i=1}^{n} b_i \leq n$.
Note that $2^{b_i} \cdot c_i = a_i \leq 2n \implies b_i \leq \left \lfloor \log_2\left({\frac{2n}{c_i}}\right) \right \rfloor$.
Summing gives $\sum_{i=1}^{n} b_i \leq \sum_{i=1}^{n} \left \lfloor \log_2\left({\frac{2n}{2i-1}}\right) \right \rfloor$.
We will show a stronger thing that the RHS is equal to $n$.
Note that each number $2^{\left \lfloor \log_2\left({\frac{2n}{2i-1}}\right) \right \rfloor} \cdot (2i-1)$ is the largest number of the form $2^t \cdot (2i-1)$ which is at most $2n$, thus we obtain $2n \geq 2^{\left \lfloor \log_2\left({\frac{2n}{2i-1}}\right) \right \rfloor} \cdot (2i-1) \geq n+1$ for all $1 \leq i \leq n$.
But since each of the numbers $2^{\left \lfloor \log_2\left({\frac{2n}{2i-1}}\right) \right \rfloor} \cdot (2i-1)$ are distinct, (their odd parts are different) we get that $$\prod_{i=1}^{n} 2^{\left \lfloor \log_2\left({\frac{2n}{2i-1}}\right) \right \rfloor} \cdot (2i-1) = (n+1)(n+2) \cdots (2n-1)(2n) \implies \sum_{i=1}^{n} \left \lfloor \log_2\left({\frac{2n}{2i-1}}\right) \right \rfloor = n$$, so we are done. $\blacksquare$
SerdarBozdag
04.12.2021 23:23
All numbers are of the form $2^{x_i}y_i$ where $y_i$ is odd. Because of the condition $\operatorname{lcm}(a_i,a_j)>2n$, $\{y_i|i=1,2,...,n\}=\{1,3,5,...,2n-1\}$. Obviously, there exists $z_i$ for all $i$ such that $n<z_i \le 2n$ and $\frac{z_i}{2^{x_i}y_i}$ is a power of two. Also these $z_i$'s are different because $y_i$ is the largest odd divisor of $z_i$. Thus $\{z_i|i=1,2,...,n\}=\{n+1,n+2,n+3,...,2n\}$.$\square$