16th Balkan Mathematical Olympiad Problems 1999

16th Balkan Mathematical Olympiad Problems 1999

A1.  O is the circumcenter of the triangle ABC. XY is the diameter of the circumcircle perpendicular to BC. It meets BC at M. X is closer to M than Y. Z is the point on MY such that MZ = MX. W is the midpoint of AZ. Show that W lies on the circle through the midpoints of the sides of ABC. Show that MW is perpendicular to AY.

A2.  p is an odd prime congruent to 2 mod 3. Prove that at most p-1 members of the set {m² - n³ - 1: 0 < m, n < p} are divisible by p.

A3.  ABC is an acute-angled triangle area 1. Show that the triangle whose vertices are the feet of the perpendiculars from the centroid to AB, BC, CA has area between 4/27 and 1/4.

A4.  0 = a₁, a₂, a₃, ... is a non-decreasing, unbounded sequence of non-negative integers. Let the number of members of the sequence not exceeding n be b_n. Prove that (x₀ + x₁ + ... + x_m)(y₀ + y₁ + ... + y_n) ≥ (m + 1)(n + 1). 

Solutions

16th Balkan 1999 Problem 1

O is the circumcenter of the triangle ABC. XY is the diameter of the circumcircle perpendicular to BC. It meets BC at M. X is closer to M than Y. Z is the point on MY such that MZ = MX. W is the midpoint of AZ. Show that W lies on the circle through the midpoints of the sides of ABC. Show that MW is perpendicular to AY.

Solution

XW and AM are medians of AZX, so they meet at the centroid G of AZX and AG = 2/3 AM. But AM is also a median of ABC, so G is also the centroid of ABC. Now consider the similarity, center G, which takes X to W. It takes A, B, C to the midpoints of the opposite sides and hence the circumcircle of ABC to the circle through the midpoints. But X lies on the circumcircle of ABC, so W lies on the circle through the midpoints.

The similarity takes MW to AX, but the similarity takes lines to lines which are parallel. AX is perpendicular to AY (because XY is a diameter of the circumcircle through AXY). Hence MW is also perpendicular to AY. 

16th Balkan 1999 Problem 2

p is an odd prime congruent to 2 mod 3. Prove that at most p-1 members of the set {m² - n³ - 1: 0 < m, n < p} are divisible by p.

Solution

We show that p has p distinct cubic residues if it is an odd prime congruent to 2 mod 3. Let k be a primitive root of p. So any non-zero residue of p can be written as kⁿ for some n in the range 1, 2, ... , p-1, and kⁿ = k^m mod p iff p-1 divides m-n. Now we claim that, for distinct m, n in the range 1, 2, ... , p-1, we have k³ⁿ and k^3m distinct mod p. For if they are equal then p-1 divides 3(m-n). But p-1 is not a multiple of 3, so p-1 must divide m-n. But m-n is in the range 1, ... , p-2 so it cannot be divisible by p-1.

So the values -1³, -2³, ... , -(p-1)³ are all incongruent mod p. Thus for each m, the p-1 values m² - 1³ - 1, m² - 2³ - 1, ... , m² - (p-1)³ - 1 are all incongruent mod p. Hence at most one of them is divisible by p. So the set {m² - n³ - 1: 0 < m, n < p} has at most one member divisible by p for each m and hence at most p-1 in all. 

16th Balkan 1999 Problem 3

ABC is an acute-angled triangle area 1. Show that the triangle whose vertices are the feet of the perpendiculars from the centroid to AB, BC, CA has area between 4/27 and 1/4.

Solution

Let the centroid be G and the feet of the perpendiculars to BC, CA, AB be D, E, F respectively. Since G is 1/3 of the way along the median from the midpoint, area BGC = 1/3 area ABC = 1/3. But area BGC = a.GD/2, hence GD = 2/(3a). Similarly, GE = 2/(3b) and GF = 2/(3c). Now area GEF = (GE.GF.sin EFG)/2 = (2 sin A)/(9bc). But area ABC = (bc sin A)/2, so bc = 2/sin A. So area GEF = (sin²A)/9. Hence Area DEF = (sin²A + sin²B + sin²C)/9. So we need to show that 4/3 ≤ (sin²A + sin²B + sin²C) ≤ 9/4.

Take A ≤ B ≤ C. We have C ≤ π/2, so A + B ≥ π/2, so B ≥ π/4. Now sin²x has decreasing derivative between π/4 and π/2, so sin²B + sin²C ≤ 2 sin²((B+C)/2) = 2 cos²A/2 = cos A + 1. Hence (sin²A + sin²B + sin²C) ≤ sin²A + cos A + 1 = 2 - cos²A + cos A = 9/4 - (cos A - 1/2)² ≤ 9/4. Note that we can only have equality at the last step if cos A = 1/2 or A = π/3, which implies the triangle is equilateral. It is easy to check that in this case (sin²A + sin²B + sin²C) = 9/4.

In the other direction we have in fact that sin²A + sin²B + sin²C >= 2, which is significantly stronger than what we need. This is slightly awkward to prove. Take C = π/2 - 2y, B = π/4 + y + x, A = π/4 + y - x. So we are assuming that x, y >= 0, and x + 3y ≤ π/4. Now sin²A + sin²B + sin²C = (1/√2 cos(x - y) - 1/√2 sin(x - y) )² + (1/√2 cos(x + y) + 1/√2 sin(x + y) )² + cos²2y = 1 - cos(x - y)sin(x - y) + cos(x + y)sin(x + y) + cos²2y = 1 + cos²2y - 1/2 sin2(x - y) + 1/2 sin2(x + y) = 1 + cos²2y + cos 2x sin 2y = 2 + sin 2y (cos 2x - sin 2y). But sin 2y ≥ 0 and sin 2y < sin 6y ≤ sin(π/2 - 2x) = cos 2x. Hence sin 2y (cos 2x - sin 2y) ≥ 0 (with equality iff y = 0, so that the triangle is right-angled).

Comment. It is curious that the question made the inequality weaker than necessary. It should have been "between 2/9 and 1/4".

16th Balkan 1999 Problem 4

0 = a₁, a₂, a₃, ... is a non-decreasing, unbounded sequence of non-negative integers. Let the number of members of the sequence not exceeding n be b_n. Prove that (x₀ + x₁ + ... + x_m)(y₀ + y₁ + ... + y_n) ≥ (m + 1)(n + 1).

Solution

If x_m = 0, then y₀ ≥ m+1 and so all of y₀, y₁, ... , y_n ≥ m+1, so the inequality holds. If x_m > 0, then let x_k be the first non-zero term and suppose x_k = h > 0. Reduce x_k to 0. Then ∑x_i is reduced by h. Each of y₀, y₁, ... , y_h-1 is increased by 1 and the other y_j are unchanged, so ∑y_j is increased by at most h. Hence ∑x_i + ∑y_j is not increased. Repeat until we reach x_m = 0. Then the resulting inequality is true. We have not increased the lhs and the rhs is unchanged, so the orignal inequality was true.

[more...]

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.

[more...]

14th Balkan Mathematical Olympiad Problems 1997

14th Balkan Mathematical Olympiad Problems 1997

A1.  ABCD is a convex quadrilateral. X is a point inside it. XA² + XB² + XC² + XD² is twice the area of the quadrilateral. Show that it is a square and that X is its center.

A2.  A collection of m subsets of X = {1, 2, ... , n} has the property that given any two elements of X we can find a subset in the collection which contains just one of the two. Prove that n ≤ 2^m.

A3.  Two circles C and C' lying outside each other touch at T. They lie inside a third circle and touch it at X and X' respectively. Their common tangent at T intersects the third circle at S. SX meets C again at P and XX' meets C again at Q. SX' meets C' again at U and XX' meets C' again at V. Prove that the lines ST, PQ and UV are concurrent.

A4.  Find all real-valued functions on the reals which satisfy f( xf(x) + f(y) ) = f(x)² + y for all x, y. 

Solutions

14th Balkan 1997 Problem 1

ABCD is a convex quadrilateral. X is a point inside it. XA² + XB² + XC² + XD² is twice the area of the quadrilateral. Show that it is a square and that X is its center.

Solution

XA² + XB² ≥ 2·XA·XB with equality iff XA = XB. But XA·XB ≥ 2 area XAB with equality iff ∠AXB = 90^o. Hence (XA² + XB²) + (XB² + XC²) + (XC² + XD²) + (XD² + XA²) ≥ 4 (area XAB + area XBC + area XCD + area XDA) with equality iff ∠AXB = ∠BXC = ∠CXD = ∠DXA = 90^o and XA = XB = XC = XD. But we are given that equality holds. Hence AXC and BXD are straight line segments with X as their midpoint. Hence ABCD is a square center X.

14th Balkan 1997 Problem 2

A collection of m subsets of X = {1, 2, ... , n} has the property that given any two elements of X we can find a subset in the collection which contains just one of the two. Prove that n ≤ 2^m.

Solution

Let the subsets be Y₁, ... , Y_m. Define f: X → {0, 1, 2, ... , 2^m-1} by f(x) = the binary number a₁a₂ ... a_m where the binary digit a_i is 1 iff x belongs to Y_i. Then we claim that if x ≠ y we must have f(x) ≠ f(y). For if f(x) = f(y) then we could not find A_i such that just one of x, y was in A_i (since their binary expansions would agree in the ith digit). So f is injective. But its range has 2^m elements, so its domain cannot have more than 2^m elements. In other words n ≤ 2^m.

14th Balkan 1997 Problem 3

Two circles C and C' lying outside each other touch at T. They lie inside a third circle and touch it at X and X' respectively. Their common tangent at T intersects the third circle at S. SX meets C again at P and XX' meets C again at Q. SX' meets C' again at U and XX' meets C' again at V. Prove that the lines ST, PQ and UV are concurrent.

Solution

The similarity center X takes P to S and Q to X', so PQ is parallel to SX'. Similarly, UV is parallel to SX. Extend PQ and UV to meet at K. Then SUKP is a parallelogram so KU = SP and KP = SU. Also KQV and SX'X are similar triangles. So KQ/KV = SX'/SX.

Since ST is tangent to C and C', we have SP.SX = ST² = SU. SX'. Hence SX'/SX = SP/SU. Hence KQ/KV = SP/SU = KU/KP, so KP.KQ = KU.KV.

If K does not lie on ST, then ST must cut one of the segments KP and KU. Suppose it is KU. So let ST meet KU at A. Extend PK to meet ST at B. Then KQ.KP < BQ.BP = BT² < AT² = AT.AU < KV.KU. Contradiction. Similarly, we get a contradiction if ST cuts KP. Hence K must lie on ST. 

14th Balkan 1997 Problem 4

Find all real-valued functions on the reals which satisfy f( xf(x) + f(y) ) = f(x)² + y for all x, y.

Solution Answer: (1) f(x) = x for all x; (2) f(x) = -x for all x.

Put x = 0, then f(f(y)) = f(0)² + y. Put y = -f(0)² and k = f(y). Then f(k) = 0. Now put x = y = k. Then f(0) = 0 + k, so k = f(0). Put y = k, x = 0, then f(0) = f(0)² + k, so k = 0. Hence f(0) = 0.

Put x = 0, f(f(y)) = y (*). Put y = 0, f(xf(x)) = f(x)² (**). Put x = f(z) in (**), then using f(z) = x, we have f(zf(z)) = z². Hence z² = f(z)² for all z (***). In particular, f(1) = 1 or -1. Suppose f(1) = 1. Then putting x = 1 in the original relation we get f(1 + f(y) ) = 1 + y. Hence (1 + f(y) )² = (1 + y)². Hence f(y) = y for all y.

Similarly if f(1) = -1, then putting x = 1 in the original relation we get f(-1 + f(y) ) = 1 + y. Hence (-1 + f(y) )² = (1 + y)², so f(y) = -y for all y.

Finally, it is easy to check that f(x) = x does indeed satisfy the original relation, as does f(x) = -x.

[more...]

13th Balkan Mathematical Olympiad Problems 1996

13th Balkan Mathematical Olympiad Problems 1996

A1.  Let d be the distance between the circumcenter and the centroid of a triangle. Let R be its circumradius and r the radius of its inscribed circle. Show that d² ≤ R(R - 2r).

A2.  p > 5 is prime. A = {p - n² where n² < p}. Show that we can find integers a and b in A such that a > 1 and a divides b.

A3.  In a convex pentagon consider the five lines joining a vertex to the midpoint of the opposite side. Show that if four of these lines pass through a point, then so does the fifth.

A4.  Can we find a subset X of {1, 2, 3, ... , 2¹⁹⁹⁶-1} with at most 2012 elements such that 1 and 2¹⁹⁹⁶-1 belong to X and every element of X except 1 is the sum of two distinct elements of X or twice an element of X? 

Solutions

13th Balkan 1996 Problem 1

Let d be the distance between the circumcenter and the centroid of a triangle. Let R be its circumradius and r the radius of its inscribed circle. Show that d² ≤ R(R - 2r).

Solution

Use vectors. Take the origin as the circumcenter O. Let A be the vector OA, B be the vector OB and C be the vector OC. Then the vector OG = (A + B + C)/3. Hence 9 OG² = A² + B² + C² + 2(A.B + B.C + C.A). Now A² = B² = C² = R². We have A.B = 2R² cos 2C = 2R² - AB² = 2R² - c² (with the usual notation AB = c, BC = a, CA = b). Hence 9 OG² = 9 R² - (a² + b² + c²). By the arithmetic geometric mean inequality we have (a² + b² + c²) ≥ 3 (abc)^2/3. Hence R² - OG² ≥ (abc)^2/3/3.

Now the area of ABC = area IAB + area IBC + area ICA = rc/2 + ra/2 + rb/2, where I is the incenter. It is also 1/2 ab sin C. But considering the triangle ABO, we have c = 2R sin C and hence 2 area ABC = r(a + b + c) = abc/(2R). So 2rR = abc/(a + b + c) ≤ 1/3 (abc)^2/3. Hence R² - OG² ≥ 2rR.

13th Balkan 1996 Problem 2

5 is prime. A = {p - n² where n² < p}. Show that we can find integers a and b in A such that a > 1 and a divides b.

Solution

Take m² to be the largest square less than p. Let p - m² = k. Then p - (m - k)² = (m² + k) - (m² - 2km + k²) = k(2m - k + 1). So p - m² divides p - |m - k|² (*).

Note that we cannot have k = m because then m would divide p. We cannot have (m - k) = m because then p = m². We cannot have (k - m) = m, because then p = m² + 2m = m(m+2). So (*) provides suitable a and b unless k = 1.

If k = 1, them m must be even (otherwise p = m² + 1 would be even), hence p - (m-1)² = 2m divides p - 1 = m². 

13th Balkan 1996 Problem 3

In a convex pentagon consider the five lines joining a vertex to the midpoint of the opposite side. Show that if four of these lines pass through a point, then so does the fifth.

Solution

Let the pentagon be ABCDE. Use vectors. Take the origin O to be the point at which the lines from each of A, B, C D to the midpoint of the opposite side meet. Take the vector OA to be a, OB to be b etc. The side opposite A is CD. Its midpoint is (c + d)2. So we have a x (c + d) = 0 and hence a x c = d x a. Similarly, b x d = e x b, c x e = a x c, d x a = b x d. Hence e x b = b x d = d x a = a x c = c x e, which shows that the line from E also passes through the origin. 

13th Balkan 1996 Problem 4

Can we find a subset X of {1, 2, 3, ... , 2¹⁹⁹⁶-1} with at most 2012 elements such that 1 and 2¹⁹⁹⁶-1 belong to X and every element of X except 1 is the sum of two distinct elements of X or twice an element of X?

Solution Answer: yes.

In the sequence 2ⁿ - 1, 2ⁿ⁺¹ - 2, 2ⁿ⁺² - 2², ... , 2²ⁿ - 2ⁿ, 2²ⁿ - 1 each number is double its predecessor, except for the last number which is the sum of its predecessor and the first number. Thus by adding n elements we can extend a sequence from 2ⁿ - 1 to 2²ⁿ - 1 whilst preserving the property that each element (except the first) is the sum of two previous elements or is double a previous elements.

Thus starting with 1 = 2¹ - 1, we can construct a sequence of 1 + 2 + 3 + 5 + 9 + 17 + 33 + 65 + 129 = 264 terms which has the property and last term 2²⁵⁶ - 1. With 243 doublings, we can extend the sequence to last term 2⁴⁹⁹ - 2²⁴³. The sequence already includes the 6 terms 2²⁴³ - 2¹¹⁵ (115 doublings after 2¹²⁸ - 1), 2¹¹⁵ - 2⁵¹, 2⁵¹ - 2¹⁹, 2¹⁹ - 2³, 2³ - 2, and 1, so by successively adding these we reach the 264 + 243 + 6 = 513rd term 2⁴⁹⁹ - 1.

We can now extend this to 2⁹⁹⁸ - 1 with a further 500 terms, then to 2¹⁹⁹⁶ - 1 with a further 999 terms, giving 2012 in all.

[To be completely explicit the set is:
1, 2=1+1, 3=1+2, 6=3+3, 12= 6+6, 15=12+3, 30=15+15, 60=30+30, 120=60+60, 240=120+120
255=240+15, 2⁸⁺ⁿ-2ⁿ=(2^8+n-1-2^n-1)+(2^8+n-1-2^n-1), n = 1, 2, ... , 8
2¹⁶-1=(2¹⁶-2⁸)+(2⁸-1), 2¹⁶⁺ⁿ-2ⁿ=(2^16+n-1-2^n-1)+(2^16+n-1-2^n-1), n = 1, 2, ... , 16
2³²-1=(2³²-2¹⁶)+(2¹⁶-1), 2³²⁺ⁿ-2ⁿ=(2^32+n-1-2^n-1)+(2^32+n-1-2^n-1), n = 1, 2, ... , 32
2⁶⁴-1=(2⁶⁴-2³²)+(2³²-1), 2⁶⁴⁺ⁿ-2ⁿ=(2^64+n-1-2^n-1)+(2^64+n-1-2^n-1), n = 1, 2, ... , 64
2¹²⁸-1=(2¹²⁸-2⁶⁴)+(2⁶⁴-1), 2¹²⁸⁺ⁿ-2ⁿ=(2^128+n-1-2^n-1)+(2^128+n-1-2^n-1), n = 1, 2, ... , 128
2²⁵⁶-1=(2²⁵⁶-2¹²⁸)+(2¹²⁸-1), 2²⁵⁶⁺ⁿ-2ⁿ=(2^256+n-1-2^n-1)+(2^256+n-1-2^n-1), n = 1, 2, ... , 243
2⁴⁹⁹-2¹¹⁵=(2⁴⁹⁹-2²⁴³)+(2²⁴³-2¹¹⁵), 2⁴⁹⁹-2⁵¹)=(2⁴⁹⁹-2¹¹⁵)+(2¹¹⁵-2⁵¹), 2⁴⁹⁹-2¹⁹=(2⁴⁹⁹-2⁵¹)+(2⁵¹-2¹⁹), 2⁴⁹⁹-2³=(2⁴⁹⁹-2¹⁹)+(2¹⁹-2³), 2⁴⁹⁹-2=(2⁴⁹⁹-2³)+6, 2⁴⁹⁹-1=(2⁴⁹⁹-2)+1
2⁴⁹⁹⁺ⁿ-2ⁿ=(2^499+n-1-2^n-1)+(2^499+n-1-2^n-1), n = 1, ... , 499
2⁹⁹⁸-1=(2⁹⁹⁸-2⁴⁹⁹)+(2⁴⁹⁹-1), 2⁹⁹⁸⁺ⁿ-2ⁿ=(2^998+n-1-2^n-1)+(2^998+n-1-2^n-1), n = 1, 2, ... , 998
2¹⁹⁹⁶-1=(2¹⁹⁹⁶-2⁹⁹⁸)+(2⁹⁹⁸-1) ].

[more...]

12th Balkan Mathematical Olympiad Problems 1995

12th Balkan Mathematical Olympiad Problems 1995

A1.  Define a_n by a₃ = (2 + 3)/(1 + 6), a_n = (a_n-1 + n)/(1 + n a_n-1). Find a₁₉₉₅.

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 x² - (m² - m + 1)(x - n² - 1) - (n² + 1)² = 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 a_n by a₃ = (2 + 3)/(1 + 6), a_n = (a_n-1 + n)/(1 + n a_n-1). Find a₁₉₉₅.

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 a_2n = (2n² + n + 1)/(2n² + n - 1), a_2n+1 = (2n² + 3n)/(2n² + 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) = ( (2n² + 3n) + (2n+2)(2n² + 3n + 2) )/( (2n² + 3n + 2) + (2n+2)(2n² + 3n) ) = (4n³ + 12n² + 13n + 4)/(4n³ + 12n² + 9n + 2) = (2n² + 5n + 4)(2n + 1)/( 2n² + 5n + 2)(2n + 1) ) = (2(n+1)² + (n+1) + 1)/(2(n+1)² + (n+1) - 1). Similarly f(2n+3) = (2n² + 5n + 4 + (2n + 3)(2n² + 5n + 2) )/(2n² + 5n + 2 + (2n+3)(2n² + 5n + 4) ) = (2n² + 7n + 5)/(2n² + 7n + 7) = (2(n+1)² + 3(n+1) )/(2(n+1)² + 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 = 180^o - angle OAO' = 90^o, so angle ACF + angle AFC = 45^o.

Angle CAL = angle CAO + angle OAO' + angle O'AL = angle ACF (OAC isosceles) + 90^o + (90^o - 1/2 angle AO'L) = angle ACF + 180^o - angle ABL = angle ACF + 180^o - angle ABD (same angle) = 180^o (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 = 180^o - (angle ACF + angle AFC) = 135^o. Angle MBN = angle EBA + angle ABD = angle EFA (AFBE cyclic) + angle ACD (ACBD cyclic) = 45^o. 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 x² - (m² - m + 1)(x - n² - 1) - (n² + 1)² = 0 are positive integers, but not squares.

Solution

Put M = m² - m + 1, N = n² + 1. Then the equation is x² - Mx + MN - N² = (x - N)(x - M + N). So the roots are N and M - N. N is obviously a positive integer and since N² < N² + 1 < (N + 1)² it cannot be a square.

M - N is obviously an integer. We have m > n, so m ≥ n+1, so M > (m-1)² +1 ≥ n² + 1 = N. So M - N is positive. It remains to show that M - N = m² - m - n² cannot be a square.

We claim that if m(m-1) = n² + k², 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 n² + k² = 0 mod p. Hence n² = - k² mod p. Taking both sides the power (p-1)/2, which is odd, we get n^p-1 = - k^p-1 mod p. But it is well-known that if p does not divide h then h^p-1 = 1 mod p (this is Fermat's little theorem - see below for a proof). So p must divide both n and k. Thus p² must divide m(m-1). We now divide through m(m-1) = n² + k² by p² 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 h^p-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   x

  x   x

x   o   x

There are n² points, so n²(n² - 1)/2 = (n - 1)n²(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)n²(n + 1)/12.

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) )² translates. Hence the total number of squares is ∑_a=1^n-1 ∑_b=2^n+1-a (n+2 - (a+b) )². 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=3ⁿ⁺¹ (n+2-k)²(k-2). Putting h = k-2, this becomes simply: ∑_h=1^n-1 (n-h)²h = n² ∑ h - 2n ∑ h² + ∑ h^{3 = n2} (n-1)n/2 - 2n(n-1)n(2n-1)/6 + (n-1)²n²/4 = (n-1)²n²(n+1)/12 as required.

[more...]

11th Balkan Mathematical Olympiad Problems 1994

11th Balkan Mathematical Olympiad Problems 1994

A1.  Given a point P inside an acute angle XAY, show how to construct a line through P meeting the line AX at B and the line AY at C such that the area of the triangle ABC is AP².

A2.  Show that x⁴ - 1993 x³ + (1993 + n) x² - 11x + n = 0 has at most one integer root if n is an integer.
A3.  What is the maximum value f(n) of |s₁ - s₂| + |s₂ - s₃| + ... + |s_n-1 - s_n| over all permutations s₁, s₂, ... , s_n of 1, 2, ... , n?
A4.  Find the smallest n > 4 for which we can find a graph on n points with no triangles and such that for every two unjoined points we can find just two points joined to both of them.

Solutions

11th Balkan 1994 Problem 1

Given a point P inside an acute angle XAY, show how to construct a line through P meeting the line AX at B and the line AY at C such that the area of the triangle ABC is AP².

Solution

Take D on AX such that PD is parallel to AY. Let AP = p, AD = d, DB = x and let the perpendicular distance from P to AX be h. The triangles ABC and DBP are similar, so (x + d)²/x² = area ABC/area DBP = p²/xh. Hence x² - 2bx + d² = 0 where b = p²/h - d.

To find b, we can take a line parallel to AX and a distance p from it (on the same side as P). Suppose it meets the line AP at Z. Then AP/h = AZ/p, so AZ = p²/h. Then if the circle center A radius AD meets AZ at W, we have WZ = b.

Now take a circle radius b and take a point T on the circle a distance d from the diameter UV. Let the foot of the perpendicular from T to UV be S. Then SU and SV are the two possible values of x.

11th Balkan 1994 Problem 2

Show that x⁴ - 1993 x³ + (1993 + n) x² - 11x + n = 0 has at most one integer root if n is an integer.

Solution

If it has two integer roots, then a quadratic (x² - ax + b), with a and b integral, is a factor of x⁴ - 1993 x³ + (1993 + n) x² - 11x + n. Suppose the other factor is (x² - cx + d). So (x² - ax + b)(x² - cx + d) = x⁴ - 1993 x³ + (1993 + n) x² - 11x + n.

Comparing coefficients: (1) a + c = 1993; (2) ac + b + d = 1993 + n; (3) bc + ad = 11; (4) bd = n. Note first that (1) implies c is integral, and then (2) implies d is integral. Subtracting (1) and (4) from (2) gives ac - a - c = bd - b - d. It is convenient to put A = a - 1, B = b - 1, C = c - 1, D = d - 1. Then we get A + C = 1991, AC = BD and (B + 1)(C + 1) + (A + 1)(D + 1) = 11. Expanding the last equation and multiplying it through by B, we get: B²(C + 1) + BC + B + ABD + BD + AB + B = 11B. Substituing AC for BD, we get B²(C + 1) + B(A + C - 9) + A²C + AC, or B²(C + 1) + 2.991B + A(A+1)C = 0. This quadratic for B must have real roots, so we require A(A+1)C(C+1) <= 991². But A + C = 1991 and A and C are integral, so AC > 991 unless A or C = 0. Similarly, (A + 1)(C + 1) > 991 unless A or C = -1.

So (A, C) = (0, 1991), (-1, 1992), (1991, 0), or (1992, -1). But (B + 1(C + 1) + (A + 1)(D + 1) = 11, so we cannot have (A, C) = (-1, 1992) or (1992, -1) which imply 1993 divides 11. Hence AC = 0 and so BD = n = 0. Hence, (A, B, C, D) = (0, 0, 1991, -1982) or (1991, -1982, 0, 0). Thus the two integer roots are roots of x² - x + 1 = 0 or of x² - 1991x - 1982 = 0. But neither equation has integer roots.

An alternative solution by Nizameddin Ordulu and Ali Adalý is as follows:

-n = (x⁴ - 1993x³ + 1993x² - 11x)/(x² + 1) = (x² - 1993x + 1992) + (1982x - 1992)/(x² + 1). So if x is an integer, then x² + 1 must divide (1982x - 1992) = 2(991x - 996) and hence also 2(991x - 996)(991x + 996) = 2.991²(x² + 1) - 2(991² + 996²). So x² + 1 divides 2(991² + 996²).

If you have access to Maple or Mathematica or something similar, then it is easy. You just note that 991² + 996² = 593.3329, where 593 and 3329 are primes. So there are x² + 1 = 1, 2, 593, 2.593, 3329, 2.3329, 593.3329 or 2.593.3329. Hence x² = 0, 1, 592, 2.593 - 1, 3328, 2.3329 - 1, 593.3329 - 1 or 2.593.3329 - 1. Again with the help of Maple, 592 = 2⁴37, 2.593 - 1 = 3.5.79, 3328 = 2⁸13, 2.3329 - 1 = 3.7.317, 593.3329 - 1 = 2⁴3²13709, 2.593.3329 - 1 = 107.36899, none of which are squares. So the only possibilities are x = 0, ±1.

If x = 0, then n = 0. If x = 1, then n = 5, if x = -1, then n = -1999. So there is one integral root for n = 0, 5, -1999 and none for other values of n.

However, it is not really practical to carry out the factorisations by hand in a reasonable time. The major obstacle is getting 991² + 996² = 593.3329. Not many people are familiar with all 108 primes up to 593. Even if they are, testing for division by all of them is time-consuming. Checking that 2, 593, 2.593 etc are not squares is much easier.

11th Balkan 1994 Problem 3

What is the maximum value f(n) of |s₁ - s₂| + |s₂ - s₃| + ... + |s_n-1 - s_n| over all permutations s₁, s₂, ... , s_n of 1, 2, ... , n?

Solution Answer: f(2m) = 2m² - 1, f(2m+1) = 2m² + 2m - 1.

In a maximal arrangement the terms must alternately increase and decrease. For suppose we have a < b < c or a > b > c, then |a - b| + |b - c| = |a - c|, so we can remove the middle term without affecting the sum. If we place it at one of the ends we must then increase the sum by at least 1. So suppose the peaks are p₁, p₂, ... and the troughs are t₁ + t₂ + ... . Then the sum is 2S p_i - 2S t_i + an end correction.

It is now convenient to look separately at n odd and n even. Suppose n = 2m. Then one of the ends must be a peak and the other a trough. Suppose p₁ and t₁ are at the ends. Then the end correction is -p₁ + t₁. So the maximum sum is achieved by taking the peaks to be {m+1, m+2, ... , 2m}, the troughs to be {1, 2, ... , m}, p₁ to be m+1 and t₁ to be m. The sum is then 2( (m+1) + (m+2) + ... + (m+m) ) - 2( 1 + 2 + ... + m) - 1 = 2m² - 1. This is obviously maximal and easily achieved: just select elements alternately from {m+1, m+2 , ... , 2m} and {1, 2, ... , m}, taking care that the end points are m and m+1.

For n odd = 2m+1, we either have m+1 peaks and m troughs or vice versa. In the first case we must take the peaks as {m+1, ... , 2m+1}, the troughs as {1, 2, ... , m} and the two endpoints as m+1 and m+2. The sum is then 2( (m+1) + (m+2) + ... + (m+m+1) ) - 2(1 + 2 + ... + m) - (m+1) - (m+2) = 2m² + 4m+2 - 2m - 3 = 2m² + 2m - 1. If we have m peaks and m+1 troughs, then the peaks must be {m+2, ... , 2m+1}, the troughs {1, 2, ... , m+1}, and the end points m and m+1. The sum is then 2( (m+2) + (m+3) + ... + (m+m+1) ) - 2(1 + 2 + ... + m+1} + m + m+1 = 2m² - 2 + 2m+1 = 2m² + 2m - 1, which is the same.

11th Balkan 1994 Problem 4

Find the smallest n > 4 for which we can find a graph on n points with no triangles and such that for every two unjoined points we can find just two points joined to both of them.

Solution Answer: n = 16.

Let X be one of the points. Suppose it has degree m, so that it is joined to A₁, A₂, ... , A_m. So no A_i, A_j can be joined (or we would have a triangle XA_iA_j). If m = 1, then there cannot be any other points, for suppose Y is another point. Then Y is not joined to X, so there must be two points joined to X and Y, but there is only one point joined to X. Contradiction. So this gives n = 2. So take m > 1. Now for each A_i, A_j, there must be a unique point B_ij joined to both A_i and A_j. B_ij cannot be joined to any other A_k, for then we would have three points joined to both X and B_ij. Finally, A_i cannot be joined to any points except X and the B_ij, for if it was joined to B, then B is not joined to any other A_j (otherwise it would be B_ij). So there is only one point, namely A_i joined to both X and B. Contradiction.

Now every point is either joined to X or joined to a point which is joined to X (for if X is not joined to Y, then there is a point Z joined to X and Y). So there are no points in the graph except X, the A_i and the B_ij. So n = 1 + m + m(m-1)/2. Also every A_i has degree m (it is joined to X and m-1 points B_ij). X was arbitrary, so we have proved that every two adjacent points have the same degree. Hence all the points have degree m.

If m = 2, then n = 4. But we are told n > 4. If m = 3, then n = 7. But B₁₂ cannot be joined to B₂₃ or B₁₃ (or we get a triangle), so it only has degree 2. Contradiction. So there is no graph for n = 7. If m = 4, then n = 11. But B₁₂ cannot be joined to B₂₃ or B₂₄ (or we get a triangle with A₂). It cannot be joined to B₁₄ or B₁₃ (or we get a triangle with A₁). So the only B_ij available to it is B₃₄ and so it has degree < 4. Contradiction. So m ≥ 5.

m = 5 gives n = 16. We verify that that works. Join B_hi to B_jk iff all of h, i, j, k are distinct. Clearly that does not create any triangles. Now consider all possible pairs of unjoined points. Case 1: X, B_ij. The only two points joined to both are A_i and A_j. Case 2: A_i, A_j. The only two points joined to both are X and B_ij. Case 3: A_i, B_jk (with all i, j, k distinct). Let u, v be the other two suffices. Then B_iu, B_iv are the only two points joined to A_i and B_jk. Case 4. B_ij and B_ik. Again let u, v be the other two suffices (apart from i, j, k). The only two points joined to B_ij and B_ik are A_i and B_uv.

[more...]

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

[more...]

9th Balkan Mathematical Olympiad Problems 1992

9th Balkan Mathematical Olympiad Problems 1992

A1.  Let a(n) = 3⁴ⁿ. For which n is (m^a(n)+6 - m^a(n)+4 - m⁵ + m³) always divisible by 1992?

A2.  Prove that (2n² + 3n + 1)ⁿ ≥ 6ⁿn! n! for all positive integers.

A3.  ABC is a triangle area 1. Take D on BC, E on CA, F on AB, so that AFDE is cyclic. Prove that: area DEF ≤ EF²/(4 AD²).

A4.  For each n > 2 find the smallest f(n) such that any subset of {1, 2, 3, ... , n} with f(n) elements must have three which are relatively prime (in pairs). 

Solutions

9th Balkan 1992 Problem 1

Let a(n) = 3⁴ⁿ. For which n is (m^a(n)+6 - m^a(n)+4 - m⁵ + m³ always divisible by 1992?

Solution Answer: n odd.

1992 = 24·83. Let f(m) = (m^a(n) - m^a(n)-2 - m⁵ + m³. Factorising, we have f(m) = m³(m² - 1)(m^a(n)+1 - 1). Now if m is even, then 8 divides m³. If m is odd, then m-1 and m+1 are consecutive even numbers, so one is divisible by 4 and hence 8 divides m² - 1. One of m-1, m, m+1 must be divisible by 3. Hence 24 always divides m³(m² - 1) and hence f(m). Now if m is not divisible by 83, then m⁸² = 1 mod 83, since 83 is prime. If n is odd and m is not divisible by 83, then a(n) + 1 = (82 - 1)ⁿ + 1, which is divisible by 82 and hence m^a(n)+1 - 1 is divisible by 83. But m³ is certainly divisible by 83 if m is, so we have established that 1992 always divides f(m) for n odd.

If n is even, then a(n) + 1 = (82 - 1)ⁿ + 1 = 2 mod 82. Hence m^a(n)+1 = m² mod 83. So, in particular, if we take m = 2, then m^a(n)+1 - 1 = 3 mod 83. But 2³(2² - 1) = 24, which is also not divisible by 83. So for even n, f(2) is not divisible by 1992. 

9th Balkan 1992 Problem 2

Prove that (2n² + 3n + 1)ⁿ ≥ 6ⁿn! n! for all positive integers.

Solution

(a - x)x = a²/4 - (x - a/2)², so (a - x)x ≤ a²/4. In particular, 6(n+1-m)m ≤ 6(n+1)²/4. Now n² ≥ 1, so 6n² + 12n + 6 ≤ 8n² + 12n + 4 or 6(n+1)²/4 ≤ 2n² + 3n + 1. Hence 6(n + 1 - m)m ≤ (2n² + 3n + 1). Multiplying together the inequalities for m = 1, ... , n we get 6ⁿ n! n! ≤ (2n² + 3n + 1)ⁿ.

Alternatively, with more insight, by Michael Lipnowski:

n(n+1)(2n+1)/6 = 1² + 2² + ... + n², so (2n² + 3n + 1)/6 = (1² + 2² + ... + n²)/n ≥ n!^2/n by AM/GM.

9th Balkan 1992 Problem 3

ABC is a triangle area 1. Take D on BC, E on CA, F on AB, so that AFDE is cyclic. Prove that: area DEF ≤ EF²/(4 AD²).

Solution

Extend AD to meet the circumcircle of ABC again at P. Then ∠DEF = ∠DAF (circle AFDE) = ∠PAB (same angle) = ∠PCB (circle ABPC). Similarly, ∠DFE = ∠DAE = ∠PAC = ∠PBC. So triangles DEF and PCB are similar. So area DEF = (EF²/BC²) area PCB. But triangles PCB and ABC have the same base BC, so area PCB = (PD/AD) area ABC = PD/AD. Hence area DEF = (EF²/BC²) (PD/AD).

BC = BD + DC, so 1/BC² = 1/(BC + CD)² ≤ 1/(4 BD.DC) by AM/GM. But ABPC is cyclic, so BD.DC = AD.PD. Hence 1/BC² ≤ 1/(4 AD.PD). Hence area DEF ≤ EF²/( 4 AD²).

9th Balkan 1992 Problem 4

For each n > 2 find the smallest f(n) such that any subset of {1, 2, 3, ... , n} with f(n) elements must have three which are relatively prime (in pairs).

Solution

Answer: f(6m) = f(6m+1) = 4m+1, f(6m+2) = 4m+2, f(6m+3) = 4m+3, f(6m+4) = f(6m+5) = 4m+4.

Let S_n = {1, 2, ... , n}. Now 4m members of S_6m are divisible by 2 or 3 (or both). So f(6m) > 4m. Now suppose X is a subset of S_6m with 4m+1 members. Then one of the sets {1, 2, ... , 6}, {7, 8, ... , 12}, ... , {6m-5, ... 6m} must contain 5 or more members of X. Suppose it is {6r+1, 6r+2, 6r+3, 6r+4, 6r+5, 6r+6}. Then it must contain at least one of {6r+2, 6r+3, 6r+5}, {6r+1, 6r+3, 6r+4}, or {6r+1, 6r+4, 6r+5} all of which have relatively prime members. (Consider for example {6r+2, 6r+3, 6r+5}. If s > 1 divides 6r+3 and 6r+5, then it divides their difference 2, so it must be 2, but 2 does not divide 6r+3. Similarly, for the other cases.) That establishes that f(6m) = 4m+1.

For n = 6m+1, the argument is the same except that any subset X of S_6m+1 must either contain 5 elements of some {6r+1, 6r+2, ... , 6r+6} or 5 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-2, 6m, 6m+1}. So we have to deal with the case where it contains 5 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-1, 6m, 6m+1}. But in that case it must include 3 elements from {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

For n = 6m+2, the argument is similar except that we have to show that any 6 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-1, 6m, 6m+1, 6m+2} include 3 which are relatively prime. But 6 elements must include at least 3 from {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

For n = 6m+3, we have to show that any 7 elements of {6m-5, 6m-4, 6m-3, 6m-2, 6m-1, 6m, 6m+1, 6m+2, 6m+3} include 3 which are relatively prime. But 7 elements must include 3 from {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

For n = 6m+4, we have to show that any 8 elements of {6m-5, ... , 6m+4} include 3 which are relatively prime, but again they must include 3 of {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

Finally, for n = 6m+5, we have to show that any 8 elements of {6m-5, ... 6m+5} include 3 which are relatively prime. But the 8 can only include at most 2 of 6m+3, 6m+4, 6m+5 (which are all relatively prime), and at most all of 3 of {6m-4, 6m, 6m+2}, so again it must include at least 3 of {6m-5, 6m-3, 6m-2, 6m-1, 6m+1} which are all relatively prime.

[more...]

8th Balkan Mathematical Olympiad Problems 1991

8th Balkan Mathematical Olympiad Problems 1991

A1.  The circumcircle of the acute-angled triangle ABC has center O. M lies on the minor arc AB. The line through M perpendicular to OA cuts AB at K and AC at L. The line through M perpendicular to OB cuts AB at N and BC at P. MN = KL. Find angle MLP in terms of angles A, B and C.

A2.  Find an infinite set of incongruent triangles each of which has integral area and sides which are relatively prime integers, but none of whose altitudes are integral.

A3.  A regular hexagon area H has its vertices on the perimeter of a convex polygon of area A. Prove that 2A ≤ 3H. When do we have equality?

A4.  A is the set of positive integers and B is A ∪ {0}. Prove that no bijection f: A → B can satisfy f(mn) = f(m) + f(n) + 3 f(m) f(n) for all m, n. 

Solutions

8th Balkan 1991 Problem 1

The circumcircle of the acute-angled triangle ABC has center O. M lies on the minor arc AB. The line through M perpendicular to OA cuts AB at K and AC at L. The line through M perpendicular to OB cuts AB at N and BC at P. MN = KL. Find angle MLP in terms of angles A, B and C.

Solution : Answer: angle C.

∠MKN = ∠AKL (opposite angles) = 90^o - ∠OAB = 1/2 ∠AOB = ∠C. A similar argument shows that ∠MNK = ∠C, so MNK is isosceles and MN = MK.

Also triangles AKL and ACB are similar, so AK/KL = AC/CB (*). Extend ML to meet the circumcircle again at R. Then since OA is perpendicular to MR, we have AM = AR. Triangles AKR and MKB are similar, because ∠AKR = ∠MKB (opposite angles) and ∠ARK = ∠ARM (same angle) = ∠ABM (ARBM cyclic) = ∠MBK (same angle). So AK/AR = MK/MB. Hence MK/AK = MB/AR = MB/AM. Multiplying by (*) we get MK/KL = (AC/BC) (BM/AM) (**). But MK = MN = KL. Hence (AC/BC) (BM/AM) = 1.

But a similar argument to that used to show (**) gives that MN/NP = (BC/AC) (AM/BM). Hence MN = NP. So N is the midpoint of MP and K is the midpoint of ML. Hence ∠MLP = ∠MKN = ∠C.

8th Balkan 1991 Problem 2

Find an infinite set of incongruent triangles each of which has integral area and sides which are relatively prime integers, but none of whose altitudes are integral.

Solution

One possible answer is: r² + 4, r⁴ + 3r² + 1, r⁴ + 4r² + 3 with r any integer not ±2 mod 5.

We use Heron's formula. Take the sides as a + b, n, n + a - b. This involves no loss of generality and makes Heron's expression more convenient. Let the area be A. Heron gives A² = (n+a)(n-b)ab. Suppose we take n - b = ar², n + a = bs². Then A = abrs. We require a(r² + 1) = b(s² - 1). The simplest idea is not to take a = s² - 1, b = r² + 1, but then the area is rs(s² - 1)(r² + 1), n = s²r² + 1 and n + a - b = (s² - 1)(r² + 1) which divides the area, so one of the altitudes is integral.

The next simplest idea is to take b = 1, s - 1 = r² + 1, a = s + 1 = r² + 3. This gives sides r² + 4, r⁴ + 3r² + 1, r⁴ + 4r² + 3 and area A = r(r² + 2)(r² + 3). We need to check that each pair of sides is relatively prime and that each altitude is non-integral.

Any common factor of r² + 4 and r⁴ + 3r² + 1 must also divide r²(r² + 4) - (r⁴ + 3r² + 1) = r² - 1 and hence also (r² + 4) - (r² - 1) = 5. But 5 only divides r² + 4 if r = ±2 mod 5, so for other values of r, these two sides are relatively prime.

Any common factor of r² + 4 and r⁴ + 4r² + 3 must also divide r⁴ + 4r² + 3 - r²(r² + 4) = 3. But any square is 0 or 1 mod 3, so r² + 4 cannot be divisible by 3. Hence these two sides are relatively prime. Finally, any common factor of (r⁴ + 3r² + 1) and (r⁴ + 4r² + 3) must also divide their difference r² + 2. Hence also (r⁴ + 3r² + 1) - r²(r² + 2) = r² + 1 and hence 1. So these two sides are relatively prime.

r² + 4 is relatively prime to r² + 3, has at most a factor 2 in common with r² + 2 and at most a factor 4 in common with r. So r² + 4 can only divide A if r = 2. If (r⁴ + 3r² + 1) divides A then it also divides (r² + 2)(r⁴ + 3r² + 1) - rA= r² + 2. But (r⁴ + 3r² + 1) > r² + 2. So (r⁴ + 3r² + 1) does not divide A. Finally, if (r⁴ + 4r² + 3) = (r² + 3)(r² + 1) divides A, then r² + 1 divides r(r² + 2), but that is impossible since r² + 1 and r² + 2 are relatively prime and r² + 1 > r. 

8th Balkan 1991 Problem 3

A regular hexagon area H has its vertices on the perimeter of a convex polygon of area A. Prove that 2A ≤ 3H. When do we have equality?

Solution

We use the basic result that there is at least one support line through any point on the boundary of a convex set. The support line has the property that all points of the convex set lie on one side of the line (or on the line itself). Since each vertex of the hexagon lies on the boundary of the polygon, there is a support line through each vertex of the hexagon.

Let the hexagon be ABCDEF. Take points P, Q outside the hexagon so that ABP, BCQ are equilateral triangles. Let the support lines through A, B, C, D, E, F be L_A, L_B, L_C, L_D, L_E, L_F respectively. Then these lines bound a hexagon H' which contains the convex polygon, so it is sufficient to show that area H' ≤ 3H/2. Let L_A and L_B meet at X and let L_B and L_C meet at Y. The area of H' is H plus the area of the triangle ABX and the area of the five corresponding triangles on the other sides. We claim that area ABX + area BCY ≤ H/6. It follows that the area of all six triangles is ≤ H/2 and so the required result follows.

Extend XY to meet AP at R and CQ at S. Since the hexagon area H is regular, AP is parallel to CQ and hence angle ARB = angle QSB. Also angle ABR = angle QBS and AB = BQ. So triangles ABR and QBS are congruent and hence have equal area. So area ABX + area BCY <= area ABR + area BCS = area QBS + area BCS = area BCQ = H/6, which establishes the claim. If we have equality then area ARX = 0, so L_A must coincide with the line AB or the line FA. Without loss of generality, it coincides with FA. Then L_B must coincide with the line BC, so H' is an equilateral triangle whose sides contain three sides of the hexagon. It is easy to see that this does indeed give equality. 

8th Balkan 1991 Problem 4

A is the set of positive integers and B is A ∪ {0}. Prove that no bijection f: A → B can satisfy f(mn) = f(m) + f(n) + 3 f(m) f(n) for all m, n.

Solution

We must take f(1) = 0, since if f(k) = 0, then f(k²) = 0 also and f is (1, 1). So for any n > 1 we have f(n) ≥ 1. Now suppose n is composite, n = rs with r, s > 1. Then f(n) = f(r) + f(s) + 3 f(r) f(s) ≥ 5. Take p and q so that f(p) = 1 and f(q) = 3. Then we have just shown that p and q are prime. Now take r so that f(r) = 8.

But now f(q²) = f(q) + f(q) + 3 f(q) f(q) = 3 + 3 + 27 = 33, and f(pr) = f(p) + f(r) + 3 f(p)f(r) = 1 + 8 + 3·8 = 33. f is a bijection so we must have q² = pr, but that is impossible, since p and q are distinct primes.

Comment. How did I come by that? I started playing with small values, but could not reach any obvious contradiction - unfortunately, I did not go as far as 33. So I started to look harder. I noticed a pattern in f(pⁿ). It seemed to be (4ⁿ-1)/3. That suggested looking at other f(qⁿ). Sure enough it appeared that if f(q) = 2, then f(qⁿ) = (7ⁿ-1)/3. If f(s) = 3, then f(sⁿ) = (10ⁿ-1)/3. I then noticed that that implied that f(pⁿq^m) = (4ⁿ7^m-1)/3. At that point I knew I was almost there because it seemed likely that we could find two different factorisations. So I worked out a few more and found that if f(r) = 8, then f(rⁿ) = (25ⁿ-1)/3. Since 25¹.4¹=10² I was home, apart from some routine tidying up. At that point I had not proved any of the patterns. In fact, it is easy to show that if f(p) = k, then f(pⁿ) = ( (3k+1)ⁿ-1)/3, but it is not necessary for the proof.

[more...]

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.

[more...]

6th Balkan Mathematical Olympiad Problems 1989

6th Balkan Mathematical Olympiad Problems 1989

A1.  Find all integers which are the sum of the squares of their four smallest positive divisors.

A2.  A prime p has decimal digits p_np_n-1...p₀ with p_n > 1. Show that the polynomial p_nxⁿ + p_n-1x^n-1 + ... + p₁x + p₀ has no factors which are polynomials with integer coefficients and degree strictly between 0 and n.

A3.  The triangle ABC has area 1. Take X on AB and Y on AC so that the centroid G is on the opposite of XY to B and C. Show that area BXGY + area CYGX ≥ 4/9. When do we have equality?

A4.  S is a collection of subsets of {1, 2, ... , n} of size 3. Any two distinct elements of S have at most one common element. Show that S cannot have more than n(n-1)/6 elements. Find a set S with n(n-4)/6 elements.

Solutions

6th Balkan 1989 Problem 1

Find all integers which are the sum of the squares of their four smallest positive divisors.

Solution Answer: 130.

n cannot be odd, because then its four smallest divisors would be odd and hence the sum of their squares even.

So the two smallest divisors are 1 and 2. If 4 divides n, then the four smallest divisors are either 1, 2, 4, 8 or 1, 2, 4, p (where p may be 3 or 5 or more). In the first case the sum of the squares is odd, but n is even, so it fails. In the second case we have 21 + p² = 4pm, where m is the product of the other factors of n. But any solution must divide 21, so p must be 3 or 7. But then 21 + p² is not divisible by 4, so this does not give any solutions.

So we can assume 2 divides n, but not 4. So if p is the smallest odd prime dividing n, then the three smallest divisors are 1, 2 and p. If the next smallest is q, then three of the four smallest are odd and hence the sum of the squares is odd. So the next smallest must be 2p. Thus we have 5 + 5p² = 2pm. So 5 divides n, so p must be 3 or 5. p = 3 gives square sum 50, which fails (not divisible by 3). p = 5 gives n = 130, which work. 

6th Balkan 1989 Problem 2

A prime p has decimal digits p_np_n-1...p₀ with p_n > 1. Show that the polynomial p_nxⁿ + p_n-1x^n-1 + ... + p₁x + p₀ has no factors which are polynomials with integer coefficients and degree strictly between 0 and n.

Solution

If w is a (complex) root of the polynomial, then since each coefficient is at most 9, we have |p_n| ≤ 9(1/|w| + 1/|w|² + ... + 1/|w|^n-1). So if |w| ≥ 9, then |p_n| ≤ 9(1/9 + 1/81 + ... ) < 9/8. But p_n ≥ 2, so we must have |w| < 9.

Suppose the polynomial has a factor with integer coefficients (and positive degree less than n). Then Gauss' lemma tells us that it must be a product of two polynomials with integer coefficients (and each with positive degree less than n). Suppose they are f(x) and g(x). Suppose the (complex) roots of f(x) are z₁, ... , z_m. Then f(x) = A(x - z₁) ... (x - z_m) with A and integer. Hence |f(10)| = |A| |10 - z₁| ... |10 - z_m|. But |A| ≥ 1 and each factor |10 - z_i| > 10 - 9 = 1. So |f(10)| > 1. Similarly, |g(10)| > 1. But f(10) and g(10) are integers and their product is the prime p. So we have a contradiction. So the polynomial cannot have any such factor.

6th Balkan 1989 Problem 3

The triangle ABC has area 1. Take X on AB and Y on AC so that the centroid G is on the opposite of XY to B and C. Show that area BXGY + area CYGX ≥ 4/9. When do we have equality?

Solution Answer: equality iff XY is parallel to BC and passes through G.

Area BXGY + area CXGY = 2 area XGY + area BXY + area CXY. Let M be the midpoint of BC. Then the distance of M from the line XY is the average of the distances of B and C, so area BXY + area CXY = 2 area MXY. Hence area BXGY + area CXGY = 2 area XGY + 2 area MXY = 2 area GXM + 2 area GYM = area AXG + area AYG (since AG = 2 GM).

Take B' on the side AB and C' on the side AC so that B'C' is parallel to BC and passes through G. AB'C' is similar to ABC with sides 2/3 as long, so area AB'C' = 4/9. Thus we wish to show that area AXG + area AYG ≥ area AB'C'. If X lies between B and B' and Y lies between C and C', then the distance of X from AG is greater than the distance of B', so area AXG > AB'G, and, similarly, area AYG > AC'G, so we are done. So assume X lies between A and B'. Let the ray XG meet AC at Y'. Then since G lies on the opposite side of XY to B and C, Y must lie between Y' and C. So area GYC' ≥ GY'C' and it is sufficient to show that area AXY' ≥ AB'C', or equivalently that area XGB' ≤ area Y'GC'.

By Menelaus' theorem applied to the triangle AB'C', we have (XB'/XA) (GC'/GB') (Y'C'/Y'A) = 1, or (XB'/XA) (Y'A/Y'C') = 1, since G is the midpoint of B'C'. So AB'/AC' ≥ AX/AY' = XB'/Y'C'. Let h_B be the distance of G from AB and h_C the distance of G from AC. Then (h_BAB')/(h_CAC') = area AGB'/area AGC' = 1, so h_C/h_B = AB'/AC'. Hence h_C/h_B ≥ XB'/Y'C', so area Y'GC' ≥ XGB' as required.

For equality we must have X = B' and Y = C'. 

6th Balkan 1989 Problem 4

S is a collection of subsets of {1, 2, ... , n} of size 3. Any two distinct elements of S have at most one common element. Show that S cannot have more than n(n-1)/6 elements. Find a set S with n(n-4)/6 elements.

Solution

Let T be the set of all pairs which are contained in an element of S. Each member of S gives rise to 3 pairs and the pairs corresponding to each member of S must be distinct (otherwise two members of S would have more than one common element). Hence T has 3S elements. But the total number of available pairs is n(n-1)/2, so S ≤ n(n-1)/6.

The next part is harder. Let S be the set of all triples {a, b, c} whose sum is divisible by n (and with a, b, c unequal). We show that S has n(n-3)/6 members.

There are n(n-1) ordered pairs (a, b) with a and b unequal. We can then require c = n - a - b mod n, so c is uniquely determined. However, in n cases we will get c = a (for each a there is a unique b such that 2a + b = n), and in n cases we will get c = b. These may overlap, but certainly there are at least n² - 3n ordered triples (a, b, c) where a, b, c are all unequal. Hence there are n(n-3)/6 unordered sets {a, b, c} with a, b, c all unequal and a + b + c = n. Obviously two such sets cannot have just two elements in common.

Note on Steiner and Kirkman Triple Systems

If |S| = n(n-1)/6, then S is called at Steiner triple system. It is well-known that such systems exist iff n = 1 or 3 mod 6. That is harder to prove. The standard approach is induction. The inductive step is to show that if a system is possible for n, then one is also possible for 2n+1 and for 2n+7. This is sufficient. For suppose we have proved the result for m < n and n = 1 mod 6. If n = 12k + 1, then n = 2(6k - 3) + 7, whilst if n = 12k + 7, then n = 2(6k + 3) + 1. Similarly if n = 12k + 3, then n = 2(6k + 1) + 1, whilst if n = 12k + 9, then n = 2(6k + 1) + 7.

n to 2n+1 is easy. Take A to be a collection of triples of {1, 2, ... , n} which form a Steiner system. Take X = {x₁, x₂, ... , x_n, y₁, y₂, ... , y_n, z}. Take as the collection of triples from X: (1) the n triples {z, x_i, y_i}, (2) the n(n-1)/6 triples {x_i, x_j, x_k}, where ijk is in A, (3) the 3n(n-1)/6 triples {x_i, y_j, y_k}, where ijk is in A. A little reflection shows that this is a Steiner triple system.

n to 2n+7 is harder and not given here. We require n > 3. As our starting values we need n = 3 (obvious), n = 7 (fairly obvious), n = 9 (fairly obvious), n = 13 (less obvious). These are exhibited below.

n = 7     n = 9           n = 13              n = 15
unique) (unique)         1 of 2            1 of several
1 2 3     1 2 3     1  2  3   1  7 13     1  2  3   1  8 14
1 4 5     4 5 6     1  4  5   1  9 12     4  5  6   2  6  9
1 6 7     7 8 9     1  6  8   1 10 11     7  8  9   3  7 12
2 4 6               2  8 13   2  4  6    10 11 12   4 10 13
2 5 7     1 4 7     2 11 12   2  5  7    13 14 15   5 11 15
3 4 7     2 5 9     3  5 12   2  9 10
3 5 6     3 6 8     3  9 13   3  4  7     1  4  7   1  9 11
                    4  9 11   3  6 11     2  5 14   2  8 10
          1 5 8     4 10 13   3  8 10     3  6 11   3  4 15
          2 6 7     5  6 10   4  8 12     8 12 13   5  7 13
          3 4 9     6  7  9   5  8  9     9 10 15   6 12 14
                    7 10 12   5 11 13
          1 6 9     7  8 11   6 12 13     1  5 10   1 12 15
          2 4 8                           2  4 12   2 11 13
          3 5 7                           3  9 13   3  5  8
                                          6  8 15   4  9 14
                                          7  11 14  6  7 10
                                          1  6 13
                                          2  7 15
                                          3 10 14
                                          4  8 11
                                          5  9 12

Note that the systems for n = 9 and 15 are also Kirkman triple systems (meaning that the triples can be partitioned into (n-1)/2 sets each containing all the points just once). Proving that this is always possible for n=3 mod 6 is harder.

[more...]