6th All Soviet Union Mathematical Olympiad 1972 Problems & Solutions

1.  ABCD is a rectangle. M is the midpoint of AD and N is the midpoint of BC. P is a point on the ray CD on the opposite side of D to C. The ray PM intersects AC at Q. Show that MN bisects the angle PNQ.

2.  Given 50 segments on a line show that you can always find either 8 segments which are disjoint or 8 segments with a common point.

3.  Find the largest integer n such that 4²⁷ + 4¹⁰⁰⁰ + 4 ⁿ is a square.

4.  a, m, n are positive integers and a > 1. Show that if a^m + 1 divides aⁿ + 1, then m divides n. The positive integer b is relatively prime to a, show that if a^m + b^m divides aⁿ + bⁿ then m divides n.

5.  A sequence of finite sets of positive integers is defined as follows. S₀ = {m}, where m > 1. Then given S_n you derive S_n+1 by taking k² and k+1 for each element k of S_n. For example, if S₀ = {5}, then S₂ = {7, 26, 36, 625}. Show that S_n always has 2ⁿ distinct elements.

6.  Prove that a collection of squares with total area 1 can always be arranged inside a square of area 2 without overlapping.

7.  O is the point of intersection of the diagonals of the convex quadrilateral ABCD. Prove that the line joining the centroids of ABO and CDO is perpendicular to the line joining the orthocenters of BCO and ADO.

8.  9 lines each divide a square into two quadrilaterals with areas 2/5 and 3/5 that of the square. Show that 3 of the lines meet in a point.

9.  A 7-gon is inscribed in a circle. The center of the circle lies inside the 7-gon. A, B, C are adjacent vertices of the 7-gon show that the sum of the angles at A, B, C is less than 450 degrees.

10.  Two players play the following game. At each turn the first player chooses a decimal digit, then the second player substitutes it for one of the stars in the subtraction | **** - **** |. The first player tries to end up with the largest possible result, the second player tries to end up with the smallest possible result. Show that the first player can always play so that the result is at least 4000 and that the second player can always play so that the result is at most 4000.

11.  For positive reals x, y let f(x, y) be the smallest of x, 1/y, y + 1/x. What is the maximum value of f(x, y)? What are the corresponding x, y?

12.  P is a convex polygon and X is an interior point such that for every pair of vertices A, B, the triangle XAB is isosceles. Prove that all the vertices of P lie on some circle center X.

13.  Is it possible to place the digits 0, 1, 2 into unit squares of 100 x 100 cross-lined paper such that every 3 x 4 (and every 4 x 3) rectangle contains three 0s, four 1s and five 2s?

14.  x₁, x₂, ... , x_n are positive reals with sum 1. Let s be the largest of x₁/(1 + x₁), x₂/(1 + x₁ + x₂), ... , x_n/(1 + x₁ + ... + x_n). What is the smallest possible value of s? What are the corresponding x_i?

15.  n teams compete in a tournament. Each team plays every other team once. In each game a team gets 2 points for a win, 1 for a draw and 0 for a loss. Given any subset S of teams, one can find a team (possibly in S) whose total score in the games with teams in S was odd. Prove that n is even.

[Read More...]

5th All Soviet Union Mathematical Olympiad 1971 Problems & Solutions

1.  Prove that we can find a number divisible by 2ⁿ whose decimal representation uses only the digits 1 and 2.

2.  (1) A₁A₂A₃ is a triangle. Points B₁, B₂, B₃ are chosen on A₁A₂, A₂A₃, A₃A₁ respectively and points D₁, D₂ D₃ on A₃A₁, A₁A₂, A₂A₃ respectively, so that if parallelograms A_iB_iC_iD_i are formed, then the lines A_iC_i concur. Show that A₁B₁·A₂B₂·A₃B₃ = A₁D₁·A₂D₂·A₃D₃. (2) A₁A₂ ... A_n is a convex polygon. Points B_i are chosen on A_iA_i+1 (where we take A_n+1 to mean A₁), and points D_i on A_i-1A_i (where we take A₀ to mean A_n) such that if parallelograms A_iB_iC_iD_i are formed, then the n lines A_iC_i concur. Show that ∏ A_iB_i = ∏ A_iD_i.

3.  (1) Player A writes down two rows of 10 positive integers, one under the other. The numbers must be chosen so that if a is under b and c is under d, then a + d = b + c. Player B is allowed to ask for the identity of the number in row i, column j. How many questions must he ask to be sure of determining all the numbers? (2) An m x n array of positive integers is written on the blackboard. It has the property that for any four numbers a, b, c, d with a and b in the same row, c and d in the same row, a above c (in the same column) and b above d (in the same column) we have a + d = b + c. If some numbers are wiped off, how many must be left for the table to be accurately restored?

4.  Circles, each with radius less than R, are drawn inside a square side 1000R. There are no points on different circles a distance R apart. Show that the total area covered by the circles does not exceed 340,000 R².

5.  You are given three positive integers. A move consists of replacing m ≤ n by 2m, n-m. Show that you can always make a series of moves which results in one of the integers becoming zero. [For example, if you start with 4, 5, 10, then you could get 8, 5, 6, then 3, 10, 6, then 6, 7, 6, then 0, 7, 12.]

6.  The real numbers a, b, A, B satisfy (B - b)² < (A - a)(Ba - Ab). Show that the quadratics x² + ax + b = 0 and x² + Ax + B = 0 have real roots and between the roots of each there is a root of the other.

7.  The projections of a body on two planes are circles. Show that the circles have the same radius.

8.  An integer is written at each vertex of a regular n-gon. A move is to find four adjacent vertices with numbers a, b, c, d (in that order), so that (a - d)(b - c) < 0, and then to interchange b and c. Show that only finitely many moves are possible. For example, a possible sequence of moves is shown below:

1  7  2  3  5  4
1  2  7  3  5  4
1  2  3  7  5  4
1  2  3  5  7  4
2  1  3  5  7  4

9.  A polygon P has an inscribed circle center O. If a line divides P into two polygons with equal areas and equal perimeters, show that it must pass through O.

10.  Given any set S of 25 positive integers, show that you can always find two such that none of the other numbers equals their sum or difference.

11.  A and B are adjacent vertices of a 12-gon. Vertex A is marked - and the other vertices are marked +. You are allowed to change the sign of any n adjacent vertices. Show that by a succession of moves of this type with n = 6 you cannot get B marked - and the other vertices marked +. Show that the same is true if all moves have n = 3 or if all moves have n = 4.

12.  Equally spaced perpendicular lines divide a large piece of paper into unit squares. N squares are colored black. Show that you can always cut out a set of disjoint square pieces of paper, so that all the black squares are removed and the black area of each piece is between 1/5 and 4/5 of its total area.

13.  n is a positive integer. S is the set of all triples (a, b, c) such that 1 ≤ a, b, c, ≤ n. What is the smallest subset X of triples such that for every member of S one can find a member of X which differs in only one position. [For example, for n = 2, one could take X = { (1, 1, 1), (2, 2, 2) }.]

14.  Let f(x, y) = x² + xy + y². Show that given any real x, y one can always find integers m, n such that f(x-m, y-n) <= 1/3. What is the corresponding result if f(x, y) = x² + axy + y² with 0 ≤ a ≤ 2?

15.  A switch has two inputs 1, 2 and two outputs 1, 2. It either connects 1 to 1 and 2 to 2, or 1 to 2 and 2 to 1. If you have three inputs 1, 2, 3 and three outputs 1, 2, 3, then you can use three switches, the first across 1 and 2, then the second across 2 and 3, and finally the third across 1 and 2. It is easy to check that this allows the output to be any permutation of the inputs and that at least three switches are required to achieve this. What is the minimum number of switches required for 4 inputs, so that by suitably setting the switches the output can be any permutation of the inputs? 

Solutions

Problem 1

Prove that we can find a number divisible by 2ⁿ whose decimal representation uses only the digits 1 and 2.

Solution

Induction on n. We claim that we can find N with n digits, all 1 or 2, so that N is divisible by 2ⁿ. True for n = 1: take N = 2. Suppose it is true for n. If 2ⁿ⁺¹ divides N, then since 2ⁿ⁺¹ divides 2 x 10ⁿ it also divides N' obtained from N by placing a 2 in front of it. If 2ⁿ⁺¹ does not divide N, then N = 2ⁿ x odd and 10ⁿ = 2ⁿ x odd, so N + 10ⁿ (in other words the n+1 digit number obtained by placing a 1 in front of N) is divisible by 2ⁿ⁺¹. 

Problem 1

(1) Player A writes down two rows of 10 positive integers, one under the other. The numbers must be chosen so that if a is under b and c is under d, then a + d = b + c. Player B is allowed to ask for the identity of the number in row i, column j. How many questions must he ask to be sure of determining all the numbers?

(2) An m x n array of positive integers is written on the blackboard. It has the property that for any four numbers a, b, c, d with a and b in the same row, c and d in the same row, a above c (in the same column) and b above d (in the same column) we have a + d = b + c. If some numbers are wiped off, how many must be left for the table to be accurately restored?

Solution

(1) is trivial. We can write the condition as b - a = d - c, so the 10 numbers in the first row and 1 in the second row can all be chosen arbitrarily. Hence at least 11 questions are needed. But they are also sufficient. Having determined those numbers, the others immediately follow.

(2). The m+n-1 numbers in the first row and first column can all be chosen arbitrarily, but are sufficient to determine all the numbers. Hence at least m+n-1 numbers must survive.

[Read More...]

4th All Soviet Union Mathematical Olympiad 1970 Problems & Solutions

1.  Given a circle, diameter AB and a point C on AB, show how to construct two points X and Y on the circle such that (1) Y is the reflection of X in the line AB, (2) YC is perpendicular to XA.

2.  The product of three positive numbers is 1, their sum is greater than the sum of their inverses. Prove that just one of the numbers is greater than 1.

3.  What is the greatest number of sides of a convex polygon that can equal its longest diagonal?

4.  n is a 17 digit number. m is derived from n by taking its decimal digits in the reverse order. Show that at least one digit of n + m is even.

5.  A room is an equilateral triangle side 100 meters. It is subdivided into 100 rooms, all equilateral triangles with side 10 meters. Each interior wall between two rooms has a door. If you start inside one of the rooms and can only pass through each door once, show that you cannot visit more than 91 rooms. Suppose now the large triangle has side k and is divided into k² small triangles by lines parallel to its sides. A chain is a sequence of triangles, such that a triangle can only be included once and consecutive triangles have a common side. What is the largest possible number of triangles in a chain?

6.  Given 5 segments such that any 3 can be used to form a triangle. Show that at least one of the triangles is acute-angled.

7.  ABC is an acute-angled triangle. The angle bisector AD, the median BM and the altitude CH are concurrent. Prove that angle A is more than 45 degrees.

8.  Five n-digit binary numbers have the property that every two numbers have the same digits in just m places, but no place has the same digit in all five numbers. Show that 2/5 ≤ m/n ≤ 3/5.

9.  Show that given 200 integers you can always choose 100 with sum a multiple of 100.

10.  ABC is a triangle with incenter I. M is the midpoint of BC. IM meets the altitude AH at E. Show that AE = r, the radius of the inscribed circle.

11.  Given any positive integer n, show that we can find infinitely many integers m such that m has no zeros (when written as a decimal number) and the sum of the digits of m and mn is the same.

12.  Two congruent rectangles of area A intersect in eight points. Show that the area of the intersection is more than A/2.

13.  If the numbers from 11111 to 99999 are arranged in an arbitrary order show that the resulting 444445 digit number is not a power of 2.

14.  S is the set of all positive integers with n decimal digits or less and with an even digit sum. T is the set of all positive integers with n decimal digits or less and an odd digit sum. Show that the sum of the kth powers of the members of S equals the sum for T if 1 ≤ k < n.

15.  The vertices of a regular n-gon are colored (each vertex has only one color). Each color is applied to at least three vertices. The vertices of any given color form a regular polygon. Show that there are two colors which are applied to the same number of vertices. 

Solutions

Problem 1

Given a circle, diameter AB and a point C on AB, show how to construct two points X and Y on the circle such that (1) Y is the reflection of X in the line AB, (2) YC is perpendicular to XA.

Solution

AB is a diameter, so BX is perpendicular to AX and hence parallel to YC. YX is perpendicular to BC, so YC = YB. Hence X and Y lie on the perpendicular bisector of BC. 

Problem 2

The product of three positive numbers is 1, their sum is greater than the sum of their inverses. Prove that just one of the numbers is greater than 1.

Solution

The product of the numbers is 1, so they cannot all be greater than 1 or all less than 1. If all equalled 1, then the sum would not be greater than the sum of the inverses. So we must have either one or two greater than 1. Thus it is sufficient to show that we cannot have two of the numbers greater than 1.

Suppose that a, b > 1. Then since a + b + c > 1/a + 1/b + 1/c, we have a + b + 1/ab > 1/a + 1/b + ab, and hence (1 - 1/a)(1 - 1/b) > (a - 1)(b - 1). Dividing by (a - 1)(b -1) gives ab < 1. Contradiction. 

Problem 2

What is the greatest number of sides of a convex polygon that can equal its longest diagonal?

Solution

Answer: 2, except for the equilateral triangle.

It is easy to find two. Take the two sides to be AB and AC with angle BAC =60 deg, and take the other vertices on the minor arc of the circle center A radius AB between B and C.

Let the longest diagonal have length k. Suppose there are three sides with length k. Extend them (if necessary) so they meet at A, B, C. Suppose ∠A > 60^o. Take the vertices on side AB to be P, Q (where we may have P = A, or Q = B, or both). Take the vertices on side AC to be R, S (where we may have R = A, or S = C, or both). Then AQ ≥ k, AS ≥ k, so QS > k. Contradiction. Hence angle A ≤ 60^o. The same is true for ∠B and ∠C. Hence ∠A = ∠B = ∠C = 60^o. But now QS > k unless A = P = R. Similarly, B and C must be vertices of the convex polygon, so that it is just an equilateral triangle. 

Problem 4

n is a 17 digit number. m is derived from n by taking its decimal digits in the reverse order. Show that at least one digit of n + m is even.

Solution

Let the number be n with digits d₁d₂ ... d₁₇, so that the reversed number n' has digits d₁₇d₁₆ ... d₁. Let the digits of n + n' be a₀a₁ ... a₁₇, where a₀ may be zero. Let the carry forward when adding digits to get a_i be c_i-1, so that, in general, c_i + d_i + d_18-i = a_i + 10 c_i-1. Obviously c_i is 0 or 1.

Suppose all the digits a_i are odd (except that a₀ may be zero). Now c₉ + 2d₉ = a₉ + 10 c₈. Since a₉ is odd, c₉ must be 1. But if we consider c₁₀ + d₁₀ + d₈ = a₁₀ + 10 c₉, we see that since a₁₀ is odd it is at least 1 and hence d₈ + d₁₀ is at least 10. Hence there must be a non-zero carry c₉ in c₁₀ + d₁₀ + d₈ = a₁₀ + 10 c₉ irrespective of the value of c₁₀.

We can now iterate and conclude successively that c₁₂, c₁₄, c₁₆ must be non-zero.

Problem 6

Given 5 segments such that any 3 can be used to form a triangle. Show that at least one of the triangles is acute-angled.

Solution

Let the segments have length a ≤ b ≤ c ≤ d ≤ e. Then if all triangles are obtuse we have e² > c² + d², d² > b² + c², c² > a² + b². Adding e² > a² + 2b² + c² > a² + 3b². But e ≤ a + b, so e² ≤ a² + 2ab + b² ≤ a² + 3b². Contradiction.

Problem 7

ABC is an acute-angled triangle. The angle bisector AD, the median BM and the altitude CH are concurrent. Prove that angle A is more than 45 degrees.

Solution

We use Ceva's theorem. Since AD, BM, CH are concurrent, we have (BD/DC).(CM/MA).(AH/BH) = 1. But CM = MA and since AD is the angle bisector BD/DC = AB/AC, so (AB/AC).(AH/BH) = 1. Hence AH/AC = BH/AB < 1. So angle HAC > angle HCA. But angle AHC = 90 deg, so angle A > 45 deg. 

Problem 13

If the numbers from 11111 to 99999 are arranged in an arbitrary order show that the resulting 444445 digit number is not a power of 2.

Solution

Let the set of numbers be S. Define the function f on S as follows. Replace each digit i in n by 9-i for 0 < i < 9. This gives f(n). Then f( f(n) ) = n, so f is a bijection. The fixed points have only the digits 0 and 9 and so are all divisible by 9. The other points divide into pairs (n, f(n)) and the sum of each pair is divisible by 9. Hence the sum of all the numbers in S is divisible by 9.

[Read More...]

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.

[Read More...]

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.

[Read More...]

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.  

[Read More...]

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.

[Read More...]