1. Show that x4 > x - 1/2 for all real x.
2. The line joining the midpoints of two opposite sides of a convex quadrilateral makes equal angles with the diagonals. Show that the diagonals are equal.
3. A graph has 30 points and each point has 6 edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.
4. Does there exist a rectangle which can be dissected into 15 congruent polygons which are not rectangles? Can a square be dissected into 15 congruent polygons which are not rectangles?
5. The point P lies inside the triangle ABC. A line is drawn through P parallel to each side of the triangle. The lines divide AB into three parts length c, c', c" (in that order), and BC into three parts length a, a', a" (in that order), and CA into three parts length b, b', b" (in that order). Show that abc = a'b'c' = a"b"c".
6. Find three non-zero reals such that all quadratics with those numbers as coefficients have two distinct rational roots.
7. What is the largest possible value of | ... | |a1 - a2| - a3| - ... - a1990|, where a1, a2, ... , a1990 is a permutation of 1, 2, 3, ... , 1990?
8. An equilateral triangle of side n is divided into n2 equilateral triangles of side 1. A path is drawn along the sides of the triangles which passes through each vertex just once. Prove that the path makes an acute angle at at least n vertices.
9. Can the squares of a 1990 x 1990 chessboard be colored black or white so that half the squares in each row and column are black and cells symmetric with respect to the center are of opposite color?
10. Let x1, x2, ... , xn be positive reals with sum 1. Show that x12/(x1 + x2) + x22/(x2 + x3) + ... + xn-12/(xn-1 + xn) + xn2/(xn + x1) ≥ 1/2.
11. ABCD is a convex quadrilateral. X is a point on the side AB. AC and DX intersect at Y. Show that the circumcircles of ABC, CDY and BDX have a common point.
12. Two grasshoppers sit at opposite ends of the interval [0, 1]. A finite number of points (greater than zero) in the interval are marked. A move is for a grasshopper to select a marked point and jump over it to the equidistant point the other side. This point must lie in the interval for the move to be allowed, but it does not have to be marked. What is the smallest n such that if each grasshopper makes n moves or less, then they end up with no marked points between them?
13. Find all integers n such that [n/1!] + [n/2!] + ... + [n/10!] = 1001.
14. A, B, C are adjacent vertices of a regular 2n-gon and D is the vertex opposite to B (so that BD passes through the center of the 2n-gon). X is a point on the side AB and Y is a point on the side BC so that angle XDY = π/2n. Show that DY bisects angle XYC.
15. A graph has n points and n(n-1)/2 edges. Each edge is colored with one of k colors so that there are no closed monochrome paths. What is the largest possible value of n (given k)?
16. Given a point X and n vectors xi with sum zero in the plane. For each permutation of the vectors we form a set of n points, by starting at X and adding the vectors in order. For example, with the original ordering we get X1 such that XX1 = x1, X2 such that X1X2 = x2 and so on. Show that for some permutation we can find two points Y, Z with angle YXZ = 60 deg, so that all the points lie inside or on the triangle XYZ.
17. Two unequal circles intersect at X and Y. Their common tangents intersect at Z. One of the tangents touches the circles at P and Q. Show that ZX is tangent to the circumcircle of PXQ.
18. Given 1990 piles of stones, containing 1, 2, 3, ... , 1990 stones. A move is to take an equal number of stones from one or more piles. How many moves are needed to take all the stones?
19. A quadratic polynomial p(x) has positive real coefficients with sum 1. Show that given any positive real numbers with product 1, the product of their values under p is at least 1.
20. A cube side 100 is divided into a million unit cubes with faces parallel to the large cube. The edges form a lattice. A prong is any three unit edges with a common vertex. Can we decompose the lattice into prongs with no common edges?
21. For which positive integers n is 32n+1 - 22n+1 - 6n composite?
22. If every altitude of a tetrahedron is at least 1, show that the shortest distance between each pair of opposite edges is more than 2.
23. A game is played in three moves. The first player picks any real number, then the second player makes it the coefficient of a cubic, except that the coefficient of x3 is already fixed at 1. Can the first player make his choices so that the final cubic has three distinct integer roots?
24. Given 2n genuine coins and 2n fake coins. The fake coins look the same as genuine coins but weigh less (but all fake coins have the same weight). Show how to identify each coin as genuine or fake using a balance at most 3n times.
Solutions
Problem 1
Show that x4 > x - 1/2 for all real x.
Solution
x4 - x + 1/2 = (x2 - 1/2)2 + (x - 1/2)2 ≥ 0. We could only have equality if x2 = x = 1/2, which is impossible, so the inequality is strict.
Problem 2
The line joining the midpoints of two opposite sides of a convex quadrilateral makes equal angles with the diagonals. Show that the diagonals are equal.
Solution
Let L, M, N be the midpoints of BC, CD, DA. Assume that NL makes equal angles with AC and BD, so ∠NLM = ∠BEL = ∠AFN = ∠LNM, so LM = MN and hence BD = AC.
Problem 3
A graph has 30 points and each point has 6 edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.
Answer
1990
Solution
There are 30·29·28/6 = 4060 triples in all. Let m be the number of triples with 0 or 3 edges, and let n be the number of triples with 1 or 2 edges. So m + n = 4060. Each point is joined to 6 others, so it is in 6·5/2 = 15 triples where it is joined to both the other points, and it is in 23·22/2 = 253 triples where it is not joined to either of the other points. So the total number of triples (a,b,c), where a is joined to b and c or not joined to b or c is 30(15+253) = 8040. This counts the m triples 3 times each, and the n triples once each, so 3m+n = 8040. Hence m = 1990.
Problem 4
Does there exist a rectangle which can be dissected into 15 congruent polygons which are not rectangles? Can a square be dissected into 15 congruent polygons which are not rectangles?
Answer
yes, yes
Solution
By stretching vertically we get a square.
Problem 5
The point P lies inside the triangle ABC. A line is drawn through P parallel to each side of the triangle. The lines divide AB into three parts length c, c', c" (in that order), and BC into three parts length a, a', a" (in that order), and CA into three parts length b, b', b" (in that order). Show that abc = a'b'c' = a"b"c".
Solution
The three small triangles are similar, so a/a" = c'/c = b"/b' and a/a' = c'/c" = b"/b. Hence (a/a")(b/b") = (c'/c)(c"/c') = c"/c, so abc = a"b"c". Similarly, (a/a')(c/c') = (b"/b)(b'/b") = b'/b, so abc = a'b'c'.
Problem 6
Find three non-zero reals such that all quadratics with those numbers as coefficients have two distinct rational roots.
Answer
1,2,-3
Solution
If a + b + c = 0, then 1 is a root of ax2 + bx + c, and so the other root is -b/a - 1, which is rational.
Problem 7
What is the largest possible value of | ... | |a1 - a2| - a3| - ... - a1990|, where a1, a2, ... , a1990 is a permutation of 1, 2, 3, ... , 1990?
Answer
1989
Solution
Since |a-b| ≤ max(a,b), a trivial induction shows that the expression does not exceed max(a1, a2, ... , a1990) = 1990. But for integers |a-b| has the same parity as a+b, so a trivial induction shows that the expression has the same parity as a1 + a2 + ... + a1990 = 1990·1991/2, which is odd. So it cannot exceed 1989. That can be attained by the permutation 2, 4, 5, 3, 6, 8, 9, 7, ... , 4k+2, 4k+4, 4k+5, 4k+3, ... , 1984+2, 1984+4, 1984+5, 1984+3, 1990, 1. Because we get successively 2, 3, 0; 6, 2, 7, 0; 10, 2, 11, 0; ... ; 4k+2, 2, 4k+3, 0; ... ; 1986, 2, 1987, 0; 1990, 1989.
Problem 8
An equilateral triangle of side n is divided into n2 equilateral triangles of side 1. A path is drawn along the sides of the triangles which passes through each vertex just once. Prove that the path makes an acute angle at at least n vertices.
Solution
The diagram has 1 + 2 + ... + n = n(n+1)/2 upright triangles and 1 + 2 + ... + n-1 = n(n-1)/2 upside down triangles. It has 1 + 2 + ... + n+1 = (n+1)(n+2)/2 vertices. So the path must be (n+1)(n+2)/2 - 1 = (n2+3n)/2 units long. Each unit length of the path is in just one upright triangle. The path cannot contain all three sides of a small triangle, or it would pass through a vertex more than once. So it must contain two sides of (n2+3n)/2 - n(n+1)/2 = n triangles. But if it contains two sides of a triangle, then it must make an acute angle at the vertex where they meet.
Problem 9
Can the squares of a 1990 x 1990 chessboard be colored black or white so that half the squares in each row and column are black and cells symmetric with respect to the center are of opposite color?
Answer
no
Solution
Suppose it can be done. Divide the board into 4 quadrants. Suppose there are b black and 9952 - b white squares in the top left quadrant. Then there are 9952 - b black and b white squares in the bottom right quadrant (by the symmetry property).
If half the squares in each row are black, then half the squares in the first 995 rows are black, so the number of black squares in the top right quadrant is 995·1990/2 - b = 9952 - b. So if half the squares in each column are black, then half the squares in the right-hand half of the board are black, so (9952 - b) + (9952 - b) = 9952, in other words, b = 9952/2, which is impossible.
Problem 10
Let x1, x2, ... , xn be positive reals with sum 1. Show that x12/(x1 + x2) + x22/(x2 + x3) + ... + xn-12/(xn-1 + xn) + xn2/(xn + x1) ≥ 1/2.
Solution
∑ xi2/(xi+xi+1) - ∑ xi+12/(xi+xi+1) = ∑ (xi - xi+1) = 0. Hence ∑ xi2/(xi+xi+1) = ½ ∑ (xi2+xi+12)/(xi+xi+1) ≥ ¼ ∑ (xi + xi+1) = ½.
Labels:
All Soviet Union Mathematical Olympiad Problems,
ASU
Previous Article
