2016 AMC 10B Problem 25

Write $x = n + t$ with $n = \lfloor x \rfloor$ and $t = \{x\} \in [0, 1)$. Then $kx = kn + kt$ with $kn$ an integer, so $\lfloor kx \rfloor = kn + \lfloor kt \rfloor$ and each term is
$$\lfloor kx \rfloor - k\lfloor x \rfloor = \lfloor kt \rfloor.$$
Thus $f(x) = g(t) = \sum_{k=2}^{10} \lfloor kt \rfloor$ depends only on the fractional part, and we may take $0 \le t < 1$.

Each $\lfloor kt \rfloor$ is a nondecreasing step function of $t$ that jumps by $1$ exactly when $kt$ passes an integer, i.e. at $t = \tfrac{j}{k}$ for $j = 1, \ldots, k-1$. So $g$ is nondecreasing, starts at $g(0) = 0$, and increases exactly when $t$ crosses a fraction in $(0,1)$ whose reduced denominator is at most $10$. Every crossing strictly raises $g$, so $g$ takes one value on each interval between consecutive jump points, and different intervals give different values.

The number of distinct values is therefore $1$ plus the number of distinct fractions in $(0,1)$ with denominator at most $10$. Counting reduced fractions by denominator with Euler's $\varphi$:
$$\varphi(2) + \varphi(3) + \cdots + \varphi(10) = 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31.$$

So $g$ takes $31 + 1 = 32$ distinct values.

The answer is $\boxed{\textbf{(A)}\ 32}$.

The combination $\lfloor kx \rfloor - k\lfloor x \rfloor$ is designed to kill the integer part of $x$, so an apparently unbounded problem lives on $[0,1)$. A sum of monotone step functions is monotone, and a monotone step function has exactly one more value than it has jump points; the whole problem is then counting distinct jump points, where the trap is that different $(j,k)$ pairs can name the same fraction. Reduced fractions with denominator $k$ are counted by $\varphi(k)$.

List the distinct fractions with denominator at most $10$ directly (the Farey sequence $F_{10}$ without $0$ and $1$): $\tfrac1{10}, \tfrac19, \tfrac18, \tfrac17, \tfrac16, \tfrac15, \tfrac29, \tfrac14, \tfrac27, \tfrac3{10}, \tfrac13, \ldots$; there are $31$ of them, giving $32$ values. Also, $g$ is never constant on all of $[0,1)$, and the value $g(t)$ is at most $\sum (k-1) = 45$, so "infinitely many" is impossible once you see $f$ depends only on $t$.

• Counting the $45$ pairs $(j, k)$ with $1 \le j < k \le 10$ as separate jump points, forgetting that equal fractions like $\tfrac12 = \tfrac24 = \tfrac36$ are one jump.
• Believing $f$ grows without bound as $x$ increases (choice E) because $\lfloor kx \rfloor$ does; the subtracted $k\lfloor x \rfloor$ cancels that growth.