Maths Olympiad Prep

Library / China Southeastern Mathematical Olympiad /35 of 39

China Southeastern Mathematical Olympiad

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⌋=⌊⌊x⌋m⌋. \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=12013⌊xk!⌋=∑k=12013⌊⌊x⌋k!⌋=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+1⌋−⌊x⌋+∑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) (x∈Zx \in \mathbb{Z}) is monotonously increasing. Now, we find integers aa and bb, such that
f(a−1)<0≤f(a)<f(a+1)<…<f(b−1)<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=16⌊1173k!⌋=1173+586+195+48+9+1=2012≤2013, \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=16⌊1174k!⌋=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!⌋(2≤k≤2013). \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.