1. Are there more positive integers under a million for which the nearest square is odd or for which it is even?
2. A monic quartic and a monic quadratic both have real coefficients. The quartic is negative iff the quadratic is negative and the set of values for which they are negative is an interval of length more than 2. Show that at some point the quartic has a smaller value than the quadratic.
3. ABCD is parallelogram and P a point inside, such that the midpoint of AD is equidistant from P and C, and the midpoint of CD is equidistant from P and A. Let Q be the midpoint of PB. Show that ∠PAQ = ∠PCQ.
4. No three diagonals of a convex 2000-gon meet at a point. The diagonals (but not the sides) are each colored with one of 999 colors. Show that there is a triangle whose sides are on three diagonals of the same color.
5. 2001 coins, each value 1, 2 or 3 are arranged in a row. Between any two coins of value 1 there is at least one coin, between any two of value 2 there are at least two coins, and between any two of value 3 there are at least three coins. What is the largest number of value 3 coins that could be in the row?
6. Given a graph of 2n+1 points, given any set of n points, there is another point joined to each point in the set. Show that there is a point joined to all the other points.
7. N is any point on AC is the longest side of the triangle ABC, such that the perpendicular bisector of AN meets the side AB at K and the perpendicular bisector of NC meets the side BC at M. Prove that BKOM is cyclic, where O is the circumcenter of ABC.
8. Find all odd positive integers n > 1 such that if a and b are relatively prime divisors of n, then a + b - 1 divides n.
9. Let A1, A2, ... , A100 be subsets of a line, each a union of 100 disjoint closed segments. Prove that the intersection of all hundred sets is a union of at most 9901 disjoint closed segments. [A single point is considered to be a closed segment.]
10. The circle C' is inside the circle C and touches it at N. A tangent at the point X of C' meets C at A and B. M is the midpoint of the arc AB which does not contain N. Show that the circumradius of BMX is independent of the position of X.
11. Some pairs of towns in a country are joined by roads, so that there is a unique route from any town to another which does not pass through any town twice. Exactly 100 of the towns have only one road. Show that it is possible to construct 50 new roads so that there will still be a route between any two towns even if any one of the roads (old or new) is closed for maintenance.
12. x3 + ax2 + bx + c has three distinct real roots, but (x2 + x + 2001)3 + a(x2 + x + 2001)2 + b(x2 + x + 2001) + c has no real roots. Show that 20013 + a 20012 + b 2001 + c > 1/64.
13. An n x n Latin square has the numbers from 1 to n2 arranged in its cells (one per cell) so that the sum of every row and column is the same. For every pair of cells in a Latin square the centers of the cells are joined by an arrow pointing to the cell with the larger number. Show that the sum of these vectors is zero.
14. The altitudes AD, BE, CF of the triangle ABC meet at H. Points P, Q, R are taken on the segments AD, BE, CF respectively, so that the sum of the areas of triangles ABR, AQC and PBC equals the area of ABC. Show that P, Q, R, H are cyclic.
15. S is a set of 100 stones. f(S) is the set of integers n such that we can find n stones in the collection weighing half the total weight of the set. What is the maximum possible number of integers in f(S)?
16. There are two families of convex polygons in the plane. Each family has a pair of disjoint polygons. Any polygon from one family intersects any polygon from the other family. Show that there is a line which intersects all the polygons.
17. N contestants answered an exam with n questions. ai points are awarded for a correct answer to question i and nil for an incorrect answer. After the questions had been marked it was noticed that by a suitable choice of positive numbers ai any desired ranking of the contestants could be achieved. What is the largest possible value of N?
18. The quadratics x2 + ax + b and x2 + cx + d have real coefficients and take negative values on disjoint intervals. Show that there are real numbers h, k such that h(x2 + ax + b) + k(x2 + cx + d) > 0 for all x.
19. m > n are positive integers such that m2 + mn + n2 divides mn(m + n). Show that (m - n)3 > mn.
20. A country has 2001 towns. Each town has a road to at least one other town. If a subset of the towns is such that any other town has a road to at least one member of the subset, then it has at least k > 1 towns. Show that the country may be partitioned into 2001 - k republics so that no two towns in the same republic are joined by a road.
21. ABCD is a tetrahedron. O is the circumcenter of ABC. The sphere center O through A, B, C meets the edges DA, DB, DC again at A', B', C'. Show that the tangent planes to the sphere at A', B', C' pass through the center of the sphere through A', B', C', D.
Solutions
Problem 1
Are there more positive integers under a million for which the nearest square is odd or for which it is even?
Answer
odd
Solution
There are 2n integers for which the closest integer is n2, namely n2-n+1, n2-n+2, ... , n2+n. So there are 2(1 + 3 + 5 + ... + 999) = 500·1000 integers under a million for which the nearest square is odd. Hence there are 499999 integers for which the nearest square is even.
Problem 3
ABCD is parallelogram and P a point inside, such that the midpoint of AD is equidistant from P and C, and the midpoint of CD is equidistant from P and A. Let Q be the midpoint of PB. Show that ∠PAQ = ∠PCQ.
Solution
Let M, N be the midpoints of AD, CD respectively, and let R, S be the midpoints of AP, CP respectively. Since Q, R are the midpoints of PB, PA, we have QR parallel to AB and half its length. Hence QR = CN and is parallel to it. So QRNC is a parallelogram. Hence NR is parallel to CQ. But NR is perpendicular to AP (because NA = NP), so CQ is perpendicular to AP. Suppose they meet at E, so that ∠PEC = 90o.
Similarly, QS is equal and parallel to AM, so AMSQ is a parallelogram, so AQ is parallel to MS and hence perpendicular to CP. Suppose they meet at F, so that ∠AFP = 90o.
But now triangles AFP and CEP are similar, so ∠PAF = ∠PCE, as required.
Thanks to Bekjan Jumabaev
Problem 5
2001 coins, each value 1, 2 or 3 are arranged in a row. Between any two coins of value 1 there is at least one coin, between any two of value 2 there are at least two coins, and between any two of value 3 there are at least three coins. What is the largest number of value 3 coins that could be in the row?
Answer
501
Solution
The only way we can have two value 3 coins the minimum distance apart is ...31213... . If we repeat that pattern then the conditions are all satisfied. So the optimal configuration is 312131213... . Since 2001 = 1 mod 4 that will give the last coin as 3 and a total of 1 + 2000/4 = 501 value 3 coins.
Thanks to Bekjan Jumabaev
Problem 7
N is any point on AC is the longest side of the triangle ABC, such that the perpendicular bisector of AN meets the side AB at K and the perpendicular bisector of NC meets the side BC at M. Prove that BKOM is cyclic, where O is the circumcenter of ABC.
Solution
Let the midpoints of BC, BA be Q, R respectively. Then OQ is perpendicular to BC and OR is perpendicular to AB, so OQBR is cyclic. Hence ∠B + ∠QOR = 180o. So it is sufficient to show that ∠MOQ = ∠KOR, because then ∠MOK = ∠QOR.
Let the line through O parallel to BC meet the perpendiculars from K and M to AC at S and T respectively. Then ∠OQM = ∠OTM = 90o, so MQOT is cyclic, so ∠MOQ = ∠MTQ. Similarly, ∠KOR = ∠KSR. But QR and ST are both half the length of AC and parallel to it, so QRST is a parallelogram. Hence ∠MTQ = ∠KSR. Hence ∠MOQ = ∠KOR as required.
Thanks to Bekjan Jumabaev
Problem 10
The circle C' is inside the circle C and touches it at N. A tangent at the point X of C' meets C at A and B. M is the midpoint of the arc AB which does not contain N. Show that the circumradius of BMX is independent of the position of X.
Solution
Let C, C' have centers O, O' respectively. An expansion center N takes C' to C. Suppose it takes X to M'. Then OM' is parallel to O'X and hence perpendicular to AB, so M' = M.
Let the radii of C, C' be R, R' respectively. Let the circumradius of BMX be r. Then MX = 2r sin B, but MA = 2R sin B, so r/R = MX/MA. Triangles XMB, XAN are similar, so MX/MA = MX/MB = AX/AN.
Put ∠AON = k. Then AN2 = 2R2(1 - cos k) and AX2 = O'A2 - O'X2 = R2 + (R-R')2 - 2(R-R') cos k = 2R(R-R')(1 - cos k). Hence (AX/AN)2 = (R-R')/R. So r2 = R(R-R'), which is independent of k.
Thanks to Bekjan Jumabaev
Problem 12
x3 + ax2 + bx + c has three distinct real roots, but (x2 + x + 2001)3 + a(x2 + x + 2001)2 + b(x2 + x + 2001) + c has no real roots. Show that 20013 + a 20012 + b 2001 + c > 1/64.
Solution
We can write x2 + x + 2001 = (x + 1/2)2 + 2000 - 1/4, so it takes any value ≥ 2000 - 1/4. Hence the roots of x3 + ax2 + bx + c must all be < 2000 - 1/4. Suppose the roots are p, q, r. We have p, q, r < 2000 - 1/4, hence 2000-p > 1/4. Similarly, 2000-q > 1/4 and 2000-r > 1/4. Multiplying we get 20013 + a 20012 + b 2001 + c > 1/64.
Thanks to Suat Namli
Labels:
Russian Mathematical Olympiad
Previous Article
