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.  

[Read More...]

5th All Russian Mathematical Olympiad Problems 1965

5th All Russian Mathematical Olympiad Problems 1965

1. (a)  Each of x₁, ... , x_n is -1, 0 or 1. What is the minimal possible value of the sum of all x_ix_j with 1 ≤ i < j ≤ n? (b)  Is the answer the same if the x_i are real numbers satisfying 0 ≤ |x_i| ≤ 1 for 1 ≤ i ≤ n?

2.  Two players have a 3 x 3 board. 9 cards, each with a different number, are placed face up in front of the players. Each player in turn takes a card and places it on the board until all the cards have been played. The first player wins if the sum of the numbers in the first and third rows is greater than the sum in the first and third columns, loses if it is less, and draws if the sums are equal. Which player wins and what is the winning strategy?

3.  A circle is circumscribed about the triangle ABC. X is the midpoint of the arc BC (on the opposite side of BC to A), Y is the midpoint of the arc AC, and Z is the midpoint of the arc AB. YZ meets AB at D and YX meets BC at E. Prove that DE is parallel to AC and that DE passes through the center of the inscribed circle of ABC.

4.  Bus numbers have 6 digits, and leading zeros are allowed. A number is considered lucky if the sum of the first three digits equals the sum of the last three digits. Prove that the sum of all lucky numbers is divisible by 13.

5.  The beam of a lighthouse on a small rock penetrates to a fixed distance d. As the beam rotates the extremity of the beam moves with velocity v. Prove that a ship with speed at most v/8 cannot reach the rock without being illuminated.

6.  A group of 100 people is formed to patrol the local streets. Every evening 3 people are on duty. Prove that you cannot arrange for every pair to meet just once on duty.

7.  A tangent to the inscribed circle of a triangle drawn parallel to one of the sides meets the other two sides at X and Y. What is the maximum length XY, if the triangle has perimeter p?

8.  The n² numbers x_ij satisfy the n³ equations: x_ij + x_jk + x_ki = 0. Prove that we can find numbers a₁, ... , a_n such that x_ij = a_i - a_j.

9.  Can 1965 points be arranged inside a square with side 15 so that any rectangle of unit area placed inside the square with sides parallel to its sides must contain at least one of the points?

10.  Given n real numbers a₁, a₂, ... , a_n, prove that you can find n integers b₁, b₂, ... , b_n, such that the sum of any subset of the original numbers differs from the sum of the corresponding b_i by at most (n + 1)/4.

11.  A tourist arrives in Moscow by train and wanders randomly through the streets on foot. After supper he decides to return to the station along sections of street that he has traversed an odd number of times. Prove that this is always possible. [In other words, given a path over a graph from A to B, find a path from B to A consisting of edges that are used an odd number of times in the first path.]

12. (a)  A committee has met 40 times, with 10 members at every meeting. No two people have met more than once at committee meetings. Prove that there are more than 60 people on the committee. (b)  Prove that you cannot make more than 30 subcommittees of 5 members from a committee of 25 members with no two subcommittees having more than one common member.

13.  Given two relatively prime natural numbers r and s, call an integer good if it can be represented as mr + ns with m, n non-negative integers and bad otherwise. Prove that we can find an integer c, such that just one of k, c - k is good for any k. How many bad numbers are there?

14.  A spy-plane circles point A at a distance 10 km with speed 1000 km/h. A missile is fired towards the plane from A at the same speed and moves so that it is always on the line between A and the plane. How long does it take to hit?

15.  Prove that the sum of the lengths of the edges of a polyhedron is at least 3 times the greatest distance between two points of the polyhedron.

16.  An alien moves on the surface of a planet with speed not exceeding u. A spaceship searches for the alien with speed v. Prove the spaceship can always find the alien if v>10u.

Solutions

Problem 1

(a)  Each of x₁, ... , x_n is -1, 0 or 1. What is the minimal possible value of the sum of all x_ix_j with 1 <= i < j <= n? (b)  Is the answer the same if the x_i are real numbers satisfying 0 <= |x_i| <= 1 for 1 <= i <= n?
Solution

(a)  Answer: -[n/2].
Let A = (x₁ + ... + x_n)², B = x₁² + ... + x_n². Then we must minimize A - B. For n even, we separately minimize A and maximize B by taking half the x's to be +1 and half to be -1. For n odd we can take [n/2] x's to be +1, [n/2] to be -1, and one to be 0. That minimizes A and gives B one less than its maximum. That is the best we can do if we fix A = 0, since A = 0 requires an even number of x's to be non-zero and hence at least one to be zero. If we do not minimize A, then since its value must be an integer, its value will be at least 1. In that case, even if B is maximized we will not get a lower total.
(b)  Answer: -[n/2]. For n even, the same argument works. For n odd we can clearly get -[n/2], so it remains to prove that we cannot get a smaller sum. Suppose otherwise, so that x_i is a minimal sum with sum less than -[n/2]. Let x_n = x, then the sum is x(x₁ + ... + x_n-1) + sum of terms x_ix_j with 1 <= i, j < n. But this is less than the sum for n-1, so x(x₁ + ... + x_n-1) must be negative, and since it is minimal we must have |x| = 1. But the same argument shows that all the terms have modulus 1. We now have a contradiction since we know that the minimum in this case is -[n/2].

Problem 2

Two players have a 3 x 3 board. 9 cards, each with a different number, are placed face up in front of the players. Each player in turn takes a card and places it on the board until all the cards have been played. The first player wins if the sum of the numbers in the first and third rows is greater than the sum in the first and third columns, loses if it is less, and draws if the sums are equal. Which player wins and what is the winning strategy?
Solution

The first player always wins.
Let the board be:

. F .
S . S
. F .

We call the squares marked F the F-squares, the squares marked S the S-squares, and the remaining squares the neutral squares. The first player wins if the sum of the two cards on the F-squares exceeds the sum of the two cards on the S-squares. We also call the first player F and the second player S. Let the cards be a₁>a₂> ... >a₉. Let t₁ = a₁ + a₉, t₂ = a₂ + a₈, t₃ = a₃ + a₇, t₄ = a₄ + a₆.
If t₁ > t₂, or t₁ = t₂ > t₃, or t₁ = t₂ = t₃ >= t₄ (*), then F's strategy is to get a total of t₁ or better on the F-squares and to force S to a lower score on the S-squares. If (*) does not hold, then F's strategy is to force S to t₁ or lower, and to get a higher score.
If (*) holds, then F starts by playing a₁ to an F-square. S must play to the remaining F-square, otherwise F will play a₃ or better to it on his next move and win. So S must play a₉ to the remaining F-square, giving F a total of t₁.
Now if t₁ > t₂, then F forces S to t₂ or worse by playing a₈ to an S-square.
If t₁ = t₂ > t₃, then F forces S to t₃ or worse by playing a₂ to a neutral square. If S plays to an S-square, then he cannot do better than a₃ + a₈, which loses. So he plays a₈ to a neutral square. But now F plays a₃ to an S-square, and S cannot do better than t₃.
If t₁ = t₂ = t₃ > t₄, then F forces S to t₄ or worse. He starts by playing a₂ to a neutral square. If does not prevent F playing a₈ to an S-square on his next move, then he cannot do better than a₃ + a₈, which loses. So he must play a₈ to a neutral square. Now F plays a₃ to a neutral square. If S does not prevent F playing a₇ to an S-square on the following move, then he cannot do better than a₄ + a₇ which loses, so he plays a₇ to a neutral square. F now plays a₄ to an S-square. S cannot now do better than t₄, which loses.
Finally, if t₁ = t₂ = t₃ = t₄, then F proceeds as in the last case except that at the end he plays a₄ to the last neutral square instead of to an S-square. S now gets a₅ + a₆ on the S-squares, which loses.
If (*) does not hold, then F starts by playing a₉ to an S-square. If S does not play to the other S-square, then F will play a₇ or a₈ there on his next move and S will lose. So S must play a₁ to the other square, and gets a total of t₁. F now plays to get t₂, t₃ or t₄ on the F-squares.
If t₁ < t₂, then F plays a₂ to an F-square and so gets at least t₂ and wins.
If t₁ = t₂ < t₃, then F plays a₈ to a neutral square. If S does not prevent F playing a₂to an F-square on his next move, then F will get at least a₂ + a₇ and win. So S must play a₂ to a neutral square. Now F plays a₃ to an F-square and so gets at least t₃ on the F-squares and wins.
Finally, if t₁ = t₂ = t₃ < t₄, then F plays as in the previous case, except that at the end he plays a₇ to a neutral square instead of a₃ to an F-square. S must prevent F playing a₃ to an F-square the following move, or F gets at least a₃ + a₆ and wins. So S plays a₃ to a neutral square. F now plays a₄ to an F square and so must get at least t₄, which wins.

Problem 3

A circle is circumscribed about the triangle ABC. X is the midpoint of the arc BC (on the opposite side of BC to A), Y is the midpoint of the arc AC, and Z is the midpoint of the arc AB. YZ meets AB at D and YX meets BC at E. Prove that DE is parallel to AC and that DE passes through the center of the inscribed circle of ABC.
Solution

ZY bisects the angle AYB, so AD/BD = AY/BY. Similarly, XY bisects angle BYC, so CE/BE = CY/BY. But AY = CY. Hence AD/BD = CE/BE. Hence triangles BDE and BAC are similar and DE is parallel to AC.
Let BY intersect AC at W and AX at I. I is the in-center. AI bisects angle BAW, so WI/IB = AW/AB. Now consider the triangles AYW, BYA. Clearly angle AYW = angle BYA. Also angle WAY = angle CAY = angle ABY. Hence the triangles are similar and AW/AY = AB/BY. So AW/AB = AY/BY. Hence WI/IB = AY/BY = AD/BD. So triangles BDI and BAW are similar and DI is parallel to AW and hence to DE. So DE passes through I.

Problem 4

Bus numbers have 6 digits, and leading zeros are allowed. A number is considered lucky if the sum of the first three digits equals the sum of the last three digits. Prove that the sum of all lucky numbers is divisible by 13.
Solution

The total is made up of numbers of the form abcabc, and pairs of numbers abcxyz, xyzabc. The former is abc.1001 and the sum of the pair is 1001(abc + xyz). So the total is divisible by 1001 and hence by 13.


Problem 5

The beam of a lighthouse on a small rock penetrates to a fixed distance d. As the beam rotates the extremity of the beam moves with velocity v. Prove that a ship with speed at most v/8 cannot reach the rock without being illuminated.
Solution

Let the lighthouse be at L. Take time t = 0 at the moment the boat starts its run, so that at t = 0 it is at S a distance d from L, and thereafter it is at a distance less than d. Take A and B a distance d from L so that ALBS is a semicircle with diameter AB and S the midpoint of the arc AB. During the period to t = 2.5 pi.d/v the boat has traveled a distance less than d, so it cannot reach AB. But it is a distance less than d from L, so it must be inside the semicircle. But during this period the beam sweeps across from LA to LB and so it must illuminate the boat.

Problem 6

A group of 100 people is formed to patrol the local streets. Every evening 3 people are on duty. Prove that you cannot arrange for every pair to meet just once on duty.
Solution

Every time a person is on duty he is paired with two other people, so if the arrangement were possible the number of pairs involving a particular person would have to be even. But it is 99.

Problem 7

A tangent to the inscribed circle of a triangle drawn parallel to one of the sides meets the other two sides at X and Y. What is the maximum length XY, if the triangle has perimeter p?
Solution

Let BC be the side parallel to XY, h the length of the altitude from A, and r the radius of the in-circle. Then XY/BC = (h - 2r)/h. But r.p = h.BC. So XY = (p - 2BC)BC/p = (p²/8 - 2(BC - p/4)²)/p. So the maximum occurs when BC = p/4 and has value p/8.


Problem 8

The n² numbers x_ij satisfy the n³ equations: x_ij + x_jk + x_ki = 0. Prove that we can find numbers a₁, ... , a_n such that x_ij = a_i - a_j.
Solution

Taking i = j = k, we have that x_ii = 0. Now taking j=k, we have that x_ij = - x_ji. Define a_i = x_i1. Then we have x_i1 + x_1j + x_ji = 0. Hence x_ij = a_i - a_j.

Problem 9

Can 1965 points be arranged inside a square with side 15 so that any rectangle of unit area placed inside the square with sides parallel to its sides must contain at least one of the points?
Solution

Yes. Place a grid of 900 points in 30 equally spaced rows and columns, so that each point is a distance 15/31 from its nearest neighbours (or 15/31 from the edge). This blocks all rectangles except those slimmer than 1/2. Those slimmer than 1/2 must have length at least 2, so we can block them with a smaller set of rows and columns containing more finely spaced points.
Label the rows 1-30. In each of the 7 rows 3, 7, 11, 15, 19, 23, 27 place an additional 31 points, so that each of these rows has 61 equally spaced points at a spacing of 15/62. Similarly for the columns. So in total we are placing an additional 2.7.31 = 434 points. Any rectangle of length >2 must encounter one of these rows (or columns) and hence must have width less than 1/4. This blocks any rectangle except those with width < 1/4.
In each of the 3 rows 7, 15, 23 place an additional 62 points, so that each of these rows has 123 equally spaced points at a spacing of 15/124. Similarly for the columns. So in total we are placing an additional 2.3.62 = 372 points. Any rectangle of length >4 must encounter one of these rows (or columns) and hence must have width less than 1/8. This blocks any rectangle except those with width < 1/8 and hence length > 8.
In row 15 place an additional 124 points, so that it has a total of 247 equally spaced points at a spacing of 15/247. Similarly for column 15. This requires an additional 248 points. Any rectangle which can fit through these gaps has area at most 15 x 15/247 < 1. So we have blocked all rectangles with area 1 or more and used 900 + 434 + 372 + 248 = 1954 points.
Ilan Mayer, who seems to solve these problems effortlessly, came up with a neater arrangement of points. He used narrowly spaced points along widely spaced diagonals: (k/15, k/15) for k = 1,2,...,224; ((28*n+k)/15, k/15) for n = 1,2,...,7, k = 1,2,...,224-28*n; (k/15, (28*n+k)/15) for n = 1,2,...,7, k = 1,2,...,224-28*n. The diagonals are spaced 28/15 apart, so the biggest rectangle that can be fitted between two diagonals has sides 15/15 less epsilon and 15/15 less epsilon. For example, take the vertices as (14/15 + e, e), (29/15 - e, e), (14/15 + e, 15/15 - e), (29/15 - e, 15/15 - e). If one allows a rectangle to touch points (in other words if one took the rectangles to exclude their boundaries) then this does not work - many 15 x 1/15 rectangles will fit. But one can add an additional point on each of the 15 lines, keeping the points on each line evenly spaced. That blocks rectangles without boundary and still has only 1821 points.

Problem 10

Given n real numbers a₁, a₂, ... , a_n, prove that you can find n integers b₁, b₂, ... , b_n, such that |a_i - b_i| < 1 and the sum of any subset of the original numbers differs from the sum of the corresponding b_i by at most (n + 1)/4.
Solution

We can take all a_i to lie in the range (0,1) and all b_i to be 0 or 1. The largest positive value of the sum of (a_i - b_i) for any subset is achieved by taking the subset of those i for which b_i = 0. Similarly, the largest negative value is achieved by taking those i for which b_i = 1. So the worst subset will be one of those two.
If a_i < a_j, then we cannot have b_i = 1 and b_j = 0 if the set of b_is is to minimise the maximum sum, because swapping them would reduce the sum of a's with b = 0 and the sum of (1 - a)'s with b = 1. So if we order the a's so that a₁ <= a₂ <= ... <= a_n, then a best set of b's is b_i = 0 for i <= some k, and b_i = 1 for i > k. [If some of the a_i are equal, then we can find equally good sets of b's do not have this form, but we cannot get a lower maximum sum by departing from this form.]
Let L_i = a₁ + a₂ + ... + a_i, and R_i = a_i+1 + a_i+2 + ... + a_n. As we increase i the sums L_i increase and the sums R_i decrease, so for some k we must have L_k < R_k, L_k+1 >= R_k+1. Either k or k+1 must correspond to the optimum choice of b's to minimise the maximum sum.
Now assume that the a's form a maximal set, in other words they are chosen so that the minimum is as large as possible. We show first that in this case L_k+1 = R_k. Suppose L_k+1 < R_k. Then we could increase each of a_k+1, a_k+2, ... , a_n by epsilon. This would leave L_k unaffected, but slightly increase L_k+1 and slightly reduce R_k. For small epsilon this does not change the value of k, but increases the smaller of L_k+1 and R_k, thus increasing the minimum and contradicting the maximality of the original a's. Similarly, if L_k+1 > R_k, we could decrease each of a₁, a₂, ... , a_k+1 by epsilon, thus slightly increasing R_k and reducing L_k+1.
Suppose not all of a₁, a₂, ... , a_k+1 are equal. Take i so that a_i < a_i+1. Now increase each of a₁, a₂, ... , a_i by epsilon and reduce each of a_i+1, a_i+2, ... , a_k+1 by epsilon', with epsilon and epsilon' sufficiently small that we do not upset the ordering or change the value of k, and with their relative sizes chosen so that L_k+1 is increased. R_k is also increased, so we contradict the maximality of the a's. Hence all a₁, a₂, ... , a_k+1 are equal. Similarly, we show that all of a_k+1, ... , a_n are equal. For if not we can increase slightly a_k+1, ... , a_j and reduce slightly a_j+1, ... , a_n to get a contradiction.
So we have established that all the a's must be equal. Suppose n is odd = 2m+1 and that all the a's equal x. Then for the optimum k we have (k+1)x = (2m+1-k)(1-x), hence k+1 = (2m+2)(1-x) and the maximum difference is (k+1)x = (2m+2)(1-x)x. This is maximised by taking x = 1/2, k = m, and is (m+1)/2 = (n+1)/4. If n is even = 2m, then for the optimum k we have (k+1)x = (2m-k)(1-x), so k+1 = (2m+1)(1-x), and the maximum difference is (k+1)x = (2m+1)(1-x)x. However, in this case we cannot take x = 1/2, because that would give k = m - 1/2 which is non-integral, so we take k = m-1 or m, both of which give a maximum difference of m(m+1)/(2m+1) = n(n+2)/(4n+4) < (n+1)/4.

Problem 11

A tourist arrives in Moscow by train and wanders randomly through the streets on foot. After supper he decides to return to the station along sections of street that he has traversed an odd number of times. Prove that this is always possible. [In other words, given a path over a graph from A to B, find a path from B to A consisting of edges that are used an odd number of times in the first path.]
Solution

Disregard all edges except those used in the path from A to B, and for each of those let the multiplicity be the number of times it was traversed. Let the degree of a vertex be the sum of the multiplicities of its edges. The key is to notice that the degree of every vertex except A and B must be even. For as we traverse the path from A to B we increase the degree by 2 each time we pass through a vertex. But at the start of the path, as we leave A, we only increase its degree by 1. Similarly as we arrive at B for the last time.
Now construct a path from B as follows. Since B has odd degree it must have an edge of odd multiplicity. Suppose the edge connects B to C. Follow that edge and reduce its multiplicity by one, so that B's degree and C's degree are each reduced by one. Now C has odd degree, so it must have an edge of odd multiplicity. Repeat. Since there are only finitely many edges we must eventually be unable to continue the path. But the only way that can happen is if we reach A.

Problem 12

(a)  A committee has met 40 times, with 10 members at every meeting. No two people have met more than once at committee meetings. Prove that there are more than 60 people on the committee.
(b)  Prove that you cannot make more than 30 subcommittees of 5 members from a committee of 25 members with no two subcommittees having more than one common member.
Solution

(a)  Each meeting involves 10.9/2 = 45 pairs. So after 40 meetings, there have been 1800 pairs. We are told that these are all distinct. But if there are N people on the committee, then there are only N(N-1)/2 pairs available. For N=60, this is only 1770.
(b)  A subcommittee of 5 has 5.4/2 = 10 pairs. So 31 subcommittees have 310 pairs, and these are all distinct, since no two people are on more than one subcommittee. But a committee of 25 only has 25.24/2 = 300 pairs available.



Problem 13

Given two relatively prime natural numbers r and s, call an integer good if it can be represented as mr + ns with m, n non-negative integers and bad otherwise. Prove that we can find an integer c, such that just one of k, c - k is good for any k. How many bad numbers are there?
Solution

Notice that 0 is good and all negative numbers are bad. Take c = rs - r - s. First c, is bad. For suppose otherwise: c = mr + ns. Then mr + ns = (s-1)r - s. Hence (s-1-m)r = (n+1)s, so r divides n+1. Say n+1=kr, and then s-1-m=ks, so m = (1-k)s - 1. But n+1 is positive, so k>=1, and hence m is negative. Contradiction.
If k is good, then c-k must be bad (otherwise c would be good). Suppose k is bad. Since r and s are relatively prime we can find integers a and b with ar + bs = 1 and hence integers m and n with mr + ns = k. Adding a multiple of sr - rs to both sides if necessary, this gives a pair m, n with mr + ns = k and m non-negative. Now take the pair with the smallest possible non-negative m. Then m <= s-1 (for otherwise m' = m-s, n' = n+r would be a pair with smaller non-negative m). Also n <= -1, otherwise k would be good. Now c - k = (s - 1 - m)r + (-n - 1)s and the coefficients s - 1 - m and -n - 1 are both non-negative, so c - k is good.
So exactly (rs - r - s + 1)/2 integers are bad.

Problem 14

A spy-plane circles point A at a distance 10 km with speed 1000 km/h. A missile is fired towards the plane from A at the same speed and moves so that it is always on the line between A and the plane. How long does it take to hit?
Solution

Answer: 18pi sec.
Let C be the position of the spy-plane at the moment the missile is fired. Let B be the point a quarter of the way around the circle from C (in the direction the spy-plane is moving). Then the missile moves along the semi-circle on diameter AB and hits the plane at B.
To see this take a point P on the quarter circle and let the line AX meet the semi-circle at Q. Let O be the center of the semicircle. The angle BOQ is twice the angle BAQ, so the arc BP is the same length as the arc BQ. Hence also the arc AQ is the same length as the arc CP.

Problem 15

Prove that the sum of the lengths of the edges of a polyhedron is at least 3 times the greatest distance between two points of the polyhedron.
Solution

If A and B are at the greatest distance, then they must be vertices. For suppose A is not a vertex. Then there is a segment XY entirely contained in the polyhedron with A as an interior point. But now at least one of angles BAX, BAY must be at least 90. Suppose it is BAX. Then BX is longer than BA. Contradiction.
Take a plane through A perpendicular to the line AB. Then the polyhedron must lie entirely on one side of the plane, for if Z lay on the opposite side to B, then BZ would be longer than BA. Now move the plane slightly towards B keeping it perpendicular to AB. The intersection of the plane and the polyhedron must be a small polygon. The polygon must have at least 3 vertices, each of which must lie on an edge of the polyhedron starting at A. Select three of these edges.
As the plane is moved further towards B, the selected vertices may sometimes split into multiple vertices or they may sometimes coalesce. In the former case, just choose one of the daughter vertices. In the latter case, let O be the point of intersection of the plane and AB. Let O' be the point of intersection at the last coalescence (or A if there was none). Then we have three paths along edges, with no edges in common, each of which projects onto O'O and hence has length at least O'O. Now select one or more new vertices to replace any lost through coalescence and repeat.

[Read More...]

4th All Russian Mathematical Olympiad Problems 1964

4th All Russian Mathematical Olympiad Problems 1964

1.  In the triangle ABC, the length of the altitude from A is not less than BC, and the length of the altitude from B is not less than AC. Find the angles.

2.  If m, k, n are natural numbers and n>1, prove that we cannot have m(m+1) = kⁿ.

3.  Reduce each of the first billion natural numbers (billion = 10⁹) to a single digit by taking its digit sum repeatedly. Do we get more 1s than 2s?

4.  Given n odd and a set of integers a₁, a₂, ... , a_n, derive a new set (a₁ + a₂)/2, (a₂ + a₃)/2, ... , (a_n-1 + a_n)/2, (a_n + a₁)/2. However many times we repeat this process for a particular starting set we always get integers. Prove that all the numbers in the starting set are equal. For example, if we started with 5, 9, 1, we would get 7, 5, 3, and then 6, 4, 5, and then 5, 4.5, 5.5. The last set does not consist entirely of integers.

5. (a)  The convex hexagon ABCDEF has all angles equal. Prove that AB - DE = EF - BC = CD - FA.

(b)  Given six lengths a₁, ... , a₆ satisfying a₁ - a₄ = a₅ - a₂ = a₃ - a₆, show that you can construct a hexagon with sides a₁, ... , a₆ and equal angles.

6.  Find all possible integer solutions for √(x + √(x ... (x + √(x)) ... )) = y, where there are 1998 square roots.

7.  ABCD is a convex quadrilateral. A' is the foot of the perpendicular from A to the diagonal BD, B' is the foot of the perpendicular from B to the diagonal AC, and so on. Prove that A'B'C'D' is similar to ABCD.

8.  Find all natural numbers n such that n² does not divide n!.

9.  Given a lattice of regular hexagons. A bug crawls from vertex A to vertex B along the edges of the hexagons, taking the shortest possible path (or one of them). Prove that it travels a distance at least AB/2 in one direction. If it travels exactly AB/2 in one direction, how many edges does it traverse?

10.  A circle center O is inscribed in ABCD (touching every side). Prove that ∠AOB + ∠COD = 180^o.

11.  The natural numbers a, b, n are such that for every natural number k not equal to b, b - k divides a - kⁿ. Prove that a = bⁿ.

12.  How many (algebraically) different expressions can we obtain by placing parentheses in a₁/a₂/ ... /a_n?

13.  What is the smallest number of tetrahedrons into which a cube can be partitioned?

14. (a)  Find the smallest square with last digit not 0 which becomes another square by the deletion of its last two digits. (b)  Find all squares, not containing the digits 0 or 5, such that if the second digit is deleted the resulting number divides the original one.

15.  A circle is inscribed in ABCD. AB is parallel to CD, and BC = AD. The diagonals AC, BD meet at E. The circles inscribed in ABE, BCE, CDE, DAE have radius r₁, r₂, r₃, r₄ respectively. Prove that 1/r₁ + 1/r₃ = 1/r₂ + 1/r₄.

Solutions

Problem 1

In the triangle ABC, the length of the altitude from A is not less than BC, and the length of the altitude from B is not less than AC. Find the angles.
Solution

Let k be twice the area of the triangle. Then k≥BC², k≥AC² and k≤AC.BC, with equality in the last case only if AC is perpendicular to BC. Hence AC and BC have equal lengths and are perpendicular. So the angles are 90, 45, 45.

Problem 2

If m, k, n are natural numbers and n>1, prove that we cannot have m(m+1) = kⁿ.
Solution

m and m+1 have no common divisors, so each must separately be an nth power. But the difference betwee the two nth powers is greater than 1 (for n>1).



Problem 3

Reduce each of the first billion natural numbers (billion = 10⁹) to a single digit by taking its digit sum repeatedly. Do we get more 1s than 2s?
Solution

Taking digit sums repeatedly gives the remainder after dividing the number by 9, or 9 if the number is exactly divisible by 9. 10⁹ - 1 = 9n, and for any r>=0 the nine consecutive numbers 9r+1, 9r+2, ... , 9r+9 include just one number giving remainder 1 and one number giving remainder 2. Hence the numbers up to 10⁹ - 1 give equal numbers of 1s and 2s. 10⁹ itself gives 1, so there is just one more of the 1s than the 2s.

Problem 4

Given n odd and a set of integers a₁, a₂, ... , a_n, derive a new set (a₁ + a₂)/2, (a₂ + a₃)/2, ... , (a_n-1 + a_n)/2, (a_n + a₁)/2. However many times we repeat this process for a particular starting set we always get integers. Prove that all the numbers in the starting set are equal.
For example, if we started with 5, 9, 1, we would get 7, 5, 3, and then 6, 4, 5, and then 5, 4.5, 5.5. The last set does not consist entirely of integers.
Solution

Let the smallest value be s and suppose it occurs m times (with m<n). Then the values in the next stage are all at least s, and at most m-1 equal s. So after at most m iterations the smallest value is increased.
We can never reach a stage where all the values are equal, because if (a₁+a₂)/2 = (a₂+a₃)/2 = ... = (a_n-1+a_n)/2 = (a_n+a₁)/2, then a₁+a₂ = a₂+a₃ and hence a₁ = a₃. Similarly, a₃ = a₅, and so a₁ = a₃ = a₅ = ... = a_n (n odd). Similarly, a₂ = a₄ = ... = a_n-1. But we also have a_n + a₁ = a₁ + a₂ and so a₂ = a_n, so that all a_i are equal. In other words, if all the values are equal at a particular stage, then they must have been equal at the previous stage, and hence at every stage.
Thus if the values do not start out all equal, then the smallest value increases indefinitely. But that is impossible, because the sum of the values is the same at each stage, and hence the smallest value can never exceed (a₁ + ... + a_n)/n.
Note that for n even the argument breaks down because a set of unequal numbers can iterate into a set of equal numbers. For example: 1, 3, 1, 3, ... , 1, 3.

Problem 5

The convex hexagon ABCDEF has all angles equal. Prove that AB - DE = EF - BC = CD - FA.

(b)  Given six lengths a₁, ... , a₆ satisfying a₁ - a₄ = a₅ - a₂ = a₃ - a₆, show that you can construct a hexagon with sides a₁, ... , a₆ and equal angles.
Solution

(a)  Extend AB, CD, EF. We get an equilateral triangle with sides AF + AB + BC, BC + CD + DE, ED + EF + FA. Hence AB - DE = CD - FA = EF - BC, as required.
(b)  Take an equilateral triangle with sides s, t, u lengths a₂ + a₃ + a₄, a₄ + a₅ + a₆, and a₆ + a₁ + a₂ respectively. Construct BC length a₂ parallel to t with B on u and C on s. Construct DE length a₄ parallel to u with D on s and E on t. Construct FA length a₆ parallel to s with F on t and A on u. Then ABCDEF is the required hexagon, with AB = a₁, BC = a₂ etc.



Problem 6

Find all possible integer solutions for sqrt(x + sqrt(x ... (x + sqrt(x)) ... )) = y, where there are 1998 square roots.
Solution

Let s₁ = sqrt(x), s₂ = sqrt(x + s₁), s₃ = sqrt(x + s₂) and so on. So the equation given is y = s₁₉₉₈. We show first that all s_n must be integral for 1 <= n <= 1998. y is integral, so s₁₉₉₈ is integral. Now suppose s_n is integral. Then s_n-1 = s_n² - x is integral, proving the claim.
So in particular s₁ and s₂ are integers and s₂² = s₁² + s₁. But if s₁ > 0, then s₁² < s₁² + s₁ < (s₁ + 1)², which is impossible. Similarly s₁ < 0 is impossible. So the only possible solution is s₁ = 0 and hence x = 0 and y = 0.

Problem 7

ABCD is a convex quadrilateral. A' is the foot of the perpendicular from A to the diagonal BD, B' is the foot of the perpendicular from B to the diagonal AC, and so on. Prove that A'B'C'D' is similar to ABCD.
Solution

Let the diagonals meet at O. Then CC'O is similar to AA'O (because CC'O = AA'O = 90, and COC', AOA' are opposite angles), so A'O/C'O = AO/CO. Similarly, B'O/D'O = BO/DO. AA'O is also similar to BB'O, so A'O/B'O = AO/BO. Thus OA':OB':OC':OD' = OA:OB:OC:OD. Hence triangles OA'B' and OAB are similar. Likewise OB'C' and OBC, OC'D' and OCD, and OD'A' and ODA. Hence result.



Problem 8

Find all natural numbers n such that n² does not divide n!.
Solution

Answer: n = 4 or prime.
If n = rs, with 1 < r < s, then r < s < n, and hence rsn = n² divides n!. Similarly, if n = r² with r > 2, then r < 2r < n, and hence n² divides n!. This covers all possibilities except n = 4 or n = prime, and it is easy to see that in these cases n² does not divide n!.

Problem 9

Given a lattice of regular hexagons. A bug crawls from vertex A to vertex B along edges of the hexagons, taking the shortest possible path (or one of them). Prove that it travels a distance at least AB/2 in one direction. If it travels exactly AB/2 in one direction, how many edges does it traverse?
Solution

1      2
    ./ \./ \.           directions    |     /
    |   |   |                         *    *     *
  ./°\./°\./°\.                                    \
  |   |   |   |                                    3
./°\./°\./°\./
|   |   |   |
*\./°\./°\./° 

Suppose vertex A is that marked * at the bottom left. Without loss of generality, B is in a 60 degree sector as shown. Assume the edges have unit length. The vertices can be partitioned into two sets (marked ° and . in the diagram). Each set forms a skewed lattice with axes at 60 degrees. Any path must alternate between the two lattices.
If B is on the same lattice as A, then we can give B coordinates (m,n) relative to A and the shortest path from A to B must move m units east and n units east of north. The shortest path between a lattice point and the next lattice point east is evidently one edge in direction 3 followed by one edge in direction 2. Similarly, the shortest path between a lattice point and the next lattice point east of north is one edge in direction 1, followed by one edge in direction 2. So a shortest path from A to B must have m+n edges in direction 2.
B is a distance √3(m+n/2) east of A and a distance 3n/2 north of A, so AB² = (3m²+3mn+3n²) < (4m²+8mn+4n²) = 4 (m+n)². So in this case the bug must travel more than AB/2 in direction 2.
Now suppose B is on the other lattice. Let C be the lattice point immediately north of A and D the lattice point in direction 3 from A. Then a shortest path from A to B must either be A to C and then a shortest path from C to B, or A to D and then a shortest path from D to B. Take B to have coordinates (m, n) relative to C or D.
In the first case, AB² = (√3(m+n/2))² + (3n/2 + 1)² = (3m² + 3mn + 3n²) + 3n + 1 and a shortest path has m+n units in direction 2. But 4(m + n)² > (3m² + 3mn + 3n²) + 3n + 1, if m² + n² + 5mn > 3n + 1, which is true for m, n at least 1. If m=0 and n=1, then a shortest path has 2 units in direction 1 and AB = √7 < 4. If m=1 and n=0, then AB=2 and a shortest path has 1 unit in each direction. So in this case (the only one so far) we have equality.
It remains to consider the case where the path starts out towards D. In this case AB² = (√3(m+n/2) + √3/2)² + (3n/2 -1/2)² = (3m²+3mn+3n²) + 3m + 1 and a path has m + n units in direction 2. But 4(m + n)² > (3m² + 3mn + 3n²) + 3m + 1 for m²+n² + 5mn > 3m + 1, which is true for m, n at least 1. If m=1, n=0, then a shortest path has 2 units in direction 3 and AB = √7 < 4. Finally, if m=0 and n=1, then a shortest path has 1 unit in each direction and AB = 2.
Thus the answer to the final question is 3, because the only cases where the bug travels exactly AB/2 in one direction are where it goes to the opposite vertex of a hexagon it is on.




Problem 10

A circle center O is inscribed in ABCD (touching every side). Prove that angle AOB + angle COD equals 180 degrees.
Solution

Let AB touch the circle at W, BC at X, CD at Y, and DA at Z. Then AO bisects angle ZOW and BO bisects angle XOW. So angle AOB is half angle ZOX. Similarly angle COD is half angle XOZ and hence angle AOB + angle COD equals 180.

Problem 11

The natural numbers a, b, n are such that for every natural number k not equal to b, b - k divides a - kⁿ. Prove that a = bⁿ.
Solution

We have kⁿ - a = bⁿ - a (mod b - k). Hence bⁿ - a = 0 (mod b- k) for every k not equal to b. But if bⁿ does not equal a, then by taking k - b > bⁿ - a we could render the equation false.

Problem 12

How many (algebraically) different expressions can we obtain by placing parentheses in a₁/a₂/ ... /a_n?
Solution

Answer 2^n-2. a₁ must be in the numerator, and a₂ must be in the denominator, but the other symbols can be in either. This is easily proved by induction.

Problem 13

What is the smallest number of tetrahedrons into which a cube can be partitioned?
Solution

Answer: 5.
Tetrahedral faces are triangular, so each cube face requires at least two tetrahedral faces. So at least 12 tetrahedral faces are needed in all. At most three faces of a tetrahedron can be mutually orthogonal (and no two faces can be parallel), so at most 3 faces from each tetrahedron can contribute towards these 12. So we require at least 4 tetrahedra to provide the cube faces. But these tetrahedra each have volume at most 1/6 (1/3 x face area x 1, and face area is at most 1/2). So if we have only 4 tetrahedra in total then their total volume is less than the cube's volume. Contradiction. Hence we need at least 5 tetrahedra.
It can be done with 5: lop off 4 non-adjacent corners to leave a tetrahedron. More precisely, take the cube as ABCDA'B'C'D' with ABCD horizontal, A' directly under A, B' directly under B and so on. Then the five tetrahedra are AA'BD, CC'BC, DD'A'C', BB'A'C', BDA'C'.

Problem 14

a)  Find the smallest square with last digit not 0 which becomes another square (not zero) by the deletion of its last two digits. #(b)  Find all squares, not containing the digits 0 or 5, such that if the second digit is deleted the resulting number divides the original one.
Solution

(a)  This one must have slipped through: 121!
(b)  Answer: 16,36,121,484. Suppose the number has more than 2 digits. Write it as (10m + n)10^r + s, where 1 <= m <= 9, 0 <= n <= 9, 0 <= s < 10^r. Then we have k(m.10^r + s) = (10m +n)10^r + s, for some k > 1.
s does not contain the digits 0 or 5, so 5 does not divide s. Hence 5 divides k-1, and so k must be 6, 11, or 16 (if k was 21 or more, then the rhs would be negative). Since 25 does not divide k-1, we must have r=1 and s is a single digit.
We look at each possibility for k in turn. k = 6 gives no solutions. k = 11 gives about two dozen multiples of 11 from 121 to 891. By inspection the only squares are 121 and 484. k = 16 gives 192, which is not a square.
In addition, there is the possibility of 2 digit solutions, which I had overlooked. It is easiest to check each of the 2 digit squares, thus finding the additional solutions 16, 36.

Problem 15

A circle is inscribed in ABCD. AB is parallel to CD, and BC = AD. The diagonals AC, BD meet at E. The circles inscribed in ABE, BCE, CDE, DAE have radius r₁, r₂, r₃, r₄ respectively. Prove that 1/r₁ + 1/r₃ = 1/r₂ + 1/r₄.
Solution

A necessary and sufficient condition for ABCD to have an inscribed circle is AB + CD = BC + AD. So we have AB + CD = 2AD, which we use repeatedly. Extend DC to X so that BX is parallel to EC. Then DX = AB + CD = 2AD and the triangles DEC, AEB, DBX are similar. Let h be the perpendicular distance from AB to CD. The similar triangles give us the heights of DEC and AEB in terms of h.
1/r₁ = perimeter ABE/(2 area ABE) = (AB + 2EB)/(AB.height) = (AB + 2.BD.AB/(AB+CD))/(AB.h.AB/(AB+CD)) = 2(AD + BD)/(AB.h). Similarly, 1/r₃ = 2(AD + BD)/(CD.h).
The area of AED = area ABD - area ABE = 1/2 AB.h.CD/(2AD), so 1/r₂ = 1/r₄ = perimeter ADE/(2 area ADE) = (AD + BD)/(h.AB.CD/2AD), and 1/r₂ + 1/r₄ = 2(AD + BD)/h   2AD/(AB.CD) = 2(AB + BD)/h   (AB + CD)/(AB.CD) = 1/r₁ + 1/r₃.

[Read More...]

3rd All Russian Mathematical Olympiad Problems 1963

3rd All Russian Mathematical Olympiad Problems 1963

1.  Given 5 circles. Every 4 have a common point. Prove that there is a point common to all 5.

2.  8 players compete in a tournament. Everyone plays everyone else just once. The winner of a game gets 1, the loser 0, or each gets 1/2 if the game is drawn. The final result is that everyone gets a different score and the player placing second gets the same as the total of the four bottom players. What was the result of the game between the player placing third and the player placing seventh?

3. (a)  The two diagonals of a quadrilateral each divide it into two parts of equal area. Prove it is a parallelogram.

(b)  The three main diagonals of a hexagon each divide it into two parts of equal area. Prove they have a common point. [If ABCDEF is a hexagon, then the main diagonals are AD, BE and CF.]

4.  The natural numbers m and n are relatively prime. Prove that the greatest common divisor of m+n and m²+n² is either 1 or 2.

5.  Given a circle c and two fixed points A, B on it. M is another point on c, and K is the midpoint of BM. P is the foot of the perpendicular from K to AM.

(a) prove that KP passes through a fixed point (as M varies);

(b) find the locus of P.

6.  Find the smallest value x such that, given any point inside an equilateral triangle of side 1, we can always choose two points on the sides of the triangle, collinear with the given point and a distance x apart.

7. (a)  A 6 x 6 board is tiled with 2 x 1 dominos. Prove that we can always divide the board into two rectangles each of which is tiled separately (with no domino crossing the dividing line).

(b)  Is this true for an 8 x 8 board?

8.  Given a set of n different positive reals {a₁, a₂, ... , a_n}. Take all possible non-empty subsets and form their sums. Prove we get at least n(n+1)/2 different sums.

9.  Given a triangle ABC. Let the line through C parallel to the angle bisector of B meet the angle bisector of A at D, and let the line through C parallel to the angle bisector of A meet the angle bisector of B at E. Prove that if DE is parallel to AB, then CA=CB.

10.  An infinite arithmetic progression contains a square. Prove it contains infinitely many squares.

11.  Can we label each vertex of a 45-gon with one of the digits 0, 1, ... , 9 so that for each pair of distinct digits i, j one of the 45 sides has vertices labeled i, j?

12.  Find all real p, q, a, b such that we have (2x-1)²⁰ - (ax+b)²⁰ = (x²+px+q)¹⁰ for all x.

13.  We place labeled points on a circle as follows. At step 1, take two points at opposite ends of a diameter and label them both 1. At step n>1, place a point at the midpoint of each arc created at step n-1 and label it with the sum of the labels at the two adjacent points. What is the total sum of the labels after step n?

For example, after step 4 we have: 1, 4, 3, 5, 2, 5, 3, 4, 1, 4, 3, 5, 2, 5, 3, 4.

14.  Given an isosceles triangle, find the locus of the point P inside the triangle such that the distance from P to the base equals the geometric mean of the distances to the sides.

Solutions

Problem 1

Given 5 circles. Every 4 have a common point. Prove that there is a point common to all 5. 

Solution

Let the circles be a, b, c, d, e. Let A be a point common to b, c, d, e, let B be a point common to a, c, d, e and so on. If any two of A, B, C, D, E coincide then the coincident point is on all 5 circles. Suppose they are all distinct. Then A, B, C are on d and e. Hence d and e coincide (3 points determine a circle). Hence D is on all 5 circles.

Problem 2

8 players compete in a tournament. Everyone plays everyone else just once. The winner of a game gets 1, the loser 0, or each gets 1/2 if the game is drawn. The final result is that everyone gets a different score and the player placing second gets the same as the total of the four bottom players. What was the result of the game between the player placing third and the player placing seventh? 

Solution

The bottom 4 played 6 games amongst themselves, so their scores must total at least 6. Hence the number 2 player scored at least 6. The maximum score possible is 7, so if the number 2 player scored more than 6, then he must have scored 6 1/2 and the top player 7. But then the top player must have won all his games, and hence the number 2 player lost at least one game and could not have scored 6 1/2. Hence the number 2 player scored exactly 6, and the bottom 4 players lost all their games with the top 4 players. In particular, the number 3 player won against the number 7 player.

Problem 3

(a)  The two diagonals of a quadrilateral each divide it into two parts of equal area. Prove it is a parallelogram.

(b)  The three main diagonals of a hexagon each divide it into two parts of equal area. Prove they have a common point. [If ABCDEF is a hexagon, then the main diagonals are AD, BE and CF.] 

Solution

(a)  Let the quadrilateral be ABCD and let the diagonals AC, BD meet at E. Then area ABC = AC.EB.sin CEB/2, and area ADC = AC.ED.sin CEB/2, so E is the midpoint of BD. Similarly, it is the midpoint of AC. Hence the triangles AEB and CED are congruent, so angle CDE = angle ABE, and hence AB is parallel to CD. Similarly, AD is parallel to BC.

(b)  Let the hexagon be ABCDEF. Let BE, CF meet at J, let AD, CF meet at K, and let AD, BE meet at L. Let AK=a, BJ=b, CJ=c, DL=d, EL=e, FK=f. Also let KL=x, JL=y and JK=z. Consider the pair of diagonals AD, BE. They divide the hexagon into 4 parts: the triangles ALB and DLE, and the quadrilaterals AFEL and BCDL. Since area ALB + area AFEL = area DLE + area BCDL, and area ALB + area BCDL = area DLE + area AFEL, the two triangles must have the same area (add the two inequalities). But area ALB = 1/2 AL.BL.sin ALB, and area DLE = 1/2 DL.EL.sin DLE = 1/2 DL.EL.sin ALB, so AL.BL = DL.EL or de = (a+x)(b+y). Similarly, considering the other two paris of diagonals, we get bc = (e+y)(f+z) and af = (c+z)(d+x). Multiplying the three inequalities gives: abcdef = (a+f)(b+y)(c+z)(d+x)(e+y)(f+z). But x, y, z are non-negative, so they must be zero and hence the three diagonals pass through a common point.

Problem 4

The natural numbers m and n are relatively prime. Prove that the greatest common divisor of m+n and m²+n² is either 1 or 2.Solution

If d divides m+n and m²+n², then it also divides (m+n)² - (m²+n²) = 2mn and hence also 2m(m+n) - 2mn = 2m² and 2n(m+n) - 2mn = 2n². But m and n are relatively prime, so m² and n² are also. Hence d must divide 2.

Problem 5

Given a circle c and two fixed points A, B on it. M is another point on c, and K is the midpoint of BM. P is the foot of the perpendicular from K to AM.

(a) prove that KP passes through a fixed point (as M varies);
(b) find the locus of P. 

Solution

(a)  Take Y on the circle so that angle ABY=90. Then AY is a diameter and so angle AMY=90. Take X as the midpoint of BY. Then triangles BXK and BYM are similar, so XK is parallel to YM. Hence XK is perpendicular to AM, and so P is the intersection of XK and AM. In other words, KP always passes through X.
(b)  P must lie on the circle diameter AX, and indeed all such points can be obtained (given a point P on the circle, take M as the intersection of AP and the original circle). So the locus of P is the circle diameter AX.

Problem 6
Find the smallest value x such that, given any point inside an equilateral triangle of side 1, we can always choose two points on the sides of the triangle, collinear with the given point and a distance x apart.

Solution

Answer: 2/3.
Let O be the center of ABC. Let AO meet BC at D, let BO meet CA at E, and let CO meet AB at F. Given any point X inside ABC, it lies in one of the quadrilaterals AEOF, CDOE, BFOD. Without loss of generality, it lies in AEOF. Take the line through X parallel to BC. It meets AB in P and AC in Q. Then PQ is shorter than the parallel line MON with M on AB and N on AC, which has length 2/3. If we twist the segment PXQ so that it continues to pass through X, and P remains on AB and Q on AC, then its length will change continuously. Eventually, one end will reach a vertex, whilst the other will be on the opposite side and hence the length of the segment will be at least that of an altitude, which is greater than 2/3. So at some intermediate position its length will be 2/3.
To show that no value smaller than 2/3 is possible, it is sufficient to show that any segment POQ with P and Q on the sides of the triangle has length at least 2/3. Take P on MB and Q on AN with P, O, Q collinear. Then PQ cos POM = MN - QN cospi/3 + PM cos pi/3. But PM>QN (using the sine rule, PM = OM sinPOM/sinOPM and QN = ON sinQON/sinOQN, but OM=ON, angle POM = angle QON, and angle OQN = angle OPM + pi/3 > angle OPM), and hence PQ > MN sec POM > MN.

Problem 7

(a)  A 6 x 6 board is tiled with 2 x 1 dominos. Prove that we can always divide the board into two rectangles each of which is tiled separately (with no domino crossing the dividing line).
#(b)  Is this true for an 8 x 8 board?
Solution

(a)  We say a domino bridges two columns if half the domino is in each column. We show that for 0<n<6 the number of dominoes bridging columns n and n+1 must be at least 2 and even.
Consider first n=1. There cannot be 3 dominoes entirely in column 1, or it would be separately tiled. So there must be at least one domino bridging columns 1 and 2. The number must be even, because it must equal the number of squares in column 1 (even) less twice the number of dominoes (entirely) in column 1.
Now suppose it is true for n<5 and consider column n+1. There must be at least one domino bridging columns n+1 and n+2, or columns 1 thru n+1 would be separately tiled. The number must be even, because it must equal the number of squares in column n+1 (even) less the number bridging n and n+1 (even) less twice the number entirely in the column.
So in total there are at least 5 x 2 = 10 dominoes bridging columns. By the same argument there are at least another 10 bridging rows, but there are only 18 dominoes in total.
(b)  No. For example:

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

 

Problem 8

Given a set of n different positive reals {a₁, a₂, ... , a_n}. Take all possible non-empty subsets and form their sums. Prove we get at least n(n+1)/2 different sums.
Solution

Assume a₁ < a₂ < ... < a_n. We have the following collection of increasing sums:

a1 < a2 < ... < an		n sums
a1+an < a2+an < ... < an-1+an		n-1 sums
a1+an-1+an < a2+an-1+an < ... < an-2+an-1+an		n-2 sums
...
a1 + a2 + ... + an		1 sum

A total of 1+2+ ... +n = n(n+1)/2.




Problem 9

Given a triangle ABC. Let the line through C parallel to the angle bisector of B meet the angle bisector of A at D, and let the line through C parallel to the angle bisector of A meet the angle bisector of B at E. Prove that if DE is parallel to AB, then CA=CB.
Solution

The idea is to find an expression for the perpendicular distance h from D to AB. Let γ = ∠ACB, α = ½∠CAB, and β = ½∠ABC. We have h = AP sin α.
Using the sine rule on APC, we have AP = AC sin(γ+β)/sin(α+β), so h = AC sin α sin(γ+β)/sin(α+β). Similarly, the perpendicular distance k from E to AB is BC sin β sin(γ+α)/sin(α+β).
We also have that AC/BC = sin 2β/sin 2α, and hence h/k = sin 2β sin α sin(γ+β)/(sin 2α sin β sin(γ+α)). Using the fact that sin(γ+β) = sin(2α+β), and the expression for sin 2θ, we get h/k = (sin(2α+2β) + sin 2α)/(sin(2α+2β) + sin 2β) and hence h = k iff the triangle is isosceles.
For some reason the geometric solution took me longer to find. Let ED meet BC at X. Then XCD and XBE are isosceles, so BC = BX + XC = DX + XE = DE. Similarly, AC = DE. Hence AC = BC.

Problem 10

An infinite arithmetic progression contains a square. Prove it contains infinitely many squares.
Solution

Let the square be a² and the difference d, so that all numbers of the form a²+nd belong to the arithmetic progression (for n a natural number). Take n to be 2ar + dr², then a²+nd = (a+dr)².



Problem 11

Can we label each vertex of a 45-gon with one of the digits 0, 1, ... , 9 so that for each pair of distinct digits i, j one of the 45 sides has vertices labeled i, j?
Solution

10 x 5 > 45, so some digit i₀ must appear less than 5 times. But each occurrence can give at most 2 edges i₀, j, so there are at most 8 edges i₀, j, which is one too few.


Problem 12

Find all real p, q, a, b such that we have (2x-1)²⁰ - (ax+b)²⁰ = (x²+px+q)¹⁰ for all x.
Solution

Comparing coefficients of x²⁰, we must have a = (2²⁰ - 1)^1/20 (note that we allow either the positive or the negative root).
Set x=1/2. Then we must have (ax + b)²⁰ = 0 = (x²+px+q)¹⁰, and hence ax + b =0 and x²+px+q = 0. So b = -a/2, and 1/4 + p/2 + q = 0.
Set x=0. Then we get q¹⁰ = 1 - b²⁰ = 1/2²⁰, so q = 1/4 or -1/4, and p= -1 or 0 respectively. Comparing the coefficients of x¹⁹, we must have p = -1 and q = 1/4. So, if there is a solution, then it must be: a = (2²⁰ - 1)^1/20, b = -a/2, p = -1, q = 1/4. This is indeed a solution because with these values, the lhs = 2²⁰(x - 1/2)²⁰ - (x - 1/2)²⁰a²⁰ = (x - 1/2)²⁰ = (x² - x + 1/4)¹⁰ = rhs.

Problem 13

We place labeled points on a circle as follows. At step 1, take two points at opposite ends of a diameter and label them both 1. At step n>1, place a point at the midpoint of each arc created at step n-1 and label it with the sum of the labels at the two adjacent points. What is the total sum of the labels after step n?

For example, after step 4 we have: 1, 4, 3, 5, 2, 5, 3, 4, 1, 4, 3, 5, 2, 5, 3, 4.
Solution


Answer: 2.3^n-1.
True for n=1. The new points added at step n+1 have twice the sum of the points after step n, because each old point contributes to two new points. hence the total after step n+1 is three times the total after step n.

Problem 14

Given an isosceles triangle, find the locus of the point P inside the triangle such that the distance from P to the base equals the geometric mean of the distances to the sides.
Solution

Let the triangle be ABC, with AB=AC. Take the circle through B and C which has AB and AC as tangents. The required locus is the arc BC.
Suppose P lies on the arc. Let the perpendiculars from P meet BC in L, AB in N and AC in M. Join PB and PC. The triangles PNB and PLC are similar (PNB and PLC are both 90, and NBP = LCP because NB is tangent to the circle). Hence PN/PL = PB/PC. Similarly, triangles PMC and PLB are similar and hence PM/PL = PC/PB. Multiplying gives the required result PL² = PM.PN.
If P is inside the circle and not on it, take P' as the intersection of the line AP and the arc. We have PL<P'L, but PM>P'M and PN>P'N, hence PL²<PM.PN. Similarly, if P is outside the circle and not on it, then PL²>PM.PN.

[Read More...]

2nd All Russian Mathematical Olympiad Problems 1962

2nd All Russian Mathematical Olympiad Problems 1962

1.  ABCD is any convex quadrilateral. Construct a new quadrilateral as follows. Take A' so that A is the midpoint of DA'; similarly, B' so that B is the midpoint of AB'; C' so that C is the midpoint of BC'; and D' so that D is the midpoint of CD'. Show that the area of A'B'C'D' is five times the area of ABCD.

2.  Given a fixed circle C and a line L throught the center O of C. Take a variable point P on L and let K be the circle center P through O. Let T be the point where a common tangent to C and K meets K. What is the locus of T?

3.  Given integers a₀, a₁, ... , a₁₀₀, satisfying a₁>a₀, a₁>0, and a_r+2=3 a_r+1 - 2 a_r for r=0, 1, ... , 98. Prove a₁₀₀ > 2⁹⁹

4.  Prove that there are no integers a, b, c, d such that the polynomial ax³+bx²+cx+d equals 1 at x=19 and 2 at x=62.

5.  Given an n x n array of numbers. n is odd and each number in the array is 1 or -1. Prove that the number of rows and columns containing an odd number of -1s cannot total n.

6.  Given the lengths AB and BC and the fact that the medians to those two sides are perpendicular, construct the triangle ABC.

7.  Given four positive real numbers a, b, c, d such that abcd=1, prove that a² + b² + c² + d² + ab + ac + ad + bc + bd + cd ≥ 10.

8.  Given a fixed regular pentagon ABCDE with side 1. Let M be an arbitary point inside or on it. Let the distance from M to the closest vertex be r₁, to the next closest be r₂ and so on, so that the distances from M to the five vertices satisfy r₁ ≤ r₂ ≤ r₃ ≤ r₄ ≤ r₅. Find (a) the locus of M which gives r₃ the minimum possible value, and (b) the locus of M which gives r₃ the maximum possible value.

9.  Given a number with 1998 digits which is divisible by 9. Let x be the sum of its digits, let y be the sum of the digits of x, and z the sum of the digits of y. Find z.

10.  AB=BC and M is the midpoint of AC. H is chosen on BC so that MH is perpendicular to BC. P is the midpoint of MH. Prove that AH is perpendicular to BP.

11.  The triangle ABC satisfies 0 ≤ AB ≤ 1 ≤ BC ≤ 2 ≤ CA ≤ 3. What is the maximum area it can have?

12.  Given unequal integers x, y, z prove that (x-y)⁵ + (y-z)⁵ + (z-x)⁵ is divisible by 5(x-y)(y-z)(z-x).

13.  Given a₀, a₁, ... , a_n, satisfying a₀ = a_n = 0, and and a_k-1 - 2a_k + a_k+1 ≥ 0 for k=0, 1, ... , n-1. Prove that all the numbers are negative or zero.

14.  Given two sets of positive numbers with the same sum. The first set has m numbers and the second n. Prove that you can find a set of less than m+n positive numbers which can be arranged to part fill an m x n array, so that the row and column sums are the two given sets. 

Solutions

Problem 1

ABCD is any convex quadrilateral. Construct a new quadrilateral as follows. Take A' so that A is the midpoint of DA'; similarly, B' so that B is the midpoint of AB'; C' so that C is the midpoint of BC'; and D' so that D is the midpoint of CD'. Show that the area of A'B'C'D' is five times the area of ABCD. 

Solution

Compare the triangles A'B'A and ADB. The base of A'B'A can be taken as A'A, which is the same length as AD. The height of A'B'A is AB' times sin B'AA', which is twice AB times sin BAD. So area A'B'A = 2 area ADB. Similarly, area B'C'B = 2 area BAC, area C'D'C = 2 area CBD, and area D'A'D = 2 area DCA. So adding, the area A'B'A + area C'D'C = 2 area ABCD, and area B'C'B + area D'A'D = 2 area ABCD. But ABCD = A'B'A + B'C'B + C'D'C + D'A'D + ABCD. Hence result.

Problem 2

Given a fixed circle C and a line L throught the center O of C. Take a variable point P on L and let K be the circle center P through O. Let T be the point where a common tangent to C and K meets K. What is the locus of T?

Solution

Let the common tangent meet C at S. Let X be the intersection of C and OP lying between O and P. PT = PO, hence ∠POT = ∠PTO, so ∠OPT = 180^o - 2 ∠POT. But PT and OS are parallel, because both are perpendicular to the common tangent. Hence ∠POS = 2 ∠POT, so ∠SOT = ∠XOT. Hence TX is tangent to C, in other words T lies on the (fixed) tangent to C at X. Conversely, it is easy to see that any such point can be obtained (just take P such that PO = PT). Thus the required locus is the pair of tangents to C which are perpendicular to L. 

Problem 3

Given integers a₀, a₁, ... , a₁₀₀, satisfying a₁>a₀, a₁>0, and a_r+2=3 a_r+1 - 2 a_r for r=0, 1, ... , 98. Prove a₁₀₀ > 2⁹⁹. 

Solution

An easy induction gives a_r = (2^r - 1)a₁ - (2^r - 2)a₀ for r = 2, 3, ... , 100. Hence, in particular, a₁₀₀ = (2¹⁰⁰ - 2)(a₁ - a₀) + a₁. But a₁ and (a₁ - a₀) are both at least 1. Hence result. 

Problem 4

Prove that there are no integers a, b, c, d such that the polynomial ax³+bx²+cx+d equals 1 at x=19 and 2 at x=62. 

Solution

If there were such values, then subtract the equation with x = 19 from the equation with x = 62 to get: a(62³ - 19³) + b(62² - 19²) + c(62 - 19) = 1. But the left hand side is divisible by 62 -19 = 43, contradiction. 

Problem 5

Given an n x n array of numbers. n is odd and each number in the array is 1 or -1. Prove that the number of rows and columns containing an odd number of -1s cannot total n. 

Solution

If we change a -1 to 1, we affect the total number of rows and columns (containing an odd number of -1s) by 0, 2 or -2. After changing all the -1s we have total of 0. Hence the starting total must be even. So it cannot be n. 

Problem 6

Given the lengths AB and BC and the fact that the medians to those two sides are perpendicular, construct the triangle ABC. 

Solution

Let M be the midpoint of AB and X the midpoint of MB. Construct the circle center B, radius BC/2 and the circle diameter AX. If they do not intersect (so BC<AB/2 or BC>AB) then the construction is not possible. If they intersect at N, then take C so that N is the midpoint of BC. Let CM meet AN at O. Then AO/AN = AM/AX =2/3, so the triangles AOM and ANX are similar. Hence ∠AOM = ∠ANX = 90^o. 

Problem 7

Given four positive real numbers a, b, c, d such that abcd=1, prove that a² + b² + c² + d² + ab + ac + ad + bc + bd + cd >= 10. 

Solution

Applying the arithmetic/geometric mean result to the 10 numbers gives the result immediately. 

Problem 8

Given a fixed regular pentagon ABCDE with side 1. Let M be an arbitary point inside or on it. Let the distance from M to the closest vertex be r₁, to the next closest be r₂ and so on, so that the distances from M to the five vertices satisfy r₁ ≤ r₂ ≤ r₃ ≤ r₄ ≤ r₅. Find (a) the locus of M which gives r₃ the minimum possible value, and (b) the locus of M which gives r₃ the maximum possible value. 

Solution

Let X be the midpoint of AB and O the center of ABCDE. Suppose M lies inside AXO. Then ME=r₃. So we maximise r₃ by taking M at X, with distance 1.5590, and we minimise r₃ by taking M as the intersection of AO and EB with distance 0.8090. AXO is one of 10 congruent areas, so the required loci are (a) the 5 midpoints of the diagonals, and (b) the 5 midpoints of the sides. 

Problem 9

Given a number with 1998 digits which is divisible by 9. Let x be the sum of its digits, let y be the sum of the digits of x, and z the sum of the digits of y. Find z. 

Solution

x ≤ 9·1998 = 17982. Hence y ≤ the greater of 1+7+9+9+9=35 and 9+9+9+9=36. But 9 divides the original number and hence also x, y and z. Hence z=9. 

Problem 10

AB=BC and M is the midpoint of AC. H is chosen on BC so that MH is perpendicular to BC. P is the midpoint of MH. Prove that AH is perpendicular to BP. 

Solution

Take X on AH so that BX is perpendicular to AH. Extend to meet HM at P'. Let N be the midpoint of AB. A, B, M and X are on the circle center N radius NA (because angles AMB and AXB are 90). Also MN is parallel to BC (because AMN, ACB are similar), so NM is perpendicular to MH, in other words HM is a tangent to the circle. hence P'M·P'M = P'X·P'B. Triangles P'XH and P'HB are similar (angles at P' same and both have a right angle), so P'H/P'X = P'B/P'H, so P'H·P'H = P'X·P'B. Hence P'H = P'M and P' coincides with P. 

Problem 11

The triangle ABC satisfies 0 ≤ AB ≤ 1 ≤ BC ≤ 2 ≤ CA ≤ 3. What is the maximum area it can have? 

Solution

If we ignore the restrictions of CA, then the maximum area is 1, achieved when AB is perpendicular to BC. But in this case CA satisfies the restrictions. 

Problem 12

Given unequal integers x, y, z prove that (x-y)⁵ + (y-z)⁵ + (z-x)⁵ is divisible by 5(x-y)(y-z)(z-x). 

Solution

Put x-y=r, y-z=s. Then z-x = -(r+s), and (x-y)⁵ + (y-z)⁵ + (z-x)⁵ = r⁵ + s⁵ - (r+s)⁵ = -5r⁴s - 10r³s² - 10r²s³ - 5rs⁴ = -5rs(r+s)(r² + rs + s²). 

Problem 13

Given a₀, a₁, ... , a_n, satisfying a₀ = a_n = 0, and and a_k-1 - 2a_k + a_k+1 ≥ 0 for k=0, 1, ... , n-1. Prove that all the numbers are negative or zero.

Solution

The essential point is that if we plot the values a_r against r, then the curve formed by joining the points is cup shaped. Its two endpoints are on the axis, so the other points cannot be above it.There are many ways of turning this insight into a formal proof. Barry Paul's was neater than mine: a_r+1-a_r ≥ a_r-a_r-1. Hence (easy induction) if a_s - a_s-1> 0, then a_n > a_s. Take a_s to be the first positive, then certainly a_s > a_s-1, so a_n > 0. Contradiction. 

Problem 14

Given two sets of positive numbers with the same sum. The first set has m numbers and the second n. Prove that you can find a set of less than m+n positive numbers which can be arranged to part fill an m x n array, so that the row and column sums are the two given sets.

Example: row sums 1, 5, 3; column sums 2, 7. Array is:

x5
x1
21

Solution

Induction on m+n. Trivial for m+n=2.

Let x be the largest number in the two given sets. Suppose it is a row total; let y be the largest column total. If y<x, then replace x by x-y in the set of row totals and remove y from the col totals. By induction find <=m+n-2 positive numbers in an m x (n-1) array with the new totals. Adding a col empty except for y in the row totalling x-y gives the required original set.

If y=x, then drop x from the row totals and y from the col totals and argue as before.

If x was a col total we interchange rows and cols in the argument.

[Read More...]