Maths Olympiad Prep

Library / /35 of 40

Algebra Difficulty 7.1 National olympiad, round 2 Prove it China

Let f(x)=x1!+x2!++x2013!f(x) = \lfloor \frac{x}{1!} \rfloor + \lfloor \frac{x}{2!} \rfloor + \dots + \lfloor \frac{x}{2013!} \rfloor, where x\lfloor x \rfloor is the greatest integer no greater than xx. Call an integer nn a good number if the equation f(x)=nf(x) = n has a real solution xx. Find the number of good numbers in the set {1,3,5,,2013}\{1, 3, 5, \dots, 2013\}.

Solution

First, we point out two obvious facts:
(a) If mm is a positive integer and xx is real, then
xm=xm. \lfloor \frac{x}{m} \rfloor = \lfloor \frac{\lfloor x \rfloor}{m} \rfloor.
(b) For any integer ll and positive even number mm, we have
2l+1m=2lm. \lfloor \frac{2l + 1}{m} \rfloor = \lfloor \frac{2l}{m} \rfloor.
Let m=k!m = k! (k=1,2,,2013k = 1, 2, \dots, 2013) in (a) and summing up, we have
f(x)=k=12013xk!=k=12013xk!=f(x), f(x) = \sum_{k=1}^{2013} \lfloor \frac{x}{k!} \rfloor = \sum_{k=1}^{2013} \lfloor \frac{\lfloor x \rfloor}{k!} \rfloor = f(\lfloor x \rfloor),
that is, f(x)=nf(x) = n has a real solution if and only if f(x)=nf(x) = n has an integer solution. So, we only consider xx as an integer. Since
f(x+1)f(x)=x+1x+k=22013(x+1k!xk!)1,1 f(x+1) - f(x) = \lfloor x+1 \rfloor - \lfloor x \rfloor + \sum_{k=2}^{2013} \left( \lfloor \frac{x+1}{k!} \rfloor - \lfloor \frac{x}{k!} \rfloor \right) \ge 1, \quad \textcircled{1}
we see that f(x)f(x) (xZx \in \mathbb{Z}) is monotonously increasing. Now, we find integers aa and bb, such that
f(a1)<0f(a)<f(a+1)<<f(b1)<f(b)2013<f(b+1). \begin{align*} f(a-1) < 0 &\le f(a) < f(a+1) < \dots \\ &< f(b-1) < f(b) \le 2013 < f(b+1). \end{align*}
Note that f(1)<0=f(0)f(-1) < 0 = f(0), so a=0a = 0. Since
f(1173)=k=161173k!=1173+586+195+48+9+1=20122013, \begin{align*} f(1173) &= \sum_{k=1}^{6} \left\lfloor \frac{1173}{k!} \right\rfloor = 1173 + 586 + 195 + 48 + 9 + 1 \\ &= 2012 \le 2013, \end{align*}
f(1174)=k=161174k!=1174+587+195+48+9+1=2014>2013, \begin{align*} f(1174) &= \sum_{k=1}^{6} \left\lfloor \frac{1174}{k!} \right\rfloor = 1174 + 587 + 195 + 48 + 9 + 1 \\ &= 2014 > 2013, \end{align*}
we see that b=1173b = 1173.
So the good numbers in {1,3,5,...,2013}\{1, 3, 5, ..., 2013\} are the odd numbers in
{f(0),f(1),,f(1173)}. \{f(0), f(1), \dots, f(1173)\}.
Let x=2lx = 2l (l=0,1,,586l = 0, 1, \dots, 586) in ①. By (b), we have
2l+1k!=2lk!(2k2013). \left\lfloor \frac{2l + 1}{k!} \right\rfloor = \left\lfloor \frac{2l}{k!} \right\rfloor \quad (2 \le k \le 2013).
Thus,
f(2l+1)f(2l)=1+k=22013(2l+1k!2lk!)=1, f(2l + 1) - f(2l) = 1 + \sum_{k=2}^{2013} \left( \left\lfloor \frac{2l+1}{k!} \right\rfloor - \left\lfloor \frac{2l}{k!} \right\rfloor \right) = 1,
that is, there is exactly one odd number in f(2l)f(2l) and f(2l+1)f(2l + 1).
Therefore, there are 11742=587\frac{1174}{2} = 587 odd numbers in {f(0),f(1),,f(1173)}\{f(0), f(1), \dots, f(1173)\}, that is, there are 587 good numbers in the set {1,3,5,,2013}\{1, 3, 5, \dots, 2013\}.
\square

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.