1st All Soviet Union Mathematical Olympiad 1967 Problems & Solutions

1.  In the acute-angled triangle ABC, AH is the longest altitude (H lies on BC), M is the midpoint of AC, and CD is an angle bisector (with D on AB). (a)  If AH ≤ BM, prove that the angle ABC ≤ 60.

(b)  If AH = BM = CD, prove that ABC is equilateral.

2. (a)  The digits of a natural number are rearranged and the resultant number is added to the original number. Prove that the answer cannot be 99 ... 9 (1999 nines). (b)  The digits of a natural number are rearranged and the resultant number is added to the original number to give 10¹⁰. Prove that the original number was divisible by 10.

3.  Four lighthouses are arbitarily placed in the plane. Each has a stationary lamp which illuminates an angle of 90 degrees. Prove that the lamps can be rotated so that at least one lamp is visible from every point of the plane.

4. (a)  Can you arrange the numbers 0, 1, ... , 9 on the circumference of a circle, so that the difference between every pair of adjacent numbers is 3, 4 or 5? For example, we can arrange the numbers 0, 1, ... , 6 thus: 0, 3, 6, 2, 5, 1, 4. (b)  What about the numbers 0, 1, ... , 13?

5.  Prove that there exists a number divisible by 5¹⁰⁰⁰ with no zero digit.

6.  Find all integers x, y satisfying x² + x = y⁴ + y³ + y² + y.

7.  What is the maximum possible length of a sequence of natural numbers x₁, x₂, x₃, ... such that x_i ≤ 1998 for i ≥ 1, and x_i = |x_i-1 - x_i-2| for i ≥3.

8.  499 white rooks and a black king are placed on a 1000 x 1000 chess board. The rook and king moves are the same as in ordinary chess, except that taking is not allowed and the king is allowed to remain in check. No matter what the initial situation and no matter how white moves, the black king can always:

(a)  get into check (after some finite number of moves);

(b)  move so that apart from some initial moves, it is always in check after its move;

(c)  move so that apart from some initial moves, it is always in check (even just after white has moved).

Prove or disprove each of (a) - (c).

9.  ABCD is a unit square. One vertex of a rhombus lies on side AB, another on side BC, and a third on side AD. Find the area of the set of all possible locations for the fourth vertex of the rhombus.

10.  A natural number k has the property that if k divides n, then the number obtained from n by reversing the order of its digits is also divisible by k. Prove that k is a divisor of 99. 

Solutions

Problem 1

In the acute-angled triangle ABC, AH is the longest altitude (H lies on BC), M is the midpoint of AC, and CD is an angle bisector (with D on AB).

(a)  If AH <= BM, prove that the angle ABC <= 60.

(b)  If AH = BM = CD, prove that ABC is equilateral.

Solution

As usual let a, b, c be the lengths of BC, CA, AB respectively and let A, B, C denote the angles BAC, ABC, BCA respectively. We use trigonometry and try to express the quantities of interest in terms of a, b and C.

(a)  Since AH is the longest altitude, BC must be the shortest side (use area = side x altitude/2). So b² >= a², and c² >= a². Using the formula c² = a² + b² - 2ab cos C, we deduce that b² >= 2ab cos C. Hence 2b² >= a² + 2ab cos C. After a little manipulation this gives: a² + b² - 2ab cos C >= 4/3 (a² + b²/4 - ab cos C) or c² >= 4/3 BM². But we are given that BM >= AH = b sin C, so (b²sin²C)/c² <= 3/4. But the sine formula gives sin B = (b sin C)/c, so sin²C <= 3/4. The triangle is acute-angled, hence B <= 60 degrees.

(b)  The angle bisector theorem gives AD/BD = b/a, hence AD/AB = b/(a+b), so AD = bc/(a+b). Hence, using the sine formula, CD/sin A = AD/(sin C/2). So CD = bc sin A/((a+b) sin C/2) = ba sin C/((a+b) sin C/2), using the sine formula again. But we are given that CD ≥ AH = b sin C, so a/((a+b) sin C/2) ≥ 1. But a is the shortest side, so a/(a+b) ≤ 1/2 and hence sin C/2 < 1/2. The triangle is acute-angled, so C/2 ≤ 30 degrees, and C ≤ 60 degrees. BC is the shortest side, so A is the smallest angle and hence A ≤ 60 degrees. Also since AH ≤ BM, B ≤ 60 degrees. But the angles sum to 180 degrees, so they must all be 60 degrees and hence the triangle is equilateral. 

Problem 2

(a)  The digits of a natural number are rearranged and the resultant number is added to the original number. Prove that the answer cannot be 99 ... 9 (1999 nines).
(b)  The digits of a natural number are rearranged and the resultant number is added to the original number to give 10¹⁰. Prove that the original number was divisible by 10.

Solution

(a)  Let the digits of the original number be a₁, a₂, ... and the rearranged digits be b₁, b₂, ... . Suppose that in the addition there is a carry, in other words a_i+b_i > 9 for some i. Take the largest such i. Then the resulting digit in that position cannot be a 9. Contradiction. So there cannot be any carries. Hence each pair a_i+b_i= 9. Let n be the total number of digits 0, 1, 2, 3, and 4 in the number. Then each of these must be paired with a digit 5, 6, 7, 8 or 9. So the total number of digits 5, 6, 7, 8 and 9 must also be n, and hence the number must have an even number of digits. But we are told that the answer and hence the original number has an odd number of digits.
(b)  In the addition the carry can never be 2, because that would require the previous carry to be at least 2, and the first carry cannot be 2. So all carries are 0 or 1. If a carry is 1, then all subsequent carries must also be 1. If the first carry is 0, then the corresponding digits must be 0 and hence the original number is divisible by 10. If it is not, then all carries are 1 and hence after the first carry all the digit pairs sum to 9. But arguing as in (a), this means that there must be an even number of digits, excluding the last (where we have a digit sum 10), and hence an odd number of digits in the original number. But 10¹⁰ has an odd number of digits and hence the original number had an even number of digits. Contradiction.

Problem 3

Four lighthouses are arbitarily placed in the plane. Each has a stationary lamp which illuminates an angle of 90 degrees. Prove that the lamps can be rotated so that at least one lamp is visible from every point of the plane.

Solution

Take a north direction, arbitary except that no points are aligned north-south or east-west. Take the two most northerly points. Point the lamp for the more easterly of these two in the direction SW (so that it covers directions S to W). Point the lamp for the other in the direction SE. For the other two points, point the lamp for the more easterly in the direction NW, and the lamp for the other in the direction NE.

Clearly the lamps cover all directions, the only possible problem is uncovered strips. However, the two lamps pointing N are below the two lamps pointing S, and the two lamps pointing E are west of the two lamps pointing W, so there are no uncovered strips.

Problem 4

(a)  Can you arrange the numbers 0, 1, ... , 9 on the circumference of a circle, so that the difference between every pair of adjacent numbers is 3, 4 or 5? For example, we can arrange the numbers 0, 1, ... , 6 thus: 0, 3, 6, 2, 5, 1, 4.

(b)  What about the numbers 0, 1, ... , 13?

Solution

No. Each of the numbers 0, 1, 8, 9 can only be adjacent to 3, 4, 5 or 6. But they can only accomodate 3 numbers, not 4.

0, 3, 7, 10, 13, 9, 12, 8, 11, 6, 2, 5, 1, 4 is a solution for 13.

In passing, there are obviously no solutions for 4 or 5. There is just the one solution for 6 (given in the question). For 7 there are 5 solutions: 0, 3, 6, 1, 5, 2, 7, 4; 0, 3, 6, 1, 4, 7, 2, 5; 0, 3, 6, 2, 7, 4, 1, 5; 0, 3, 7, 4, 1, 6, 2, 5; 0, 4, 1, 6, 3, 7, 1, 5. For 8 there is the solution 0, 3, 7, 2, 6, 1, 5, 8, 4, and maybe others. 

Problem 5

Prove that there exists a number divisible by 5¹⁰⁰⁰ with no zero digit.

Solution

We first find a multiple of 5¹⁰⁰⁰ which has no zeros in the last 1000 digits. Suppose that we have a multiple n.5¹⁰⁰⁰ whose last zero is in place r (treating the last place as place 0, the next to last as place 1 and so on). Then n(10^r + 1) has the same digits in places 0 to r-1 and a non-zero digit in place r, and hence no zeros in places 0 to r. So repeating, we find a multiple n.5¹⁰⁰⁰ with no zeros in the last 1000 digits.

Now let m be the remainder when n is divided by 2¹⁰⁰⁰, so n = k.2¹⁰⁰⁰ + m, and hence m.5¹⁰⁰⁰ = n.5¹⁰⁰⁰ - k.10¹⁰⁰⁰. So m.5¹⁰⁰⁰ has the same last 1000 digits as n.5¹⁰⁰⁰. But it has less than 1001 digits, and hence it has exactly 1000 digits and no zeros.

Problem 6

Find all integers x, y satisfying x² + x = y⁴ + y³ + y² + y.

Solution

The only solutions are x,y = -1,1-; 0,-1; -1,0; 0,0; -6,2; or 5,2.

(y² + y/2 - 1/2)(y² + y/2 + 1/2) = y⁴ + y³ + 1/4 y² - 1/4 < y⁴ + y³ + y² + y except for -1 <= y <= -1/3. Also (y² + y/2)(y² + y/2 + 1) = y⁴ + y³ + 5/4 y² + y/2 which is greater than y⁴ + y³ + y² + y unless 0 <= y <= 2.

But no integers are greater than y² + y/2 - 1/2 and less than y² + y/2. So the only possible solutions have y in the range -1 to 2. Checking these 4 cases, we find the solutions listed.

Problem 7

What is the maximum possible length of a sequence of natural numbers x₁, x₂, x₃, ... such that x_i ≤ 1998 for i >= 1, and x_i = |x_i-1 - x_i-2| for i ≥3.

Solution

Answer 2998.

The sequence is completely determined by its first two elements. If the largest element of the sequence is n, then it must occur as one of the first two elements. Because x₃ and x₄ are both smaller than the largest of the first two elements and hence all subsequent elements are too.

Let f(n, m) be the length of the sequence with x₁ = n, x₂ = m. It is straightforward to verify by induction that f(1,2n) = f(2n-1,2n) = 3n + 1, f(2n,1) = f(2n,2n-1) = 3n, f(2n,2n+1) = 3n + 3, f(1,2n+1) = f(2n+1,1) = 3n + 2, f(2n+1,2n) = 3n + 1. A rather more fiddly induction then shows that these are the best possible lengths. Hence the longest sequence with no element more than 1998 is that starting 1, 1998 which has length 2998. 

Problem 8

499 white rooks and a black king are placed on a 1000 x 1000 chess board. The rook and king moves are the same as in ordinary chess, except that taking is not allowed and the king is allowed to remain in check. No matter what the initial situation and no matter how white moves, the black king can always:
(a)  get into check (after some finite number of moves);
(b)  move so that apart from some initial moves, it is always in check after its move;
(c)  move so that apart from some initial moves, it is always in check (even just after white has moved).
Prove or disprove each of (a) - (c).

Solution

(a)  True. Black moves to one end of a main diagonal and then moves along the diagonal to the opposite end. Each of the 499 rooks is in some row. Since black moves through each row, every rook must change row. But each of the rooks is also in some column and so every rook must also change column. A rook cannot change row and column in the same move, so white must make at least 998 moves before black reaches the opposite end of the diagonal. But it cannot start until black is two moves from its starting position, because if it moves a rook into row (or column) one or two earlier, then black is checked or can move into check. So it has only 997 moves available, which is one too few.

(b)  False. Suppose the contrary, that after move n, the king is always in check after its move. Let the corners of the board be A, B, C, D. After move n, white moves all its rooks inside a square side 23 at corner A. The king must now be in the 23 rows between A and B or in the 23 columns between A and D. Suppose the latter. Then white moves all its rooks inside a square side 23 at corner B. This should take 499 moves. However, it could take longer if black used his king to obstruct the move. The worst case would be 3 x 23 additional moves (the king can only obstruct one row of 23 rooks, and each rook in the obstructed row could take 4 moves instead of one to reach its destination.). During this period the king must remain in the 23 rows from A to B or the 23 columns from A to D, since it must remain in check. Thus it cannot get to B by the completion of the process. In fact, it must be at least 999 - 46 (the total number of moves required) - (499 + 69) (the number of moves available) = 385 moves behind.

White now moves all the rooks inside a square side 23 at corner C. The king cannot cut across (or it will be unchecked). It must keep within 23 squares of the edge. So it ends up 770 moves behind (more in fact, since it cannot obstruct the move as effectively). Finally, white moves all the rooks inside a square side 23 at corner D. The king cannot get to the side CD by the time this process is completed. So there is then a lag of over two hundred moves before it can get back into check. Note that it does not help black to change direction. Whatever black does, white ends up with all the rooks at a corner and the king a long way from the two checked sides.

(c)  False. This follows from (b). But we may also use a simpler argument. Take coordinates x = 1 to 1000, y = 1 to 1000. White gets its pieces onto (2,0), (4,0), ... , (998,0). If the king moves onto (2n,*), then white moves its rook from (2n,0) to (2n-1,0), leaving the king unchecked. If the king moves to (2n-1,*) or (2n+1,*), then white moves its rook back to (2n,0), leaving the king unchecked. If the king stays on the line (2n,*), then white fills in time by toggling one of its endmost rooks to an adjacent square (and the king remains unchecked). The only way the black king can escape this repeated unchecking is by moving up to the line y = 0. If it does so, then white transfers all its rooks to the line y = 1000 and repeats the process. The transfer takes 499 moves. It takes black 1000 moves to follow, so during the 501 moves before black catches up, the king is subject to repeated unchecking. 

Problem 9

ABCD is a unit square. One vertex of a rhombus lies on side AB, another on side BC, and a third on side AD. Find the area of the set of all possible locations for the fourth vertex of the rhombus.

Solution

Answer: 2 1/3.

Let the square be ABCD. Let the vertices of the rhombus be P on AB, Q on AD, and R on BC. We require the locus of the fourth vertex S of the rhombus. Suppose P is a distance x from B. We may take x <= 1/2, since the locus for x > 1/2 is just the reflection of the locus for x < 1/2. Then since PR is parallel to QS, S is a distance x from the line AD. Also, by continuity, as Q varies over AD (with P fixed a distance x from B), the locus of S is a line segment.

The two extreme positions for S occur when Q coincides with A and when R coincides with C. When Q coincides with A the rhombus has side 1-x. Hence BR² = (1-x)² - x² = 1 - 2x. In this case SR is parallel to AB, so the distance of S from AB is √(1-2x). When R coincides with C, the rhombus has side √(1+x²), so AQ² = 1 + x² - (1-x)² = 2x. Hence the distance of S from AB is 1 + √(2x).

Thus the locus of S over all possible rhombi is the interior of a curvilinear quadrilateral with vertices MDNC, where M is the midpoint of AB and N is the reflection of M in CD. Moreover the curve from M to C is just the translate of the curve from D to N, for if we put y = 1/2 - x, then √(1-2x) becomes √(2y). Thus if L is the midpoint of CD, then the area in the MLC plus the area in DLN is just 1/2, and the total area of the curvilinear quadrilateral is 1.

However, the arrangement of the vertices discussed above is not the only one. The order of vertices above is PQSR. We could also have PQRS or PSQR. In either case QR is a side rather than a diagonal of the rhombus. We consider the case PQRS (the case PSQR is just the reflection in the line MN). As before it is convenient to keep P fixed, but this time we take x to be the distance AP. Take y to be the distance AQ.

As before we find that S must lie on a line parallel to BC a distance x from it (on the other side to AD). Again we find that for fixed P, the locus of S is a segment of this line. If we assume that AQ > BR, then the two extreme positions are (1) QR parallel to AB, giving S on the line AB, (2) Q at D, giving S a distance x from the line AB. So as x varies from 0 to 1 we get a right-angled triangle sides 1, 1 and √2 and area 1/2. However, we can also have BR > AQ. This gives points below the line AB. The extreme position is with R at C. Suppose QD = y. Then 1 + y² = x² + (1 - y)², so y = x²/2. This gives S a distance y below the line AB. This gives an additional area of 1/6 (by calculus - integrate x²/2 from 0 to 1; I do not see how to do it without).

The triangle and the curvilinear triangle together form a curvilinear triangle area 1/2 + 1/6 = 2/3. There is an identical triangle formed by reflection in MN. Thus the total area is 1 + 2/3 + 2/3 = 2 1/3.

Thanks to Robert Hill and John Jones for pointing out that the original solution missed out the two triangles. 

Problem 10

A natural number k has the property that if k divides n, then the number obtained from n by reversing the order of its digits is also divisible by k. Prove that k is a divisor of 99.

Solution

Let r(m) denote the number obtained from m by reversing the digits.

We show first that k cannot be divisible by 2 or 5. It cannot be divisible by both, for then it ends in a zero and hence r(k) < k and so is not divisible by k (contradiction). So if 5 divides k, then the last digit of k must be 5. Since r(k) is divisible by 5 its last digit must also be 5, so the first digit of k is 5. But now 3k has first digit 1 (3.5 > 10 and 3.6 < 20), so r(3k) has last digit 1 and cannot be divisible by 5. Contradiction. If 2 divides k, then every multiple of k must be even. So the last digit of r(k) must be even and hence the first digit of k must be 2, 4, 6, or 8. If 2, then 5k has first digit 1, so r(2k) is odd. Contradiction. Similarly, if the first digit is 4, 3k has first digit 1; if 6, then 5k has first digit 3; if 8, then 2k has first digit 1. Contradiction. So k is not divisible by 2 or 5.

Suppose k = 10ⁿa_n + ... + a₀. k divides r(k), so a₀ >= 1. Hence (10ⁿ⁺¹ - 1)k = 10²ⁿ⁺¹a_n + ... + 10ⁿ⁺¹a₀ - (10ⁿa_n + ... + a₀) = 10²ⁿ⁺¹a_n + ... + 10ⁿ⁺¹(a₀-1) + 10ⁿc_n + ... + 10c₁ + (c₀+1), where c_i = 9 - a_i. The reverse of this, 10²ⁿ⁺¹(c₀+1) + 10²ⁿc₁ + ... + 10ⁿ⁺¹c_n + 10ⁿ(a₀-1) + ... + a_n, is also divisible by k. So is the reverse of k, 10ⁿa₀ + ... + a_n and hence also their difference: 10ⁿ(10ⁿ⁺¹(c₀+1) + 10ⁿc₁ + ... + 10c_n - 1). k has no factors 2 or 5, so k must divide 10ⁿ⁺¹(c₀+1) + 10ⁿc₁ + ... + 10c_n - 1. Adding 10k, we find that k also divides 10ⁿ⁺² + 10ⁿ9 + ... + 10.9 - 1 = 1099...989 (n - 2 consecutive 9s) = 11(10ⁿ⁺¹ - 1).

We can now carry out exactly the same argument starting with (10ⁿ⁺² - 1)k. This leads to k dividing 10ⁿ⁺²(c₀+1) + ... + 10²c₀ + 10.9 - 1 and hence also 10ⁿ⁺³ + 10ⁿ⁺¹9 + ... + 10²9 + 10.8 + 9 = 11(10ⁿ⁺² - 1). Subtracting 10 times this from the previous number we conclude that k must divide 11(10ⁿ⁺¹ - 1) - 11(10ⁿ⁺¹ - 10) = 99.

Finally, we note that any factor of 99 has the required property. For 3 and 9 divide a number if and only if they divide its digit sum. So if m is divisible by 3 or 9, then the number formed by any rearrangement of its digits is also divisble by 3 or 9. m is divisible by 11 if and only if the difference between the sums of alternate digits is divisible by 11, so if m is divisible by 11, then so is its reverse.

Annotation:  

• The 1st All Russian Mathematical Olympiad was in 1961. In 1967 it was renamed the All Soviet Union Mathematical Olympiad and the numbering restarted, hence 1st ASU 1967. In 1992 it was renamed again as the Commonwealth of Independent States MO and the numbering restarted. But it was not held again. So 1992 was the last year. 
• The problems were intended for schoolchildren aged 14-17. Each year there were two papers of 3 or 4 questions each at three different levels (according to form, roughly ages, 14, 15, 16), but with some overlap between the levels. I can usually do the the easier questions as fast as I can write down the answer, which is almost never true for modern IMO questions. The hardest questions are comparable to the IMO.  
• The years up to 1987 are apparently published in Russian with solutions in Vasilev N B, Egorov A A, The problems of the All-Soviet-Union mathematical competitions, Moscow, Nauka 1988. ISBN 5020137308. Unfortunately, I have not yet been able to get hold of a copy. However, Vladimir Pertsel published a large text file many years ago on the internet containing an English translation of the problems only. Unfortunately, some of the problems were rather hard to understand and I have substantially changed the wording here.
  The years from 1989 to 1992 were published in English with solutions by Arkadii Slinko, USSR Mathematical Olympiads 1989-1992, Australian Mathematical Trust, 1997, ISBN 0646336185. The AMT publishes a series of olympiad problem books, which can be ordered by email.