Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[noodle0117]

Hello all,

I'm trying to figure out a math proof but I'm rather stuck on how to do so.
The problem itself isn't intuitively hard, but I'm not sure on how to figure it out formally.

Here's the problem:
Prove that there exists a positive real number c such that x + y ≥ c min{x, y} for
every two positive integers x, y.

Thanks

[Whatsifsowhatsit]

It's been too long since I was taught to do such things formally, but it is indeed intuitively quite simple. The most difficult situation is when you have x=y (A), I think, and then basically x+y = 2x, so if c ≤ 2, you have it. You just have to show (A) formally, which I wouldn't be sure how to do. You might be able to imagine that if x >> y or vice versa, it's not that difficult to get higher than the right hand side of the inequality by just adding the much larger number, and work from there. So again, you can see that intuitively when you think about it a bit, it's the formal part that I wouldn't be able to do anymore. I should look back into this at some point. I wonder if Khan Academy has anything on formal mathematical proofs.

Hopefully that helps some, at least.

[RulerOfNothing]

Let us assume x>=y (so x=a+y where a is positive or zero), which we can do because x+y=y+x and min{x,y}=min{y,x}. The inequality then reduces to a+2y>=c*y. If we let c be equal to one then we get a+2y>=y, which is equivalent to a+y>=0. Since a is positive or zero and y is always positive then this statement is true for all values of a and y. I am not quite sure how to finish this proof exactly (it is a bit late here), but I hope this helps.

[Virex]

Tips:
1: Can you express c in x and y?
2: What happens when x = y? And what happens when x > y or y > x?

Spoiler: Don't watch if you're merely looking for tips (click to show/hide)

Proof for any positive number, assuming deriving the actual values c can take is sufficient

x + y ≥ c min{x, y}

min{x, y} > 0
(x + y)/min{x,y} ≥ c
max{x,y}/min{x,y} + 1 ≥ c
Domain of c is (0 max{x,y}/min{x,y}+1]

min{x, y} > 0,
max{x,y} > 0,
max{x,y}/min{x,y} ≥ 1
So the smallest possible domain (I'm fairly sure I'm butchering a term here) of c is (0 2], which contains the integers 1 and 2, Q.E.D.

[Skyrunner]

What does x + y >= c min(x, y) mean? c* min()? O_o

Edit: Assuming yes, here's my own proof:

Spoiler (click to show/hide)

First, since x, y are natural numbers, they cannot be zero, and their product is always positive.

Therefore, we can say that
(x + y) / min(x, y) >= c
because x, y are never negative, nor are they equal to zero.

Also,
(x + y) / min(x, y) = (y+ x) / min (y, x) in all cases.

Now, let us assume that y >= x.

Therefore
1 + y/x >= c

x/y > 0, due to the domain of x and y. Therefore 1+x/y>1. Therefore a positive real c exists for all x, y.

[noodle0117]

Thanks a lot!