15th Balkan Mathematical Olympiad Problems 1998

15th Balkan Mathematical Olympiad Problems 1998

A1.  How many different integers can be written as [n²/1998] for n = 1, 2, ... , 1997?
A2.  x_i are distinct positive reals satisfying x₁ < x₂ < ... < x_2n+1. Show that x₁ - x₂ + x₃ - x₄ + ... - x_2n + x_2n+1 < (x₁ⁿ - x₂ⁿ + ... - x_2nⁿ + x_2n+1ⁿ)^1/n.

A3.  Let S be the set of all points inside or on a triangle. Let T be the set S with one interior point excluded. Show that one can find points P_i, Q_i such that P_i and Q_i are distinct and the closed segments P_iQ_i are all disjoint and have union T.
A4.  Prove that there are no integers m, n satisfying m² = n⁵ - 4.

Solutions

15th Balkan 1998 Problem 1

How many different integers can be written as [n²/1998] for n = 1, 2, ... , 1997?
Solution
Answer: 1498.
Let f(k) = [k²/1998]. We have k²/1998 - (k - 1)²/1998 = (2k - 1)/1998 > 1 for k ≥ 1000. Hence for k > 1000, f(k) ≥ f(k - 1) + 1. So the 998 values k = 1000, 1001, ... , 1997 generate 998 distinct values of f(k) all at least f(1000) = [999·1000/1998 + 1·1000/1998] = [500 + 1000/1998] = 500.
If k < 1000, then k²/1998 - (k - 1)²/1998 < 1. So the real values 1/1998, 4/1998, 9/1998, ... , 999²/1998 are spaced at intervals of less than one and hence every integer from 1 to f(999) must lie between two of them. Thus for k = 1, 2, ... , 999, f(k) generates every integer from 0 to f(999) = [999·999/1998] = [999/2] = 499, a total of 500 integers.

15th Balkan 1998 Problem 2

x_i are distinct positive reals satisfying x₁ < x₂ < ... < x_2n+1. Show that x₁ - x₂ + x₃ - x₄ + ... - x_2n + x_2n+1 < (x₁ⁿ - x₂ⁿ + ... - x_2nⁿ + x_2n+1ⁿ)^1/n.
Solution
It is easier to prove the more general result where the powers and root use any m > 1, instead of n: x₁ - x₂ + x₃ - x₄ + ... - x_2n + x_2n+1 < (x₁^m - x₂^m + ... - x_2n^m + x_2n+1^m)^1/m. The reason is that it is then essentially sufficient to prove it for n = 1. For having established it for n = 1 we have an almost trivial induction (it is much easier than it looks). Suppose it is true for n, then x₁ - x₂ + x₃ - x₄ + ... - x_2n + x_2n+3 < (x₁^m - x₂^m + ... - x_2n^m + x_2n+1^m)^1/m - x_2n+2 + x_2n+3. Now put y = (x₁^m - x₂^m + ... - x_2n^m + x_2n+1^m)^1/m. Since (x₁^m - x₂^m + ... - x_2n^m + x_2n+1^m) = x₁^m + (x₃^m - x₂^m + (x₅^m - x₄^m) + ... + (x_2n+1^m - x_2n^m) and each term is positive, y is positive. But x_2n+2^m - y^m = (x_2n+2^m - x_2n+1^m) + (x_2n^m - x_2n-1^m) + ... + (x₂^m - x₁^m) and again each term is positive so y < x_2n+2. So we can now apply the theorem for n = 1 to get y - x_2n+2 + x_2n+3 < (y^m - x_2n+2^m + x_2n+3^m)^1/m, which gives the result for n+1.
So it remains to prove the case n = 1. In other words we must show that for 0 < x < y < z we have x - y + z < (x^m - y^m + z^m)^1/m. Put f(x) = x - y + z - (x^m - y^m + z^m)^1/m. Then f '(x) = 1 - (x^m/(x^m - y^m + z^m))^1-1/m. But x^m < x^m - y^m + z^m, so f '(x) > 0 for 0 < x < y. But f(y) = 0, so f(x) < 0 for 0 < x < y, which is the required result.

15th Balkan 1998 Problem 3

Let S be the set of all points inside or on a triangle. Let T be the set S with one interior point excluded. Show that one can find points P_i, Q_i such that P_i and Q_i are distinct and the closed segments P_iQ_i are all disjoint and have union T.
Solution
Let the excluded interior point be O. Let the vertices be A, B, C. Take points D, E, F on BC, CA, AB. Now T is the disjoint union of T₁, T₂, T₃, where: T₁ is the quadrilateral OFAE and its interior, but excluding O, F and the segment OF; T₂ is the quadrilateral ODBF and its interior, but excluding O, D and the segment OD; and T₃ is the quadrilateral OECD and its interior, but excluding O, E and the segment OE. But it is now trivial to express T₁ as a disjoint union of closed intervals - just take each interval to have one endpoint on AF and the other on EO. Similarly for T₂ and T₃. [If you wish, you can make it even more trivial by choosing D, E, F so that OD is parallel to AB, OE to BC and OF to AC.]

15th Balkan 1998 Problem 4

Prove that there are no integers m, n satisfying m² = n⁵ - 4.
Solution
m² = 0, 1, 3, 4, 5 or 9 mod 11, but n⁵ - 4 = 6, 7 or 8 mod 11.