When Does It Increase?

Algebra Level 2

r = 1 34 18 r 35 = ? \large \sum_{r=1}^{34} \left \lfloor \frac{18r}{35} \right \rfloor =\, ?

Notation : \lfloor \cdot \rfloor denotes the floor function .

195 196 256 289

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.

7 solutions

Pi Han Goh
Aug 17, 2016

Relevant wiki: Floor and Ceiling Functions - Problem Solving

Since 18 and 35 are coprime, then for integer 1 r 34 1\leq r \leq 34 , the fractional part of 18 r 35 \dfrac{18r}{35} can take the values 1 35 , 2 35 , , 34 35 \dfrac{1}{35}, \dfrac{2}{35} , \ldots, \dfrac{34}{35} .

By definition, x { x } = x x - \{ x \} = \lfloor x \rfloor . We can rewrite the summation in question as

r = 1 34 18 r 35 = r = 1 34 ( 18 r 35 { 18 r 35 } ) = r = 1 34 18 r 35 r = 1 34 r 35 = r = 1 34 17 r 35 = 17 35 r = 1 34 r = 17 35 34 ( 34 + 1 ) 2 = 1 7 2 = 289 . \begin{aligned} \sum_{r=1}^{34} \left \lfloor \dfrac{18r}{35} \right \rfloor &=& \sum_{r=1}^{34} \left( \dfrac{18r}{35} - \left \{ \dfrac{18r}{35} \right \} \right) \\ &=& \sum_{r=1}^{34} \dfrac{18r}{35} - \sum_{r=1}^{34} \dfrac r{35} \\ &=& \sum_{r=1}^{34} \dfrac{17r}{35} = \dfrac{17}{35} \sum_{r=1}^{34} r \\ &=& \dfrac{17}{35} \cdot \dfrac{34(34+1)}2 = 17^2 = \boxed{289} . \\ \end{aligned}

The second last step follows from the algebraic identity , 1 + 2 + 3 + + n = n ( n + 1 ) 2 1 + 2 + 3 + \cdots + n = \dfrac {n(n+1)}2 .

How do you go from the Sum(18r/35-{18r/35}) to Sum(18r/35) - Sum(r/35). What happened to the second 18?

Pat Laplante - 4 years, 9 months ago

Log in to reply

r = 1 34 { 18 r 35 } = r = 1 34 r 35 \displaystyle \sum_{r=1}^{34} \left \{\dfrac{18r}{35} \right \}= \sum_{r=1}^{34} \dfrac r{35} as explained in the first line.

Pi Han Goh - 4 years, 9 months ago

seems fraction function of 18r/35 (denoted by {18r/35}) is not r/35, obviously, but Sum({18r/35}) is equal to Sum(r/35), because, if r=35 we have 0 of remainder, but since its <35, we will have 34 remainders which we can see are= 18/35;1/35;19/35;2/35;20/35;3/35;21/35;4/35;...;17/35 so we have on the numerators all the numbers from 1 to 34.

In fact Sum({a*r/b})=Sum(r/b); and as it may seem, the coefficient "disappears". The only thing that changes with a is the order in which the numerators appear; for example= Sum({34r/35})=34/35+33/35+32/35+31/35+...+1/35=Sum(r/35)

For me its like magic :V

Eliud Alejandro Maldonado Sanchez - 3 years, 3 months ago

Interesting to use {x} as x mod 1

chase marangu - 2 years, 4 months ago
J Chaturvedi
Aug 18, 2016

18r/35 = r/2 + r/70,
The contribution of r/70, towards sum of floor function would be zero for each of the number from 1 to 34 and, therefore, it can be ignored.
The contribution of r/2, towards sum of floor function would be reduced by 1/2, for each of the 17 odd numbers from 1 to 34.
Therefore, required sum;
= (1/2)(1+2+3+....+34) - 17/2,
= (1/2)(34×35/2) - 17/2 = (17/2)(35 -1),
= 17^2 = 289.


Oli Hohman
Aug 18, 2016

To get an intuition for the problem, try plugging in values and seeing what you get. When you plug in r = 1, you get 0. Then from there, r =2 and r = 3 both give you 1, r=4 and r=5 both give you 2, r=6 and r=7 both give you 3...etc.

Since this is a 33 term sequence between r=2 and r=34, the series can be thought of as

the sum from n=1 to n=16 of (2n) + 17 = 17*(16+1) = 17^2 = 289

I did this way.

Niranjan Khanderia - 4 years, 1 month ago

I did it like this.

Gabor Koranyi - 2 years, 5 months ago
Zaber Mahbub
Aug 18, 2016

include <iostream>

using namespace std;

int main() { int sum=0; for (int r=1;r<=34;r++) { sum+=(int)(18*r/35); } cout<<sum; }

Gabriel Chacón
Jan 16, 2019

My approach was as follows:

I noticed that each value of the fraction inside the floor function is slightly larger than 18 r 36 = r 2 \frac{18r}{36}=\frac{r}{2} , which is much easier to sum:

r = 1 34 r 2 = 0 + 2 × ( 1 + 2 + + 16 ) + 17 = 1 7 2 = 289 \displaystyle \sum_{r=1}^{34}\left \lfloor \dfrac{r}{2} \right \rfloor=0+2\times(1+2+\ldots +16)+17=17^2=\boxed{289} ,

which is the value asked for, since the accumulated excesses are insufficient to make any of the terms in the original sum jump to the next integer value.

1
2
3
4
5
sum_ = 0
for r in range(1,35):
    sum_ += 18*r/35

print sum_

1
289

Alternatively, (0+17) 18/2+(1+16) 16/2 = 289

Lin Lyons - 2 years, 4 months ago
Lukas Leibfried
Sep 3, 2016

We know that the first term in the sum drops out. We also know that every remaining term in the sum will appear twice with the exception of 17. Therefore, we multiply the sum of the natural numbers from 1 to 16 by 2 and add 17 for our final answer of 289.

I wrote this solution on a mobile device and didn't feel like using TeX.

Yes this is how I did it partly. Generate the first 5 terms get the pattern and the add in pairs. You get Summation (2r-1) 17 odd terms or sq(17) = 289

subhash shanbhag - 3 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...