Number Theory

Bài toán (Indian NMO 2014)

Với số tự nhiên bất kì $n$, chứng minh rằng:

$$\lfloor \frac{n}{1}\rfloor +\lfloor \frac{n}{2}\rfloor +...+\lfloor \frac{n}{n}\rfloor +\lfloor \sqrt{n}\rfloor$$ là số chẵn Lời giải :

Bổ đề 1 : Với số nguyên dương $n$ và số nguyên dương $a$. Ta có :

i) $\lfloor \frac{n+1}{a}\rfloor =\lfloor \frac{n}{a}\rfloor khia\nmid n+1$

ii) $\lfloor \frac{n+1}{a}\rfloor =\lfloor \frac{n}{a}\rfloor +1khia\mid n+1$

Chứng minh :

Đặt $n+1=ka+r,t\in \left[0,a-1\right]$. Nếu $r=0$ thì $\lfloor \frac{n}{a}\rfloor =\lfloor \frac{ka-1}{a}\rfloor =k+\lfloor \frac{-1}{a}\rfloor =k-1=\lfloor \frac{n+1}{a}\rfloor -1$

Nếu $r\ne 0$ thì $\lfloor \frac{n}{a}\rfloor =\lfloor \frac{ka+r-1}{a}\rfloor =k+\lfloor \frac{r-1}{a}\rfloor =k=\lfloor \frac{n+1}{a}\rfloor$

Bổ đề được chứng minh.

Bổ đề 2 : Với số nguyên dương $n$, ta có :

i) $\lfloor \sqrt{n+1}\rfloor =\lfloor \sqrt{n}\rfloor$ nếu $n+1$ không là số chính phương.

ii) $\lfloor \sqrt{n+1}\rfloor =\lfloor \sqrt{n}\rfloor +1$ nếu $n+1$ là số chính phương.

Chứng minh :

Nếu $n+1$ chính phương, đặt $n+1=a^2$ thì $\lfloor \sqrt{n+1}\rfloor =\lfloor \sqrt{a^2}\rfloor =a$

Còn $a-1=\sqrt{a^2-2a+1}<\sqrt{n}=\sqrt{a^2-1}<\sqrt{a^2}=a\Rightarrow \lfloor \sqrt{n}\rfloor =a-1=\lfloor \sqrt{n+1}\rfloor -1$

Nếu $n+1$ không chính phương. Gỉa sử $\lfloor \sqrt{n+1}\rfloor =a,\lfloor \sqrt{n}\rfloor =b\Rightarrow a\ge b$. Ta có $a\le \sqrt{n+1}\Rightarrow a^2\le n+1$ nhưng do dấu bằng không xảy ra (vì $n+1$ không chính phương) nên $a^2<n+1\Rightarrow a^2\le n\Rightarrow a\le \sqrt{n}\Rightarrow a\le \lfloor n\rfloor =b$. Kéo theo $a=b$.

Bổ đề được chứng minh.

 Quay trở lại bài toán : 

Ta chứng minh bằng quy nạp. Kiểm tra được dễ dàng với những giá trị đầu tiên. Gỉa sử :

$A$$=\lfloor \frac{n}{1}\rfloor +\lfloor \frac{n}{2}\rfloor +...+\lfloor \frac{n}{n}\rfloor +\lfloor \sqrt{n}\rfloor$$=2m$

Ta xét với $n+1$ :

Gỉa sử $n+1$ có đúng $k$ ước nguyên dương, hiển nhiên các ước này thuộc tập $\left\{1,2,3,...,n+1\right\}$

Khi đó :

$B$$=\lfloor \frac{n+1}{1}\rfloor +\lfloor \frac{n+1}{2}\rfloor +...+\lfloor \frac{n+1}{n}\rfloor +\lfloor \frac{n+1}{n+1}\rfloor +\lfloor \sqrt{n+1}\rfloor$$=\left(\lfloor \frac{n}{1}\rfloor +\lfloor \frac{n}{2}\rfloor +...+\lfloor \frac{n}{n}\rfloor \right)+k+\lfloor \sqrt{n+1}\rfloor$$=2m+k+\lfloor \sqrt{n+1}\rfloor -\lfloor \sqrt{n}\rfloor$

• Nếu $n+1$ không là số chính phương thì trong phân tích tiêu chuẩn của $n+1$ sẽ có một thừa số nguyên tố có số mũ lẻ. Gỉa sử $n+1=p_1^{t_1}.p_2^{t_2}...p_i^{t_i}..p_s^{t_s}$ với $t_i$ lẻ. khi đó $2\mid k=(t_1+1)(t_2+1)...(t_s+1)$ vì $t_i$ lẻ.

Tức trường hợp này $k$ chẵn, đặt $k=2k^{\prime }$.

Mặt khác theo bổ đề trên khi $n+1$ không chính phương thì $\lfloor \sqrt{n+1}\rfloor =\lfloor \sqrt{n}\rfloor$

Do vậy ta có $B=2m+2k^{\prime }$ chẵn.

• Nếu $n+1$ chính phương thì tất cả các ước nguyên tố trong phân tích tiêu chuẩn đều có số mũ chẵn. Khi đó số ước của $n+1$ lẻ, tức $k=2k^{\prime }+1$.

Theo bổ đề lại có $\lfloor \sqrt{n+1}\rfloor =\lfloor \sqrt{n}\rfloor +1$

Do vậy ta có $B=2m+2k^{\prime }+2$ chẵn.

Theo nguyên lí quy nạp bài toán được chứng minh.