Prove that expression is always even.

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Prove that expression is always even.

G H J

Reveal topic tags

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

Source: INMO 2014- Problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

676 posts

#1 h Feb 2, 2014, 12:38 PM • 2 Y

Y by Adventure10, cubres

Let $n$ be a natural number. Prove that,
$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor$
is even.

This post has been edited 1 time. Last edited by ahaanomegas, Feb 2, 2014, 2:31 PM
Reason: Fixed LaTeX

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

#2 h Feb 2, 2014, 12:46 PM • 4 Y

Y by Adventure10, Mango247, cubres, and 1 other user

Just induct. The idea is common.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#3 h Feb 2, 2014, 1:27 PM • 6 Y

Y by makar, ashrith9sagar_1, Adventure10, Mango247, cubres, aidan0626

$\sum_{k=1}^n [\frac{n}{k}]=\sum_{k=1}^n\tau(k)$ . $\tau(k)$ - is number of divisors of k.
If $k\not =m^2$ divisors $d,\frac{k}{d}$ different and $\tau(k)$ is even.
$\tau(k)$ is odd only if $k=m^2$ . Therefore
$\sum_{k=1}^n[\frac{n}{k}]+[\sqrt n]=2[\sqrt n]\mod 2 =0\mod 2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1510 posts

mathuz

#4 h Feb 2, 2014, 2:04 PM • 5 Y

Y by DanDumitrescu, Adventure10, Mango247, Math_DM, cubres

[Moderator: Please do not double-post and/or quote the post immediately before yours.]

$\sum_{k=1}^n \left \lfloor \frac{ n }{ k }\right \rfloor=\sum_{k=1}^n \tau(k)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

131 posts

Shravu

#5 h Feb 2, 2014, 4:00 PM • 5 Y

Y by Pluto1708, ashrith9sagar_1, Adventure10, Mango247, cubres

Yes, Induction....

gif(n+1/k) > gif(n/k) if and only if k|n+1 gif(n+1/k) = gif(n/k)+1 so there is pairing

and if n+1 is a square gif(root(n+1)) > gif(root(n))

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

181 posts

Askr

#6 h Feb 2, 2014, 4:33 PM • 7 Y

Y by Unknown-6174, Uagu, SHREYAS333, stevoo, Adventure10, Mango247, cubres

We prove the statement by Induction.

For n = 1, [1/1] + [1^(1/2)] = 1+1 = 2 (Base Case)
Lets assume that for n = n, [n/1] + [n/2] + [n/3] + .............. + [n/n] + [n^(1/2)] = even
Now, for n=n+1, we take two cases :

(i) n+1 is not a perfect square :
In this case n+1 has k factors (excluding 1 and n+1) where k is even.
If b is not a factor of n+1, then [(n+1)/b] = [n/b].
If b is a factor of n+1, then [(n+1)/b] = [n/b] +1. There will be k such cases.
Also, [(n+1)^(1/2)] = [n^(1/2)] since n+1 is not a perfect square.
therefore, [(n+1)/1] + [(n+1)/2] + [(n+1)/3] + ............... + [(n+1)/n] + [(n+1)/(n+1)] + [(n+1)^(1/2)]
= [n/1] + [n/2] + [n/3] + ............. + [n/n] + [n^(1/2)] + k + 2
= even (since k is even)

(ii) n+1 is a perfect square :
In this case n+1 has k factors (excluding 1 and n+1) where k is odd.
If b is not a factor of n+1, then [(n+1)/b] = [n/b].
If b is a factor of n+1, then [(n+1)/b] = [n/b] +1. There will be k such cases.
Also, [(n+1)^(1/2)] = [n^(1/2)] + 1 since n+1 is a perfect square.
therefore, [(n+1)/1] + [(n+1)/2] + [(n+1)/3] + ............... + [(n+1)/n] + [(n+1)/(n+1)] + [(n+1)^(1/2)]
= [n/1] + [n/2] + [n/3] + ............. + [n/n] + [n^(1/2)] + k + 3
= even (since k is odd)

We have proved both the cases.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1581 posts

makar

#7 h Feb 2, 2014, 7:06 PM • 10 Y

Y by isomorphicdevikram, mathbuzz, Pluto1708, AlastorMoody, ashrith9sagar_1, Supercali, Adventure10, Mango247, cubres, TestX01

shivangjindal wrote:

Let $n$ be a natural number. Prove that,
$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor$
is even.

By counting number of Lattice point in first quadrant and below or on the curve $xy=n$ in two different ways, we get:

$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor =2\sum _{k=1}^{\left\lfloor \sqrt{n} \right\rfloor }\left\lfloor \frac{n}{k} \right\rfloor -\left\lfloor \sqrt{n} \right\rfloor^2$

Now

$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor=\underbrace{2\sum _{k=1}^{\left\lfloor \sqrt{n} \right\rfloor }\left\lfloor \frac{n}{k} \right\rfloor}_\text{Even} -\underbrace{ \left\lfloor \sqrt{n} \right\rfloor\left(\left\lfloor \sqrt{n} \right\rfloor-1\right)}_\text{Even}=\text{Even}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

803 posts

#8 h Feb 3, 2014, 6:26 AM • 7 Y

Y by AHKR, div5252, maths_arka, Adventure10, Mango247, Math_DM, cubres

Non-inductive solution --
Lemma -- $[\frac{n}{1}]+......+[\frac{n}{n}]=d(1)+d(2)+....d(n)$
Proof -- the number of elements in S={1,2,...,n} ,which are divisible by $q$ is $[\frac{n}{q}]$ .
Now , the rest is trivial

end of lemma

Back to the main problem --
Now , note that ,
$\sum[\frac{n}{k}]+[\sqrt{n}] =d(1)+d(2)+.....+d(n)+[\sqrt{n}]=f(n)$ (say)
Now , note that , $d(k)=1(mod2)$ iff $k$ is a perfect square ..
There are only $[\sqrt{n}]$ perfect squares in {1,2,...,n}.
hence , $f(n)=[\sqrt{n}]+[\sqrt{n}]=0(mod2)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

641 posts

BSJL

#9 h Apr 23, 2014, 9:03 AM • 3 Y

Y by Adventure10, Mango247, cubres

We just need to notice that the following two points:

1. For $n=1$ , It is true.

2. $([\frac{n+1}{1}]+......+[\frac{n+1}{n+1}]+[\sqrt{n+1}])-([\frac{n}{1}]+......+[\frac{n}{n}]+[\sqrt{n}])=2d(n+1)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2125 posts

#12 h Sep 5, 2019, 4:51 PM • 3 Y

Y by Arhaan, Adventure10, cubres

INMO 2014 P2 wrote:

Let $n$ be a natural number. Prove that,
$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor$ is even.

Solution: Notice, for $n,k \in \mathbb{N}$ , $\left \lfloor \frac{n}{k} \right \rfloor$ denotes the number of positive multiples of $k$ below $\left \lfloor \frac{n}{k} \right \rfloor$ . Also, any multiple in the form of $k \times \ell \le n$ will be counted twice, once in $\left \lfloor \frac{n}{k} \right \rfloor$ and in $\left \lfloor \frac{n}{\ell} \right \rfloor$ where $k, \ell$ are distinct. Only Numbers that can be represented in the form of squares (eg: $n \times n$ ) are not counted twice, but adding a $\lfloor {\sqrt{n}} \rfloor$ to the expression makes all the counts twice and hence the resultant is even $\qquad \blacksquare$

This post has been edited 1 time. Last edited by AlastorMoody, Sep 5, 2019, 4:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#13 h May 26, 2022, 2:57 AM • 2 Y

Y by centslordm, cubres

It is well known that $\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor=\sum_{i=1}^n d(i),$ where $d(i)$ denotes the number of factors of $i.$ Notice $d(i)\equiv 1\pmod{2}$ if and only if $i$ is a perfect square. We know there are $\left\lfloor\sqrt{n}\right\rfloor$ perfect squares from $1$ to $n$ so $\left(\sum_{i=1}^n d(i)\right)+\left\lfloor\sqrt{n}\right\rfloor\equiv 2\left\lfloor\sqrt{n}\right\rfloor\equiv 0\pmod{2}.$ $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

225 posts

#14 h Aug 8, 2022, 10:59 AM • 2 Y

Y by panche, cubres

We will first prove the following well-known result:
Claim:
If $d(n)$ is the number of divisors of a positive integer $n$ , then
$d(1)+d(2)+\ldots+d(n)=\lfloor\frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\ldots+\lfloor\frac{n}{n}\rfloor$ Proof of the claim:
$\begin{align*} d(1)+d(2)+\ldots+d(n)&=\sum_{k=1}^{n}{\sum_{i|k}{1}}\\ &=\sum_{i=1}^{n}{\sum_{\substack{1\le j\le n\\ i|j}}{1}}\\ &=\sum_{i=1}^{n}{\lfloor\frac{n}{i}\rfloor}=\lfloor\frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\ldots+\lfloor\frac{n}{n}\rfloor \end{align*}$ as desired.

Now we proceed with induction. The base case $n=1$ is clear. Assume that $2| d(1)+\ldots+d(k)+\lfloor\sqrt{k}\rfloor$ . Then for $k+1$
$\begin{align*} 2&|d(1)+d(2)+\ldots+d(k)+d(k+1)+\lfloor\sqrt{k+1}\rfloor\Longleftrightarrow\\ 2&|d(1)+d(2)+\ldots+d(k)+d(k+1)+\lfloor\sqrt{k+1}\rfloor+\lfloor\sqrt{k}\rfloor-\lfloor\sqrt{k}\rfloor\Longleftrightarrow\\ 2&| d(k+1)+\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt{k}\rfloor \end{align*}$ If $k+1$ is a square, then $d(k+1)$ is odd, while $\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt{k}\rfloor=1$ . If $k+1$ is not a square, $d(k+1)$ is even, and $\lfloor\sqrt{k+1}\rfloor-\lfloor\sqrt{k}\rfloor=0$ , finishing the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeismathematics

1188 posts

lifeismathematics

#15 h Aug 11, 2023, 12:49 PM • 1 Y

Y by Math_DM

first of all we have $\left \lfloor \frac{n}{1} \right \rfloor +\left \lfloor \frac{n}{2} \right \rfloor +\cdots+\left \lfloor \frac{n}{n} \right \rfloor=\tau(1)+\tau(2)+\cdots+\tau(n)$

clearly, $\tau(j) \equiv 0 \pmod 2$ if $j$ is not a perfect square, and $\equiv 1 \pmod 2$ if it is a perfect square. We notice in set $\{1,2 , \cdots , n\}$ we have $\lfloor \sqrt{n} \rfloor$ many perfect squares, so we have $\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor$ $\equiv 2 \lfloor \sqrt{n} \rfloor \equiv 0 \pmod 2$ as there are just $\lfloor \sqrt{n} \rfloor$ many perfect squares in $[n]$ so done. $\blacksquare$

This post has been edited 1 time. Last edited by lifeismathematics, Aug 11, 2023, 12:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

920 posts

#16 h Sep 29, 2024, 1:07 PM

Y by

Basic idea:
d(1) + d(2) + \cdots + d(n) + [\sqrt{n}
and parity changes only when n is a square
where parity of [sqrt(n)] changes too
so parity of expression is invariant
now we see at n = 1 its even
so its always even
qed

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

106 posts

#17 h Oct 13, 2024, 5:53 PM

Y by

[n/1] + [n/2] +.... + [n/n] = d(1) + d(2) +.... d(n) (lemma)
no. of divisors of a square is odd
Case 1->
there are an even number of naturals <= [rootn] (the squares till n are even in no. )
<=> [rootn] is even and the sum of all d(i) from 1 to [rootn] is obv even and we are done
similar logic for the other case works

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

548 posts

cursed_tangent1434

#18 h Feb 21, 2025, 3:39 PM

Y by

This problem really made me appreciate how theory dependent Olympiad number theory really was. Knowing that one trick really made solving the problem much easier. The following lemma is essential.

Lemma : For all positive integers $n$ and $k$ ,
$\left\lfloor \frac{n}{k} \right\rfloor - \left\lfloor \frac{n-1}{k} \right\rfloor = \begin{cases}1 & k \mid n \\ 0 & k \nmid n\end{cases}$

Proof : The proof is clear. $[\left\lfloor \frac{n}{k} \right\rfloor > \left\lfloor \frac{n-1}{k} \right\rfloor$ if and only if we jump to a new multiple of $k$ .

Now, we proceed via induction. Note how the problem is clear for $n=1$ . Now, assuming the problem when $n=k$ we show the result when $n=k+1$ . Note,
$\begin{align*} \left(\sum_{i=1}^{k+1} \left \lfloor \frac{k+1}{i} \right \rfloor + \sqrt{k+1} \right) - \left(\sum_{i=1}^{k} \left \lfloor \frac{k}{i} \right \rfloor + \sqrt{k} \right ) &= d(k+1) + \sqrt{k+1}- \sqrt{k} \end{align*}$
Now, if $k+1$ is not a perfect square, $d(k+1)$ is even, and $\sqrt{k+1}=\sqrt{k}$ . Thus, the result holds when $n=k+1$ as well. Further if $k+1$ is a perfect square, $\sqrt{k+1}-\sqrt{k}=1$ but $d(k+1)$ is odd, and thus again the result holds for $n=k+1$ and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

601 posts

eg4334

#19 h Feb 25, 2025, 1:58 AM

Y by

It rewrites into $d(1)+d(2) + \dots + d(n) + \lfloor \sqrt{n} \rfloor$ . All the $d(i)$ are even except the squares but the latter term makes up for it by adding one for each square.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

29 posts

#21 h Feb 26, 2025, 11:29 PM

Y by

It's known that $\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor = d(1) + d(2) + \cdots + d(n)$ where $d(x)$ is the number of divisors of $x$ , so the problem is now equivalent to showing that $d(1) + d(2) + \cdots + d(n) + \left\lfloor \sqrt{n} \right\rfloor$ is even.

Let's express $n$ as $k^2 + l$ where $0 \leq l \leq 2k$ , and let's consider two cases:

Case 1: $k$ is odd.

In this case, there is an odd number of squares bewteen $1$ and $n$ inclusive, and notice that it does not matter where $n$ lies between $k^2$ and $(k+1)^2$ since we remember that $d(x)$ is odd if and only if $x$ is a square. This means that $d(1) + d(2) + \cdots + d(n)$ is odd, and $\left\lfloor \sqrt{n} \right\rfloor = k$ which is odd, so the total sum is even. $\square$

Case 2: $k$ is even.

Similarly, we don't care where $n$ lies between $k^2$ and $(k+1)^2$ and notice that there is an even number of squares between $1$ and $n$ inclusive. Therefore, $d(1) + d(2) + \cdots + d(n)$ is even and $\left\lfloor \sqrt{n} \right\rfloor = k$ , which is also even, so the total sum is even. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11093 posts

#22 h Feb 28, 2025, 4:28 AM

Y by

shivangjindal wrote:

Let $n$ be a natural number. Prove that,
$\left\lfloor \frac{n}{1} \right\rfloor+ \left\lfloor \frac{n}{2} \right\rfloor + \cdots + \left\lfloor \frac{n}{n} \right\rfloor + \left\lfloor \sqrt{n} \right\rfloor$ is even.

Claim: $\tau(n+1)+\left\lfloor\sqrt{n+1}\right\rfloor-\left\lfloor\sqrt n\right\rfloor$ is even for all $n\ge0$

Let $\left\lfloor\sqrt{n+1}\right\rfloor=k$ .

Case 1: $n+1$ is a square
We claim that $\left\lfloor\sqrt{n+1}\right\rfloor-\left\lfloor\sqrt n\right\rfloor=1$ .

Write $n+1=k^2$ . We have, since $k\ge0$ :
$k^2-1\ge(k-1)^2\Rightarrow n\ge(k-1)^2$ as well as $n<n+1=k^2$ . Then $k-1\le\sqrt n<k$ so we must have $\left\lfloor\sqrt n\right\rfloor=k-1$ , so:
$\left\lfloor\sqrt{n+1}\right\rfloor-\left\lfloor\sqrt n\right\rfloor=1.$
Then since $\tau(n+1)$ is odd, our claim is proven for this case.

Case 2: $n+1$ isn't a square
We claim that $\left\lfloor\sqrt{n+1}\right\rfloor-\left\lfloor\sqrt n\right\rfloor=0$ .

By the definition of $k$ , we have $k^2\le n+1<(k+1)^2$ , but since $n+1$ isn't a square, this inequality is strict on both sides. Then $k^2\le n<n+1<(k+1)^2$ so $\left\lfloor\sqrt n\right\rfloor=k$ , hence $\left\lfloor\sqrt{n+1}\right\rfloor-\left\lfloor\sqrt n\right\rfloor=0$ .

Then since $\tau(n+1)$ is odd, our claim is proven.

We finish the problem by summing this from $0$ to $n-1$ , giving that:
$\sum_{i=1}^n\tau(i)+\left\lfloor\sqrt n\right\rfloor$ is even, and we're done since $\sum_{i=1}^n\tau(i)=\sum_{i=1}^n\left\lfloor\frac ni\right\rfloor$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

377 posts

alexanderhamilton124

#23 h Yesterday at 3:50 AM

Y by

Breh
Let us induct. We are clearly done for $n = 1$ , so suppose we are done for $n \in \{1, \dots, k\}$ . Let $f(n)$ be our expression. Note that

$\left\lfloor \frac{k + 1}{x} \right\rfloor - \left\lfloor \frac{k}{x} \right\rfloor = 1 \text{ if } x \mid (k + 1), \text{ and } 0 \text{ otherwise}.$
Hence:

$f(k + 1) - f(k) = d(k + 1) + \left\lfloor \sqrt{k + 1} \right\rfloor - \left\lfloor \sqrt{k} \right\rfloor$
If $k + 1$ is not a perfect square, $d(k + 1)$ is even and

$\left\lfloor \sqrt{k + 1} \right\rfloor = \left\lfloor \sqrt{k} \right\rfloor$
which gives $f(k + 1) - f(k)$ even, so $f(k + 1)$ even as well, and we're done.

If $k + 1$ is a perfect square, $d(k + 1)$ is odd and

$\left\lfloor \sqrt{k + 1} \right\rfloor = \left\lfloor \sqrt{k} \right\rfloor + 1,$
so $f(k + 1) - f(k)$ is even again and we're done.

This post has been edited 1 time. Last edited by alexanderhamilton124, 4 hours ago

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a