protypuns's blog

Number theory question
By protypuns, history, 9 years ago, In English

I was solving a problem, but I couldn't do it. So I looked at the editorial, in witch this was given:

(X + Y) / (A + B) <= MAX{X / A, Y / B}

where X, Y, A, B >= 0 and are integers.

So my question is, what is the proof to that? Sorry for the stupid question, but I couldn't find this anywhere.

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

There is more general fact that . Then .

Proof is simple algebra:

Multiplying side by side you get a(b + d) > b(a + c) removing ab there you get again.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

The inequality doesn't hold for x = 2, a = 1, b = 1, y = 8.

(x + y) / (a + b) <= max(x / a, x / b)
(2 + 8) / (1 + 1) <= max(2 / 1, 2 / 1)
10 / 2 <= max(2, 2)
5 <= 2

Did you mean (x + y) / (a + b) <= max(x / a, y / b)?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    ops sorry :/

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      No problem. The solution is quite simple:

      Without loss of generality, assume that x / a >= y / b. Our inequality simplifies to (x + y) / (a + b) <= x / a.

      Multiplying out, we get that ax + ay <= ax + bx, and ay <= bx, which holds due to our original assumption that x / a >= y / b.

      → Reply