Maths Olympiad Prep

Library / /244 of 520

Number theory Difficulty 5.2 AIME, harder Find the answer

5. Let f(x)=[x1!]+[x2!]++[x2013!]f(x)=\left[\frac{x}{1!}\right]+\left[\frac{x}{2!}\right]+\cdots+\left[\frac{x}{2013!}\right], where [x][x] denotes the greatest integer not exceeding the real number xx. For an integer nn, if the equation f(x)=nf(x)=n has a real solution, then nn is called a "good number". Find the number of good numbers in the set {1,3,5,,2013}\{1,3,5, \cdots, 2013\}.
(Wu Genxiu, Contributed)

A number or a short expression. Spacing and $ signs are ignored.

Solution

5. First, give two obvious conclusions:
(1) If mm is a positive integer and xx is a real number, then
[xm]=[[x]m]; \left[\frac{x}{m}\right]=\left[\frac{[x]}{m}\right] ;
(2) For any integer ll and positive even number mm, we have
[2l+1m]=[2lm] \left[\frac{2 l+1}{m}\right]=\left[\frac{2 l}{m}\right] \text {. }

Returning to the original problem.
In conclusion (1), let m=k!(k=1,2,,2013)m=k!(k=1,2, \cdots, 2013), and summing up, we get
f(x)=k=12013[xk!]=k=12013[[x]k!]=f([x]), f(x)=\sum_{k=1}^{2013}\left[\frac{x}{k!}\right]=\sum_{k=1}^{2013}\left[\frac{[x]}{k!}\right]=f([x]),

This shows that the equation f(x)=nf(x)=n has a real solution if and only if the equation f(x)=nf(x)=n has an integer solution.
From now on, we only need to consider the case where xx is an integer.
 By f(x+1)f(x)=[x+1][x]+k=22013([x+1k!][xk!])1, \begin{array}{l} \text { By } f(x+1)-f(x) \\ =[x+1]-[x]+\sum_{k=2}^{2013}\left(\left[\frac{x+1}{k!}\right]-\left[\frac{x}{k!}\right]\right) \\ \geqslant 1, \end{array}

we know that f(x)(xZ)f(x)(x \in \mathbf{Z}) is monotonically increasing.
Next, find integers aa and bb such that
f(a1)2013, \begin{array}{l} f(a-1)2013, \end{array}

so b=1173b=1173.
Therefore, the good numbers in {1,3,5,,2013}\{1,3,5, \cdots, 2013\} are the odd numbers in {f(0),f(1),,f(1173)}\{f(0), f(1), \cdots, f(1173)\}.

In equation (1), let x=2l(l=0,1,,586)x=2 l(l=0,1, \cdots, 586), by conclusion (2) we know
[2l+1k!]=[2lk!](2k2013). Hence f(2l+1)f(2l)=1+k=22013([2l+1k!][2lk!])=1, \begin{array}{l} {\left[\frac{2 l+1}{k!}\right]=\left[\frac{2 l}{k!}\right](2 \leqslant k \leqslant 2013) .} \\ \text { Hence } f(2 l+1)-f(2 l) \\ =1+\sum_{k=2}^{2013}\left(\left[\frac{2 l+1}{k!}\right]-\left[\frac{2 l}{k!}\right]\right)=1, \end{array}

This shows that f(2l)f(2 l) and f(2l+1)f(2 l+1) have exactly one odd number.
Thus, {f(0),f(1),,f(1173)}\{f(0), f(1), \cdots, f(1173)\} contains exactly 11742=587\frac{1174}{2}=587 odd numbers, i.e., the set {1,3,5,,2013}\{1,3,5, \cdots, 2013\} contains 587 good numbers.

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.