Bariz - Problem

Source: MEMO 2018 I4

Tags: number theory, algebra, floor function

sqing

07.09.2018 16:21

(a) Prove that for every positive integer $m$ there exists an integer $n\ge m$ such that $$\left \lfloor \frac{n}{1} \right \rfloor \cdot \left \lfloor \frac{n}{2} \right \rfloor \cdots \left \lfloor \frac{n}{m} \right \rfloor =\binom{n}{m} \\\\\\\\\\\\\\\ (*)$$(b) Denote by $p(m)$ the smallest integer $n \geq m$ such that the equation $ (*)$ holds. Prove that $p(2018) = p(2019).$ Remark: For a real number $x,$ we denote by $\left \lfloor x \right \rfloor$ the largest integer not larger than $x.$

Here is the full solution. Note the bound $$\left\lfloor\frac{n}{k}\right\rfloor\geqslant \frac{n-k+1}{k}$$with equality if and only if $k\mid n+1$. Thus $$\left \lfloor \frac{n}{1} \right \rfloor \cdot \left \lfloor \frac{n}{2} \right \rfloor \cdots \left \lfloor \frac{n}{m} \right \rfloor \geqslant \frac{n}{1}\cdot\frac{(n-1)}{2}\cdot\frac{(n-2)}{3}\cdots \frac{(n-m+1)}{m} = \binom{n}{m}$$thus $n$ satisfies the condition if and only if $k\mid n+1$ for all $k=1,2,...,m$ or $ \mathrm{lcm}(1,2,...,m)\mid n+1$. Thus $p(m) = \mathrm{lcm}(1,2,...,m)-1$, completing part (a). Finally, notice that $$2019\mid \mathrm{lcm}(1,2,3,...,673,...,2017,2018) \implies \mathrm{lcm}(1,2,...,2018) = \mathrm{lcm}(1,2,...,2019)$$or $p(2018)=p(2019)$, completing part (b).