15th All Soviet Union Mathematical Olympiad Problems 1981

1.  A chess board is placed on top of an identical board and rotated through 45 degrees about its center. What is the area which is black in both boards?

2.  AB is a diameter of the circle C. M and N are any two points on the circle. The chord MA' is perpendicular to the line NA and the chord MB' is perpendicular to the line NB. Show that AA' and BB' are parallel.

3.  Find an example of m and n such that m is the product of n consecutive positive integers and also the product of n+2 consecutive positive integers. Show that we cannot have n = 2.

4.  Write down a row of arbitrary integers (repetitions allowed). Now construct a second row as follows. Suppose the integer n is in column k in the first row. In column k in the second row write down the number of occurrences of n in row 1 in columns 1 to k inclusive. Similarly, construct a third row under the second row (using the values in the second row), and a fourth row. An example follows:

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

Show that the fourth row is always the same as the second row.

5.  Let S be the set of points (x, y) given by y ≤ - x² and y ≥ x² - 2x + a. Find the area of the rectangle with sides parallel to the axes and the smallest possible area which encloses S.

6.  ABC, CDE, EFG are equilateral triangles (not necessarily the same size). The vertices are counter-clockwise in each case. A, D, G are collinear and AD = DG. Show that BFD is equilateral.

7.  1000 people live in a village. Every evening each person tells his friends all the news he heard during the day. All news eventually becomes known (by this process) to everyone. Show that one can choose 90 people, so that if you give them some news on the same day, then everyone will know in 10 days.

8.  The reals a and b are such that a cos x + b cos 3x > 1 has no real solutions. Show that |b| ≤ 1.

9.  ABCD is a convex quadrilateral. K is the midpoint of AB and M is the midpoint of CD. L lies on the side BC and N lies on the side AD. KLMN is a rectangle. Show that its area is half that of ABCD.

10.  The sequence a_n of positive integers is such that (1) a_n ≤ n^3/2 for all n, and (2) m-n divides k_m - k_n (for all m > n). Find a_n.

11.  Is it possible to color half the cells in a rectangular array white and half black so that in each row and column more than 3/4 of the cells are the same color?

12.  ACPH, AMBE, AHBT, BKXM and CKXP are parallelograms. Show that ABTE is also a parallelogram (vertices are labeled anticlockwise).

13.  Find all solutions (x, y) in positive integers to x³ - y³ = xy + 61.

14.  Eighteen teams are playing in a tournament. So far, each team has played exactly eight games, each with a different opponent. Show that there are three teams none of which has yet played the other.

15.  ABC is a triangle. A' lies on the side BC with BA'/BC = 1/4. Similarly, B' lies on the side CA with CB'/CA = 1/4, and C' lies on the side AB with AC'/AB = 1/4. Show that the perimeter of A'B'C' is between 1/2 and 3/4 of the perimeter of ABC.

16.  The positive reals x, y satisfy x³ + y³= x - y. Show that x² + y² < 1.

17.  A convex polygon is drawn inside the unit circle. Someone makes a copy by starting with one vertex and then drawing each side successively. He copies the angle between each side and the previous side accurately, but makes an error in the length of each side of up to a factor 1±p. As a result the last side ends up a distance d from the starting point. Show that d < 4p.

18.  An integer is initially written at each vertex of a cube. A move is to add 1 to the numbers at two vertices connected by an edge. Is it possible to equalise the numbers by a series of moves in the following cases? (1) The initial numbers are (1) 0, except for one vertex which is 1. (2) The initial numbers are 0, except for two vertices which are 1 and diagonally opposite on a face of the cube. (3) Initially, the numbers going round the base are 1, 2, 3, 4. The corresponding vertices on the top are 6, 7, 4, 5 (with 6 above the 1, 7 above the 2 and so on).

19.  Find 21 consecutive integers, each with a prime factor less than 17.

20.  Each of the numbers from 100 to 999 inclusive is written on a separate card. The cards are arranged in a pile in random order. We take cards off the pile one at a time and stack them into 10 piles according to the last digit. We then put the 1 pile on top of the 0 pile, the 2 pile on top of the 1 pile and so on to get a single pile. We now take them off one at a time and stack them into 10 piles according to the middle digit. We then consolidate the piles as before. We then take them off one at a time and stack them into 10 piles according to the first digit and finally consolidate the piles as before. What can we say about the order in the final pile?

21.  Given 6 points inside a 3 x 4 rectangle, show that we can find two points whose distance does not exceed √5.

22.  What is the smallest value of 4 + x²y⁴ + x⁴y² - 3x²y² for real x, y? Show that the polynomial cannot be written as a sum of squares. [Note the candidates did not know calculus.]

23.  ABCDEF is a prism. Its base ABC and its top DEF are congruent equilateral triangles. The side edges are AD, BE and CF. Find all points on the base wich are equidistant from the three lines AE, BF and CD.

[more...]

14th All Soviet Union Mathematical Olympiad Problems 1980

1.  All two digit numbers from 19 to 80 inclusive are written down one after the other as a single number N = 192021...7980. Is N divisible by 1980?

2.  A square is divided into n parallel strips (parallel to the bottom side of the square). The width of each strip is integral. The total width of the strips with odd width equals the total width of the strips with even width. A diagonal of the square is drawn which divides each strip into a left part and a right part. Show that the sum of the areas of the left parts of the odd strips equals the sum of the areas of the right parts of the even strips.

3.  35 containers of total weight 18 must be taken to a space station. One flight can take any collection of containers weighing 3 or less. It is possible to take any subset of 34 containers in 7 flights. Show that it must be possible to take all 35 containers in 7 flights.

4.  ABCD is a convex quadrilateral. M is the midpoint of BC and N is the midpoint of CD. If k = AM + AN show that the area of ABCD is less than k²/2.

5.  Are there any solutions in positive integers to a⁴ = b³ + c²?

6.  Given a point P on the diameter AC of the circle K, find the chord BD through P which maximises the area of ABCD.

7.  There are several settlements around Big Lake. Some pairs of settlements are directly connected by a regular shipping service. For all A ≠ B, settlement A is directly connected to X iff B is not directly connected to Y, where B is the next settlement to A counterclockwise and Y is the next settlement to X counterclockwise. Show that you can move between any two settlements with at most 3 trips.

8.  A six digit (decimal) number has six different digits, none of them 0, and is divisible by 37. Show that you can obtain at least 23 other numbers which are divisible by 37 by permuting the digits.

9.  Find all real solutions to:

sin x + 2 sin(x+y+z) = 0

sin y + 3 sin(x+y+z) = 0

sin z + 4 sin(x+y+z) = 0

10.  Given 1980 vectors in the plane. The sum of every 1979 vectors is a multiple of the other vector. Not all the vectors are multiples of each other. Show that the sum of all the vectors is zero.

11.  Let f(n) be the sum of n and its digits. For example, f(34) = 41. Is there an integer such that f(n) = 1980? Show that given any positive integer m we can find n such that f(n) = m or m+1.

12.  Some unit squares in an infinite sheet of squared paper are colored red so that every 2 x 3 and 3 x 2 rectangle contains exactly two red squares. How many red squares are there in a 9 x 11 rectangle?

13.  There is a flu epidemic in elf city. The course of the disease is always the same. An elf is infected one day, he is sick the next, recovered and immune the third, recovered but not immune thereafter. Every day every elf who is not sick visits all his sick friends. If he is not immune he is sure to catch flu if he visits a sick elf. On day 1 no one is immune and one or more elves are infected from some external source. Thereafter there is no further external infection and the epidemic spreads as described above. Show that it is sure to die out (irrespective of the number of elves, the number of friends each has, and the number infected on day 1). Show that if one or more elves is immune on day 1, then it is possible for the epidemic to continue indefinitely.

14.  Define the sequence a_n of positive integers as follows. a₁ = m. a_n+1 = a_n plus the product of the digits of a_n. For example, if m = 5, we have 5, 10, 10, ... . Is there an m for which the sequence is unbounded?

15.  ABC is equilateral. A line parallel to AC meets AB at M and BC at P. D is the center of the equilateral triangle BMP. E is the midpoint of AP. Find the angles of DEC.

16.  A rectangular box has sides x < y < z. Its perimeter is p = 4(x + y + z), its surface area is s = 2(xy + yz + zx) and its main diagonal has length d = √(x² + y² + z²). Show that 3x < (p/4 - √(d² - s/2) and 3z > (p/4 + √(d² - s/2).

17.  S is a set of integers. Its smallest element is 1 and its largest element is 100. Every element of S except 1 is the sum of two distinct members of the set or double a member of the set. What is the smallest possible number of integers in S?

18.  Show that there are infinitely many positive integers n such that [a^3/2] + [b^3/2] = n has at least 1980 integer solutions.

19.  ABCD is a tetrahedron. Angles ACB and ADB are 90 deg. Let k be the angle between the lines AC and BD. Show that cos k < CD/AB.

20.  x₀ is a real number in the interval (0, 1) with decimal representation 0.d₁d₂d₃... . We obtain the sequence x_n as follows. x_n+1 is obtained from x_n by rearranging the 5 digits d_n+1, d_n+2, d_n+3, d_n+4, d_n+5. Show that the sequence x_n converges. Can the limit be irrational if x₀ is rational? Find a number x₀ so that every member of the sequence is irrational, no matter how the rearrangements are carried out.

[more...]

13th All Soviet Union Mathematical Olympiad Problems 1979

1.  T is an isosceles triangle. Another isosceles triangle T' has one vertex on each side of T. What is the smallest possible value of area T'/area T?

2.  A grasshopper hops about in the first quadrant (x, y >= 0). From (x, y) it can hop to (x+1, y-1) or to (x-5, y+7), but it can never leave the first quadrant. Find the set of points (x, y) from which it can never get further than a distance 1000 from the origin.

3.  In a group of people every person has less than 4 enemies. Assume that A is B's enemy iff B is A's enemy. Show that we can divide the group into two parts, so that each person has at most one enemy in his part.

4.  Let S be the set {0, 1}. Given any subset of S we may add its arithmetic mean to S (provided it is not already included - S never includes duplicates). Show that by repeating this process we can include the number 1/5 in S. Show that we can eventually include any rational number between 0 and 1.

5.  The real sequence x₁ ≥ x₂ ≥ x₃ ≥ ... satisfies x₁ + x₄/2 + x₉/3 + x₁₆/4 + ... + x_N/n ≤ 1 for every square N = n². Show that it also satisfies x₁ + x₂/2 + x₃ /3 + ... + x_n/n ≤ 3.

6.  Given a finite set X of points in the plane. S is a set of vectors AB where (A, B) are some pairs of points in X. For every point A the number of vectors AB (starting at A) in S equals the number of vectors CA (ending at A) in S. Show that the sum of the vectors in S is zero.

7.  What is the smallest number of pieces that can be placed on an 8 x 8 chessboard so that every row, column and diagonal has at least one piece? [A diagonal is any line of squares parallel to one of the two main diagonals, so there are 30 diagonals in all.] What is the smallest number for an n x n board?

8.  a and b are real numbers. Find real x and y satisfying: (x - y (x² - y²)^1/2 = a(1 - x² + y²)^1/2 and (y - x (x² - y²)^1/2 = b(1 - x² + y²)^1/2.

9.  A set of square carpets have total area 4. Show that they can cover a unit square.

10.  x_i are real numbers between 0 and 1. Show that (x₁ + x₂ + ... + x_n + 1)² ≥ 4(x₁² + x₂² + ... + x_n²).

11.  m and n are relatively prime positive integers. The interval [0, 1] is divided into m + n equal subintervals. Show that each part except those at each end contains just one of the numbers 1/m, 2/m, 3/m, ... , (m-1)/m, 1/n, 2/n, ... , (n-1)/n.

12.  Given a point P in space and 1979 lines L₁, L₂, ... , L₁₉₇₉ containing it. No two lines are perpendicular. P₁ is a point on L₁. Show that we can find a point A_n on L_n (for n = 2, 3, ... , 1979) such that the following 1979 pairs of lines are all perpendicular: A_n-1A_n+1 and L_n for n = 1, ... , 1979. [We regard A_-1 as A₁₉₇₉ and A₁₉₈₀ as A₁.]

13.  Find a sequence a₁, a₂, ... , a₂₅ of 0s and 1s such that the following sums are all odd:

a1a1 + a2a2 + ... + a25a25
a1a2 + a2a3 + ... + a24a25
a1a3 + a2a4 + ... + a23a25
...
a1a24 + a2a25
a1a25

Show that we can find a similar sequence of n terms for some n > 1000.

14.  A convex quadrilateral is divided by its diagonals into four triangles. The incircles of each of the four are equal. Show that the quadrilateral has all its sides equal.

15.  [unclear]

[more...]

12th All Soviet Union Mathematical Olympiad Problems 1978

1.  a_n is the nearest integer to √n. Find 1/a₁ + 1/a₂ + ... + 1/a₁₉₈₀.

2.  ABCD is a quadrilateral. M is a point inside it such that ABMD is a parallelogram. ∠CBM = ∠CDM. Show that ∠ACD = ∠BCM.

3.  Show that there is no positive integer n for which 1000ⁿ - 1 divides 1978ⁿ - 1.

4.  If P, Q are points in space the point [PQ] is the point on the line PQ on the opposite side of Q to P and the same distance from Q. K₀ is a set of points in space. Given K_n we derive K_n+1 by adjoining all the points [PQ] with P and Q in K_n. (1) K₀ contains just two points A and B, a distance 1 apart, what is the smallest n for which K_n contains a point whose distance from A is at least 1000?

(2) K₀ consists of three points, each pair a distance 1 apart, find the area of the smallest convex polygon containing K_n.

(3) K₀ consists of four points, forming a regular tetrahedron with volume 1. Let H_n be the smallest convex polyhedron containing K_n. How many faces does H₁ have? What is the volume of H_n?

5.  Two players play a game. There is a heap of m tokens and a heap of n < m tokens. Each player in turn takes one or more tokens from the heap which is larger. The number he takes must be a multiple of the number in the smaller heap. For example, if the heaps are 15 and 4, the first player may take 4, 8 or 12 from the larger heap. The first player to clear a heap wins. Show that if m > 2n, then the first player can always win. Find all k such that if m > kn, then the first player can always win.

6.  Show that there is an infinite sequence of reals x₁, x₂, x₃, ... such that |x_n| is bounded and for any m > n, we have |x_m - x_n| > 1/(m - n).

7.  Let p(x) = x² + x + 1. Show that for every positive integer n, the numbers n, p(n), p(p(n)), p(p(p(n))), ... are relatively prime.

8.  Show that for some k, you can find 1978 different sizes of square with all its vertices on the graph of the function y = k sin x.

9.  The set S₀ has the single member (5, 19). We derive the set S_n+1 from S_n by adjoining a pair to S_n. If S_n contains the pair (2a, 2b), then we may adjoin the pair (a, b). If S contains the pair (a, b) we may adjoin (a+1, b+1). If S contains (a, b) and (b, c), then we may adjoin (a, c). Can we obtain (1, 50)? (1, 100)? If We start with (a, b), with a < b, instead of (5, 19), for which n can we obtain (1, n)?

10.  An n-gon area A is inscribed in a circle radius R. We take a point on each side of the polygon to form another n-gon. Show that it has perimeter at least 2A/R.

11.  Two players play a game by moving a piece on an n x n chessboard. The piece is initially in a corner square. Each player may move the piece to any adjacent square (which shares a side with its current square), except that the piece may never occupy the same square twice. The first player who is unable to move loses. Show that for even n the first player can always win, and for odd n the second player can always win. Who wins if the piece is initially on a square adjacent to the corner?

12.  Given a set of n non-intersecting segments in the plane. No two segments lie on the same line. Can we successively add n-1 additional segments so that we end up with a single non-intersecting path? Each segment we add must have as its endpoints two existing segment endpoints.

13.  a and b are positive real numbers. x_i are real numbers lying between a and b. Show that (x₁ + x₂ + ... + x_n)(1/x₁ + 1/x₂ + ... + 1/x_n) ≤ n²(a + b)²/4ab.

14.  n > 3 is an integer. Let S be the set of lattice points (a, b) with 0 ≤ a, b < n. Show that we can choose n points of S so that no three chosen points are collinear and no four chosen points from a parallelogram.

15.  Given any tetrahedron, show that we can find two planes such that the areas of the projections of the tetrahedron onto the two planes have ratio at least √2.

16.  a₁, a₂, ... , a_n are real numbers. Let b_k = (a₁ + a₂ + ... + a_k)/k for k = 1, 2, ... , n. Let C = (a₁ - b₁)² + (a₂ - b₂)² + ... + (a_n - b_n)², and D = (a₁ - b_n)² + (a₂ - b_n)² + ... + (a_n - b_n)². Show that C ≤ D ≤ 2C.

17.  Let x_n = (1 + √2 + √3)ⁿ. We may write x_n = a_n + b_n√2 + c_n√3 + d_n√6, where a_n, b_n, c_n, d_n are integers. Find the limit as n tends to infinity of b_n/a_n, c_n/a_n, d_n/a_n.

[more...]

10th All Soviet Union Mathematical Olympiad Problems 1976

1.  50 watches, all keeping perfect time, lie on a table. Show that there is a moment when the sum of the distances from the center of the table to the center of each dial equals the sum of the distances from the center of the table to the tip of each minute hand.

2.  1000 numbers are written in line 1, then further lines are constructed as follows. If the number m occurs in line n, then we write under it in line n+1, each time it occurs, the number of times that m occurs in line n. Show that lines 11 and 12 are identical. Show that we can choose numbers in line 1, so that lines 10 and 11 are not identical.

3.  (1) The circles C₁, C₂, C₃ with equal radius all pass through the point X. C_i and C_j also intersect at the point Y_ij. Show that angle XO₁Y₁₂ + angle XO₂Y₂₃ + angle XO₃Y₃₁ = 180 deg, where O_i is the center of circle C_i.

4.  a₁ and a₂ are positive integers less than 1000. Define a_n = min{ |a_i - a_j| : 0 < i < j < n}. Show that a₂₁ = 0.

5.  Can you label each vertex of a cube with a different three digit binary number so that the numbers at any two adjacent vertices differ in at least two digits?

6.  a, b, c, d are vectors in the plane such that a + b + c + d = 0. Show that |a| + |b| + |c| + |d| ≥ |a + d| + |b + d| + |c + d|.

7.  S is a set of 1976 points which form a regular 1976-gon. T is the set of all points which are the midpoint of at least one pair of points in S. What is the greatest number of points of T which lie on a single circle?

8.  n rectangles are drawn on a rectangular sheet of paper. Each rectangle has its sides parallel to the sides of the paper. No pair of rectangles has an interior point in common. If the rectangles were removed show that the rest of the sheet would be in at most n+1 parts.

9.  There are three straight roads. On each road a man is walking at constant speed. At time t = 0, the three men are not collinear. Prove that they will be collinear for t > 0 at most twice.

10.  Initially, there is one beetle on each square in the set S. Suddenly each beetle flies to a new square, subject to the following conditions: (1) the new square may be the same as the old or different; (2) more than one beetle may choose the same new square; (3) if two beetles are initially in squares with a common vertex, then after the flight they are either in the same square or in squares with a common vertex. Suppose S is the set of all squares in the middle row and column of a 99 x 99 chess board, is it true that there must always be a beetle whose new square shares a vertex with its old square (or is identical with it)? What if S also includes all the border squares (so S is rows 1, 50 and 99 and columns 1, 50 and 99)? What if S is all squares of the board?

11.  Call a triangle big if each side is longer than 1. Show that we can draw 100 big triangles inside an equilateral triangle with side length 5 so that all the triangles are disjoint. Show that you can draw 100 big triangles with every vertex inside or on an equilateral triangle with side 3, so that they cover the equilateral triangle, and any two big triangles either (1) are disjoint, or (2) have as intersection a common vertex, or (3) have as intersection a common side.

12.  n is a positive integer. A universal sequence of length m is a sequence of m integers each between 1 and n such that one can obtain any permutation of 1, 2, ... , n by deleting suitable members of the sequence. For example, 1, 2, 3, 1, 2, 1, 3 is a universal sequence of length 7 for n = 3. But 1, 2, 3, 2, 1, 3, 1 is not universal, because one cannot obtain the permutation 3, 1, 2. Show that one can always obtain a universal sequence for n of length n² - n + 1. Show that a universal sequence for n must have length at least n(n + 1)/2. Show that the shortest sequence for n = 4 has 12 members. [You are told, but do not have to prove, that there is a universal sequence for n of length n² - 2n + 4.]

13.  n real numbers are written around a circle. One of the numbers is 1 and the sum of the numbers is 0. Show that there are two adjacent numbers whose difference is at least n/4. Show that there is a number which differs from the arithmetic mean of its two neighbours by at least 8/n². Improve this result to some k/n² with k > 8. Show that for n = 30, we can take k = 1800/113. Give an example of 30 numbers such that no number differs from the arithmetic mean of its two neighbours by more than 2/113.

14.  You are given a regular n-gon. Each vertex is marked +1 or -1. A move consists of changing the sign of all the vertices which form a regular k-gon for some 1 < k <= n. [A regular 2-gon means two vertices which have the center of the n-gon as their midpoint.]. For example, if we label the vertices of a regular 6-gon 1, 2, 3, 4, 5, 6, then you can change the sign of {1, 4}, {2, 5}, {3, 6}, {1, 3, 5}, {2, 4, 6} or {1, 2, 3, 4, 5, 6}. Show that for (1) n = 15, (2) n = 30, (3) any n > 2, we can find some initial marking which cannot be changed to all +1 by any series of moves. Let f(n) be the largest number of markings, so that no one can be obtained from any other by any series of moves. Show that f(200) = 2⁸⁰.

15.  S is a sphere with unit radius. P is a plane through the center. For any point x on the sphere f(x) is the perpendicular distance from x to P. Show that if x, y, z are the ends of three mutually perpendicular radii, then f(x)² + f(y)² + f(z)² = 1 (*). Now let g(x) be any function on the points of S taking non-negative real values and satisfying (*). Regard the intersection of P and S as the equator, the poles as the points with f(x) = 1 and lines of longitude as semicircles through both poles. (1) If x and y have the same longitude and both lie on the same side of the equator with x closer to the pole, show that g(x) > g(y). (2) Show that for any x, y on the same side of the equator with x closer to the pole than y we have g(x) > g(y). (3) Show that if x and y are the same distance from the pole then g(x) = g(y). (4) Show that g(x) = f(x) for all x.

[more...]

11th All Soviet Union Mathematical Olympiad Problems 1977

1.  P is a polygon. Its sides do not intersect except at its vertices, and no three vertices lie on a line. The pair of sides AB, PQ is called special if (1) AB and PQ do not share a vertex and (2) either the line AB intersects the segment PQ or the line PQ intersects the segment AB. Show that the number of special pairs is even.

2.  n points lie in the plane, not all on a single line. A real number is assigned to each point. The sum of the numbers is zero for all the points lying on any line. Show that all the assigned numbers must be zero.

3.  (1) The triangle ABC is inscribed in a circle. D is the midpoint of the arc BC (not containing A), similarly E and F. Show that the hexagon formed by the intersection of ABC and DEF has its main diagonals parallel to the sides of ABC and intersecting in a single point. (2) EF meets AB at X and AC at Y. Prove that AXIY is a rhombus, where I is the center of the circle inscribed in ABC.

4.  Black and white tokens are placed around a circle. First all the black tokens with one or two white neighbors are removed. Then all white tokens with one or two black neighbors are removed. Then all black tokens with one or two white neighbors and so on until all the tokens have the same color. Is it possible to arrange 40 tokens so that only one remains after 4 moves? What is the minimum possible number of moves to go from 1000 tokens to one?

5.  a_n is an infinite sequence such that (a_n+1 - a_n)/2 tends to zero. Show that a_n tends to zero.

6.  There are direct routes between every two cities in a country. The fare between each pair of cities is the same in both directions. Two travellers decide to visit all the cities. The first traveller starts at a city and travels to the city with the most expensive fare (or if there are several such, any one of them). He then repeats this process, never visiting a city twice, until he has been to all the cities (so he ends up in a different city from the one he starts from). The second traveller has a similar plan, except that he always chooses the cheapest fare, and does not necessarily start at the same city. Show that the first traveller spends at least as much on fares as the second.

7.  Each vertex of a convex polyhedron has three edges. Each face is a cyclic polygon. Show that its vertices all lie on a sphere.

8.  Given a polynomial x₁₀ + a₉x⁹ + ... + a₁x + 1. Two players alternately choose one of the coefficients a₁ to a₉ (which has not been chosen before) and assign a real value to it. The first player wins iff the resulting polynomial has no real roots. Who wins?

9.  Seven elves sit at a table. Each elf has a cup. In total the cups contain 3 liters of milk. Each elf in turn gives all his milk to the others in equal shares. At the end of the process each elf has the same amount of milk as at the start. What was that?

10.  We call a number doubly square if (1) it is a square with an even number 2n of (decimal) digits, (2) its first n digits form a square, (3) its last n digits form a non-zero square. For example, 1681 is doubly square, but 2500 is not. (1) find all 2-digit and 4-digit doubly square numbers. (2) Is there a 6-digit doubly square number? (3) Show that there is a 20-digit doubly square number. (4) Show that there are at least ten 100-digit doubly square numbers. (5) Show that there is a 30-digit doubly square number.

11.  Given a sequence a₁, a₂, ... , a_n of positive integers. Let S be the set of all sums of one or more members of the sequence. Show that S can be divided into n subsets such that the smallest member of each subset is at least half the largest member.

12.  You have 1000 tickets numbered 000, 001, ... , 999 and 100 boxes numbered 00, 01, ... , 99. You may put each ticket into any box whose number can be obtained from the ticket number by deleting one digit. Show that you can put every ticket into 50 boxes, but not into less than 50. Show that if you have 10000 4-digit tickets and you are allowed to delete two digits, then you can put every ticket into 34 boxes. For n+2 digit tickets, where you delete n digits, what is the minimum number of boxes required?

13.  Given a 100 x 100 square divided into unit squares. Several paths are drawn. Each path is drawn along the sides of the unit squares. Each path has its endpoints on the sides of the big square, but does not contain any other points which are vertices of unit squares and lie on the big square sides. No path intersects itself or any other path. Show that there is a vertex apart from the four corners of the big square that is not on any path.

14.  The positive integers a₁, a₂, ... , a_m, b₁, b₂, ... , b_n satisfy: (a₁ + a₂ + ... + a_m) = (b₁ + b₂ + ... + b_n) < mn. Show that we can delete some (but not all) of the numbers so that the sum of the remaining a's equals to the sum of the remaining b's.

15.  Given 1000 square plates in the plane with their sides parallel to the coordinate axes (but possibly overlapping and possibly of different sizes). Let S be the set of points covered by the plates. Show that you can choose a subset T of plates such that every point of S is covered by at least one and at most four plates in T.

16.  You are given a set of scales and a set of n different weights. R represents the state in which the right pan is heavier, L represents the state in which the left pan is heavier and B represents the state in which the pans balance. Show that given any n-letter string of Rs and Ls you can put the weights onto the scales one at a time so that the string represents the successive states of the scales. For example, if the weights were 1, 2 and 3 and the string was LRL, then you would place 1 in the left pan, then 2 in the right pan, then 3 in the left pan.

17.  A polynomial is monic if its leading coefficient is 1. Two polynomials p(x) and q(x) commute if p(q(x)) = q(p(x)).

(1) Find all monic polynomials of degree 3 or less which commute with x² - k.

(2) Given a monic polynomial p(x), show that there is at most one monic polynomial of degree n which commutes with p(x)².

(3) Find the polynomials described in (2) for n = 4 and n = 8.

(4) If q(x) and r(x) are monic polynomials which both commute with p(x)², show that q(x) and r(x) commute.

(5) Show that there is a sequence of polynomials p₂(x), p₃(x), ... such that p₂(x) = x² - 2, p_n(x) has degree n and all polynomials in the sequence commute.

[more...]

8th All Soviet Union Mathematical Olympiad Problems 1974

1.  A collection of n cards is numbered from 1 to n. Each card has either 1 or -1 on the back. You are allowed to ask for the product of the numbers on the back of any three cards. What is the smallest number of questions which will allow you to determine the numbers on the backs of all the cards if n is (1) 30, (2) 31, (3) 32? If 50 cards are arranged in a circle and you are only allowed to ask for the product of the numbers on the backs of three adjacent cards, how many questions are needed to determine the product of the numbers on the backs of all 50 cards?

2.  Find the smallest positive integer which can be represented as 36^m - 5ⁿ.

3.  Each side of a convex hexagon is longer than 1. Is there always a diagonal longer than 2? If each of the main diagonals of a hexagon is longer than 2, is there always a side longer than 1?

4.  Circles radius r and R touch externally. AD is parallel to BC. AB and CD touch both circles. AD touches the circle radius r, but not the circle radius R, and BC touches the circle radius R, but not the circle radius r. What is the smallest possible length for AB?

5.  Given n unit vectors in the plane whose sum has length less than one. Show that you can arrange them so that the sum of the first k has length less than 2 for every 1 < k < n.

6.  Find all real a, b, c such that |ax + by + cz| + |bx + cy + az| + |cx + ay + bz| = |x + y + z| for all real x, y, z.

7.  ABCD is a square. P is on the segment AB and Q is on the segment BC such that BP = BQ. H lies on PC such that BHC is a right angle. Show that DHQ is a right angle.

8.  The n points of a graph are each colored red or blue. At each move we select a point which differs in color from more than half of the points to which it it is joined and we change its color. Prove that this process must finish after a finite number of moves.

9.  Find all positive integers m, n such that nⁿ has m decimal digits and m^m has n decimal digits.

10.  In the triangle ABC, angle C is 90 deg and AC = BC. Take points D on CA and E on CB such that CD = CE. Let the perpendiculars from D and C to AE meet AB at K and L respectively. Show that KL = LB.

11.  One rat and two cats are placed on a chess-board. The rat is placed first and then the two cats choose positions on the border squares. The rat moves first. Then the cats and the rat move alternately. The rat can move one square to an adjacent square (but not diagonally). If it is on a border square, then it can also move off the board. On a cat move, both cats move one square. Each must move to an adjacent square, and not diagonally. The cats win if one of them moves onto the same square as the rat. The rat wins if it moves off the board. Who wins? Suppose there are three cats (and all three cats move when it is the cats' turn), but that the rat gets an extra initial turn. Prove that the rat wins.

12.  Arrange the numbers 1, 2, ... , 32 in a sequence such that the arithmetic mean of two numbers does not lie between them. (For example, ... 3, 4, 5, 2, 1, ... is invalid, because 2 lies between 1 and 3.) Can you arrange the numbers 1, 2, ... , 100 in the same way?

13.  Find all three digit decimal numbers a₁a₂a₃ which equal the mean of the six numbers a₁a₂a₃, a₁a₃a₂, a₂a₁a₃, a₂a₃a₁, a₃a₁a₂, a₃a₂a₁.

14.  No triangle of area 1 can be fitted inside a convex polygon. Show that the polygon can be fitted inside a triangle of area 4.

15.  f is a function on the closed interval [0, 1] with non-negative real values. f(1) = 1 and f(x + y) ≥ f(x) + f(y) for all x, y. Show that f(x) ≤ 2x for all x. Is it necessarily true that f(x) ≤ 1.9x for all x.

16.  The triangle ABC has area 1. D, E, F are the midpoints of the sides BC, CA, AB. P lies in the segment BF, Q lies in the segment CD, R lies in the segment AE. What is the smallest possible area for the intersection of triangles DEF and PQR?

[more...]

9th All Soviet Union Mathematical Olympiad Problems 1975

1.  (1) O is the circumcenter of the triangle ABC. The triangle is rotated about O to give a new triangle A'B'C'. The lines AB and A'B' intersect at C'', BC and B'C' intersect at A'', and CA and C'A' intersect at B''. Show that A''B''C'' is similar to ABC. (2) O is the center of the circle through ABCD. ABCD is rotated about O to give the quadrilateral A'B'C'D'. Prove that the intersection points of corresponding sides form a parallelogram.

2.  A triangle ABC has unit area. The first player chooses a point X on side AB, then the second player chooses a point Y on side BC, and finally the first player chooses a point Z on side CA. The first player tries to arrange for the area of XYZ to be as large as possible, the second player tries to arrange for the area to be as small as possible. What is the optimum strategy for the first player and what is the best he can do (assuming the second player plays optimally)?

3.  What is the smallest perimeter for a convex 32-gon whose vertices are all lattice points?

4.  Given a 7 x 7 square subdivided into 49 unit squares, mark the center of n unit squares, so that no four marks form a rectangle with sides parallel to the square. What is the largest n for which this is possible? What about a 13 x 13 square?

5.  Given a convex hexagon, take the midpoint of each of the six diagonals joining vertices which are separated by a single vertex (so if the vertices are in order A, B, C, D, E, F, then the diagonals are AC, BD, CE, DF, EA, FB). Show that the midpoints form a convex hexagon with a quarter the area of the original.

6.  Show that there are 2ⁿ⁺¹ numbers each with 2ⁿ digits, all 1 or 2, so that every two numbers differ in at least half their digits.

7.  There are finitely many polygons in the plane. Every two have a common point. Prove that there is a straight line intersecting all the polygons.

8.  a, b, c are positive reals. Show that a³ + b³ + c³ + 3abc > ab(a + b) + bc(b + c) + ca(c + a).

9.  Three flies crawl along the perimeter of a triangle. At least one fly makes a complete circuit of the perimeter. For the entire period the center of mass of the flies remains fixed. Show that it must be at the centroid of the triangle. [You may not assume, without proof, that the flies have the same mass, or that they crawl at the same speed, or that any fly crawls at a constant speed.]

10.  The finite sequence a_n has each member 0, 1 or 2. A move involves replacing any two unequal members of the sequence by a single member different from either. A series of moves results in a single number. Prove that no series of moves can terminate in a (single) different number.

11.  S is a horizontal strip in the plane. n lines are drawn so that no three are collinear and every pair intersects within the strip. A path starts at the bottom border of the strip and consists of a sequence of segments from the n lines. The path must change line at each intersection and must always move upwards. Show that: (1) there are at least n/2 disjoint paths; (2) there is a path of at least n segments; (3) there is a path involving not more than n/2 + 1 of the lines; and (4) there is a path that involves segments from all n lines.

12.  For what n can we color the unit cubes in an n x n x n cube red or green so that every red unit cube has just two red neighbouring cubes (sharing a face) and every green unit cube has just two green neighbouring cubes.

13.  p(x) is a polynomial with integral coefficients. f(n) = the sum of the (decimal) digits in the value p(n). Show that f(n) some value m infinitely many times.

14.  20 teams each play one game with every other team. Each game results in a win or loss (no draws). k of the teams are European. A separate trophy is awarded for the best European team on the basis of the k(k-1)/2 games in which both teams are European. This trophy is won by a single team. The same team comes last in the overall competition (winning fewer games than any other team). What is the largest possible value of k? If draws are allowed and a team scores 2 for a win and 1 for a draw, what is the largest possible value of k?

15.  Given real numbers a_i, b_i and positive reals c_i, d_i, let e_ij = (a_i+b_j)/(c_i+d_j). Let M_i = max_0≤j≤n e_ij, m_j =min_1≤i≤n e_ij. Show that we can find an e_ij with 1 ≤ i, j ≤ n such that e_ij = M_i = m_j.

Solutions

Problem 8
a, b, c are positive reals. Show that a³ + b³ + c³ + 3abc ≥ ab(a + b) + bc(b + c) + ca(c + a).
Solution
The inequality is homogeneous, so we can take a = 1 and put b = 1+x, c = 1+y, where x, y ≥ 0. Then after some reduction the inequality is equivalent to x³+y³+x²+y²-x²y-xy²-xy ≥ 0, or (after factorising x³+y³) to (x+y+1)(x-y)² + xy ≥ 0, which is obviously true.


Problem 10
The finite sequence a_n has each member 0, 1 or 2. A move involves replacing any two unequal members of the sequence by a single member different from either. A series of moves results in a single number. Prove that no series of moves can terminate in a (single) different number.
Solution
Suppose we start with a 0s, b 1s and c 2s. Each move changes the parity of all of a, b, c. Each moves reduces the length of the sequence by 1, so there must be a+b+c-1 moves in all. Hence the total number of 0s, the total number of 1s and the total number of 2s all have their parity changed a+b+c-1 times. So if we end up with just one 0, then a must have the opposite parity to b and c. In that case, we cannot end up with just one 1, or just one 2. Similarly in the other cases.

[more...]

7th All Soviet Union Mathematical Olympiad Problems 1973

7th All Soviet Union Mathematical Olympiad Problems 1973

1.  You are given 14 coins. It is known that genuine coins all have the same weight and that fake coins all have the same weight, but weigh less than genuine coins. You suspect that 7 particular coins are genuine and the other 7 fake. Given a balance, how can you prove this in three weighings (assuming that you turn out to be correct)?

2.  Prove that a 9 digit decimal number whose digits are all different, which does not end with 5 and or contain a 0, cannot be a square.

3.  Given n > 4 points, show that you can place an arrow between each pair of points, so that given any point you can reach any other point by travelling along either one or two arrows in the direction of the arrow.

4.  OA and OB are tangent to a circle at A and B. The line parallel to OB through A meets the circle again at C. The line OC meets the circle again at E. The ray AE meets the line OB at K. Prove that K is the midpoint of OB.

5.  p(x) = ax² + bx + c is a real quadratic such that |p(x)| ≤ 1 for all |x| ≤ 1. Prove that |cx² + bx + a| ≤ 2 for |x| ≤ 1.

6.  Players numbered 1 to 1024 play in a knock-out tournament. There ar no draws, the winner of a match goes through to the next round and the loser is knocked-out, so that there are 512 matches in the first round, 256 in the second and so on. If m plays n and m < n-2 then m always wins. What is the largest possible number for the winner?

7.  Define p(x) = ax² + bx + c. If p(x) = x has no real roots, prove that p( p(x) ) = 0 has no real roots.

8.  At time 1, n unit squares of an infinite sheet of paper ruled in squares are painted black, the rest remain white. At time k+1, the color of each square is changed to the color held at time k by a majority of the following three squares: the square itself, its northern neighbour and its eastern neighbour. Prove that all the squares are white at time n+1.

9.  ABC is an acute-angled triangle. D is the reflection of A in BC, E is the reflection of B in AC, and F is the reflection of C in AB. Show that the circumcircles of DBC, ECA, FAB meet at a point and that the lines AD, BE, CF meet at a point.

10.  n people are all strangers. Show that you can always introduce some of them to each other, so that afterwards each person has met a different number of the others. [problem: this is false as stated. Each person must have 0, 1, ... or n-1 meetings,so all these numbers must be used. But if one person has met no one, then another cannot have met everyone.]

11.  A king moves on an 8 x 8 chessboard. He can move one square at a time, diagonally or orthogonally (so away from the borders he can move to any of eight squares). He makes a complete circuit of the board, starting and finishing on the same square and visiting every other square just once. His trajectory is drawn by joining the center of the squares he moves to and from for each move. The trajectory does not intersect itself. Show that he makes at least 28 moves parallel to the sides of the board (the others being diagonal) and that a circuit is possible with exactly 28 moves parallel to the sides of the board. If the board has side length 8, what is the maximum and minimum possible length for such a trajectory.

12.  A triangle has area 1, and sides a ≥ b ≥ c. Prove that b² ≥ 2.

13.  A convex n-gon has no two sides parallel. Given a point P inside the n-gon show that there are at most n lines through P which bisect the area of the n-gon.

14.  a, b, c, d, e are positive reals. Show that (a + b + c + d + e)² ≥ 4(ab + bc + cd + de + ea).

15.  Given 4 points which do not lie in a plane, how many parallelepipeds have all 4 points as vertices? 

Solutions

Problem 1

You are given 14 coins. It is known that genuine coins all have the same weight and that fake coins all have the same weight, but weigh less than genuine coins. You suspect that 7 particular coins are genuine and the other 7 fake. Given a balance, how can you prove this in three weighings (assuming that you turn out to be correct)?

Solution

Let the coins you suspect to be genuine be G₁, G₂, ... , G₇, and the suspected fakes by F₁, F₂, ... , F₇. First weigh F₁ against G₁. Assuming F₁ weighs less, you have proved that F₁ is fake and G₁ genuine. Second, weigh F₁, G₂, G₃ against G₁, F₂, F₃. Assuming the first three weigh more you have proved that they include more genuine coins than the second three. But the second three includes one genuine coin (G₁) and the first three includes one fake (F₁), so you have proved that G₂ and G₃ are genuine and F₂ and F₃ fake. Finally, weigh F₁, F₂, F₃, G₄, G₅, G₆, G₇ against F₄, F₅, F₆, F₇, G₁, G₂, G₃. Assuming the first group weighs more it must include more genuine coins and hence just four genuine coins. Similarly, the second group must include four fakes. So you have proved the identity of the remaining coins.

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. 

[more...]

6th All Russian Mathematical Olympiad Problems 1966

6th All Russian Mathematical Olympiad Problems 1966

1.  There are an odd number of soldiers on an exercise. The distance between every pair of soldiers is different. Each soldier watches his nearest neighbour. Prove that at least one soldier is not being watched.

2. (a)  B and C are on the segment AD with AB = CD. Prove that for any point P in the plane: PA + PD ≥ PB + PC. (b)  Given four points A, B, C, D on the plane such that for any point P on the plane we have PA + PD ≥ PB + PC. Prove that B and C are on the segment AD with AB = CD.

3.  Can both x² + y and x + y² be squares for x and y natural numbers?

4.  A group of children are arranged into two equal rows. Every child in the back row is taller than the child standing in front of him in the other row. Prove that this remains true if each row is rearranged so that the children increase in height from left to right.

5.  A rectangle ABCD is drawn on squared paper with its vertices at lattice points and its sides lying along the gridlines. AD = k AB with k an integer. Prove that the number of shortest paths from A to C starting out along AD is k times the number starting out along AB.

6.  Given non-negative real numbers a₁, a₂, ... , a_n, such that a_i-1 ≤ a_i ≤ 2a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s = b₁a₁ + ... + b_na_n with each b_i +1 or -1, so that 0 ≤ s ≤ a₁.

7.  Prove that you can always draw a circle radius A/P inside a convex polygon with area A and perimeter P.

8.  A graph has at least three vertices. Given any three vertices A, B, C of the graph we can find a path from A to B which does not go through C. Prove that we can find two disjoint paths from A to B. [A graph is a finite set of vertices such that each pair of distinct vertices has either zero or one edges joining the vertices. A path from A to B is a sequence of vertices A₁, A₂, ... , A_n such that A=A₁, B=A_n and there is an edge between A_i and A_i+1 for i = 1, 2, ... , n-1. Two paths from A to B are disjoint if the only vertices they have in common are A and B.]

9.  Given a triangle ABC. Suppose the point P in space is such that PH is the smallest of the four altitudes of the tetrahedron PABC. What is the locus of H for all possible P?

10.  Given 100 points on the plane. Prove that you can cover them with a collection of circles whose diameters total less than 100 and the distance between any two of which is more than 1. [The distance between circles radii r and s with centers a distance d apart is the greater of 0 and d - r - s.]

11.  The distance from A to B is d kilometers. A plane P is flying with constant speed, height and direction from A to B. Over a period of 1 second the angle PAB changes by α degrees and the angle PBA by β degrees. What is the minimal speed of the plane?

12.  Two players alternately choose the sign for one of the numbers 1, 2, ... , 20. Once a sign has been chosen it cannot be changed. The first player tries to minimize the final absolute value of the total and the second player to maximize it. What is the outcome (assuming both players play perfectly)? Example: the players might play successively: 1, 20, -19, 18, -17, 16, -15, 14, -13, 12, -11, 10, -9, 8, -7, 6, -5, 4, -3, 2. Then the outcome is 12. However, in this example the second player played badly!

Solutions

Problem 1

There are an odd number of soldiers on an exercise. The distance between every pair of soldiers is different. Each soldier watches his nearest neighbour. Prove that at least one soldier is not being watched.
Solution

The key is to notice that no loops of size greater than two are possible. For suppose we have A₁, A₂, ... , A_n with A_i watching A_i+1 for 0 < i < n, and A_n watching A₁. Then the distance A_i-1A_i is greater than the distance A_iA_i+1 for 1 < i < n, and the distance A₁A_n is less than the distance A₁A₂. Hence the distance A₁A_n is less than the distance A_n-1A_n and so A_n-1 is closer to A_n than A₁. Contradiction.
Pick any soldier. Now pick the soldier he is watching, and so on. The total number of soldiers is finite so this process must terminate with some soldier watching his predecessor. If the process terminates after more than two soldiers have been picked, then the penultimate soldier is watched by more than one soldier. But in that case there must be another soldier who is unwatched, because the number of soldiers equals the number of soldiers watching.
If the process terminates after just two soldiers, then we have a pair of soldiers watching each other. Now repeat on the remaining soldiers. Either we find a soldier watched twice (in which case some other soldier must be unwatched) or all the soldiers pair off, except one, since the total number is odd. But that soldier must be unwatched.

Problem 2

(a)  B and C are on the segment AD with AB = CD. Prove that for any point P in the plane: PA + PD ≥ PB + PC.
(b)  Given four points A, B, C, D on the plane such that for any point P on the plane we have PA + PD ≥ PB + PC. Prove that B and C are on the segment AD with AB = CD.
Solution

(a)  Suppose the points lie in the order A, B, C, D. If P lies on AD, then the result is trivial, and we have equality if P lies outside the segment AD. So suppose P does not lie on AD.
Let M be the midpoint of AD. Take P' so that P, M, P' are collinear and PM = MP'. Then we wish to prove that PA + AP' > PB + BP'. Extend P'B to meet PA at Q. Then P'A + AQ > P'Q, so P'A + AP > P'Q + QP. But QP + BQ > PB, so QP + QP' > PB + PB'. Hence result.
(b)  Let the foot of the perpendicular from B, C onto AD be X, Y respectively. Suppose that N, the midpoint of XY, is on the same side of M, the midpoint of AD, as D. Then take P to be a remote point on the line AD, the opposite side of A to D, so that A, D, M and N are all on the same side of the line PAD from P. Then PA + PD = 2PM < 2PN ≤ PB + PC. Contradiction. So we must have N coincide with M. But we still have PA + PD = 2PM = 2PN < PB + PC, unless both B and C are on the line AD. So we must have B and C on the line AD and AB = CD. It remains to show that B and C are between A and D. Take P = B. Then if C is not between A and D, we have PC > PD (or PA), contradiction.

Problem 3

Can both x² + y and x + y² be squares for x and y natural numbers?
Solution

No. The smallest square greater than x² is (x+1)², so we must have y > 2x. Similarly x > 2y. Contradiction.

Problem 4

A group of children are arranged into two equal rows. Every child in the back row is taller than the child standing in front of him in the other row. Prove that this remains true if each row is rearranged so that the children increase in height from left to right.
Solution

Rearrange the children in the back row into order, and rearrange the front row in the same way, so that each child stays in front of the same child in the back row. Denote heights in the back row by a_i and heights in the front row by b_i. So we have a₁ ≤ a₂ ≤ ... ≤ a_n, and a_i > b_i for i = 1, 2, ... , n.
Now if i < j, but b_i > b_j, then we may swap b_i and b_j and still have each child taller than the child in front of him. For b_i < a_i <= a_j, and b_j < b_i < a_i. By repeated swaps we can get the front row into height order. [For example, identify the shortest child and swap him to the first position, then the next shortest and so on.]

Problem 5

A rectangle ABCD is drawn on squared paper with its vertices at lattice points and its sides lying along the gridlines. AD = k AB with k an integer. Prove that the number of shortest paths from A to C starting out along AD is k times the number starting out along AB.
Solution

Let ABCD have n lattice points along the side AB. Then it has kn lattice points along the side AD. Let X be the first lattice point along AB after leaving A. A shortest path from X to C must involve a total of kn + n - 1 moves between lattice points, n - 1 in the direction AB and kn in the direction BC. Hence the total number of such paths is (kn + n - 1)!/((kn)! (n - 1)!). Similarly, the number of paths starting out along AD is (kn + n - 1)!/((kn - 1)! n!). Let m = (kn + n - 1)!/((kn - 1)! (n - 1)!). Then the number starting along AB is m/(kn) and the number starting along AD is m/n, which is k times larger, as required.


Problem 6

Given non-negative real numbers a₁, a₂, ... , a_n, such that a_i-1 <= a_i <= 2a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s = b₁a₁ + ... + b_na_n with each b_i +1 or -1, so that 0 <= s <= a₁.
Solution

We show that you can pick b_n, b_n-1, ... , b_r so that s_r = b_na_n + b_n-1a_n-1 + ... + b_ra_r satisfies 0 <= s_r <= a_r. Induction on r. Trivial for r = n. Suppose true for r. Then - a_r-1 <= s_r - a_r-1 <= a_r - a_r-1 <= a_r-1. So with b_r-1 = -1 we have |s_r-1| <= a_r-1. If necessary, we change the sign of all b_n, b_n-1, ... , b_r-1 and obtain s_r-1 as required. So the result is true for all r >= 1 and hence for r = 1.

Problem 7

Prove that you can always draw a circle radius A/P inside a convex polygon with area A and perimeter P.
Solution

Draw a rectangle width A/P on the inside of each side. The rectangles at each vertex must overlap since the angle at the vertex is less than 180. The total area of the rectangles is A, so the area covered must be less than A. Hence we can find a point not in any of the rectangles. But this point must be a distance more than A/P from each side, so we can use it as the center of the required circle.

Problem 8

A graph has at least three vertices. Given any three vertices A, B, C of the graph we can find a path from A to B which does not go through C. Prove that we can find two disjoint paths from A to B.
[A graph is a finite set of vertices such that each pair of distinct vertices has either zero or one edges joining the vertices. A path from A to B is a sequence of vertices A₁, A₂, ... , A_n such that A=A₁, B=A_n and there is an edge between A_i and A_i+1 for i = 1, 2, ... , n-1. Two paths from A to B are disjoint if the only vertices they have in common are A and B.]
Solution

Take any path from A to B. Suppose it is A=A₀, A₁, ... , A_n=B. We show by induction on r that we can find two disjoint paths from A to A_r. If r = 1, then take any vertex C distinct from A and A₁. Take any path from A₁ to C which does not go through A. Now take any path from C to A which does not go through A₁. Joining these two paths together gives a path p from A to A₁ which does not involve the edge AA₁. Then p and the edge AA₁ are the required disjoint paths.
Suppose now we have two disjoint paths A, B₁, B₂, ... , B_s, A_r and A, B_t, B_t-1, ... , B_s+1, A_r and we wish to find two disjoint paths joining A and A_r+1. Take a path between A and A_r+1 which does not include A_r. If it also avoids all of B₁, ... , B_t, then we are home, because it is disjoint from the alternative path A, B₁, B₂, ... , B_s, A_r, A_r+1. If not, let B_i be the first of the B's on the path as we move from A_r+1 to A. This allows us to construct two disjoint paths from A to A_r+1. One path goes from A to B_i and then from B_i to A_r+1. The other path goes around the other way to A_r and then along the edge to A_r+1. [Explicitly, if i <= s, then the paths are A, B₁, B₂, ... , B_i, ... (new path) ... A_r+1 and A, B_t, B_t-1, ... , A_r, A_r+1. If i > s, then the paths are A, B_t, B_t-1, ... , B_i, ... (new path) ... A_r+1 and A, B₁, ... , B_s, A_r, A_r+1.] Hence, by induction, there are two disjoint paths from A to B.

Problem 9

Given a triangle ABC. Suppose the point P in space is such that PH is the smallest of the four altitudes of the tetrahedron PABC. What is the locus of H for all possible P?
Solution

Answer: the triangle DEF with FAE parallel to BC, DBF parallel to CA and DCE parallel to AB.
Let α be the angle between planes ABC and PBC. Let h be the perpendicular distance from H to the line BC, and let h_A be the perpendicular distance from A to the line BC. Then PH = h tan α, and the altitude from A to PBC is h_A sin α. Hence if PH is shorter than the altitude from A we require that h < h_A cos α < h_A. Similar arguments apply for B and C. So if PH is the shortest then H lies within triangle DEF.
If H does lie within DEF, then if we make α sufficiently small we will have h < h_A cos α and hence PH will be shorter than the altitude from A. Similarly we can make PH sufficiently short that PH is less than the altitudes from B and C. Hence the inside of DEF is the required locus.



Problem 10

Given 100 points on the plane. Prove that you can cover them with a collection of circles whose diameters total less than 100 and the distance between any two of which is more than 1. [The distance between circles radii r and s with centers a distance d apart is the greater of 0 and d - r - s.]
Solution

If we have two circles diameters d and d', the distance between which is less than 1, then they are contained in a circle diameter d+d'+1. [If the line through the centers cuts the circles in A, B, A', B', then take a circle diameter AB'.] So start with 100 circles of diameter 1/1000 each. If any pair is a distance <= 1 apart, then replace them by a single circle, increasing the total diameter by 1. Repeat until all the circles are a distance > 1 apart. We must end up with at least one circle, so the total increase is at most 99. Hence the final total diameter is at most 99 1/10.

Problem 11

The distance from A to B is d kilometers. A plane P is flying with constant speed, height and direction from A to B. Over a period of 1 second the angle PAB changes by α degrees and the angle PBA by β degrees. What is the minimal speed of the plane?
Solution

Answer: 20πd√(αβ) kilometers per hour.
Let the plane be at height h and a (horizontal) distance y from A. Let the angle PAB be θ+α and the angle PBA be φ. After 1 second, the angle PAB is θ and the angle PBA is φ+β. We have immediately that:   h/y = tan(θ+α), h/(d-y) = tan φ, h/(y+x) = tan θ, h/(d-y-x) = tan(φ+β).
Eliminating θ, we obtain: h/y = (tan α + tan θ)/(1 - tan α tan θ) = (a(y+x) + h)/(y+x-ah), where a = tan α. Hence x = a(h² + y²)/(h - ay). Similarly, eliminating φ, we obtain x = b(h² + (d-y)²)/(h + (d-y)b).
At this point I do not see how to make further progress without approximating. But approximating seems reasonable, since α and β, are certainly small, at least when expressed in radians. For example, typical values might be 10,000 ft for h and more than 10 miles for y or d-y and 500 mph for the aircraft speed. That gives x = 0.14 miles, so x/y = 0.014 and x/h = 0.07. So, let us neglect a/h, b/h, a/y etc. Then we get the simplified expressions: x = a(h² + y²)/h = b(h² + (d-y)²)/h.
If a = b, then we quickly obtain y = d/2, h = d/2, x = ad. Assume a > b. Then we can solve for h, substitute back in and obtain an expression for x in terms of y. It is convenient to divide through by d and to write X = x/d, Y = y/d. Note that since we are assuming a > b, we require Y < 1/(1 + √(a/b)). After some manipulation we obtain: X = ab(1 - 2Y)/√((a-b)(b(1-Y)² - aY²). Differentiating, we find that there is a minimum at Y = b/(a+b), which is in the allowed range, and that the minimum value of X is √(ab). By symmetry, we obtain the same result for a < b and we notice that it is also true for a = b. So in all cases we have that the minimum value of x is d√(ab).
We are assuming α and β are small, so we may take a = α, b = β. However, the question specified that α and β were measured in degrees, so to obtain the final answer we must convert, giving: x = d (π/180) √(αβ), and hence speed = 20πd√(αβ) kilometers per hour.

Problem 12

Two players alternately choose the sign for one of the numbers 1, 2, ... , 20. Once a sign has been chosen it cannot be changed. The first player tries to minimize the final absolute value of the total and the second player to maximize it. What is the outcome (assuming both players play perfectly)?
Example: the players might play successively: 1, 20, -19, 18, -17, 16, -15, 14, -13, 12, -11, 10, -9, 8, -7, 6, -5, 4, -3, 2. Then the outcome is 12. However, in this example the second player played badly!
Solution

Answer: 30.
The second player can play the following strategy: (1) if the first player plays 2n-1 for 1 <= n <= 9, then he replies 2n with the opposite sign; (2) if the first player plays 2n for 1 <= n <= 9, then he replies 2n-1 with the opposite sign; (3) if the first player plays 19 or 20, then he plays the other with the same sign. This secures a score of at least 39 (from (3) ) less 9 x 1 (from (1) and (2) ). So he can ensure a score of at least 30.
The first player can play the following strategy: (1) he opens with 1; (2) if the second player plays 2n for 1 ≤ n <= 9, then he replies with 2n+1 with the opposite sign; (3) if the second player plays 2n+1 for 1 <= n <= 9, then he replies with 2n with the opposite sign; (4) if any of these replies are impossible, or if the second player plays 20, then he replies with the highest number available with the opposite sign. If the second player does not play 20 until the last move, then this strategy ensures a score of at most 1 (from (1) ) + 9 x 1 (from (2) and (3) ) + 20 = 30. Now suppose that the second player plays 20, a₁, a₂, ... , a_n (where 1 ≤ n ≤ 9) which require a reply under (4). The reason a₁ required a move under (4) was that a₁-1 or a₁+1 was the 1st player's response to 20. Similarly, the reason a₂ required a move under (4) was that a₂-1 or a₂+1 was the 1st player's response to a₂, and so on. Thus the increment to the absolute value from these moves is at most |20-a₁+1| + |a₁-a₂+1| + ... + |a_n-1-a_n+1| + |a_n| = 20 + n. The increment from the moves under (2) and (3) is (9 - n) x 1, and the increment from the move under (1) is 1. Hence the maximum absolute value is 30.
Since the 1st player has a strategy to do no worse than 30 and the 2nd player has a strategy to do no worse than 30, these strategies must actually be optimal.  

[more...]