2nd All Soviet Union Mathematical Olympiad 1968 Problems & Solutions

1.  An octagon has equal angles. The lengths of the sides are all integers. Prove that the opposite sides are equal in pairs.

2.  Which is greater: 31¹¹ or 17¹⁴? [No calculators allowed!]

3.  A circle radius 100 is drawn on squared paper with unit squares. It does not touch any of the grid lines or pass through any of the lattice points. What is the maximum number of squares it can pass through?

4.  In a group of students, 50 speak English, 50 speak French and 50 speak Spanish. Some students speak more than one language. Prove it is possible to divide the students into 5 groups (not necessarily equal), so that in each group 10 speak English, 10 speak French and 10 speak Spanish.

5.  Prove that:       2/(x² - 1) + 4/(x² - 4) + 6/(x² - 9) + ... + 20/(x² - 100) =

11/((x - 1)(x + 10)) + 11/((x - 2)(x + 9)) + ... + 11/((x - 10)(x + 1)).

6.  The difference between the longest and shortest diagonals of the regular n-gon equals its side. Find all possible n.

7.  The sequence a_n is defined as follows: a₁ = 1, a_n+1 = a_n + 1/a_n for n ≥ 1. Prove that a₁₀₀ > 14.

8.  Given point O inside the acute-angled triangle ABC, and point O' inside the acute-angled triangle A'B'C'. D, E, F are the feet of the perpendiculars from O to BC, CA, AB respectively, and D', E', F' are the feet of the perpendiculars from O' to B'C', C'A', A'B' respectively. OD is parallel to O'A', OE is parallel to O'B' and OF is parallel to O'C'. Also OD·O'A' = OE·O'B' = OF·O'C'. Prove that O'D' is parallel to OA, O'E' to OB and O'F' to OC, and that O'D'·OA = O'E'·OB = O'F'·OC.

9.  Prove that any positive integer not exceeding n! can be written as a sum of at most n distinct factors of n!.

10.  Given a triangle ABC, and D on the segment AB, E on the segment AC, such that AD = DE = AC, BD = AE, and DE is parallel to BC. Prove that BD equals the side of a regular 10-gon inscribed in a circle with radius AC.

11.  Given a regular tetrahedron ABCD, prove that it is contained in the three spheres on diameters AB, BC and AD. Is this true for any tetrahedron?

12. (a)  Given a 4 x 4 array with + signs in each place except for one non-corner square on the perimeter which has a - sign. You can change all the signs in any row, column or diagonal. A diagonal can be of any length down to 1. Prove that it is not possible by repeated changes to arrive at all + signs. (b)  What about an 8 x 8 array?

13.  The medians divide a triangle into 6 smaller triangles. 4 of the circles inscribed in the smaller triangles have equal radii. Prove that the original triangle is equilateral.

14.  Prove that we can find positive integers x, y satisfying x² + x + 1 = py for an infinite number of primes p.

15.  9 judges each award 20 competitors a rank from 1 to 20. The competitor's score is the sum of the ranks from the 9 judges, and the winner is the competitor with the lowest score. For each competitor the difference between the highest and lowest ranking (from different judges) is at most 3. What is the highest score the winner could have obtained?

16.  {a_i} and {b_i} are permutations of {1/1,1/2, ... , 1/n}. a₁ + b₁ ≥ a₂ + b₂ ≥ ... ≥ a_n + b_n. Prove that for every m (1 ≤ m ≤ n) a_m + a_n ≥ 4/m.

17.  There is a set of scales on the table and a collection of weights. Each weight is on one of the two pans. Each weight has the name of one or more pupils written on it. All the pupils are outside the room. If a pupil enters the room then he moves the weights with his name on them to the other pan. Show that you can let in a subset of pupils one at a time, so that the scales change position after the last pupil has moved his weights.

18.  The streets in a city are on a rectangular grid with m east-west streets and n north-south streets. It is known that a car will leave some (unknown) junction and move along the streets at an unknown and possibly variable speed, eventually returning to its starting point without ever moving along the same block twice. Detectors can be positioned anywhere except at a junction to record the time at which the car passes and it direction of travel. What is the minimum number of detectors needed to ensure that the car's route can be reconstructed?

19.  The circle inscribed in the triangle ABC touches the side AC at K. Prove that the line joining the midpoint of AC with the center of the circle bisects the segment BK.

20.  The sequence a₁, a₂, ... , a_n satisfies the following conditions: a₁ = 0, |a_i| = |a_i-1 + 1| for i = 2, 3, ... , n. Prove that (a₁ + a₂ + ... + a_n)/n ≥ -1/2.

21.  The sides and diagonals of ABCD have rational lengths. The diagonals meet at O. Prove that the length AO is also rational. 

Solutions

Problem 1

An octagon has equal angles. The lengths of the sides are all integers. Prove that the opposite sides are equal in pairs.

Solution

Extend the sides to form two rectangles. Let the sides of the octagon have length a, b, c, d, e, f, g, h. Then we can find the rectangle sides. For example, one of the rectangles has opposite sides a + (b + h)/√2 and e + (d + f)/√2. Hence either a = e or √2 = (b + h - d - f)/(a - e). The root is irrational, so we must have a = e. Similarly for the other pairs of opposite sides. 

Problem 2

Which is greater: 31¹¹ or 17¹⁴? [No calculators allowed!]

Solution

17² = 289 > 9.31. So 17¹⁴ > 9⁷ 31⁷. But 3⁷ = 2187 > 31². Hence 17¹⁴ > 31¹¹. 

Problem 3

A circle radius 100 is drawn on squared paper with unit squares. It does not touch any of the grid lines or pass through any of the lattice points. What is the maximum number of squares can it pass through?

Solution

Take compass directions aligned with the grid. Let N, E, S, W be the most northerly, easterly, southerly and westerly points on the circle. The arc from N to E must cross 100 north-south grid lines and 100 east-west grid lines. Each time it crosses a grid line it changes square (and it never crosses two grid lines at once, because it does not pass through any lattice points), so the arc N to E must pass through 200 in addition to the starting square. Similarly for the other 4 arcs. So the circle passes through a total of 800 squares (we count the starting square in the last 200).

Problem 4

In a group of students, 50 speak English, 50 speak French and 50 speak Spanish. Some students speak more than one language. Prove it is possible to divide the students into 5 groups (not necessarily equal), so that in each group 10 speak English, 10 speak French and 10 speak Spanish.

Solution

Let EF denote the number of students speaking English and French. Similarly define ES, FS, E, F, S, EFS. Then ES + EF + E + EFS = 50, EF + FS + F + EFS = 50. Subtracting: ES - F = FS - E. Similarly, ES - F = EF - S.

Pair off members of FS with members of E. Similarly, members of ES with F,and members of EF with S. The resulting pairs have one person speaking each language. If ES = F, then the only remaining students are those in EFS, who speak all three languages. We thus have a collection of units (pairs or individuals) each containing one speaker of each language.

If ES < F, then after the pairing off we are left with equal numbers of members of E, F, and S. These may be formed into triplets, with each triplet containing one speaker of each language. As before we also have the students in EFS. Again, we have partitioned the student body into units with each unit containing one speaker of each language.

If ES > F, then after the pairing off, we are left with an equal number of members of ES, FS and EF. These may be formed into triplets, with each triplet containing two speakers of each language. So, in this case we partition the student body into units with each unit containing either one speaker of each language, or two speakers of each language.

Finally, we may divide the units into 5 groups with 10 speakers of each language in each group.

Problem 5

Prove that:

      2/(x² - 1) + 4/(x² - 4) + 6/(x² - 9) + ... + 20/(x² - 100) =

11/((x - 1)(x + 10)) + 11/((x - 2)(x + 9)) + ... + 11/((x - 10)(x + 1)).

Solution

lhs = 1/(x - 1) - 1/(x + 1) + 1/(x - 2) - 1/(x + 2) + ... + 1/(x + 10) - 1/(x - 10) =

1/(x - 1) - 1/(x + 10) + 1/(x - 2) - 1/(x + 9) + ... + 1/(x - 10) - 1/(x + 1) = rhs. 

Problem 6

The difference between the longest and shortest diagonals of the regular n-gon equals its side. Find all possible n.

Solution

Answer: n = 9.

For n < 6, there is at most one length of diagonal. For n = 6, 7 the longest and shortest, and a side of the n-gon form a triangle, so the difference between the longest and shortest is less than the side.

For n > 7 the side has length 2R sin π/n, the shortest diagonal has length 2R sin 2π/n, and the longest diagonal has length 2R for n even and 2R cos π/2n for n odd (where R is the radius of the circumcircle). Thus we require:

      sin 2π/n + sin π/n = 1 and n even, or

      sin 2π/n + sin π/n = cos π/2n and n odd.

Evidently the lhs is a strictly decreasing function of n and the rhs is an increasing function of n, so there can be at most one solution of each equation. The second equation is satisfied by n = 9, although it is easier to see that there is a quadrilateral with the longest diagonal and shortest diagonals as one pair of opposite sides, and 9-gon sides as the other pair of opposite sides. The angle between the longest side and an adjacent side is 60, so that its length is the length of the shortest diagonal plus 2 x 9-gon side x cos 60. Hence that is the only solution for n odd.

For n = 8 we have the same quadrilateral as for the 9-gon except that the angle is 67.5 and hence the difference is less than 1. For n = 10, sin 2π/10 + sin π/10 = sin π/10 (2 cos π/10 + 1) < 3 sin π/10 < 3 π/10 < 1. So there are no solutions for n even ≥ 10, and hence no solutions for n even.

Problem 7

The sequence a_n is defined as follows: a₁ = 1, a_n+1 = a_n + 1/a_n for n ≥ 1. Prove that a₁₀₀ > 14.

Solution

First we must notice that for 1 ≤ a, b we have a < b, then a + 1/a < b + 1/b. This is basic to any estimation.

The obvious approach is to notice that if a_i ≤ n, then a_i+1 ≥ a_i + 1/n. Hence it takes at most n steps to get from n - 1 to n. Unfortunately, this does not quite work: we need 2 + 3 + ... + 14 = 104 steps to get from 1 to 14.

The trick is to notice that a_n+1² > a_n² + 2. But a₂ = 2, so a_n² > 2n. That gives a₁₀₀² > 200 > 14². 

Problem 8

Given point O inside the acute-angled triangle ABC, and point O' inside the acute-angled triangle A'B'C'. D, E, F are the feet of the perpendiculars from O to BC, CA, AB respectively, and D', E', F' are the feet of the perpendiculars from O' to B'C', C'A', A'B' respectively. OD is parallel to O'A', OE is parallel to O'B' and OF is parallel to O'C'. Also OD·O'A' = OE·O'B' = OF·O'C'. Prove that O'D' is parallel to OA, O'E' to OB and O'F' to OC, and that O'D'·OA = O'E'·OB = O'F'·OC.

Solution

 

Let Γ be the circumcircle of DEF. Let OD, OE, OF meet it again at A", B", C" respectively. Then the figure O'A'B'C' must be similar to OA"B"C". So to prove that OD is parallel to O'A', we have to prove that AO is perpendicular to B"C".

So AO meets B"C" at D". Now since ∠AFC" = 90^o and ∠AD"C" = 90^o, both F and D" lie on the circle diameter AC". Hence AO·OD" = OF·OC". Similarly, BO meets C"A" at E", and CO meets A"B" at F", and BO·OE" = OD·OA" and CO·OF" = OE·OB". Hence OD"·OA = OE"·OB = OF"·OC. So using the similarity, O'D'·OA = O'E'·OB = O'F'·OC.

Problem 9

Prove that any positive integer not exceeding n! can be written as a sum of at most n distinct factors of n!.

Solution

Given m ≤ n! write m = nq + r   (*), with 0 ≤ q, 0 ≤ r < m. Then q ≤ (n-1)!, so q is a sum of at most n-1 distinct factors of (n-1)!. r is itself a factor of n! and is not divisible by n, so (*) expresses m as a sum of at most n distinct factors of n!.

Problem 10

Given a triangle ABC, and D on the segment AB, E on the segment AC, such that AD = DE = AC, BD = AE, and DE is parallel to BC. Prove that BD equals the side of a regular 10-gon inscribed in a circle with radius AC.

Solution

DA = DE, so DAE is isosceles. DE is parallel to BC, so ABC is isosceles, so BA = AC/(2 cos A). Hence BD = AC/(2 cos A) - AC. But AE = 2 AC cos A, so we have an equation for c=cos A: 4 c² + 2c - 1 = 0.

2π/5, 4π/5, 6π/5, 8π/5 and 10π/5 are the roots of: real part of (cos θ + i sin θ)⁵ = 1. Expanding this gives that cos 2π/5, cos 4π/5, cos 6π/5, cos 8π/5 and 1 are the roots of 16c⁵ - 20c³ + 5c - 1 = 0. Dividing by (c - 1) gives 16c⁴ + 16c³ - 4c² - 4c + 1 = (4c² + 2c - 1)². So cos 2π/5 (= cos 8π/5) and cos 4π/5 (= cos 6π/5) are the roots of 4c² + 2c - 1 = 0.

We know that A < 90^o (since A = C and their sum is less than 180^o). Hence A = 2π/5. So BD = 2 AC cos 2π/5 = 2 AC sin π/10, which is the side length for a regular 10-gon inscribed in a circle radius AC. 

Problem 11

Given a regular tetrahedron ABCD, prove that it is contained in the three spheres on diameters AB, BC and AD. Is this true for any tetrahedron?

Solution

Let the tetrahedron have side 1. Then the center O is a distance 1/√8 from the center of each of the spheres, so it is contained in each of the spheres. We now use convexity.

Two circles with diameters two of the sides of a triangle cover the triangle (consider the foot of the altitude to the third side), so faces ABC and ABD are certainly contained in the spheres. Consider face ACD. The sphere on BC passes through the midpoints of AC and CD, and through C, so it contains the triangle formed by these three points (by convexity). But the rest of ACD is contained in the sphere on AD. Similarly for the face BCD. Hence all the faces are contained in the spheres. But now take any point P inside the tetrahedron. Extend OP to meet a face at X. X lies in one of the spheres, but O also lies in the sphere and hence all points on OX, including P (by convexity).

False in general. Take ABCD to be a plane square, then no points on CD are in the spheres except C and D (and we can obviously distort this slightly to make it less degenerate). 

Problem 12

(a)  Given a 4 x 4 array with + signs in each place except for one non-corner square on the perimeter which has a - sign. You can change all the signs in any row, column or diagonal. A diagonal can be of any length down to 1. Prove that it is not possible by repeated changes to arrive at all + signs.

(b)  What about an 8 x 8 array?

Solution

(a)   Let S be the set of the 8 positions on the perimeter not at a corner. Any move changes the sign of either 2 or 0 of the members of S. We start with an odd number of members of S with a minus sign, so we must always have an odd number of members of S with a minus sign and hence cannot get all plus signs.

(b)   Also impossible. The same argument works.

Problem 13

The medians divide a triangle into 6 smaller triangles. 4 of the circles inscribed in the smaller triangles have equal radii. Prove that the original triangle is equilateral.

Solution

Denote the side lengths by a, b, c and the corresponding median lengths by m_a, m_b, m_c. The six small triangles all have equal area. [Let the areas be t₁, ... , t₆. It is obvious that the adjacent pairs have equal height and equal base, so we have t₁ = t₂, t₃ = t₄, t₅ = t₆. The three on each side of a median sum to the same area, so t₁ + t₂ + t₃ = t₄ + t₅ + t₆, t₁ + t₅ + t₆ = t₂ + t₃ + t₄. Subtracting gives t₁ = t₄. Similarly, t₂ = t₅ and we are home.] So by the usual result that the twice area of a triangle equals its perimeter times its in-radius, we conclude that the perimeters of four of the small triangles are equal.

Two of them must share a side of the original triangle. Suppose it is a. Then we have: a/2 + m_a/3 + 2m_b/3 = a/2 + m_a/3 + 2m_c/3. So m_b = m_c. That implies that b = c. [Because the triangle formed by the centroid and side a is isosceles, so the median is perpendicular to the side, so the main triangle is isosceles.]

Using the facts that b = c and m_b = m_c, we see that two of the remaining small triangles have perimeter b/2 + m_b and two have perimeter b/2 + m_b/3 + 2m_a/3. So there are two cases to consider. In the first case a/2 - m_a/3 = b/2 - m_b/3. That implies a = b, since if a < b, m_a > m_b (consider the triangle formed by the centroid and the side c). So the triangle is equilateral.

The second case is harder. We have: a/2 + m_a/3 + 2m_b/3 = b/2 + m_b, and hence a/2 + m_a/3 = b/2 + m_b/3 (*). Take the angle between a and b to be q. Then m_a = b sin q, a =2b cos q, and m_b² = b²/4 + a² - ab cos q = b²/4 + 2b² cos²q. We can now use (*) to get an equation for q. First we square (*) to get: m_b² = (3a/2 - 3b/2 + m_a)². We divide out the factor b² to get: 1/4 + 2 cos²q = 3 1/4 + 8 cos²q - 9 cos q + 3 sin q(2 cos q - 1). Squaring, so that we can use sin²q = 1 - cos²q, and writing c = cos q, we get: (1 - c²)(4c² - 4c + 1) = 4c⁴ - 12c³ + 13c² - 6c + 1. Hence 8c⁴ - 16c³ + 10c² - 2c = 0. Factorizing: c(c - 1)(2c - 1)² = 0. c = 0 and c = 1 give degenerate triangles, so we must have c = 1/2 and hence the triangle is equilateral. 

Problem 14

Prove that we can find positive integers x, y satisfying x² + x + 1 = py for an infinite number of primes p.

Solution

This is a trivial variant on the proof that there are an infinite number of primes. Suppose that we can only find x, y for a finite number of primes p₁, p₂, ... , p_n. Set x = p₁p₂...p_n. Then none of the p_i can divide x(x+1) + 1. But it must have prime factors. Contradiction. 

Problem 15

9 judges each award 20 competitors a rank from 1 to 20. The competitor's score is the sum of the ranks from the 9 judges, and the winner is the competitor with the lowest score. For each competitor the difference between the highest and lowest ranking (from different judges) is at most 3. What is the highest score the winner could have obtained?

Solution

Answer: 24.

At most 4 competitors can receive a rank 1. For a competitor with a rank 1 can only receive ranks 1, 2, 3 or 4. There are only 36 such ranks available and each competitor with a rank 1 needs 9 of them.

If only one competitor receives a rank 1, then his score is 9. If only 2 competitors receive a rank 1, then one of them must receive at least five rank 1s. His maximum score is then 5.1 + 4.4 = 21. If 4 competitors receive a rank 1, then they must use all the 36 ranks 1, 2, 3, and 4. The total score available is thus 9(1 + 2 + 3 + 4) = 90, so at least one competitor must receive 22 or less. Thus the winner's maximum score is at most 22. If 3 competitors receive a rank 1, then the winner's score is maximised by giving all three competitors the same score and letting them share the 27 ranks 1, 3 and 4. That gives a winner's score of 9(1 + 3 + 4)/3 = 24. That can be achieved in several ways, for example: each competitor gets 3 1s, 3 3s and 3 4s, or one competitor gets 4 1s and 5 4s, another gets 3 1s, 3 3s and 3 4s, another gets 2 1s 6 3s and one 4. Note that it is trivial to arrange ranks for the remaining 17 competitors. For example: give one 5 2s and 4 5s total 30, one 4 2s and 5 5s total 33, and then one 9 6s, one 9 7s and so on.

Thus the answer is 24, with three joint winners. If there is required to be a single winner, then the answer is 23.