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.