10th Balkan Mathematical Olympiad Problems 1993

10th Balkan Mathematical Olympiad Problems 1993

A1.  Given reals a₁ ≤ a₂ ≤ a₃ ≤ a₄ ≤ a₅ ≤ a₆ satisfying a₁ + a₂ + a₃ + a₄ + a₅ + a₆ = 10 and (a₁ - 1)² + (a₂ - 1)² + (a₃ - 1)² + (a₄ - 1)² + (a₅ - 1)² + (a₆ - 1)² = 6, what is the largest possible a₆?

A2.  How many non-negative integers with not more than 1993 decimal digits have non-decreasing digits? [For example, 55677 is acceptable, 54 is not.]

A3.  Two circles centers A and B lie outside each other and touch at X. A third circle center C encloses both and touches them at Y and Z respectively. The tangent to the first two circles at X forms a chord of the third circle with midpoint M. Prove that ∠YMZ = ∠ACB.

A4.  p is prime and k is a positive integer > 1. Show that we can find positive integers (m, n) ≠ (1, 1) such that (m^p + n^p)/2 = ( (m + n)/2 )^k iff k = p. 

Solutions

10th Balkan 1993 Problem 1

Given reals a₁ ≤ a₂ ≤ a₃ ≤ a₄ ≤ a₅ ≤ a₆ satisfying a₁ + a₂ + a₃ + a₄ + a₅ + a₆ = 10 and (a₁ - 1)² + (a₂ - 1)² + (a₃ - 1)² + (a₄ - 1)² + (a₅ - 1)² + (a₆ - 1)² = 6, what is the largest possible a₆?

Solution Answer: a₆ = 3 1/3.

Adding twice the first equation to the second gives a₁² + a₂² + ... + a₆² = 20. Hence (a₁ - 4/3)² + (a₂ - 4/3)² + (a₃ - 4/3)² + (a₄ - 4/3)² + (a₅ - 4/3)² + (a₆ - 4/3)² = 20 - 10·8/3 + 6·16/9 = 4. So a₆ - 4/3 ≤ 2, or a₆ ≤ 3 1/3. It is easy to check that a₁ = a₂ = a₃ = a₄ = a₅ = 4/3, a₆ = 3 1/3 is indeed a solution.

10th Balkan 1993 Problem 2

How many non-negative integers with not more than 1993 decimal digits have non-decreasing digits? [For example, 55677 is acceptable, 54 is not.]

Solution Answer: 2002C9 = 1,398,276,498,745,133,921,413,500.

Let mCn represent the binomial coefficient m!/(n! (m-n)! ). We prove first a simple lemma: kCk + (k+1)Ck + (k+2)Ck + ... + nCk = (n+1)C(k+1). This is an almost trivial induction. It is obviously true for n = k. Suppose it is true for n. Then the sum up to (n+1)Ck = (n+1)C(k+1) + (n+1)Ck = (n+2)C(k+1) as required.

Call numbers with non-decreasing digits NDDs. 0 is a special case, it is the only NDD involving the digit zero. It is convenient to regard 0 as having 0 digits. With this convention, we show that in base n there are (n+m-2)Cm NDDs with m digits. We use induction on m. Clearly the result is true for m = 1 (and any n) provided we accept the convention just stated. Suppose it is true for m. Now consider an m+1 digit number.

If its first digit is 1, then the remaining digits form an m digit NDD, so there are just (n+m-2)Cm possibilities. If the first digit is 2, then the remaining m digits are all at least 2, so the number of possibilities is the same as for m digit NDDs to base m-1, which is (n+m-3)Cm. Similarly, for first digit 3 we have (n+m-4)Cm possibilities, and so on down to (n+m-n)Cm = 1 possibilities for first digit n. Hence the total number of possibilities is mCm + (m+1)Cm + (m+2)Cm + ... + (m+n-2)Cm = (m+n-1)C(m+1), by the lemma. So the result is true for m+1. Hence for all m.

In particular, there are (n+8)C8 n-digit decimal NDDs. Note that n=0 also gives the correct number 1 for 0-digit numbers. Hence there are 8C8 + 9C8 + ... + 2001C8 decimal numbers with at most 1993 digits and all digits non-decreasing. Applying the lemma again, this sum is 2002C9. 

10th Balkan 1993 Problem 3

Two circles centers A and B lie outside each other and touch at X. A third circle center C encloses both and touches them at Y and Z respectively. The tangent to the first two circles at X forms a chord of the third circle with midpoint M. Prove that ∠YMZ = ∠ACB.

Solution

The circles center A and C touch at Y, so CAY is a straight line. Similarly, CBZ is a straight line. So ∠ACB = ∠YCZ. So we have to show that C, M, Y and Z lie on a circle.

Suppose that the tangents to the large circle at Y and Z meet at K. Suppose the line KX meets the circle center A again at X' and the circle center B again at X". Then X' and X" must be on opposite sides of X. But KY² = KX.KX', since KY is also a tangent to the circle center A, and KZ² = KX·KX", since KZ is also a tangent to the circle center B. So KX' = KX". Hence X' = X = X", so K also lies on the tangent to the two small circles at X.

But now we can see that Y, Z and M all lie on the circle diameter CK (because ∠CYK = ∠CZK = ∠CMK = 90^o - the last because M is the midpoint of the chord MK of the large circle).

10th Balkan 1993 Problem 4

p is prime and k is a positive integer > 1. Show that we can find positive integers (m, n) ≠ (1, 1) such that (m^p + n^p)/2 = ( (m + n)/2 )^k iff k = p.

Solution

x = 2, y = 2 is a solution if k = p. Let z = (x+y)/2. If x+y is odd, then 2z^m is not integral. Contradiction. Hence x+y is even. x=y=1 is not allowed, so z is at least 2. Hence (x^p+y^p)/2 < (x+y)^p/2 ≤ (2z)^p/2 < z^2p, so m < 2p. But (x^p + y^p)/2 ≥ z^p, so m ≥ p.

Put x = z+k, y = z-k. If k = 0, then lhs = z^p, rhs = z^m, so m = p and then any z is a solution. If k is non-zero, then ((z+k)^p+(z-k)^p)/2= z^p + pC2 z^p-2k² + ... + pCp-1 z k^p-1 = z^m. So p divides z^m - z^p