23rd Russian 1997

23rd Russian 1997 problems


1. p(x) is a quadratic polynomial with non-negative coefficients. Show that p(xy)² ≤ p(x²)p(y²).
2. A convex polygon is invariant under a 90^o 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 (m² - n²)² = 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 = 90^o.
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 x² + bx + c = 0 and x² + (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)², b + c = gcd(b,c)², c + a = gcd(c,a)².
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.