7th Balkan Mathematical Olympiad Problems 1990

7th Balkan Mathematical Olympiad Problems 1990

A1.  The sequence u_n is defined by u₁ = 1, u₂ = 3, u_n = (n+1) u_n-1 - n u_n-2. Which members of the sequence which are divisible by 11?

A2.  Expand (x + 2x² + 3x³ + ... + nxⁿ)² and add the coefficients of xⁿ⁺¹ through x²ⁿ. Show that the result is n(n+1)(5n² + 5n + 2)/24.

A3.  The feet of the altitudes of the triangle ABC are D, E, F. The incircle of DEF meets its sides at G, H, I. Prove that ABC and GHI have the same Euler line (the line through the circumcenter and the centroid).

A4.  The function f is defined on the positive integers and f(m) ≠ f(n) if m - n is prime. What is the smallest possible size of the image of f.

Solutions

7th Balkan 1990 Problem 1

The sequence u_n is defined by u₁ = 1, u₂ = 3, u_n = (n+1) u_n-1 - n u_n-2. Which members of the sequence which are divisible by 11?

Solution: Answer: all n except 1, 2, 3, 5, 6, 7, 9.

We calculate the residues mod 11 to be: u₁ = 1, u₂ = 3, u₃ = -2, u₄ = 0, u₅ = -1, u₆ = 4, u₇ = 6, u₈ = 0, u₉ = 1, u₁₀ = 0, u₁₁ = 0. But now u_n = 0 mod 11 for all n ≥ 11. So u_n is divisible by 11 for n = 4, 8 and n ≥ 10.

7th Balkan 1990 Problem 2

Expand (x + 2x² + 3x³ + ... + nxⁿ)² and add the coefficients of xⁿ⁺¹ through x²ⁿ. Show that the result is n(n+1)(5n² + 5n + 2)/24.

Solution: Let the coefficient of x^m be a_m. Multiplying out, we find:

an+1 = 1.n  + 2(n-1)  +  3(n-2)  + ...  + (n-2)3  + (n-1)2 +  n.1
an+2 = 2.n  + 3(n-1)  +  4(n-2)  + ... +  (n-1)3  +  n.2
an+3 = 3.n  + 4(n-1)  +  5(n-2)  + ... +  n.3
...
a2n-1 =(n-1)n +n(n-1)
a2n = n.n

Adding the columns, we get (1+ ... + n)n + (2+...+n)(n-1) + (3+...+n)(n-2) + ... + (n-1+n)2 + n.1. Doubling, we get (n+1)n² + (n+2)(n-1)² + (n+3)(n-2)² + ... + (2n-1)2² + 2n·1² = n(1² + ... + n²) + (1·n² + 2(n-1)² + 3(n-2)² + ... + n.1²).

It is well-known that 1² + ... + n² = n(n+1)(2n+1)/6. We claim that 1.n² + 2(n-1)² + ... + n.1² = n(n+1)²(n+2)/12. The result then follows immediately, since ( n²(n+1)(2n+1)/6 + n(n+1)²(n+2)/12 )/2 = n(n+1) ( 2n(2n+1) + (n+1)(n+2) )/24 = n(n+1)(5n²+5n+2)/24.

It is also well-known that 1³ + 2³ + ... + n³ = n²(n+1)²/4. [If you forget the sums of the powers it is easiest to start with ∑ r(r+1)(r+2) ... (r+m) = n(n+1)...(n+m+1)/(m+2) which is easy to remember and trivial to prove (by induction).]. Adding n·n² + (n-1)·(n-1)² + ... + 1·1² to 1·n² + 2(n-1)² + ... + n·1² we get (n+1)(n² + (n-1)² + ... + 1²) = n(n+1)²(2n+1)/6. Hence 1.n² + 2(n-1)² + ... + n.1² = n(n+1)²(2n+1)/6 - n²(n+1)²/4 = 1/12 n(n+1)²(4n+2 - 3n) = n(n+1)²(n+2)/12, as claimed.

7th Balkan 1990 Problem 3

The feet of the altitudes of the triangle ABC are D, E, F. The incircle of DEF meets its sides at G, H, I. Prove that ABC and GHI have the same Euler line (the line through the circumcenter and the centroid).

Solution

Let O be the intersection of the altitudes of ABC. ∠OEC = ∠ODC = 90^o, so OECD is cyclic, so ∠ODE = ∠OCE. ∠ADC = ∠AFC = 90^o, so AFDC is cyclic, so ∠OCE = ∠FCA = ∠FDA. So AD bisects ∠EDF. Hence O is the incenter of DEF. So it is the circumcenter of GHI.

Let H lie on DE and I on DF. Then DH and DI are tangents to the circle center O through H and I, so HI is perpendicular to DO. But so is BC, so HI is parallel to BC. Similarly GH is parallel to AB and IG to CA. So the Euler lines of GHI and ABC are parallel. But they both pass through O (which is the circumcenter of GHI and the orthocenter of ABC). Hence they coincide. 

7th Balkan 1990 Problem 4

The function f is defined on the positive integers and f(m) ≠ f(n) if m - n is prime. What is the smallest possible size of the image of f.

Solution Answer: 4.

f(1), f(3), f(6), f(8) must all be different. So the image must contain at least 4 elements. But the example f(n) = residue of n mod 4 shows that 4 is sufficient.