Prove that $n!\cdot(n+1)!\cdot(n+2)!$ divides $(3n)!$ for every integer $n \geq 3$.
Problem
Source: Moldova TST 2021
Tags: number theory
20.09.2021 16:46
induction
20.09.2021 19:31
any ideas?
20.09.2021 21:52
Let $v_p(n)=k $ for $n=p^kt , (p \nmid t) $ and let $s_p(n)$ denote the sum of the digits in the base-$p$ expansion of $n$ It is well-known that $v_p(n!)=\frac{n - s_p(n)}{p-1}$ We need to show for every prime $p\ge n+2$ , $v_p(n!)+v_p((n+1)!) +v_p((n+2)!) \le v_p((3n)!)$ And it is equal to show that $s_p(n)+s_p(n+1)+s_p(n+2) \ge s_p(3n)+3$ And also not that for every $a,b\in N$, $s_p(a)+s_p(b) \ge s_p(a+b)$ ,which also means $s_p(a)+s_p(b)+s_p(c) \ge s_p(a+b+c)$ $1)$ For $p>3$ $a)$ If $p|n$, $s_p(n+1)=s_p(n)+1$ and $s_p(n+2)= s_p(n)+2 \Rightarrow s_p(n)+s_p(n+1)+s_p(n+2)=3s_p(n)+3\ge s_p(3n)+3$ $b)$ If $p\nmid n$, there is a number amongst ${n,n+1,n+2}$, which its last number at base $p$ is greater than $2$ Call that number $i$, $s_p(i)=s_p(i-3)+3 $ and call other numbers $j,k$ where $(i,j,k)=(n,n+1,n+2)$. $s_p(n)+s_p(n+1)+s_p(n+2)=s_p(i)+s_p(j)+s_p(k)=s_p(i-3)++s_p(j)+s_p(k)+3\ge s_p(3n)+3$ as desired. $2)$For $ p=3$, $(n,n+1,n+2)$ are all different at $mod$ $3$. Let $i\equiv1(mod 3),j\equiv2(mod 3),k\equiv0(mod 3)$where $(i,j,k)=(n,n+1,n+2)$ $s_p(n)+s_p(n+1)+s_p(n+2)=s_p(i)+s_p(j)+s_p(k)=(s_p(i-1)+1)+(s_p(j-2)+2)+s_p(k)\ge s_p(3n)+3 $ $3)$ For $p=2$ $a)$ If $4|n$, then also $4|3n$, note that $s_p(a)+s_p(b) = s_p(a+b)$ if there is no "carry" while adding $a$ and $b$ at base $p$. But while 4 divides $n$, there is at least one carry while adding $n$ and $n+2$ (Look at the leftmost 1)$n=(1......00)_2, n+2=(1......10)_2$ So $s_2(n)+s_2(n+2)\ge s_2(2n+2)+1$ Thus,$s_2(n)+s_2(n+2)+s_2(n+1)\ge (s_2(2n+2)+1)+(s_2(n)+1)\ge s_2(3n+2)+2=s_2(3n)+3$ $b)$ If $n\equiv 1(mod4)$ $n=(1.......01)_2$ $n+1=(1........10)_2$ $n+2=(1.........11)_2$, $s_2(n)=s_2(n-1)+1, s_2(n+1)=s_2(n),s_2(n+1)+1$,also note that there is a carry at base 2 while adding $n-1,n$ and $n+1$ $s_2(n)+s_2(n+1)+s_2(n+2)=s_2(n-1)+s_2(n)+s_2(n+1)+2\ge s_2(3n)+3$ $c)$ If $n\equiv 2(mod4)$ $n=(1.......10)_2$ $n+1=(1........11)_2$ $n+2=(1.........00)_2$,also notice that there is a carry at base 2 while adding $n-2,n$ and $n+2$ $s_2(n)=s_2(n-2)+1, s_2(n+1)=s_2(n)+1, s_2(n+2)$ $s_2(n)+s_2(n+1)+s_2(n+2)=s_2(n-2)+s_2(n)+s_2(n+2)+2\ge s_2(3n)+3$ $d)$ If $n\equiv 3(mod4)$ $n=(1.......11)_2$ $n+1=(1........00)_2$ $n+2=(1.........01)_2$,again notice there is a carry at base 2 while adding $n-2,n+1$ and $n+1$ $s_2(n)=s_2(n-2)+1,s_2(n+2)=s_2(n+1)+1$ $s_2(n)+s_2(n+1)+s_2(n+2)= s_2(n-2)+s_2(n+1)+s_2(n+1)+2\ge s_2(3n)+3$ We showed that for every prime $p\ge n+2$ , $v_p(n!)+v_p((n+1)!) +v_p((n+2)!) \le v_p((3n)!)$ as desired.