AMC 10 · 2016 · #25

Grade 8 arithmetic

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

floor-functionsystematic-enumerationpattern-recognition casework ↑ Prerequisites: floor-function

📏 Long solution 💡 4 insights

Problem

For each real number x ≥ 0 define f(x)=Σ_k=2¹⁰(⌊ kx⌋ - k⌊ x⌋), where ⌊ r⌋ is the greatest integer not exceeding r. As x ranges over all values ≥ 0, count how many different numbers f(x) can equal.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

infinitely many

AMC 10 2016 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

The raw formula looks scary because x can be any size, but tool #9 (Solve an Easier Related Problem) cuts it down: writing x as a whole part plus a fractional part shows every term ⌊ kx⌋ - k⌊ x⌋ depends only on the fractional part of x. Tool #4 (Introduce a Variable) names that fractional part t, shrinking the whole real line to the single interval 0 ≤ t ＜ 1. Tool #1 (Draw a Diagram) pictures the result as a staircase that only steps up at certain fractions, and tool #5 (Look for a Pattern) shows each step lands on a brand-new value. The final count uses tool #16 (Change Focus): instead of counting the output values directly, count the input fractions where the staircase rises — those are exactly the fractions in lowest terms with denominators 2 through 10.

1STEP 1

Split x into whole and fractional parts

Write x = n + t with whole part n=⌊ x⌋ and fractional part t={x}, 0 ≤ t ＜ 1, then feed this split into each term.

x = n + t, n=⌊ x⌋∈{0,1,2,…}, 0 ≤ t ＜ 1

2STEP 2

Pull the whole part out of each floor

Since kn is whole it cancels, each term reduces to ⌊ kt⌋, so f depends only on t: f(x)=g(t).

⌊ kx⌋ - k⌊ x⌋ = (kn+⌊ kt⌋) - kn = ⌊ kt⌋ → f(x)=Σ_k=2¹⁰⌊ kt⌋ =: g(t)

3STEP 3

See g(t) as a rising staircase

Each ⌊ kt⌋ is 0 then jumps up by 1 at t=a/k, so g(t) is a non-decreasing staircase starting at g(0)=0.

g(0)=0; ⌊ kt⌋ steps up by 1 at t=1/k,2/k,…,(k-1)/k

4STEP 4

Each distinct jump point gives a brand-new value

At each jump fraction t=a/d (lowest terms) the piece k=d jumps, so g rises and never repeats: #values = 1 + #distinct jump fractions.

#{values of g} = 1 + #{a/k∈(0,1) : 2 ≤ k ≤ 10, 1 ≤ a ＜ k}_distinct

5STEP 5

Count the jump fractions as fractions in lowest terms

Reduce every fraction to lowest terms; a denominator d (2 ≤ d ≤ 10) has φ(d) valid numerators coprime to d.

#{numerators for denominator d} = φ(d) = #{a: 1 ≤ a ＜ d, gcd(a,d)=1}

6STEP 6

Add up the totients and the starting value

Sum φ(d) for d=2…10: 1+2+2+4+2+6+4+6+4 = 31 jump fractions; add the start to get 31+1 = 32, choice (A).

1+2+2+4+2+6+4+6+4 = 31, 31+1 = 32 = (A)

Answer

The count is finite, so 'infinitely many' (E) is out — sensible, since f only depends on the fractional part t, which lives in one bounded interval. Spot-check the staircase near t=1/2: only the even k (k=2,4,6,8,10) have kt whole there, so g jumps by 5 at once — confirming jumps can be larger than 1 but are always positive, so values never repeat. The biggest possible miscount is forgetting to merge equivalent fractions like 2/4=1/2; using lowest terms (totients) handles that, which is why 32 beats the naive over-counts 36, 45, and 46. The totient sum 31 plus the start 1 giving 32 matches choice (A).

💡Key takeaway

Only the fractional part of x matters, turning the sum into a staircase that climbs once at each fraction in lowest terms with denominator 2 through 10 — count those fractions (31) and add the start to get 32.

Split x into whole and fractional parts
Pull the whole part out of each floor
See g(t) as a rising staircase
Each distinct jump point gives a brand-new value
Count the jump fractions as fractions in lowest terms
Add up the totients and the starting value