3rd All Soviet Union Mathematical Olympiad 1969 Problems & Solutions

1.  In the quadrilateral ABCD, BC is parallel to AD. The point E lies on the segment AD and the perimeters of ABE, BCE and CDE are equal. Prove that BC = AD/2.

2.  A wolf is in the center of a square field and there is a dog at each corner. The wolf can run anywhere in the field, but the dogs can only run along the sides. The dogs' speed is 3/2 times the wolf's speed. The wolf can kill a single dog, but two dogs together can kill the wolf. Prove that the dogs can prevent the wolf escaping.

3.  A finite sequence of 0s and 1s has the following properties: (1) for any i < j, the sequences of length 5 beginning at position i and position j are different; (2) if you add an additional digit at either the start or end of the sequence, then (1) no longer holds. Prove that the first 4 digits of the sequence are the same as the last 4 digits.

4.  Given positive numbers a, b, c, d prove that at least one of the inequalities does not hold: a + b < c + d; (a + b)(c + d) < ab + cd; (a + b)cd < ab(c + d).

5.  What is the smallest positive integer a such that we can find integers b and c so that ax² + bx + c has two distinct positive roots less than 1?

6.  n is an integer. Prove that the sum of all fractions 1/rs, where r and s are relatively prime integers satisfying 0 < r < s ≤ n, r + s > n, is 1/2.

7.  Given n points in space such that the triangle formed from any three of the points has an angle greater than 120 degrees. Prove that the points can be labeled 1, 2, 3, ... , n so that the angle defined by i, i+1, i+2 is greater than 120 degrees for i = 1, 2, ... , n-2.

8.  Find 4 different three-digit numbers (in base 10) starting with the same digit, such that their sum is divisible by 3 of the numbers.

9.  Every city in a certain state is directly connected by air with at most three other cities in the state, but one can get from any city to any other city with at most one change of plane. What is the maximum possible number of cities?

10.  Given a pentagon with equal sides. (a)  Prove that there is a point X on the longest diagonal such that every side subtends an angle at most 90 degrees at X.

(b)  Prove that the five circles with diameter one of the pentagon's sides do not cover the pentagon.

11.  Given the equation x³ + ax² + bx + c = 0, the first player gives one of a, b, c an integral value. Then the second player gives one of the remaining coefficients an integral value, and finally the first player gives the remaining coefficient an integral value. The first player's objective is to ensure that the equation has three integral roots (not necessarily distinct). The second player's objective is to prevent this. Who wins?

12.  20 teams compete in a competition. What is the smallest number of games that must be played to ensure that given any three teams at least two play each other?

13.  A regular n-gon is inscribed in a circle radius R. The distance from the center of the circle to the center of a side is h_n. Prove that (n+1)h_n+1 - nh_n > R.

14.  Prove that for any positive numbers a₁, a₂, ... , a_n we have:   a₁/(a₂+a₃) + a₂/(a₃+a₄) + ... + a_n-1/(a_n+a₁) + a_n/(a₁+a₂) > n/4. 

Solutions

Problem 1

In the quadrilateral ABCD, BC is parallel to AD. The point E lies on the segment AD and the perimeters of ABE, BCE and CDE are equal. Prove that BC = AD/2.

Solution

Take E₁ on the line AD so that AE₁CB is a parallelogram. Then AE₁ = BC, AB = CE₁, so triangles ABE₁ and BCE₁ have equal perimeters. Moreover, E₁ is the only point on the line for which this is true. For if we move E a distance x from E₁, then we change AE₁ by x, and CE₁ by less than x. AB and BC are unchanged. So AB + BE₁ and BC + CE₁ are changed by different amounts. Hence the perimeters of ABE₁ and BCE₁ are no longer equal.

Similarly, let E₂ be the point on the line AD so that BCDE₂ is a parallelogram. Then E₂ is the unique point such that BCE₂ and CDE₂ have equal perimeters. So if all three triangles have equal perimeters, then E₁ and E₂ must coincide and hence BC = AE = DE, so BC = AD/2. 

Problem 3

A finite sequence of 0s and 1s has the following properties: (1) for any i < j, the sequences of length 5 beginning at position i and position j are different; (2) if you add an additional digit at either the start or end of the sequence, then (1) no longer holds. Prove that the first 4 digits of the sequence are the same as the last 4 digits.

Solution

Let the last 4 digits be abcd. Then the 5 digit sequences abcd0 and abcd1 must occur somewhere. If neither of them are at the beginning then there are three 5 digit sequences xabcd, two of which must therefore be the same, contradicting (1). Hence abcd are the first 4 digits. 

Problem 4

Given positive numbers a, b, c, d prove that at least one of the inequalities does not hold: a + b < c + d; (a + b)(c + d) < ab + cd; (a + b)cd < ab(c + d).

Solution

From the first and second inequalities we have ab + cd > a(c + d) + b(a + b), so cd > ad, and hence c > a. We also have ab + cd > a(a + b) + b(c + d), so cd > bc, and hence d > b. So 1/a + 1/b > 1/c + 1/d, which contradicts the third inequality. 

Problem 5

What is the smallest positive integer a such that we can find integers b and c so that ax² + bx + c has two distinct positive roots less than 1?

Solution

4x² - 4x + 1 = (2x - 1)², which has the double root 1/2. So it remains to consider a = 1, 2, 3.

-b/a is the sum of the roots, so b is negative. c/a is the product of the roots, so c is positive. If a = 1, then the product of the roots is c, which is at least 1, so both roots cannot lie strictly between 0 and 1. If a = 2, then the sum of the roots is less than 2, so b must be -1, -2, or -3. The roots are real so b² > 4ac = 8c. Hence b = -3 and c = 1. But 2x² - 3x + 1 = (2x - 1)(x - 1) and one root is not less than 1. If a = 3, then b must be -1, -2, ... , or -5. But b² > 4ac = 12c, so (b, c) = (-4, 1), (-5, 1) or (-5, 2). In the first and last case, the equation has a root 1. In the middle case it has a root 5/6 + √13/6 = 1.434 > 1. Thus there are no solutions for a = 1, 2, 3 and so the smallest value of a is 4. 

Problem 6

n is an integer. Prove that the sum of all fractions 1/rs, where r and s are relatively prime integers satisfying 0 < r < s ≤ n, r + s > n, is 1/2.

Solution

We use induction on n. If n = 2, then the only such fraction is r = 1, s = 2, giving 1/rs = 1/2, so the result holds. Suppose it holds for n-1. As we move to n, we lose the fractions with r+s=n. The other fractions 1/rs which satisfy the conditions for n-1 also satisfy the conditions for n. We also gain the fractions with s=n. These have sum = 1/n (sum 1/r for all r satisfying 0 < r < n and r relatively prime to n). But if r is relatively prime to n, then so is n - r, and n - r does not equal r (otherwise r divides n). The pair 1/r, 1/(n-r) has sum n/(r(n-r)). So the fractions with s=n have sum equal to the sum of all 1/(r(n-r) with 0 < r < n and r relatively prime to n. But that is exactly the sum of the fractions lost. Thus the total is unchanged as we move from n-1 to n. 

Problem 8

Find four different three-digit numbers (in base 10) starting with the same digit, such that their sum is divisible by three of the numbers.

Solution

Answer: 108, 117, 135, 180. Sum 540 = 108·5 = 135·4 = 180·3.

Try looking for a number of the form 3·4·5·n. We want 12n, 15n and 20n to have the same first digit. If the first digit is 1, this requires n = 9. We must now check that the fourth number which must be 60n - 12n - 15n - 20n = 13n also has three digits starting with 1. It does, so we are home. [In fact, in this case the first digit must be 1, since 20n > 3/2 12n.]

Problem 9

Every city in a certain state is directly connected by air with at most three other cities in the state, but one can get from any city to any other city with at most one change of plane. What is the maximum possible number of cities?

Solution

Answer: 10.

Take a particular city X. At most 3 cities are directly connected to X. Each of those is directly connected to at most 2 other cities (apart from X). So X is connected with at most one change to at most 9 other cities. Thus the maximum number is at most 10.

We can achieve 10 as follows. Label the cities 1, ... , 10. Make direct connections as follows:
1: 2, 3, 4;   2: 1, 5, 6;   3: 1, 7, 8;   4: 1, 9, 10;   5: 2, 7, 9;   6: 2, 8, 10;   7: 3, 5, 10;   8: 3, 6, 9;   9: 4, 5, 8;   10: 4, 6, 7.

Problem 11

Given the equation x³ + ax² + bx + c = 0, the first player gives one of a, b, c an integral value. Then the second player gives one of the remaining coefficients an integral value, and finally the first player gives the remaining coefficient an integral value. The first player's objective is to ensure that the equation has three integral roots (not necessarily distinct). The second player's objective is to prevent this. Who wins?

Solution

Answer: the first player.

The first player starts by choosing c = 0. Now if the second player selects a, then he can take b = a - 1. Then the polynomial factorizes as: x(x+1)(x+a-1) with integral roots, 0, -1, 1-a. If the second player selects b, then he can take a = b + 1. Then the polynomial factorizes as x(x+1)(x+b) with integral roots 0, -1, -b.