Waste less time on Facebook — follow Brilliant.
×

Simple Nearest Integer Inequality

Let \(x,y\) be positive real numbers. Prove that \[\dfrac{\lfloor x\rfloor+\lfloor y\rfloor}{\lfloor x+y\rfloor}\le \dfrac{\lceil x\rceil+\lceil y\rceil}{\lceil x+y\rceil}\]

Where \(\lfloor \ldots\rfloor\) is the greatest int function and \(\lceil \ldots \rceil\) is the smallest int function.

In general, prove that for reals \(x_1,x_2\ldots x_n\), that \[\dfrac{\sum\limits_{i=1}^{n}\lfloor x_i\rfloor}{\left\lfloor\sum\limits_{i=1}^{n} x_i\right\rfloor}\le \dfrac{\sum\limits_{i=1}^{n}\lceil x_i\rceil}{\left\lceil\sum\limits_{i=1}^{n} x_i\right\rceil}\]

Note by Daniel Liu
2 years, 11 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Hint:

\[\lfloor{n}\rfloor \leq \lceil{n}\rceil \leq \lfloor{n}\rfloor + 1\] Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Sharky Kesa I think the \(<\) should be changed to a \(\leq\). Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse No, cos it isn't possible. Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Sharky Kesa \(\lceil{3.5}\rceil=\lfloor{3.5}\rfloor+1 \longrightarrow 4=3+1\). Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse Sorry, didn't realise. Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Sharky Kesa It's okay bro. I like your spelling of "realize". :D Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse It's realise for me. We have to use British English. You have to use your Americanised version of English. Also, when writing by hand, s takes shorter time to write than z in cursive. Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Sharky Kesa Yeah bro, it's okay I know. Wait do you write cursive? :O Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse Yes. We have to write in cursive/running writing. It's faster. Sharky Kesa · 2 years, 11 months ago

Log in to reply

Cool problem! I think this is a valid approach:

Looking at the first equation, we see that equality is attained if \(x\) and \(y\) are both integers, which would make the equation just \(1 \leq 1\). Split this into two cases:

Case 1:

\(\lfloor{x}\rfloor+\lfloor{y}\rfloor < \lfloor{x+y}\rfloor\). In this case, obviously neither \(x\) or \(y\) are integers otherwise their sum would be the same as the floor of their sum. Thus the numerator of the RHS will become \(\lfloor{x}\rfloor+1+\lfloor{y}\rfloor+1\) and denominator \(\lfloor{x}\rfloor+\lfloor{y}\rfloor+1\). Obviously the LHS will be \(<1\) and the RHS \(>1\) so the inequality is held. Can we generalize this inequality for the general case? Yes, because for each extra term the LHS will still be \(<1\) and the denominator \(>1\) and the reverse on the RHS.

Case 2:

Both \(x\) and \(y\) are integers. The inequality becomes

\[\dfrac{x+y}{x+y} \leq \dfrac{x+y}{x+y}\]

which is obviously true. You'll see how it's really just an extension of Case 3. It will clearly also be true even for the general case given.

Case 3:

\(\lfloor{x}\rfloor+\lfloor{y}\rfloor = \lfloor{x+y}\rfloor\). This will be true as long as the fractional part of \(x\) and \(y\) do not have a sum \(>1\), unlike Case 1. So, like, \(x\) could be \(3.3\) and \(y\) could be \(1.6\), and \(0.6+0.3 \ngeq 1\). In this case, the inequality becomes

\[\dfrac{x+y-\text{frac}(x)-\text{frac}(y)}{x+y-\text{frac}(x)-\text{frac}(y)} \leq \dfrac{x+y+1-\text{frac}(x)-\text{frac}(y)}{x+y+1-\text{frac}(x)-\text{frac}(y)}\]

where \(\text{frac}(n)\) represents the fractional part, or just \(n-\lfloor{n}\rfloor\). Obviously, both sides are equal and the inequality is satisfied. We see that for all \(x_1, x_2, x_3, \dots\) this is satisfied as well since there will always be that extra \(+1\) in the numerator and denominator of the RHS since the sum of the fractional parts is \(<1\).

It is impossible for \(\lfloor{x}\rfloor\) to be greater than \(\lfloor{x+y}\rfloor\) because the largest possible value of \(\text{frac}(x)+\text{frac}(y)=0.999\dots+0.999\dots\) which is \(<2\).

Quod erat demonstratum. Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse Simpler:

Let \(x=x_1+x_f\) and \(y=y_1+y_f\) where \(x_1,y_1\) are integers and \(x_f,y_f\) are the fractional part of \(x,y\) respectively.

Note that \[\lfloor x\rfloor +\lfloor y\rfloor \le \lfloor x+y\rfloor \] because \[x_1+y_1 \le x_1+y_1+\lfloor x_f+y_f\rfloor\]

This equation becomes \[\dfrac{\lfloor x\rfloor +\lfloor y\rfloor}{\lfloor x+y\rfloor}\le 1\]

Also, note that \[\lceil x \rceil +\lceil y \rceil \ge \lceil x+y\rceil\] because \[x_1+1+y_1+1\ge x_1+y_1+\lceil x_f+y_f\rceil\]

This equation becomes \[\dfrac{\lceil x \rceil +\lceil y \rceil}{\lceil x+y\rceil}\ge 1\]

Putting the two equations together, we have \[\dfrac{\lfloor x\rfloor +\lfloor y\rfloor}{\lfloor x+y\rfloor}\le 1\le \dfrac{\lceil x \rceil +\lceil y \rceil}{\lceil x+y\rceil}\]

and we are done. \(\Box\) Daniel Liu · 2 years, 11 months ago

Log in to reply

@Daniel Liu How can you claim that \(\lfloor x\rfloor + \lfloor y\rfloor\le \lfloor x+y\rfloor\implies \frac{\lfloor x\rfloor + \lfloor y\rfloor}{\lfloor x+y\rfloor}\le 1\) given that \(\lfloor x+y\rfloor\) can be negative? I can see why it is true when it is positive, but it looks false otherwise. Mathh Mathh · 2 years, 11 months ago

Log in to reply

@Mathh Mathh Right, the inequality only holds for positive reals. Thanks for reminding me, I'll fix it. Daniel Liu · 2 years, 11 months ago

Log in to reply

@Daniel Liu Prove \[\lfloor 3x\rfloor = \lfloor x\rfloor + \left\lfloor x+\frac 13 \right\rfloor + \left\lfloor x+\frac 23 \right\rfloor \] Beakal Tiliksew · 2 years, 11 months ago

Log in to reply

@Beakal Tiliksew That is just Hermite's Identity for \(n=3\). Daniel Liu · 2 years, 11 months ago

Log in to reply

@Daniel Liu I have seen an equivalent identity to Hermite's but for ceiling functions: do you know by any chance if there is a separate name for it to quote in olympiads, or whether I'd need to prove it? Daniel Remo · 2 years, 11 months ago

Log in to reply

@Daniel Remo Indeed, \[\sum_{i=0}^{n-1}\left\lceil x+\dfrac{i}{n}\right\rceil = \lceil nx\rceil +n-1\]

It is not hard to prove from Hermite's Identity. there is no name for it, so you are better off proving it. Daniel Liu · 2 years, 11 months ago

Log in to reply

@Daniel Liu Hey yeah I realized that too. :D Finn Hulse · 2 years, 11 months ago

Log in to reply

@Daniel Liu That's what I did. I was gong to post a hint. Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Sharky Kesa I'll post it anyway. Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Daniel Liu Mmm. Essentially, you're boiling down my solution and going backwards. Cool! :D Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse I am so bad at proofs? Help me how can i practice and where should i start.@Finn Hulse @Daniel Liu Mardokay Mosazghi · 2 years, 11 months ago

Log in to reply

@Mardokay Mosazghi Brilliant. Solve some problems and read their solutions. You learn loads of stuff from well-written solutions. When I started Brilliant, I didn't even know what floor and ceiling functions. Now I can solve these sorts of proof equations mentally. Sharky Kesa · 2 years, 11 months ago

Log in to reply

@Sharky Kesa Good for you! Calvin Lin Staff · 2 years, 11 months ago

Log in to reply

@Calvin Lin Excuse me can we talk? Finn Hulse · 2 years, 11 months ago

Log in to reply

@Mardokay Mosazghi I'm not too great either. I tend to draw mine out and make them longer than they need to be, because I have trouble explaining really simple concepts... It's weird. :P Finn Hulse · 2 years, 11 months ago

Log in to reply

@Finn Hulse Experience helps. Sharky Kesa · 2 years, 11 months ago

Log in to reply

I Think the Answer is 56 Henry Chen · 2 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...