Maths Olympiad Prep

Library / /428 of 520

Number theory Difficulty 3.8 AMC 10/12 Find the answer

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

Pick one

Solution

Since x=x+{x}x = \lfloor x \rfloor + \{ x \}, we have
f(x)=k=210(kx+k{x}kx)f(x) = \sum_{k=2}^{10} (\lfloor k \lfloor x \rfloor +k \{ x \} \rfloor - k \lfloor x \rfloor)
The function can then be simplified into
f(x)=k=210(kx+k{x}kx)f(x) = \sum_{k=2}^{10} ( k \lfloor x \rfloor + \lfloor k \{ x \} \rfloor - k \lfloor x \rfloor)
which becomes
f(x)=k=210k{x}f(x) = \sum_{k=2}^{10} \lfloor k \{ x \} \rfloor
We can see that for each value of kk, k{x}\lfloor k \{ x \} \rfloor can equal integers from 00 to k1k-1.
Clearly, the value of k{x}\lfloor k \{ x \} \rfloor changes only when {x}\{ x \} is equal to any of the fractions 1k,2kk1k\frac{1}{k}, \frac{2}{k} \dots \frac{k-1}{k}.
So we want to count how many distinct fractions less than 11 have the form mn\frac{m}{n} where n10n \le 10. Explanation for this is provided below. We can find this easily by computing
k=210ϕ(k)\sum_{k=2}^{10} \phi(k)
where ϕ(k)\phi(k) is the Euler Totient Function. Basically ϕ(k)\phi(k) counts the number of fractions with kk as its denominator (after simplification). This comes out to be 3131.
Because the value of f(x)f(x) is at least 00 and can increase 3131 times, there are a total of (A) 32\fbox{\textbf{(A)}\ 32} different possible values of f(x)f(x).

Explanation:
Arrange all such fractions in increasing order and take a current mn\frac{m}{n} to study. Let pp denote the previous fraction in the list and xoldx_\text{old} (0xoldp0 \le x_\text{old} p, we clearly have all xnewxoldx_\text{new} \ge x_\text{old}. Therefore, the change must be nonnegative.
But among all numerators coprime to nn so far, mm is the largest. Therefore, choosing mn\frac{m}{n} as x{x} increases the value n{x}\lfloor n \{ x \} \rfloor. Since the overall change in f(x)f(x) is positive as fractions m/nm/n increase, we deduce that all such fractions correspond to different values of the function.
Minor Latex Edits made by MathWizard10.

Supplement
Here are all the distinct mn\frac{m}{n} and ϕ(k):\phi(k):
When n=2n=2 , mn=12\frac{m}{n}=\frac{1}{2} . ϕ(2)=1\phi(2)=1
When n=3n=3 , mn=13\frac{m}{n}=\frac{1}{3} , 23\frac{2}{3} . ϕ(3)=2\phi(3)=2
When n=4n=4 , mn=14\frac{m}{n}=\frac{1}{4} , 34\frac{3}{4} . ϕ(4)=2\phi(4)=2
When n=5n=5 , mn=15\frac{m}{n}=\frac{1}{5} , 25\frac{2}{5} , 35\frac{3}{5} , 45\frac{4}{5} . ϕ(5)=4\phi(5)=4
When n=6n=6 , mn=16\frac{m}{n}=\frac{1}{6} , 56\frac{5}{6} . ϕ(6)=2\phi(6)=2
When n=7n=7 , mn=17\frac{m}{n}=\frac{1}{7} , 27\frac{2}{7} , 37\frac{3}{7} , 47\frac{4}{7} , 57\frac{5}{7} , 67\frac{6}{7} . ϕ(7)=6\phi(7)=6
When n=8n=8 , mn=18\frac{m}{n}=\frac{1}{8} , 38\frac{3}{8} , 58\frac{5}{8} , 78\frac{7}{8} . ϕ(8)=4\phi(8)=4
When n=9n=9 , mn=19\frac{m}{n}=\frac{1}{9} , 29\frac{2}{9} , 49\frac{4}{9} , 59\frac{5}{9} , 79\frac{7}{9} , 89\frac{8}{9} . ϕ(9)=6\phi(9)=6
When n=10n=10 , mn=110\frac{m}{n}=\frac{1}{10} , 310\frac{3}{10} , 710\frac{7}{10} , 910\frac{9}{10} . ϕ(10)=4\phi(10)=4
k=210ϕ(k)=31\sum_{k=2}^{10} \phi(k)=31
31+1=(A) 3231+1=\fbox{\textbf{(A)}\ 32}
~isabelchen

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.