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 pnpn-1...p0 with pn > 1. Show that the polynomial pnxn + pn-1xn-1 + ... + p1x + p0 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 + p2 = 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 + p2 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 + 5p2 = 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 pnpn-1...p0 with pn > 1. Show that the polynomial pnxn + pn-1xn-1 + ... + p1x + p0 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 |pn| ≤ 9(1/|w| + 1/|w|2 + ... + 1/|w|n-1). So if |w| ≥ 9, then |pn| ≤ 9(1/9 + 1/81 + ... ) < 9/8. But pn ≥ 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 z1, ... , zm. Then f(x) = A(x - z1) ... (x - zm) with A and integer. Hence |f(10)| = |A| |10 - z1| ... |10 - zm|. But |A| ≥ 1 and each factor |10 - zi| > 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 hB be the distance of G from AB and hC the distance of G from AC. Then (hBAB')/(hCAC') = area AGB'/area AGC' = 1, so hC/hB = AB'/AC'. Hence hC/hB ≥ 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 n2 - 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 = {x1, x2, ... , xn, y1, y2, ... , yn, z}. Take as the collection of triples from X: (1) the n triples {z, xi, yi}, (2) the n(n-1)/6 triples {xi, xj, xk}, where ijk is in A, (3) the 3n(n-1)/6 triples {xi, yj, yk}, 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 = 15Note 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.
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
Labels:
Balkan Mathematical Olympiad
Previous Article
