Maths Olympiad Prep

Library / /9 of 13

Algebra Difficulty 6.8 National olympiad Prove it China

For each positive integer, define a function
f(n)={0,if n is the square of an integer,1n,if n is not the square of an integer. f(n) = \begin{cases} 0, & \text{if } n \text{ is the square of an integer,} \\ \left\lfloor \frac{1}{\sqrt{n}} \right\rfloor, & \text{if } n \text{ is not the square of an integer.} \end{cases}
(Here [x][x] denotes the maximum integer not exceeding xx, and
{x}=x[x]\{x\} = x - [x].) Find the value of k=1200f(k)\sum_{k=1}^{200} f(k).

Solution

For arbitrary a,kN+a, k \in \mathbb{N}^+, if k2<a<(k+1)2k^2 < a < (k+1)^2, we set
a=k2+m,m=1,2,,2k, a = k^2 + m, \quad m = 1, 2, \dots, 2k,
a=k+θ,0<θ<1, \sqrt{a} = k + \theta, \quad 0 < \theta < 1,
[1a]=[1ak]=[a+kak2]=[2k+θm]. \left[ \frac{1}{\sqrt{a}} \right] = \left[ \frac{1}{\sqrt{a-k}} \right] = \left[ \frac{\sqrt{a+k}}{a-k^2} \right] = \left[ \frac{2k+\theta}{m} \right].
For0<2k+θm2kθ<1, \text{For} \quad 0 < \frac{2k+\theta}{m} - \frac{2k}{\theta} < 1,
if there exists an integer tt between 2km\frac{2k}{m} and 2k+θm\frac{2k+\theta}{m}, then
2km<t<2k+θm. \frac{2k}{m} < t < \frac{2k+\theta}{m}.
On one hand 2k<mt2k < mt, thus 2k+1mt2k+1 \le mt. On the other hand, mt<2k+θ<2k+1mt < 2k+\theta < 2k+1, a contradiction.
Thus[2k+θm]=[2km],k<a<k+1[1{a}]=m=12k[2km],a=1n+1f(a)=k=1ni=12k[2ki].(1) \text{Thus} \quad \left[ \frac{2k+\theta}{m} \right] = \left[ \frac{2k}{m} \right], \\ \sum_{k<a<k+1} \left[ \frac{1}{\{a\}} \right] = \sum_{m=1}^{2k} \left[ \frac{2k}{m} \right], \\ \sum_{a=1}^{n+1} f(a) = \sum_{k=1}^{n} \sum_{i=1}^{2k} \left[ \frac{2k}{i} \right]. \quad (1)

Thus
a=1(n+1)2f(a)=k=1nj=12kT(j)=n[T(1)+T(2)]+(n1)[T(3)+T(4)]++[T(2n1)+T(2n)](2) \begin{aligned} \sum_{a=1}^{(n+1)^2} f(a) &= \sum_{k=1}^{n} \sum_{j=1}^{2k} T(j) \\ &= n[T(1) + T(2)] + (n-1)[T(3) + T(4)] \\ &\quad + \dots + [T(2n-1) + T(2n)] \end{aligned} \quad (2)
From (2), k=1162f(k)=k=115(16k)[T(2k1)+T(2k)].(3) \text{From (2), } \sum_{k=1}^{16^2} f(k) = \sum_{k=1}^{15} (16-k)[T(2k-1) + T(2k)]. \quad (3)

k123456789101112131415
aka_k356678698881071010

Therefore, k=1256f(k)=k=115(16k)ak=783.(4) \text{Therefore, } \sum_{k=1}^{256} f(k) = \sum_{k=1}^{15} (16-k)a_k = 783. \quad (4)
Note that f(256)=f(162)=0f(256) = f(16^2) = 0 by definition. When k{241,242,,255}k \in \{241, 242, \dots, 255\}, denote k=152+r (16r30)k = 15^2 + r\ (16 \le r \le 30), then
k15=152+r15=r152+r+15, \sqrt{k}-15=\sqrt{15^2+r}-15=\frac{r}{\sqrt{15^2+r}+15},
r31<r152+r+15<r30,130r<1{152+r}<31r<2. \frac{r}{31} < \frac{r}{\sqrt{15^2 + r + 15}} < \frac{r}{30}, \quad 1 \le \frac{30}{r} < \frac{1}{\{\sqrt{15^2 + r}\}} < \frac{31}{r} < 2.
Thus
[1k]=1,k{241,242,,255}.(5) \left[ \frac{1}{\sqrt{k}} \right] = 1, \quad k \in \{241, 242, \dots, 255\}. \quad (5)
Therefore,
k=1200f(k)=783k=201256f(k)=78315=768. \sum_{k=1}^{200} f(k) = 783 - \sum_{k=201}^{256} f(k) = 783 - 15 = 768.

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.