25th All Soviet Union Mathematical Olympiad Problems 1991

1.  Find all integers a, b, c, d such that ab - 2cd = 3, ac + bd = 1.

2.  n numbers are written on a blackboard. Someone then repeatedly erases two numbers and writes half their arithmetic mean instead, until only a single number remains. If all the original numbers were 1, show that the final number is not less than 1/n.

3.  Four lines in the plane intersect in six points. Each line is thus divided into two segments and two rays. Is it possible for the eight segments to have lengths 1, 2, 3, ... , 8? Can the lengths of the eight segments be eight distinct integers?

4.  A lottery ticket has 50 cells into which one must put a permutation of 1, 2, 3, ... , 50. Any ticket with at least one cell matching the winning permutation wins a prize. How many tickets are needed to be sure of winning a prize?

5.  Find unequal integers m, n such that mn + n and mn + m are both squares. Can you find such integers between 988 and 1991?

6.  ABCD is a rectangle. Points K, L, M, N are chosen on AB, BC, CD, DA respectively so that KL is parallel to MN, and KM is perpendicular to LN. Show that the intersection of KM and LN lies on BD.

7.  An investigator works out that he needs to ask at most 91 questions on the basis that all the answers will be yes or no and all will be true. The questions may depend upon the earlier answers. Show that he can make do with 105 questions if at most one answer could be a lie.

8.  A minus sign is placed on one square of a 5 x 5 board and plus signs are placed on the remaining squares. A move is to select a 2 x 2, 3 x 3, 4 x 4 or 5 x 5 square and change all the signs in it. Which initial positions allow a series of moves to change all the signs to plus?

9.  Show that (x + y + z)²/3 ≥ x√(yz) + y√(zx) + z√(xy) for all non-negative reals x, y, z.

10.  Does there exist a triangle in which two sides are integer multiples of the median to that side? Does there exist a triangle in which every side is an integer multiple of the median to that side?

11.  The numbers 1, 2, 3, ... , n are written on a blackboard (where n ≥ 3). A move is to replace two numbers by their sum and non-negative difference. A series of moves makes all the numbers equal k. Find all possible k.

12.  The figure below is cut along the lines into polygons (which need not be convex). No polygon contains a 2 x 2 square. What is the smallest possible number of polygons?

13.  ABC is an acute-angled triangle with circumcenter O. The circumcircle of ABO intersects AC and BC at M and N. Show that the circumradii of ABO and MNC are the same.

14.  A polygon can be transformed into a new polygon by making a straight cut, which creates two new pieces each with a new edge. One piece is then turned over and the two new edges are reattached. Can repeated transformations of this type turn a square into a triangle?

15.  An h x k minor of an n x n table is the hk cells which lie in h rows and k columns. The semiperimeter of the minor is h + k. A number of minors each with semiperimeter at least n together include all the cells on the main diagonal. Show that they include at least half the cells in the table.

16.  (1) r₁, r₂, ... , r₁₀₀, c₁, c₂, ... , c₁₀₀ are distinct reals. The number r_i + c_j is written in position i, j of a 100 x 100 array. The product of the numbers in each column is 1. Show that the product of the numbers in each row is -1. (2) r₁, r₂, ... , r_2n, c₁, c₂, ... , c_2n are distinct reals. The number r_i + c_j is written in position i, j of a 2n x 2n array. The product of the numbers in each column is the same. Show that the product of the numbers in each row is also the same.

17.  A sequence of positive integers is constructed as follows. If the last digit of a_n is greater than 5, then a_n+1 is 9a_n. If the last digit of a_n is 5 or less and a_n has more than one digit, then a_n+1 is obtained from a_n by deleting the last digit. If a_n has only one digit, which is 5 or less, then the sequence terminates. Can we choose the first member of the sequence so that it does not terminate?

18.  p(x) is the cubic x³ - 3x² + 5x. If h is a real root of p(x) = 1 and k is a real root of p(x) = 5, find h + k.

19.  The chords AB and CD of a sphere intersect at X. A, C and X are equidistant from a point Y on the sphere. Show that BD and XY are perpendicular.

20.  Do there exist 4 vectors in the plane so that none is a multiple of another, but the sum of each pair is perpendicular to the sum of the other two? Do there exist 91 non-zero vectors in the plane such that the sum of any 19 is perpendicular to the sum of the others?

21.  ABCD is a square. The points X on the side AB and Y on the side AD are such that AX·AY = 2 BX·DY. The lines CX and CY meet the diagonal BD in two points. Show that these points lie on the circumcircle of AXY.

22.  X is a set with 100 members. What is the smallest number of subsets of X such that every pair of elements belongs to at least one subset and no subset has more than 50 members? What is the smallest number if we also require that the union of any two subsets has at most 80 members?

23.  The real numbers x₁, x₂, ... , x₁₉₉₁ satisfy |x₁ - x₂| + |x₂ - x₃| + ... + |x₁₉₉₀ - x₁₉₉₁| = 1991. What is the maximum possible value of |s₁ - s₂| + |s₂ - s₃| + ... + |s₁₉₉₀ - s₁₉₉₁|, where s_n = (x₁ + x₂ + ... + x_n)/n? 

Solutions

Problem 1

Find all integers a, b, c, d such that ab - 2cd = 3, ac + bd = 1.

Answer

(a,b,c,d) = (1,3,1,0), (-1,-3,-1,0), (3,1,0,1), (-3,-1,0,-1)

Solution

11 = (ab - 2cd)² + 2(ac + bd)² = (a² + 2d²)(b² + 2c²), so we must have either (1) a² + 2d² = 1, b² + 2c² = 11, or (2) a² + 2d² = 11, b² + 2c² = 1.

(1) gives a = ±1, d = 0, b = ±3, c = ±1. If a = 1 and d = 0, then ac + bd = 1 implies c = 1, and ab - 2cd = 3 implies b = 3. Similarly, if a = -1, then c = -1, and b = -3. Similarly, (2) gives (a,b,c,d) = (3,1,0,1), (-3,-1,0,-1). 

Problem 2

n numbers are written on a blackboard. Someone then repeatedly erases two numbers and writes half their arithmetic mean instead, until only a single number remains. If all the original numbers were 1, show that the final number is not less than 1/n.

Solution

Put c = (a+b)/4. We have 1/c = 4/(a+b) ≤ 1/a + 1/b, so each move does not increase the sum of the reciprocals of the numbers. If the final number is k, then the final sum of reciprocals is 1/k. The initial sum is n, so 1/k ≤ n, or k ≥ 1/n.

Problem 3

Four lines in the plane intersect in six points. Each line is thus divided into two segments and two rays. Is it possible for the eight segments to have lengths 1, 2, 3, ... , 8? Can the lengths of the eight segments be eight distinct integers?

Answer

no, yes

Solution

 If a triangle has integer sides, one of which is 1, then it must be isosceles. So the only candidates for the segment length 1 are AB and AE. wlog AB = 1, so BF = AF. Hence cos DFE = 1 - 1/(2 AF²). Hence ED² = DF² + EF² + 2DF·EF(1 - 1/2AF²) = DF² + EF² + 2DF·EF - DF·EF/AF². But the first three terms are integers and the last term is < 1. Contradiction. (Careful, looking at the figure one is tempted to conclude that ED < AB, but a more realistic figure shows that is false.).

Building on the 3,4,5 triangle we get the figure above.

Problem 4

A lottery ticket has 50 cells into which one must put a permutation of 1, 2, 3, ... , 50. Any ticket with at least one cell matching the winning permutation wins a prize. How many tickets are needed to be sure of winning a prize?

Answer

26

Solution

Take the tickets:

1  2  3  ... 25 26 27 ... 50
 2  3  4  ... 26  1 27 ... 50
 3  4  5  ...  1  2 27 ... 50
 ...
26  1  2  ... 24 25 27 ... 50

Each of the numbers 1, 2, ... , 26 occurs in each of the places 1, 2, ... , 26, but the winning ticket cannot have all these numbers in the last 24 places. So there must be at least one match. So 26 tickets suffice.

Now given any 25 tickets we show that they could all fail to match the winning permutation. In other words, we construct a permutation which fails to match any of the 25 tickets in any cell. We place the numbers 1, 2, 3, ... , 50 in turn. We start by placing 1. Clearly at most 25 places are ruled out, so we can place the 1. Now suppose we have placed 1, 2, ... , a. There must be at least 25 places where a+1 is not ruled out. If any of them are still unoccupied, then we are done. If not, they must be occupied by numbers x₁, x₂, ... , x₂₅ already placed. Take any empty place. 26 numbers cannot be ruled out for it, and we know that a+1 is ruled out, so at least one of the x_i is not ruled out. So we can move that x_i to it and then place a+1 where the x_i came from.

Problem 5

Find unequal integers m, n such that mn + n and mn + m are both squares. Can you find such integers between 988 and 1991?

Answer

no

Solution

For example, 49 = 7², 50 = 2·5², 8 = 2·2², 9 = 3², so 49·8 + 8 = 20², 49·8 + 49 = 21².

wlog m < n. Then mn + m = (m+h)², mn + n = (m+k)², with k > h. So n - m = (m+k)² - (m+h)² = (k-h)(2m+k+h) > 2m, so n > 3m. Hence we cannot have m and n between 988 and 1991. 

Problem 6

ABCD is a rectangle. Points K, L, M, N are chosen on AB, BC, CD, DA respectively so that KL is parallel to MN, and KM is perpendicular to LN. Show that the intersection of KM and LN lies on BD.

Solution

Let LN and KM meet at O. ∠NOM = ∠NDM = 90^o, so OMDN is cyclic. Hence ∠NOD = ∠NMD. Similarly, BLOK is cyclic and ∠LOB = ∠LKB. But NM is parallel to LK and AB is parallel to CD, so ∠LKB = ∠NMD. Hence ∠NOD = ∠LOB, so DOB is a straight line.

Problem 7

An investigator works out that he needs to ask at most 91 questions on the basis that all the answers will be yes or no and all will be true. The questions may depend upon the earlier answers. Show that he can make do with 105 questions if at most one answer could be a lie.

Solution

Suppose he asks n questions as usual, and then asks "did you lie to any of the last n questions?" If the reply is a truthful no, then the n answers were correct. If the reply is a lying no, then the n answers were still correct. On the other hand if the answer is yes, then the n answers might have been correct and might not. However, a lie has certainly been told, so all future answers must be truthful and so he could ask the n questions again.

91 = 7·13, so the obvious candidates for n are 7 and 13. If we take n = 7, then the worst case is 13 check questions and 7 repeat questions. That does not work because he needs 20 extra questions and only has 14. A little thought suggests reducing n each time. So the first batch of questions is 13, followed by a check question. If the check answer is yes, then he knows a lie has been told and asks the 13 questions again. No further check questions are needed, and he has used exactly 14 extra questions. If the check answer is no, then the lie may not have been told, so the next batch of questions is 12, followed by a check question, and so on. That allows him to ask 13+12+...+1 = 91 questions. If he gets a yes to the check question after the batch of i, then he ignores the answers to that batch and asks them again, thus asking a total of 14 extra questions, but thereafter asks no check questions. 

Problem 8

A minus sign is placed on one square of a 5 x 5 board and plus signs are placed on the remaining squares. A move is to select a 2 x 2, 3 x 3, 4 x 4 or 5 x 5 square and change all the signs in it. Which initial positions allow a series of moves to change all the signs to plus?

Answer

only the central square

Solution

 

We take the 5x5 square, the two yellow 3x3 squares, which overlap at the center, and the two blue 2x2 squares. Then every square except the center square is changed an even number of times. So this works if the central square was selected.

It is easy to check that any 2x2, 3x3, 4x4 or 5x5 square has an even number of green squares, so if the selected square was green, and we change it an odd number of times, then some other green square must also be changed an odd number of times and hence end up with a minus. So if all the squares end up plus, then the selected square was not green, so it must belong to the central white column. Similarly, it must belong to the central row and hence must be the center square.

Problem 9

Show that (x + y + z)²/3 ≥ x√(yz) + y√(zx) + z√(xy) for all non-negative reals x, y, z.

Solution

By AM/GM xy + yz ≥ 2x√(yz). Adding the similar results gives 2(xy + yz + zx) ≥ 2(x√(yz) + y√(zx) + z√(xy) ).

By AM/GM x² + x² + y² + z² ≥ 4x√(yz). Adding the similar results gives x² + y² + z² ≥ x√(yz) + y√(zx) + z√(xy). Adding the first result gives (x + y + z)²/3 ≥ x√(yz) + y√(zx) + z√(xy). 

Problem 10

Does there exist a triangle in which two sides are integer multiples of the median to that side? Does there exist a triangle in which every side is an integer multiple of the median to that side?

Answer

yes, no

Solution

The obvious approach is to make the triangle isosceles. So suppose the sides are a, b, b. Then the length m of a median to one of the sides length b satisfies: a² + b² = 2m² + b²/2. The simplest possbility is to take m = b, so a² = 3b²/2. Thus if b = 2, a = √6.

Suppose we have a triangle ABC, with medians AD, BE, CF, and BC/AD, CA/BE, AB/CF all integers. If AD = BC/2, then ∠A = 90^o. If AD < BC/2, then ∠A is obtuse, so at least two of the medians must be equal to the corresponding sides. So wlog we have b² + c² = 5a²/2, c² + a² = 5b²/2. Subtracting, b² - a² = (5/2)(a² - b²), so a = b. Hence c/a = √(3/2). So the third median has length m where a² + a² = (3/4)a² + 2m², so a/m = √(8/5), which is not integral. Contradiction. 

Problem 11

The numbers 1, 2, 3, ... , n are written on a blackboard (where n ≥ 3). A move is to replace two numbers by their sum and non-negative difference. A series of moves makes all the numbers equal k. Find all possible k.

Answer

all powers of 2 ≥ n

Solution

If a prime p divides a+b and a-b, then it divides 2a and 2b, so if p is odd, it divides a and b. Thus if an odd prime p divides k, then it must divide all the original numbers including 1. So k must be a power of 2. Note that k, k → 0, 2k → 2k, 2k and k, k, k → 0, k, 2k → k, k, 2k → 0, 2k, 2k → 2k, 2k, 2k. So (by a trivial induction) if we get all the numbers equal to k, then we can get them all to equal 2k. Finally, note that we can never decrease the largest number on the board, so the answer must be all powers of 2 greater than some minimum, which must be at least n.

We use induction to show that if 2^m is the smallest power of 2 which is ≥ n, then we can get all numbers equal to 2^m. Note that 0, k → k, k → 0, 2k, so with a zero we can double each member of any set of numbers as often as we wish and finally convert the zero. For example, we could convert 0, 2, 4 to 8, 8, 8. It is convenient to take the induction hypothesis as S_n: we can convert 1, 2, ... , n to 0, 2^k, 2^k, ... , 2^k, where 2^k is the smallest power of 2 which is ≥ n.

We show first that S_n is true for n ≤ 8. For n = 3, we take 1,3 → 2,4, then 2,2 → 0,4. For n = 4, we ignore the 4 and use the case n = 3. For n = 5, we take 3,5 → 2,8. Then 2,2 → 0,4. Then we use the 0 to convert the remaining powers of 2 (1,4,4) to 8. For n = 6, we take 2,6 → 4,8 and 3,5 → 2,8, then 4,4 → 0,8. Finally, we use the 0 to convert 1 and 2 to 8. For n = 7, we take 1,7 → 6,8, then 2,6 → 4,8, then 3,5 → 2,8, then 4,4 → 0,8, then 2,6 → 4,8 and finally use the 0 to convert the remaining 4 to 8.

Let n = 2^a + b, where 0 < b ≤ 2^a and assume S_m is true for all m < n. If b = 1, we convert the pair 2^a-1, 2^a+1 to 2, 2^a+1. We have 2^a-2 > 2, so by induction we can convert 1, 2, ... , 2^a-2 to 0, 2^a, ... , 2^a. Now all the numbers except 0 are powers of 2 and we can use the 0 to convert them each to 2^a+1. Similarly, if b = 2, we convert 2^a-1, 2^a+1 to 2, 2^a+1 and 2^a-2, 2^a+2 to 4, 2^a+1 and then proceed as in the previous case. If 3 ≤ b < 2^a, then we start by converting the pairs (2^a + b, 2^a - b), (2^a + b-1, 2^a - b+1), (2^a + b-2, 2^a - b+2), ... , (2^a + 1, 2^a - 1). That gives some 2^a+1s and 2, 4, ... , 2b. Now by S_b we can convert 2, 4, ... , 2b to 0, 2^a+1, ... , 2^a+1. The remaining numbers 1, 2, ... , 2^a-b-1 can either be converted to powers of 2 by S^2a-b-1 (if 2^a-b-1 ≥ 3) or are already powers of 2. Finally we use the 0 to bring all powers of 2 up to 2^a+1. In the case b = 2^a, we ignore 2^a + b (= 2^a+1) and use the case b-1 to convert the others. 

Problem 12

The figure below is cut along the lines into polygons (which need not be convex). No polygon contains a 2 x 2 square. What is the smallest possible number of polygons?

Answer

12

Solution

We can clearly cut the polygon into 12 strips width 1, so the smallest number is ≤ 12.

There are 84 unit squares in the figure. Each cut along the edge of a unit square not already cut (and not on the boundary) increases the number of pieces by at most 1. So it is sufficient to show that at most 72 edges remain uncut (after cutting into polygons). Because then cutting the remaining edges would increase the total number of pieces by at most 72. But the final number of pieces is 84, so we would have to start with at least 12.

Initially, there are 144 edges, so we have to show that at least 72 of them are cut to make the polygons. An interior vertex has 4 edges. At least two of them must be cut, or the vertex would be the center of an uncut 2 x 2 square. If we take alternate interior vertices (36 in total, as shown below), then each has at least two cut edges, so in total at least 72 edges are cut to make the polygons.

Problem 13

ABC is an acute-angled triangle with circumcenter O. The circumcircle of ABO intersects AC and BC at M and N. Show that the circumradii of ABO and MNC are the same.

Solution

It is sufficient to show that ∠MBN = ∠C. But ∠MBN = ∠MBO + ∠OBN = ∠MAO + ∠OBN = ∠MCO + ∠OCN = ∠C. 

Problem 18

p(x) is the cubic x³ - 3x² + 5x. If h is a real root of p(x) = 1 and k is a real root of p(x) = 5, find h + k.

Solution

Put y = 2-h, where p(h) = 1, then (2-y)³ - 3(2-y)² + 5(2-y) - 1 = 0, so 8-12y+6y²-y³ - 12+12y-3y² + 10-5y - 1 = 0, or y³ - 3y² + 5y = 5, or p(y) = 5. So if h is a root of p(h) = 1, then there is a root k of p(k) = 5 such that h+k = 2. To complete the proof we have to show that p(x) = 5 has only one real root.

But x³ - 3x² + 5x = (x-1)³ + 2(x-1) + 3 which is a strictly increasing function of x-1 and hence of x. So p(x) = k has only one real root.