Maths Olympiad Prep

Library / /14 of 63

Algebra Difficulty 6.4 National olympiad Prove it Japan

For a real number rr denote by [r][r] the greatest integer less than or equal to rr. How many positive integers nn are there for which
1000000n1000000n+1=1 \lfloor \frac{1000000}{n} \rfloor - \lfloor \frac{1000000}{n+1} \rfloor = 1
is satisfied?

Solution

First, we prove the following Lemma.

Lemma. If real numbers x,yx, y and an integer kk satisfy k<xy<k+1k < x - y < k + 1, then [x][y]=k[x] - [y] = k or k+1k + 1 must hold.
Proof: Since 0x[x]<10 \le x - [x] < 1 and 0y[y]<10 \le y - [y] < 1, we have xy1<[x][y]<xy+1x - y - 1 < [x] - [y] < x - y + 1. This, together with k<xy<k+1k < x - y < k + 1, yields k1<[x][y]<k+2k - 1 < [x] - [y] < k + 2. Since [x][y][x] - [y] is an integer, we obtain the assertion of the Lemma.
For a positive integer nn, let us write f(n)=1000000nf(n) = \frac{1000000}{n}. Then, we get f(n)f(n+1)=1000000n(n+1)f(n) - f(n + 1) = \frac{1000000}{n(n+1)}.

(1) Case where 1n<7071 \le n < 707: We have n(n+1)<500000n(n + 1) < 500000 so that 2<f(n)f(n+1)2 < f(n) - f(n + 1) holds in this case. Therefore, by the Lemma, we get [f(n)][f(n+1)]2[f(n)] - [f(n + 1)] \ge 2, which shows that there are no nn satisfying the condition of the problem in this case.

(2) Case where 707n<1000707 \le n < 1000: We have 500000<n(n+1)<1000000500000 < n(n + 1) < 1000000 and therefore, 1<f(n)f(n+1)<21 < f(n) - f(n + 1) < 2 in this case. So, we have [f(n)][f(n+1)]=1[f(n)] - [f(n + 1)] = 1 or 22 by the Lemma. If we let aa (bb) be the number of nn's with 707n<1000707 \le n < 1000, for which [f(n)][f(n+1)]=1[f(n)] - [f(n + 1)] = 1 ([f(n)][f(n+1)]=2[f(n)] - [f(n + 1)] = 2, respectively), then we have
a+b=1000707=293,a+2b=[f(707)][f(1000)]=14141000=414. a + b = 1000 - 707 = 293, \quad a + 2b = [f(707)] - [f(1000)] = 1414 - 1000 = 414.
Solving these simultaneous equations, we obtain a=172a = 172.

(3) Case where n1000n \ge 1000: We have 1000000<n(n+1)1000000 < n(n + 1), so that 0<f(n)f(n+1)<10 < f(n) - f(n + 1) < 1 hold in this case. By the Lemma, we have [f(n)][f(n+1)]=0[f(n)] - [f(n + 1)] = 0 or 11. Since we have [f(n)]=0[f(n)] = 0 if n>1000n > 1000, the number of nn's for which [f(n)][f(n+1)]=1[f(n)] - [f(n + 1)] = 1 in this case equals [f(1000)]=1000[f(1000)] = 1000.

Therefore, we conclude that the desired answer for the problem is 172+1000=1172172+1000 = 1172.

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.