2016 AMC 10B Problem 25

P21-25~10 minPrint

Number Properties Fractions & Decimals Functions Map the objects to something easier to count Substitute to simplify (u = x+1/x, shifting, scaling)

Let $f(x)=\sum_{k=2}^{10}(\lfloor kx \rfloor -k \lfloor x \rfloor)$ , where $\lfloor r \rfloor$ denotes the greatest integer less than or equal to $r$ . How many distinct values does $f(x)$ assume for $x \ge 0$ ?

Show solution without answering

Key insight

Each term depends only on the part of x after the decimal point. As it grows, f steps up once at each fraction with bottom at most 10.

Solution

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.

At $t = 0$ every term is $0$ , so $f = 0$ .
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}$ .
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.
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:

bottom number	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
fractions in lowest terms	$\frac12$	$\frac13, \frac23$	$\frac14, \frac34$	$\frac15, \ldots, \frac45$	$\frac16, \frac56$	$\frac17, \ldots, \frac67$	$\frac18, \frac38, \frac58, \frac78$	$\frac19, \frac29, \frac49, \frac59, \frac79, \frac89$	$\frac1{10}, \frac3{10}, \frac7{10}, \frac9{10}$
how many	$1$	$2$	$2$	$4$	$2$	$6$	$4$	$6$	$4$

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

Why this works

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

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics
Introduction to Algebra, Chapter 16: Functions
Introduction to Number Theory, Chapter 11: Decimals and Fractions
Intermediate Algebra, Chapter 20: Some Advanced Strategies (§20.2)