Track / Stage 5 / 375 of 400 #1615 of 2604

Problem 1615

AIME late

Algebra Difficulty 5.9 Prove it Romanian Mathematical Olympiad · Romania

Let $p$ and $n$ be positive integers, with $p \ge 2$ , and let $a$ be a real number such that $1 \le a < a + n \le p$ . Prove that the set
$\{ \lfloor \log_2 x \rfloor + \lfloor \log_3 x \rfloor + \dots + \lfloor \log_p x \rfloor \mid x \in \mathbb{R},\ a \le x \le a + n \}$
has exactly $n + 1$ elements.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $f(x) = \sum_{k=2}^{p} \lfloor \log_k x \rfloor$ and let $M = \{f(x) \mid x \in [a, a+n]\}$ . It is easy to show that if $k \ge 2$ is a positive integer, then $\lfloor \log_k \lfloor x \rfloor \rfloor = \lfloor \log_k x \rfloor$ . This implies that $f(x) = f(\lfloor x \rfloor)$ , for all $x \in [1, \infty)$ , and hence $M = \{f(x) \mid x \in S\}$ , where $S = \{\lfloor a \rfloor, \lfloor a \rfloor + 1, \dots, \lfloor a \rfloor + n\}$ has $n+1$ elements. On the other hand, for $s \in S$ , $s < \lfloor a \rfloor + n \le p$ , we have $s+1 \in \{2, 3, \dots, p\}$ , and
$f(s+1)-f(s) = \sum_{k=2}^{p} (\lfloor \log_k(s+1) \rfloor - \lfloor \log_k s \rfloor) \ge \lfloor \log_{s+1}(s+1) \rfloor - \lfloor \log_{s+1} s \rfloor = 1,$
therefore $f(s+1) > f(s)$ , and this proves that $M$ has exactly $n+1$ elements.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.