Prove a Floor Inequality

During a math class, a proposed problem on a handout is as follows:

Prove that \[\lfloor x\rfloor +\dfrac{\lfloor 2x\rfloor}{2}+\dfrac{\lfloor 3x\rfloor}{3}+\cdots +\dfrac{\lfloor nx\rfloor}{n}\le \lfloor nx\rfloor\] for all positive reals $x$ and integer $n$.

Can someone help me prove it? I tried to use a periodic argument, proving it true for $x\in [0,1)$ then plugging in $x=x'+k$ for positive integer $k$ to prove the inequality for all other $x$ . However it didn't work, because my inequality substitutions were too strict and I ended up with $(n-1)x\le \lfloor nx\rfloor$ which is not true.

Thanks!

#Algebra #HelpMe! #Inequality #FloorFunction #Proof

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

http://mks.mff.cuni.cz/kalva/usa/usoln/usol815.html

mathh mathh - 7 years ago

Apparently this is USAMO 1981 #5.

David Lee - 7 years ago

Yep.

Daniel Liu - 7 years ago

I was just gonna say...

Kaan Dokmeci - 7 years ago

I think using induction approach should also work

Roger Lu - 7 years ago

I don't know if I am right or wrong ... So please correct me ... Thanks in advance ... here is my Solution : As we know, floor(x) = x - {x} , where {x} is fractional part. if we replace all the floor values in the above eqn will reduce to

LHS : nx - [ {x} + ({2x}/2) + ({3x}/3) + ({4x}/4) + ........... + ({nx}/n) ]

What is interesting to see is that {x} = {2x}/2 = {3x}/3 = ..... = {nx}/n (You can check it with any value of x :) )

Hence LHS will become : nx - n{x}

Solving RHS we got : floor(nx) = nx - {nx} As the fractional part of {nx} will always lie between 0 and 1, i.e. 0 <= {nx} < 1

And it is easy to see that the product of n and {x} in LHS is always greater than or equal to (in case of 0 as fractional value) {nx} in RHS.

Probably this will prove it ... What say guys ???

Vipin Kumar - 6 years, 12 months ago

@Daniel Liu @Finn Hulse : Guys can you please check the above solution ???

Vipin Kumar - 6 years, 12 months ago

I still don't think it proves it. @Finn Hulse

Your solution depends on the fact that $\{x\}+\dfrac{\{2x\}}{2}+\cdots+\dfrac{\{nx\}}{n}\ge \{nx\}$ but you didn't prove that.

Daniel Liu - 6 years, 11 months ago

@Daniel Liu – Meh I'm tired. :P

Finn Hulse - 6 years, 11 months ago

It's good as far as I can tell! :D

Finn Hulse - 6 years, 12 months ago

$n\{x\}\neq \{nx\}$ . Try, e.g., $x=0.6$ , $n=2$ . Then $2\cdot \{0.6\}=1.2\neq\{2\cdot 0.6\}=0.2$ .

mathh mathh - 6 years, 12 months ago

When did I say n{x} = {nx} ??? Please check it once more :)

Vipin Kumar - 6 years, 12 months ago

@Vipin Kumar – "What is interesting to see is that {x} = {2x}/2 = {3x}/3 = ..... = {nx}/n"

I could have equally said that $\{x\}\neq \frac{\{nx\}}{n}$ , just multiply both sides of your equality by $n$ (we can, since $n\neq 0$ ). Both of the equalities are equivalent.

mathh mathh - 6 years, 12 months ago

@Mathh Mathh – Yups got my mistake... thank you... :)

Vipin Kumar - 6 years, 12 months ago

that should prove it man :)...... i don't find any serious anomaly..... good job

Abhinav Raichur - 6 years, 12 months ago

{x} = {2x}/2 = {3x}/3 = ..... = {nx}/n is false (see my other comments).

mathh mathh - 6 years, 12 months ago

@Mathh Mathh – yes and it is just the special case where inequality turns to equality...... it gives maximum value of LHS

Abhinav Raichur - 6 years, 12 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$