Блог пользователя protypuns

Number theory question
Автор protypuns, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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)?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    ops sorry :/

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      → Ответить