Sum of Floor Functions

Algebra Level 3

⌊ 1 2 ⌋ + ⌊ 1 2 + 1 100 ⌋ + ⌊ 1 2 + 2 100 ⌋ + … + ⌊ 1 2 + 299 100 ⌋ = ? \large{\left \lfloor \dfrac{1}{2} \right \rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} \right\rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{2}{100} \right\rfloor + \ldots + \left\lfloor\dfrac{1}{2} + \dfrac{299}{100} \right\rfloor =\ ?}


The answer is 450.

View wiki
Akhil Bansal by Akhil Bansal , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Chew-Seong Cheong
Sep 25, 2015

Let the sum of the sequence be S S , then:

S = ∑ k = 0 299 ⌊ 1 2 + k 100 ⌋ = ∑ k = 0 299 ⌊ 50 + k 100 ⌋ = ∑ k = 0 49 ⌊ 50 + k 100 ⌋ + ∑ k = 50 149 ⌊ 50 + k 100 ⌋ + ∑ k = 150 249 ⌊ 50 + k 100 ⌋ + ∑ k = 250 299 ⌊ 50 + k 100 ⌋ = 50 ( 0 ) + 100 ( 1 ) + 100 ( 2 ) + 50 ( 3 ) = 0 + 100 + 200 + 150 = 450 \begin{aligned} S & = \sum_{k=0}^{299} \left \lfloor \frac{1}{2} + \frac{k}{100} \right \rfloor \\ & = \sum_{k=0}^{299} \left \lfloor \frac{50+k}{100} \right \rfloor \\ & = \sum_{k=0}^{49} \left \lfloor \frac{50+k}{100} \right \rfloor + \sum_{k=50}^{149} \left \lfloor \frac{50+k}{100} \right \rfloor + \sum_{k=150}^{249} \left \lfloor \frac{50+k}{100} \right \rfloor + \sum_{k=250}^{299} \left \lfloor \frac{50+k}{100} \right \rfloor \\ & = 50(0) + 100(1) + 100(2) + 50(3) \\ & = 0 + 100 + 200 + 150 = \boxed{450} \end{aligned}

13 Helpful 0 Interesting 0 Brilliant 0 Confused
Akshat Sharda
Sep 24, 2015

= [ 1 2 ] + [ 1 2 + 1 100 ] + [ 1 2 + 2 100 ] + … + [ 1 2 + 299 100 ] =\left[ \frac{1}{2} \right] + \left[ \frac{1}{2} + \frac{1}{100} \right] + \left[ \frac{1}{2} + \frac{2}{100} \right] + \ldots+ \left[\frac{1}{2} + \frac{299} {100} \right]

= [ 1 2 ] + … + [ 1 2 + 49 100 ] + [ 1 2 + 50 100 ] + … + [ 1 2 + 149 100 ] + [ 1 2 + 150 100 ] + … + [ 1 2 + 249 100 ] + [ 1 2 + 250 100 ] + … + [ 1 2 + 299 100 ] =\left[\frac{1}{2}\right]+\ldots+\left[\frac{1}{2}+\frac{49}{100}\right]+\left[\frac{1}{2}+\frac{50}{100}\right]+\ldots+\left[\frac{1}{2}+\frac{149}{100}\right]+\left[\frac{1}{2}+\frac{150}{100}\right]+\ldots+\left[\frac{1}{2}+\frac{249}{100}\right]+\left[\frac{1}{2}+\frac{250}{100}\right]+\ldots+\left[\frac{1}{2}+\frac{299}{100}\right]

= 0 × 50 + 1 × 100 + 2 × 100 + 3 × 50 =0×50+1×100+2×100+3×50

= 450 =\boxed{450}

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Do note that this problem is basically trivial using Hermite's Identity (which is almost equivalent to your method).

The given sum can be rewritten as,

S = ∑ k = 0 299 ⌊ 1 2 + k 100 ⌋ = ∑ m = 0 2 ∑ k = 0 99 ⌊ ( 2 m + 1 ) 2 + k 100 ⌋ S=\sum_{k=0}^{299}\left\lfloor\frac 12+\frac k{100}\right\rfloor=\sum_{m=0}^2\sum_{k=0}^{99}\left\lfloor\frac{(2m+1)}2+\frac k{100}\right\rfloor

Applying Hermite's Identity and simplifying gives,

S = 50 ∑ m = 0 2 ( 2 m + 1 ) = 50 × 3 2 = 450 S=50\sum_{m=0}^2 (2m+1)=50\times 3^2=450

You can also generalize it a bit. Simple application of Hermite's Identity yields the following result :

∀ x ∈ R , m , α ∈ Z + , S ( m , α , x ) = ∑ k = 0 m α − 1 ⌊ x + k α ⌋ = m ( ⌊ α x ⌋ + α ( m − 1 ) 2 ) \forall~x\in\Bbb R~,~m,\alpha\in\Bbb{Z^+}~,~S(m,\alpha,x)=\sum_{k=0}^{m\alpha-1}\left\lfloor x+\frac k{\alpha}\right\rfloor=m\left(\lfloor\alpha x\rfloor+\frac{\alpha(m-1)}{2}\right)

The problem posed here is evaluating S ( 3 , 100 , 1 2 ) S\left(3,100,\dfrac 12\right) .

Prasun Biswas - 5 years, 8 months ago

Log in to reply

Are you 17 years old??
From where do you learnt all this?

Akhil Bansal - 5 years, 8 months ago

Log in to reply

Yes, I'm 17 years old (and 4 months, to be precise). I learnt all this stuff mostly from the internet.

Prasun Biswas - 5 years, 8 months ago

Log in to reply

@Prasun Biswas – Have you given the IIT Exam ?

Akhil Bansal - 5 years, 8 months ago

Log in to reply

@Akhil Bansal – Nope. And I have almost zero interest in it. I was not cut out for engineering anyway. And IITs have extremely high standards. I'm currently studying at Jadavpur University and am planning to give the CMI and ISI entrance exams next year (I missed the exam dates this year).

Prasun Biswas - 5 years, 8 months ago

T h a n k s ! ! \huge Thanks !! for improving my knowledge!!

Akshat Sharda - 5 years, 8 months ago

Log in to reply

Wait a second, I just realized there's a minor error in the generalization. Let me edit it first.

EDIT: The error has been corrected now.

Prasun Biswas - 5 years, 8 months ago

Amazing Solution, thanks for sharing it.

Aditya Sky - 5 years ago

Same Method

Kushagra Sahni - 5 years, 8 months ago

Log in to reply

This is the only possible method.

Akhil Bansal - 5 years, 8 months ago

Log in to reply

Say That to everyone who said same method.

Kushagra Sahni - 5 years, 8 months ago

Same method...good one.

Saaket Sharma - 5 years, 8 months ago

Log in to reply

This is the only possible method..

Akhil Bansal - 5 years, 8 months ago

Nice solution

Atul Shivam - 5 years, 8 months ago

I have solved the solution over and over again and each time I get \huge598.5 \approx\ 600}

Muhammmad Humaiz - 5 years, 8 months ago

Log in to reply

This is not an arithmetic progression. It has got a sign of the floor function on every term if you see clearly. You can't solve by taking that as an AP, you need to use the concept of the floor function. And when you approximated the value of 598.5, why didn't you get 599? Why 600?

Kushagra Sahni - 5 years, 8 months ago

I always get 598.5 ≈ 600 \huge { 598.5 \approx 600}

⌊ 1 2 ⌋ + ⌊ 1 2 + 1 100 ⌋ + ⌊ 1 2 + 2 100 ⌋ + … + ⌊ 1 2 + 299 100 ⌋ \large{\left \lfloor \dfrac{1}{2} \right \rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} \right\rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{2}{100} \right\rfloor + \ldots + \left\lfloor\dfrac{1}{2} + \dfrac{299}{100} \right\rfloor \ }

= ⌊ 1 2 ⌋ + ⌊ 1 2 + 1 100 ⌋ + ⌊ 1 2 + 1 100 + 1 100 ⌋ + … + ⌊ 1 2 + 1 100 + 1 100 + 1 100 + … ( 299 t e r m s ) ⌋ \large = {\left \lfloor \dfrac{1}{2} \right \rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} \right\rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} + \dfrac{1}{100} \right\rfloor + \ldots + \left\lfloor\dfrac{1}{2} + \dfrac{1}{100} + \dfrac{1}{100} + \dfrac{1}{100} + \ldots ( 299 terms) \right\rfloor \ }

T h i s i s a n A r i t h m e t i c P r o g r e s s i o n ( d = 1 100 ) i n w h i c h a 1 = 1 2 , a n = 1 2 + 299 100 a n d n = 300. S o , S n = n 2 ( a 1 + a n ) \large { This\quad is\quad an\quad Arithmetic\quad Progression\quad (d=\frac { 1 }{ 100 } )\quad in\\ \\ which\quad { a }_{ 1 }=\frac { 1 }{ 2 } ,\quad { a }_{ n }=\frac { 1 }{ 2 } +\frac { 299 }{ 100 } \quad and\quad n=300.\quad So,\\ \\ { S }_{ n }\quad =\quad \frac { n }{ 2 } (\quad { a }_{ 1 }+\quad { a }_{ n }\quad )\quad }

S 300 = 300 2 ( 1 2 + 1 2 + 299 100 ) S 300 = 150 ( 1 + 299 100 ) S 300 = 150 ( 399 100 ) \large { S }_{ 300 }\quad =\quad \dfrac { 300 }{ 2 } (\quad \dfrac { 1 }{ 2 } +\quad \dfrac { 1 }{ 2 } +\dfrac { 299 }{ 100 } \quad )\quad \\ { S }_{ 300 }\quad =\quad 150(\quad 1+\dfrac { 299 }{ 100 } \quad )\quad \\ { S }_{ 300 }\quad =\quad 150(\quad \dfrac { 399 }{ 100 } \quad )

S 300 = 598.5 ≈ 600 \huge { { S }_{ 300 } = 598.5 \approx 600}

Muhammad Humaiz Anjum - 5 years, 8 months ago

Log in to reply

The range of the floor function is integers. So, from closure in Z \mathbb{Z} , the sum of all given floor expressions must be an integer, right !

Venkata Karthik Bandaru - 5 years, 8 months ago

The problem is that this is not an arithmetic progression. Note the floor function along with the terms. Let's take a smaller sum as an example. For instance, consider the sum ⌊ 1 3 ⌋ + ⌊ 2 3 ⌋ + ⌊ 1 ⌋ \lfloor\frac 13\rfloor+\lfloor \frac 23\rfloor+\lfloor 1\rfloor .

According to your argument , since { 1 3 , 2 3 , 1 } \{\frac 13,\frac 23,1\} is an arithmetic progression with a 1 = 1 3 , n = 3 a_1=\frac 13,n=3 and a n = 1 a_n=1 , the sum is 2 2 using the formula for summing AP.

But, note that we're not summing the terms of the arithmetic progression. We're summing the floored values of the terms of the progression. Use the definition of floor function . Using that, the sum in the mentioned example actually simplifies to 0 + 0 + 1 = 1 0+0+1=1 which is ≠ 2 \neq 2 .

Do you see where you made the mistake now?

Prasun Biswas - 5 years, 8 months ago

I always get 598.5 ≈ 600 \huge { 598.5 \approx 600}

⌊ 1 2 ⌋ + ⌊ 1 2 + 1 100 ⌋ + ⌊ 1 2 + 2 100 ⌋ + … + ⌊ 1 2 + 299 100 ⌋ \large{\left \lfloor \dfrac{1}{2} \right \rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} \right\rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{2}{100} \right\rfloor + \ldots + \left\lfloor\dfrac{1}{2} + \dfrac{299}{100} \right\rfloor \ }

= ⌊ 1 2 ⌋ + ⌊ 1 2 + 1 100 ⌋ + ⌊ 1 2 + 1 100 + 1 100 ⌋ + … + ⌊ 1 2 + 1 100 + 1 100 + 1 100 + … ( 299 t e r m s ) ⌋ \large = {\left \lfloor \dfrac{1}{2} \right \rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} \right\rfloor + \left\lfloor \dfrac{1}{2} + \dfrac{1}{100} + \dfrac{1}{100} \right\rfloor + \ldots + \left\lfloor\dfrac{1}{2} + \dfrac{1}{100} + \dfrac{1}{100} + \dfrac{1}{100} + \ldots ( 299 terms) \right\rfloor \ }

T h i s i s a n A r i t h m e t i c P r o g r e s s i o n ( d = 1 100 ) i n w h i c h a 1 = 1 2 , a n = 1 2 + 299 100 a n d n = 300. S o , S n = n 2 ( a 1 + a n ) \large { This\quad is\quad an\quad Arithmetic\quad Progression\quad (d=\frac { 1 }{ 100 } )\quad in\\ \\ which\quad { a }_{ 1 }=\frac { 1 }{ 2 } ,\quad { a }_{ n }=\frac { 1 }{ 2 } +\frac { 299 }{ 100 } \quad and\quad n=300.\quad So,\\ \\ { S }_{ n }\quad =\quad \frac { n }{ 2 } (\quad { a }_{ 1 }+\quad { a }_{ n }\quad )\quad }

S 300 = 300 2 ( 1 2 + 1 2 + 299 100 ) S 300 = 150 ( 1 + 299 100 ) S 300 = 150 ( 399 100 ) \large { S }_{ 300 }\quad =\quad \dfrac { 300 }{ 2 } (\quad \dfrac { 1 }{ 2 } +\quad \dfrac { 1 }{ 2 } +\dfrac { 299 }{ 100 } \quad )\quad \\ { S }_{ 300 }\quad =\quad 150(\quad 1+\dfrac { 299 }{ 100 } \quad )\quad \\ { S }_{ 300 }\quad =\quad 150(\quad \dfrac { 399 }{ 100 } \quad )

S 300 = 598.5 ≈ 600 \huge { { S }_{ 300 } = 598.5 \approx 600}

2 Helpful 0 Interesting 0 Brilliant 0 Confused

You seem to be forgetting that you are taking the floor of 1/2 and (1/2+299/100). The floor of 1/2 is 0, and the floor of 1/2+299/100 is 3. Therefore, you get 150 times 3 or 450.

Benry Burfer - 5 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...