IMO 2019 Shortlisted Problems

We will get an upper bound on $n$ from the speed at which $v_2\left(L_n\right)$ grows. From $$L_n=\left(2^n-1\right)\left(2^n-2\right)\cdots \left(2^n-2^{n-1}\right)=2^{1+2+\cdots +(n-1)}\left(2^n-1\right)\left(2^{n-1}-1\right)\cdots \left(2^1-1\right)$$ we read $$v_2\left(L_n\right)=1+2+\cdots +(n-1)=\frac{n(n-1)}{2}.$$ On the other hand, $v_2(m!)$ is expressed by the Legendre formula as $$v_2(m!)=\sum _{i=1}^{\infty }\lfloor \frac{m}{2^i}\rfloor$$ As usual, by omitting the floor functions, $$v_2(m!)<\sum _{i=1}^{\infty }\frac{m}{2^i}=m.$$ Thus, $L_n=m!$ implies the inequality $$\begin{array}{c}\frac{n(n-1)}{2}<m.\end{array}\text{\hspace{1em}(2)}$$ In order to obtain an opposite estimate, observe that $$L_n=\left(2^n-1\right)\left(2^n-2\right)\cdots \left(2^n-2^{n-1}\right)<{\left(2^n\right)}^n=2^{n^2}.$$ We claim that $$\begin{array}{c}{2}^{n^2}<\left(\frac{n(n-1)}{2}\right)!\text{ for }n⩾6.\end{array}\text{\hspace{1em}(3)}$$ For $n=6$ the estimate (3) is true because $2^{6^2}<6.9\cdot 10^{10}$ and $\left(\frac{n(n-1)}{2}\right)!=15!>1.3\cdot 10^{12}$. For $n⩾7$ we prove (3) by the following inequalities: $$\begin{array}{rl}\left(\frac{n(n-1)}{2}\right)!& =15!\cdot 16\cdot 17\cdots \frac{n(n-1)}{2}>2^{36}\cdot 16^{\frac{n(n-1)}{2}-15}\\ & =2^{2n(n-1)-24}=2^{n^2}\cdot 2^{n(n-2)-24}>2^{n^2}.\end{array}$$ Putting together (2) and (3), for $n⩾6$ we get a contradiction, since $$L_n<2^{n^2}<\left(\frac{n(n-1)}{2}\right)!<m!=L_n$$ Hence $n⩾6$ is not possible. Checking manually the cases $n⩽5$ we find $$\begin{array}{c}{L}_1=1=1!,L_2=6=3!,5!<L_3=168<6!,\\ 7!<L_4=20160<8!\text{ and }10!<L_5=9999360<11!.\end{array}$$ So, there are two solutions: $$(m,n)\in \{(1,1),(3,2)\}.$$

---

Alternative solution.

Like in the previous solution, the cases $n=1,2,3,4$ are checked manually. We will exclude $n⩾5$ by considering the exponents of 3 and 31 in (1). For odd primes $p$ and distinct integers $a,b$, coprime to $p$, with $p\mid a-b$, the Lifting The Exponent lemma asserts that $$v_p\left(a^k-b^k\right)=v_p(a-b)+v_p(k)\text{.}$$ Notice that 3 divides $2^k-1$ if only if $k$ is even; moreover, by the Lifting The Exponent lemma we have $$v_3\left(2^{2k}-1\right)=v_3\left(4^k-1\right)=1+v_3(k)=v_3(3k)$$ Hence, $$v_3\left(L_n\right)=\sum _{2k⩽n}{v}_3\left(4^k-1\right)=\sum _{k⩽\lfloor \frac{n}{2}\rfloor }{v}_3(3k).$$ Notice that the last expression is precisely the exponent of 3 in the prime factorisation of $\left(3\lfloor \frac{n}{2}\rfloor \right)!$. Therefore $$\begin{array}{rl}{v}_3(m!)=v_3\left(L_n\right)& =v_3\left(\left(3\lfloor \frac{n}{2}\rfloor \right)!\right)\\ 3\lfloor \frac{n}{2}\rfloor & ⩽m⩽3\lfloor \frac{n}{2}\rfloor +2\end{array}\text{\hspace{1em}(4)}$$ Suppose that $n⩾5$. Note that every fifth factor in $L_n$ is divisible by $31=2^5-1$, and hence we have $v_{31}\left(L_n\right)⩾\lfloor \frac{n}{5}\rfloor$. Then $$\begin{array}{c}\frac{n}{10}⩽\lfloor \frac{n}{5}\rfloor ⩽v_{31}\left(L_n\right)=v_{31}(m!)=\sum _{k=1}^{\infty }\lfloor \frac{m}{31^k}\rfloor <\sum _{k=1}^{\infty }\frac{m}{31^k}=\frac{m}{30}\end{array}\text{\hspace{1em}(5)}$$ By combining (4) and (5), $$3n<m⩽\frac{3n}{2}+2$$ so $n<\frac{4}{3}$ which is inconsistent with the inequality $n⩾5$.