2016 AMC 10B Problem 25

Step 1: only the part after the decimal point matters.

1. Split $x$ into its whole part $n = \lfloor x \rfloor$ and its leftover part $t = x - n$, where $0 \le t < 1$. For example, $x = 3.4$ gives $n = 3$ and $t = 0.4$.
2. Then $kx = kn + kt$, and $kn$ is a whole number. So $\lfloor kx \rfloor = kn + \lfloor kt \rfloor$.
3. Each term becomes $\lfloor kx \rfloor - k\lfloor x \rfloor = kn + \lfloor kt \rfloor - kn = \lfloor kt \rfloor$.
4. So
$$f(x) = \lfloor 2t \rfloor + \lfloor 3t \rfloor + \cdots + \lfloor 10t \rfloor,$$
which depends only on $t$. We only need to study $t$ from $0$ up to (not including) $1$.

Step 2: watch $f$ as $t$ grows.

1. At $t = 0$ every term is $0$, so $f = 0$.
2. As $t$ increases, $\lfloor kt \rfloor$ never goes down. It goes up by $1$ each time $kt$ reaches a whole number, that is, at $t = \frac1k, \frac2k, \ldots, \frac{k-1}{k}$.
3. So $f$ climbs in steps. It goes up at every fraction between $0$ and $1$ whose bottom number is at most $10$, and it stays flat between them. Each step is a real increase, so every flat stretch has a new, larger value.
4. The number of different values is $1$ (the starting value $0$) plus the number of different step points.

Step 3: count the step points. Several fractions name the same point ($\frac12 = \frac24 = \frac36 = \ldots$), so count each point once, by writing it in lowest terms and sorting by its bottom number:

That is $1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 31$ step points.

So $f$ takes $31 + 1 = 32$ different values.

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

The expression $\lfloor kx \rfloor - k\lfloor x \rfloor$ is built to cancel the whole-number part of $x$, so a problem about all $x \ge 0$ becomes a problem about $0 \le t < 1$. A total that only ever steps up has one more value than it has step points. The real work is not counting the same point twice, which is why each fraction is written in lowest terms. (The numbers in the last row are often written $\varphi(k)$: how many numbers from $1$ to $k$ share no common factor with $k$.)

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}$.