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 x2 + y and x + y2 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 a1, a2, ... , an, such that ai-1 ≤ ai ≤ 2ai-1 for i = 2, 3, ... , n. Show that you can form a sum s = b1a1 + ... + bnan with each bi +1 or -1, so that 0 ≤ s ≤ a1.
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 A1, A2, ... , An such that A=A1, B=An and there is an edge between Ai and Ai+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 A1, A2, ... , An with Ai watching Ai+1 for 0 < i < n, and An watching A1. Then the distance Ai-1Ai is greater than the distance AiAi+1 for 1 < i < n, and the distance A1An is less than the distance A1A2. Hence the distance A1An is less than the distance An-1An and so An-1 is closer to An than A1. 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 x2 + y and x + y2 be squares for x and y natural numbers?
Solution
No. The smallest square greater than x2 is (x+1)2, 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 ai and heights in the front row by bi. So we have a1 ≤ a2 ≤ ... ≤ an, and ai > bi for i = 1, 2, ... , n.
Now if i < j, but bi > bj, then we may swap bi and bj and still have each child taller than the child in front of him. For bi < ai <= aj, and bj < bi < ai. 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 a1, a2, ... , an, such that ai-1 <= ai <= 2ai-1 for i = 2, 3, ... , n. Show that you can form a sum s = b1a1 + ... + bnan with each bi +1 or -1, so that 0 <= s <= a1.
Solution
We show that you can pick bn, bn-1, ... , br so that sr = bnan + bn-1an-1 + ... + brar satisfies 0 <= sr <= ar. Induction on r. Trivial for r = n. Suppose true for r. Then - ar-1 <= sr - ar-1 <= ar - ar-1 <= ar-1. So with br-1 = -1 we have |sr-1| <= ar-1. If necessary, we change the sign of all bn, bn-1, ... , br-1 and obtain sr-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 A1, A2, ... , An such that A=A1, B=An and there is an edge between Ai and Ai+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=A0, A1, ... , An=B. We show by induction on r that we can find two disjoint paths from A to Ar. If r = 1, then take any vertex C distinct from A and A1. Take any path from A1 to C which does not go through A. Now take any path from C to A which does not go through A1. Joining these two paths together gives a path p from A to A1 which does not involve the edge AA1. Then p and the edge AA1 are the required disjoint paths.
Suppose now we have two disjoint paths A, B1, B2, ... , Bs, Ar and A, Bt, Bt-1, ... , Bs+1, Ar and we wish to find two disjoint paths joining A and Ar+1. Take a path between A and Ar+1 which does not include Ar. If it also avoids all of B1, ... , Bt, then we are home, because it is disjoint from the alternative path A, B1, B2, ... , Bs, Ar, Ar+1. If not, let Bi be the first of the B's on the path as we move from Ar+1 to A. This allows us to construct two disjoint paths from A to Ar+1. One path goes from A to Bi and then from Bi to Ar+1. The other path goes around the other way to Ar and then along the edge to Ar+1. [Explicitly, if i <= s, then the paths are A, B1, B2, ... , Bi, ... (new path) ... Ar+1 and A, Bt, Bt-1, ... , Ar, Ar+1. If i > s, then the paths are A, Bt, Bt-1, ... , Bi, ... (new path) ... Ar+1 and A, B1, ... , Bs, Ar, Ar+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 hA be the perpendicular distance from A to the line BC. Then PH = h tan α, and the altitude from A to PBC is hA sin α. Hence if PH is shorter than the altitude from A we require that h < hA cos α < hA. 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 < hA 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(h2 + y2)/(h - ay). Similarly, eliminating φ, we obtain x = b(h2 + (d-y)2)/(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(h2 + y2)/h = b(h2 + (d-y)2)/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)2 - aY2). 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, a1, a2, ... , an (where 1 ≤ n ≤ 9) which require a reply under (4). The reason a1 required a move under (4) was that a1-1 or a1+1 was the 1st player's response to 20. Similarly, the reason a2 required a move under (4) was that a2-1 or a2+1 was the 1st player's response to a2, and so on. Thus the increment to the absolute value from these moves is at most |20-a1+1| + |a1-a2+1| + ... + |an-1-an+1| + |an| = 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.
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 A1, A2, ... , An with Ai watching Ai+1 for 0 < i < n, and An watching A1. Then the distance Ai-1Ai is greater than the distance AiAi+1 for 1 < i < n, and the distance A1An is less than the distance A1A2. Hence the distance A1An is less than the distance An-1An and so An-1 is closer to An than A1. 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 x2 + y and x + y2 be squares for x and y natural numbers?
Solution
No. The smallest square greater than x2 is (x+1)2, 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 ai and heights in the front row by bi. So we have a1 ≤ a2 ≤ ... ≤ an, and ai > bi for i = 1, 2, ... , n.
Now if i < j, but bi > bj, then we may swap bi and bj and still have each child taller than the child in front of him. For bi < ai <= aj, and bj < bi < ai. 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 a1, a2, ... , an, such that ai-1 <= ai <= 2ai-1 for i = 2, 3, ... , n. Show that you can form a sum s = b1a1 + ... + bnan with each bi +1 or -1, so that 0 <= s <= a1.
Solution
We show that you can pick bn, bn-1, ... , br so that sr = bnan + bn-1an-1 + ... + brar satisfies 0 <= sr <= ar. Induction on r. Trivial for r = n. Suppose true for r. Then - ar-1 <= sr - ar-1 <= ar - ar-1 <= ar-1. So with br-1 = -1 we have |sr-1| <= ar-1. If necessary, we change the sign of all bn, bn-1, ... , br-1 and obtain sr-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 A1, A2, ... , An such that A=A1, B=An and there is an edge between Ai and Ai+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=A0, A1, ... , An=B. We show by induction on r that we can find two disjoint paths from A to Ar. If r = 1, then take any vertex C distinct from A and A1. Take any path from A1 to C which does not go through A. Now take any path from C to A which does not go through A1. Joining these two paths together gives a path p from A to A1 which does not involve the edge AA1. Then p and the edge AA1 are the required disjoint paths.
Suppose now we have two disjoint paths A, B1, B2, ... , Bs, Ar and A, Bt, Bt-1, ... , Bs+1, Ar and we wish to find two disjoint paths joining A and Ar+1. Take a path between A and Ar+1 which does not include Ar. If it also avoids all of B1, ... , Bt, then we are home, because it is disjoint from the alternative path A, B1, B2, ... , Bs, Ar, Ar+1. If not, let Bi be the first of the B's on the path as we move from Ar+1 to A. This allows us to construct two disjoint paths from A to Ar+1. One path goes from A to Bi and then from Bi to Ar+1. The other path goes around the other way to Ar and then along the edge to Ar+1. [Explicitly, if i <= s, then the paths are A, B1, B2, ... , Bi, ... (new path) ... Ar+1 and A, Bt, Bt-1, ... , Ar, Ar+1. If i > s, then the paths are A, Bt, Bt-1, ... , Bi, ... (new path) ... Ar+1 and A, B1, ... , Bs, Ar, Ar+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 hA be the perpendicular distance from A to the line BC. Then PH = h tan α, and the altitude from A to PBC is hA sin α. Hence if PH is shorter than the altitude from A we require that h < hA cos α < hA. 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 < hA 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(h2 + y2)/(h - ay). Similarly, eliminating φ, we obtain x = b(h2 + (d-y)2)/(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(h2 + y2)/h = b(h2 + (d-y)2)/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)2 - aY2). 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, a1, a2, ... , an (where 1 ≤ n ≤ 9) which require a reply under (4). The reason a1 required a move under (4) was that a1-1 or a1+1 was the 1st player's response to 20. Similarly, the reason a2 required a move under (4) was that a2-1 or a2+1 was the 1st player's response to a2, and so on. Thus the increment to the absolute value from these moves is at most |20-a1+1| + |a1-a2+1| + ... + |an-1-an+1| + |an| = 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.
Labels:
ARMO,
Russian Mathematical Olympiad
Previous Article
