12th Balkan Mathematical Olympiad Problems 1995
A1. Define an by a3 = (2 + 3)/(1 + 6), an = (an-1 + n)/(1 + n an-1). Find a1995.
A2. Two circles centers O and O' meet at A and B, so that OA is perpendicular to O'A. OO' meets the circles at C, E, D, F, so that the points C, O, E, D, O', F lie on the line in that order. BE meets the circle again at K and meets CA at M. BD meets the circle again at L and AF at N. Show that (KE/KM) (LN/LD) = (O'E/OD).
A3. m and n are positive integers with m > n and m + n even. Prove that the roots of x2 - (m2 - m + 1)(x - n2 - 1) - (n2 + 1)2 = 0 are positive integers, but not squares.
A4. Let S be an n x n array of lattice points. Let T be the set of all subsets of S of size 4 which form squares. Let A, B and C be the number of pairs {P, Q} of points of S which belong to respectively no, just two and just three elements of T. Show that A = B + 2C. [Note that there are plenty of squares tilted at an angle to the lattice and that the pair can be adjacent corners or opposite corners of the square.]
Solutions
12th Balkan 1995 Problem 1
Define an by a3 = (2 + 3)/(1 + 6), an = (an-1 + n)/(1 + n an-1). Find a1995.
Solution Answer: 1991009/1991011.
We calculate that the first few terms are 5/7, 11/9, 7/8, 11/10, 27/29, 37/35, 22/23, 28/27. The even terms are all just over 1 and the odd terms are all just under 1, so this suggests we look separately at the even and odd terms. The terms all seem to have numerator and denominator differing by 1 or 2. This suggests multiplying both by 2 where necessary so that the difference is always 2. Looking then at the even term denominators we get 9, 20, 35, 54. The differences are 11, 15, 19 which go up by 4 each time. The same is true for the odd term denominators, which are 7, 16, 29, 46, differences 9, 13, 17. Assuming this is indeed the pattern we get the formulae a2n = (2n2 + n + 1)/(2n2 + n - 1), a2n+1 = (2n2 + 3n)/(2n2 + 3n + 2).
We prove this by induction. It is true for n = 1. Suppose it is true for n. Then we have f(2n+2) = ( (2n2 + 3n) + (2n+2)(2n2 + 3n + 2) )/( (2n2 + 3n + 2) + (2n+2)(2n2 + 3n) ) = (4n3 + 12n2 + 13n + 4)/(4n3 + 12n2 + 9n + 2) = (2n2 + 5n + 4)(2n + 1)/( 2n2 + 5n + 2)(2n + 1) ) = (2(n+1)2 + (n+1) + 1)/(2(n+1)2 + (n+1) - 1). Similarly f(2n+3) = (2n2 + 5n + 4 + (2n + 3)(2n2 + 5n + 2) )/(2n2 + 5n + 2 + (2n+3)(2n2 + 5n + 4) ) = (2n2 + 7n + 5)/(2n2 + 7n + 7) = (2(n+1)2 + 3(n+1) )/(2(n+1)2 + 3(n+1) + 2). Hence the result is true for n+1. Applying it to 1995 = 2.997+1 we get the answer.
12th Balkan 1995 Problem 2
Two circles centers O and O' meet at A and B, so that OA is perpendicular to O'A. OO' meets the circles at C, E, D, F, so that the points C, O, E, D, O', F lie on the line in that order. BE meets the circle again at K and meets CA at M. BD meets the circle again at L and AF at N. Show that (KE/KM) (LN/LD) = (O'E/OD).
Solution
We have angle AOO' = 2 angle ACF, angle AO'O = 2 angle AFC. But angle AOO' + angle AO'O = 180o - angle OAO' = 90o, so angle ACF + angle AFC = 45o.
Angle CAL = angle CAO + angle OAO' + angle O'AL = angle ACF (OAC isosceles) + 90o + (90o - 1/2 angle AO'L) = angle ACF + 180o - angle ABL = angle ACF + 180o - angle ABD (same angle) = 180o (ACBD cyclic). So CAL is a straight line. Similarly, KAF is a straight line.
Applying Menelaus to the triangle CME and line KAF, we get (KE/KM) (AM/AC) (FC/FE) = 1. Applying Menelaus to the triangle FND and line LAC, we get (LD/LN) (AN/AF) (CF/CD) = 1. Hence (KE/KM) (LN/LD) = (AC/AM) (FE/FC) (AN/AF) (CF/CD) = (AC/AM) (AN/AF) (FE/CD) = (AC/AM) (AN/AF) (O'E/OD). So it suffices to show that AC/AM = AF/AN, or equivalently, that MN is parallel to CF.
Angle MAN = angle CAF = 180o - (angle ACF + angle AFC) = 135o. Angle MBN = angle EBA + angle ABD = angle EFA (AFBE cyclic) + angle ACD (ACBD cyclic) = 45o. So AMBN is cyclic, so angle AMN = angle ABN = angle ABD (same angle) = angle ACD (ACBD cyclic) = angle ACF (same angle). Hence MN parallel to CF as required.
12th Balkan 1995 Problem 3
m and n are positive integers with m > n and m + n even. Prove that the roots of x2 - (m2 - m + 1)(x - n2 - 1) - (n2 + 1)2 = 0 are positive integers, but not squares.
Solution
Put M = m2 - m + 1, N = n2 + 1. Then the equation is x2 - Mx + MN - N2 = (x - N)(x - M + N). So the roots are N and M - N. N is obviously a positive integer and since N2 < N2 + 1 < (N + 1)2 it cannot be a square.
M - N is obviously an integer. We have m > n, so m ≥ n+1, so M > (m-1)2 +1 ≥ n2 + 1 = N. So M - N is positive. It remains to show that M - N = m2 - m - n2 cannot be a square.
We claim that if m(m-1) = n2 + k2, then m and n have opposite parity. Since we are given that m + n is even, that is sufficient to prove that M - N cannot be a square.
Note first that a square = 0 or 1 mod 4. We consider four cases. If m = 1 mod 4, then m(m-1) = 0 mod 4, so n and k must both be even (if they were odd, the sum of their squares would be 2 mod 4), so m and n have opposite parity. If m = 2 mod 4, then n and k must both be odd, so again m and n have opposite parity.
If m = 3 mod 4, then there must be some prime p which is 3 mod 4 and divides m to an odd power. Since m and m-1 are relatively prime, it must also divide m(m-1) to an odd power. Similarly, if m = 0 mod 4, then m-1 = 3 mod 4 and so again we can find a prime p = 3 mod 4 which divides m(m-1) to an odd power. So we have n2 + k2 = 0 mod p. Hence n2 = - k2 mod p. Taking both sides the power (p-1)/2, which is odd, we get np-1 = - kp-1 mod p. But it is well-known that if p does not divide h then hp-1 = 1 mod p (this is Fermat's little theorem - see below for a proof). So p must divide both n and k. Thus p2 must divide m(m-1). We now divide through m(m-1) = n2 + k2 by p2 and repeat the argument. By a simple induction we find that p must divide m(m-1) to an even power. Contradiction. So there are no solutions with m = 3 or 0 mod 4.
Comment. This seems too advanced for an olympiad problem, so maybe there is an easier solution. To prove Fermat's theorem note that if p does not divide h, then h, 2h, 3h, ... , ph must be a complete set of residues mod p (in other words they all have different remainders on division by p). Obviously ph = 0 mod p, so the others must be a permutation of 1, 2, ... , p-1. Hence h.2h.3h. ... (p-1)h = 1.2. ... . (p-1) mod p. We can divide through by (p-1)! to conclude that hp-1 = 1 mod p.
12th Balkan 1995 Problem 4
Let S be an n x n array of lattice points. Let T be the set of all subsets of S of size 4 which form squares. Let A, B and C be the number of pairs {P, Q} of points of S which belong to respectively no, just two and just three elements of T. Show that A = B + 2C. [Note that there are plenty of squares tilted at an angle to the lattice and that the pair can be adjacent corners or opposite corners of the square.]
Solution
Let D be the number of pairs in just one element of T. Note that a pair cannot be in more than three elements of T. But three can be achieved, for example:
x o xThere are n2 points, so n2(n2 - 1)/2 = (n - 1)n2(n + 1)/2 pairs of points. This must equal A + B + C + D. Each square has 6 pairs of vertices, so D + 2B + 3C must equal 6 times the total number of squares. Now notice that (A + B + C + D) - (D + 2B + 3C) = A - B - 2C. So we have to show that the total number of squares is (n - 1)n2(n + 1)/12.
x x
x o x
Introduce a coordinate system labeling the points (x, y) with x and y running from 1 to n. Consider a square with two adjacent vertices (a, 1) and (1, b). The other vertices are (a+b, a) and (b, a+b), so 2 ≤ a+b ≤ n. Obviously, any square can be translated to such a square and such a square has (n+2 - (a+b) )2 translates. Hence the total number of squares is ∑a=1n-1 ∑b=2n+1-a (n+2 - (a+b) )2. Put k = a+b. Then there are k-2 points in the range of summation with a+b = k. So we may change to summing over k and get: ∑k=3n+1 (n+2-k)2(k-2). Putting h = k-2, this becomes simply: ∑h=1n-1 (n-h)2h = n2 ∑ h - 2n ∑ h2 + ∑ h3 = n2 (n-1)n/2 - 2n(n-1)n(2n-1)/6 + (n-1)2n2/4 = (n-1)2n2(n+1)/12 as required.
Labels:
Balkan Mathematical Olympiad
Previous Article
