1. p(x) is a quadratic polynomial with non-negative coefficients. Show that p(xy)2 ≤ p(x2)p(y2).
2. A convex polygon is invariant under a 90o rotation. Show that for some R there is a circle radius R contained in the polygon and a circle radius R√2 which contains the polygon.
3. A rectangular box has integral sides a, b, c, with c odd. Its surface is covered with pieces of rectangular cloth. Each piece contains an even number of unit squares and has its sides parallel to edges of the box. The pieces may be bent along box edges length c (but not along the edges length a or b), but there must be no gaps and no part of the box may be covered by more than one thickness of cloth. Prove that the number of possible coverings is even.
4. The members of the Council of the Wise are arranged in a column. The king gives each sage a black or a white cap. Each sage can see the color of the caps of all the sages in front of him, but he cannot see his own or the colors of those behind him. Every minute a sage guesses the color of his cap. The king immediately executes those sages who are wrong. The Council agree on a strategy to minimise the number of executions. What is the best strategy? Suppose there are three colors of cap?
5. Find all integral solutions to (m2 - n2)2 = 1 + 16n.
6. An n x n square grid is glued to make a cylinder. Some of its cells are colored black. Show that there are two parallel horizontal, vertical or diagonal lines (of n cells) which contain the same number of black cells.
7. Two circles meet at A and B. A line through A meets the circles again at C and D. M, N are the midpoints of the arcs BC, BD which do not contain A. K is the midpoint of the segment CD. Prove that ∠MKN = 90o.
8. A polygon can be divided into 100 rectangles, but not into 99 rectangles. Prove that it cannot be divided into 100 triangles.
9. A cube side n is divided into unit cubes. A closed broken line without self-intersections is given. Each segment of the broken line connects the centers of two unit cubes with a common face. Show that we can color the edges of the unit cubes with two colors, so that each face of a small cube which is intersected by the broken line has an odd number of edges of each color, and each face which is not intersected by the broken line has an even number of edges of each color.
10. Do there exist reals b, c so that x2 + bx + c = 0 and x2 + (b+1)x + (c+1) = 0 both have two integral roots?
11. There are 33 students in a class. Each is asked how many other students share is first name and how many share his last name. The answers include all numbers from 0 to 10. Show that two students must have the same first name and the same last name.
12. The incircle of ABC touches AB, BC, CA at M, N, K respectively. The line through A parallel to NK meets the line MN at D. The line through A parallel to MN meets the line NK at E. Prove that the line DE bisects AB and AD.
13. The numbers 1, 2, 3, ... , 100 are arranged in the cells of a 10 x 10 square so that given any two cells with a common side the sum of their numbers does not exceed N. Find the smallest possible value of N.
14. The incircle of ABC touches the sides AC, AB, BC at K, M, N respectively. The median BB' meeets MN at D. Prove that the incenter lies on the line DK.
15. Find all solutions in positive integers to a + b = gcd(a,b)2, b + c = gcd(b,c)2, c + a = gcd(c,a)2.
16. Some stones are arranged in an infinite line of pots. The pots are numbered ... -3, -2, -1, 0, 1, 2, 3, ... . Two moves are allowed: (1) take a stone from pot n-1 and a stone from pot n and put a stone into pot n+1 (for any n); (2) take two stones from pot n and put one stone into each of pots n+1 and n-2. Show that any sequence of moves must eventually terminate (so that no more moves are possible) and that the final state depends only on the initial state.
17. Consider all quadratic polynomials x2 + ax + b with integral coefficients such that 1 ≤ a, b ≤ 1997. Let A be the number with integral roots and B the number with no real roots. Which of A, B is larger?
18. P is a polygon. L is a line, and X is a point on L, such that the lines containing the sides of P meet L in distinct points different from X. We color a vertex of P red iff its the lines containing its two sides meet L on opposite sides of X. Show that X is inside P iff there are an odd number of red vertices.
19. A sphere is inscribed in a tetrahedron. It touches one face at its incenter, another face at its orthocenter, and a third face at its centroid. Show that the tetrahedron must be regular.
20. 2 x 1 dominos are used to tile an m x n square, except for a single 1 x 1 hole at a corner. A domino which borders the hole along its short side may be slid one unit along its long side to cover the hole and open a new hole. Show that the hole may be moved to any other corner by moves of this type.
Solutions
Problem 1
p(x) is a quadratic polynomial with non-negative coefficients. Show that p(xy)2 ≤ p(x2)p(y2).
Solution
lhs = ( (√a x2)(√a y2) + (√b x)(√b y) + √c √c)2 ≤ (ax4 + bx2 + c)(ay4 + by2 + c) = rhs by Cauchy-Schwartz.
Problem 5
Find all integral solutions to (m2 - n2)2 = 1 + 16n.
Answer
(m,n) = (±1,0), (±4,3), (±4,5)
Solution
Clearly n cannot be negative. On the other hand, if (m,n) is a solution, then so is (-m,n). If n = 0, then m = ±1. If m = 0, then n4 = 1 + 16n, which has no solutions (because n must divide 1, but 1 is not a solution). So let us assume m and n are positive.
We have m2 = n2 + √(1+16n) or m2 = n2 - √(1+16n). In the first case, obviously m > n. But (n+1)2 = n2 + 2n + 1 which is greater than n2 + √(1+16n) for (2n+1)2 > 1 + 16n or n > 3. So if n > 3, then m2 lies strictly between n2 and (n+1)2, which is impossible. It is easy to check that n = 1, 2 do not give solutions, but n = 3 gives the solution m = 4.
Similarly, in the second case we must have n ≤ 5, and it is easy to check that n = 1, 2, 3, 4 do not give solutions, but n = 5 gives the solution m = 4.
Problem 10
Do there exist reals b, c so that x2 + bx + c = 0 and x2 + (b+1)x + (c+1) = 0 both have two integral roots?
Solution
b = 2, c = 1
Problem 15
Find all solutions in positive integers to a + b = gcd(a,b)2, b + c = gcd(b,c)2, c + a = gcd(c,a)2.
Answer
(a,b,c) = (2,2,2)
Solution
Put d = gcd(a,b,c). Then a = Ad, b = Bd, c = Cd. Put t = gcd(A,B), r = gcd(B,C), s = gcd(A,C). If r, s have a common factor, then it divides all of A, B, C, contradicting the definition of d. So r, s, t are coprime in pairs. Hence A = Rst, B = rSt, C = rsT for some R, S, T which are relatively prime in pairs. Thus a = Rstd, b = rStd, c = rsTd.
Now a + b = gcd(a,b)2 implies A + B = t2d. Similarly, B + C = r2d, C + A = s2d. Adding, 2(A + B + C) = d(r2 + s2 + t2). Now if any odd prime divides d, then it must divide A + B + C and A + B, B + C and C + A and hence each of A, B, C, which is impossible. Similarly, if 4 divides d, then 2 divides A, B, C, which is impossible. Hence d = 1 or 2.
We can also write a + b = gcd(a,b)2 etc as Rs + rS = td, St + sT = rd, Tr + Rt = sd. Suppose (without loss of generality) that r is the smallest of r, s, t. Then 2r ≥ rd = St + sT ≥ s + t ≥ 2r. So we must have equality throughout and hence d = 2, S = T = 1 and r = s = t. But r, s, t are coprime, so r = s = t = 1. Hence from Rs + rS = td, we have R = 1 also. Hence a = b = c = 2.
Labels:
Russian Mathematical Olympiad
Previous Article
