5th All Russian Mathematical Olympiad Problems 1965
1. (a) Each of x1, ... , xn is -1, 0 or 1. What is the minimal possible value of the sum of all xixj with 1 ≤ i < j ≤ n? (b) Is the answer the same if the xi are real numbers satisfying 0 ≤ |xi| ≤ 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 n2 numbers xij satisfy the n3 equations: xij + xjk + xki = 0. Prove that we can find numbers a1, ... , an such that xij = ai - aj.
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 a1, a2, ... , an, prove that you can find n integers b1, b2, ... , bn, such that the sum of any subset of the original numbers differs from the sum of the corresponding bi 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 x1, ... , xn is -1, 0 or 1. What is the minimal possible value of the sum of all xixj with 1 <= i < j <= n? (b) Is the answer the same if the xi are real numbers satisfying 0 <= |xi| <= 1 for 1 <= i <= n?
Solution
(a) Answer: -[n/2].
Let A = (x1 + ... + xn)2, B = x12 + ... + xn2. 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 xi is a minimal sum with sum less than -[n/2]. Let xn = x, then the sum is x(x1 + ... + xn-1) + sum of terms xixj with 1 <= i, j < n. But this is less than the sum for n-1, so x(x1 + ... + xn-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:
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 a1>a2> ... >a9. Let t1 = a1 + a9, t2 = a2 + a8, t3 = a3 + a7, t4 = a4 + a6.
If t1 > t2, or t1 = t2 > t3, or t1 = t2 = t3 >= t4 (*), then F's strategy is to get a total of t1 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 t1 or lower, and to get a higher score.
If (*) holds, then F starts by playing a1 to an F-square. S must play to the remaining F-square, otherwise F will play a3 or better to it on his next move and win. So S must play a9 to the remaining F-square, giving F a total of t1.
Now if t1 > t2, then F forces S to t2 or worse by playing a8 to an S-square.
If t1 = t2 > t3, then F forces S to t3 or worse by playing a2 to a neutral square. If S plays to an S-square, then he cannot do better than a3 + a8, which loses. So he plays a8 to a neutral square. But now F plays a3 to an S-square, and S cannot do better than t3.
If t1 = t2 = t3 > t4, then F forces S to t4 or worse. He starts by playing a2 to a neutral square. If does not prevent F playing a8 to an S-square on his next move, then he cannot do better than a3 + a8, which loses. So he must play a8 to a neutral square. Now F plays a3 to a neutral square. If S does not prevent F playing a7 to an S-square on the following move, then he cannot do better than a4 + a7 which loses, so he plays a7 to a neutral square. F now plays a4 to an S-square. S cannot now do better than t4, which loses.
Finally, if t1 = t2 = t3 = t4, then F proceeds as in the last case except that at the end he plays a4 to the last neutral square instead of to an S-square. S now gets a5 + a6 on the S-squares, which loses.
If (*) does not hold, then F starts by playing a9 to an S-square. If S does not play to the other S-square, then F will play a7 or a8 there on his next move and S will lose. So S must play a1 to the other square, and gets a total of t1. F now plays to get t2, t3 or t4 on the F-squares.
If t1 < t2, then F plays a2 to an F-square and so gets at least t2 and wins.
If t1 = t2 < t3, then F plays a8 to a neutral square. If S does not prevent F playing a2to an F-square on his next move, then F will get at least a2 + a7 and win. So S must play a2 to a neutral square. Now F plays a3 to an F-square and so gets at least t3 on the F-squares and wins.
Finally, if t1 = t2 = t3 < t4, then F plays as in the previous case, except that at the end he plays a7 to a neutral square instead of a3 to an F-square. S must prevent F playing a3 to an F-square the following move, or F gets at least a3 + a6 and wins. So S plays a3 to a neutral square. F now plays a4 to an F square and so must get at least t4, 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 = (p2/8 - 2(BC - p/4)2)/p. So the maximum occurs when BC = p/4 and has value p/8.
Problem 8
The n2 numbers xij satisfy the n3 equations: xij + xjk + xki = 0. Prove that we can find numbers a1, ... , an such that xij = ai - aj.
Solution
Taking i = j = k, we have that xii = 0. Now taking j=k, we have that xij = - xji. Define ai = xi1. Then we have xi1 + x1j + xji = 0. Hence xij = ai - aj.
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 a1, a2, ... , an, prove that you can find n integers b1, b2, ... , bn, such that |ai - bi| < 1 and the sum of any subset of the original numbers differs from the sum of the corresponding bi by at most (n + 1)/4.
Solution
We can take all ai to lie in the range (0,1) and all bi to be 0 or 1. The largest positive value of the sum of (ai - bi) for any subset is achieved by taking the subset of those i for which bi = 0. Similarly, the largest negative value is achieved by taking those i for which bi = 1. So the worst subset will be one of those two.
If ai < aj, then we cannot have bi = 1 and bj = 0 if the set of bis 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 a1 <= a2 <= ... <= an, then a best set of b's is bi = 0 for i <= some k, and bi = 1 for i > k. [If some of the ai 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 Li = a1 + a2 + ... + ai, and Ri = ai+1 + ai+2 + ... + an. As we increase i the sums Li increase and the sums Ri decrease, so for some k we must have Lk < Rk, Lk+1 >= Rk+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 Lk+1 = Rk. Suppose Lk+1 < Rk. Then we could increase each of ak+1, ak+2, ... , an by epsilon. This would leave Lk unaffected, but slightly increase Lk+1 and slightly reduce Rk. For small epsilon this does not change the value of k, but increases the smaller of Lk+1 and Rk, thus increasing the minimum and contradicting the maximality of the original a's. Similarly, if Lk+1 > Rk, we could decrease each of a1, a2, ... , ak+1 by epsilon, thus slightly increasing Rk and reducing Lk+1.
Suppose not all of a1, a2, ... , ak+1 are equal. Take i so that ai < ai+1. Now increase each of a1, a2, ... , ai by epsilon and reduce each of ai+1, ai+2, ... , ak+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 Lk+1 is increased. Rk is also increased, so we contradict the maximality of the a's. Hence all a1, a2, ... , ak+1 are equal. Similarly, we show that all of ak+1, ... , an are equal. For if not we can increase slightly ak+1, ... , aj and reduce slightly aj+1, ... , an 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.
Solutions
Problem 1
(a) Each of x1, ... , xn is -1, 0 or 1. What is the minimal possible value of the sum of all xixj with 1 <= i < j <= n? (b) Is the answer the same if the xi are real numbers satisfying 0 <= |xi| <= 1 for 1 <= i <= n?
Solution
(a) Answer: -[n/2].
Let A = (x1 + ... + xn)2, B = x12 + ... + xn2. 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 xi is a minimal sum with sum less than -[n/2]. Let xn = x, then the sum is x(x1 + ... + xn-1) + sum of terms xixj with 1 <= i, j < n. But this is less than the sum for n-1, so x(x1 + ... + xn-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 a1>a2> ... >a9. Let t1 = a1 + a9, t2 = a2 + a8, t3 = a3 + a7, t4 = a4 + a6.
If t1 > t2, or t1 = t2 > t3, or t1 = t2 = t3 >= t4 (*), then F's strategy is to get a total of t1 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 t1 or lower, and to get a higher score.
If (*) holds, then F starts by playing a1 to an F-square. S must play to the remaining F-square, otherwise F will play a3 or better to it on his next move and win. So S must play a9 to the remaining F-square, giving F a total of t1.
Now if t1 > t2, then F forces S to t2 or worse by playing a8 to an S-square.
If t1 = t2 > t3, then F forces S to t3 or worse by playing a2 to a neutral square. If S plays to an S-square, then he cannot do better than a3 + a8, which loses. So he plays a8 to a neutral square. But now F plays a3 to an S-square, and S cannot do better than t3.
If t1 = t2 = t3 > t4, then F forces S to t4 or worse. He starts by playing a2 to a neutral square. If does not prevent F playing a8 to an S-square on his next move, then he cannot do better than a3 + a8, which loses. So he must play a8 to a neutral square. Now F plays a3 to a neutral square. If S does not prevent F playing a7 to an S-square on the following move, then he cannot do better than a4 + a7 which loses, so he plays a7 to a neutral square. F now plays a4 to an S-square. S cannot now do better than t4, which loses.
Finally, if t1 = t2 = t3 = t4, then F proceeds as in the last case except that at the end he plays a4 to the last neutral square instead of to an S-square. S now gets a5 + a6 on the S-squares, which loses.
If (*) does not hold, then F starts by playing a9 to an S-square. If S does not play to the other S-square, then F will play a7 or a8 there on his next move and S will lose. So S must play a1 to the other square, and gets a total of t1. F now plays to get t2, t3 or t4 on the F-squares.
If t1 < t2, then F plays a2 to an F-square and so gets at least t2 and wins.
If t1 = t2 < t3, then F plays a8 to a neutral square. If S does not prevent F playing a2to an F-square on his next move, then F will get at least a2 + a7 and win. So S must play a2 to a neutral square. Now F plays a3 to an F-square and so gets at least t3 on the F-squares and wins.
Finally, if t1 = t2 = t3 < t4, then F plays as in the previous case, except that at the end he plays a7 to a neutral square instead of a3 to an F-square. S must prevent F playing a3 to an F-square the following move, or F gets at least a3 + a6 and wins. So S plays a3 to a neutral square. F now plays a4 to an F square and so must get at least t4, 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 = (p2/8 - 2(BC - p/4)2)/p. So the maximum occurs when BC = p/4 and has value p/8.
Problem 8
The n2 numbers xij satisfy the n3 equations: xij + xjk + xki = 0. Prove that we can find numbers a1, ... , an such that xij = ai - aj.
Solution
Taking i = j = k, we have that xii = 0. Now taking j=k, we have that xij = - xji. Define ai = xi1. Then we have xi1 + x1j + xji = 0. Hence xij = ai - aj.
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 a1, a2, ... , an, prove that you can find n integers b1, b2, ... , bn, such that |ai - bi| < 1 and the sum of any subset of the original numbers differs from the sum of the corresponding bi by at most (n + 1)/4.
Solution
We can take all ai to lie in the range (0,1) and all bi to be 0 or 1. The largest positive value of the sum of (ai - bi) for any subset is achieved by taking the subset of those i for which bi = 0. Similarly, the largest negative value is achieved by taking those i for which bi = 1. So the worst subset will be one of those two.
If ai < aj, then we cannot have bi = 1 and bj = 0 if the set of bis 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 a1 <= a2 <= ... <= an, then a best set of b's is bi = 0 for i <= some k, and bi = 1 for i > k. [If some of the ai 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 Li = a1 + a2 + ... + ai, and Ri = ai+1 + ai+2 + ... + an. As we increase i the sums Li increase and the sums Ri decrease, so for some k we must have Lk < Rk, Lk+1 >= Rk+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 Lk+1 = Rk. Suppose Lk+1 < Rk. Then we could increase each of ak+1, ak+2, ... , an by epsilon. This would leave Lk unaffected, but slightly increase Lk+1 and slightly reduce Rk. For small epsilon this does not change the value of k, but increases the smaller of Lk+1 and Rk, thus increasing the minimum and contradicting the maximality of the original a's. Similarly, if Lk+1 > Rk, we could decrease each of a1, a2, ... , ak+1 by epsilon, thus slightly increasing Rk and reducing Lk+1.
Suppose not all of a1, a2, ... , ak+1 are equal. Take i so that ai < ai+1. Now increase each of a1, a2, ... , ai by epsilon and reduce each of ai+1, ai+2, ... , ak+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 Lk+1 is increased. Rk is also increased, so we contradict the maximality of the a's. Hence all a1, a2, ... , ak+1 are equal. Similarly, we show that all of ak+1, ... , an are equal. For if not we can increase slightly ak+1, ... , aj and reduce slightly aj+1, ... , an 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.
Labels:
ARMO,
Russian Mathematical Olympiad
Previous Article
