Prove that for all positive integers $n$, there exists a sequence of positive integers $a_1,a_2,\dots,a_n$ and $d_1,d_2,\dots,d_n$ satisfying all of the following three conditions. $\binom{2a_i}{a_i}$ is divisible by $d_i$ for all $i=1,2,\dots,n$ $d_{i+1}=d_i+1$ for all $i=1,2,\dots, n-1$ $d_i\neq m^k$ for all $i=1,2,\dots, n$ and positive integers $m$ and $k$ such that $k\geq 2$
Problem
Source: 2024 Thailand MO P9
Tags: number theory
11.05.2024 10:54
Isn't it trivial by CRT and catalan?
02.06.2024 12:11
The full proof of this problem is to prove these two parts: (a) Prove that there is always an existence of the sequence $d_1,d_2,\dots,d_n$ that satisfies the second and third conditions. (b) For any choice of $d_i$, we can still find $a_i$. Proof of First Part Let $x$ be a positive integer such that $d_i=x+i$ for every positive integer $i=1,2,\dots,n$. Let $p_1,p_2,\dots,p_n$ be distinct prime numbers and define $m=p_1^2p_2^2\cdots p_n^2$. Consider the system of congruence: \begin{align*} x&\equiv -1+p_1\pmod{p_1^2}\\ x&\equiv -2+p_2\pmod{p_2^2}\\ &\vdots\\ x&\equiv -n+p_n\pmod{p_n^2} \end{align*}Notice that $\gcd(p_i^2,p_j^2)=1$ for every $1\leqslant i<j\leqslant n$. By Chinese Remainder Theorem, there exists an integer $0\leqslant \delta<m$ such that $x\equiv \delta\pmod{m}$. Now, choose $x=m+\delta>1$. Obviously, $x+1,x+2,\dots,x+n$ can't be written as $m^k$ where $m,k$ are positive integers with $k>1$, this is because $v_{p_i}(x+i)=1$ for every $i=1,2,\dots,n$. So that there exists $(d_i)_{i=1}^{n}$ as desired. Proof of Second Part From the above proof, we can construct such sequence $(d_i)_{i=1}^{n}$ with $d_i>1$ for every $i=1,2,\dots,n$. For every $i=1,2,\dots,n$, choose $a_i=d_i-1>0$. From the property of Catalan's number: $$C_{d_{i}-1}=\frac{1}{d_i}\binom{2(d_i-1)}{d_i-1}\in\mathbb{Z}$$implies $\binom{2a_i}{a_i}$ is divisible by $d_i$. Hence, the sequence $a_1,a_2,\dots,a_n$ exists. Combining two parts, we can conclude that $a_1,\dots,a_n,d_1,\dots,d_n$ exist as desired.