22nd Russian 1996

22nd Russian 1996 problems


1. Can a majority of the numbers from 1 to a million be represented as the sum of a square and a (non-negative) cube?
2. Non-intersecting circles of equal radius are drawn centered on each vertex of a triangle. From each vertex a tangent is drawn to the other circles which intersects the opposite side of the triangle. The six resulting lines enclose a hexagon. Color alternate sides of the hexagon red and blue. Show that the sum of the blue sides equals the sum of the red sides.
3. aⁿ + bⁿ = p^k for positive integers a, b and k, where p is an odd prime and n > 1 is an odd integer. Show that n must be a power of p.
4. The set X has 1600 members. P is a collection of 16000 subsets of X, each having 80 members. Show that there must be two members of P which have 3 or less members in common.
5. Show that the arithmetic progression 1, 730, 1459, 2188, ... contains infinitely many powers of 10.
6. The triangle ABC has CA = CB, circumcenter O and incenter I. The point D on BC is such that DO is perpendicular to BI. Show that DI is parallel to AC.
7. Two piles of coins have equal weight. There are m coins in the first pile and n coins in the second pile. For any 0 < k ≤ min(m, n), the sum of the weights of the k heaviest coins in the first pile is not more than the sum of the weights of the k heaviest coins in the second pile. Show that if h is a positive integer and we replace every coin (in either pile) whose weight is less than h by a coin of weight h, then the first pile will weigh at least as much as the second.
8. An L is formed from three unit squares, so that it can be joined to a unit square to form a 2 x 2 square. Can a 5 x 7 board be covered with several layers of Ls (each covering 3 unit squares of the board), so that each square is covered by the same number of Ls?
9. ABCD is a convex quadrilateral. Points D and F are on the side BC so that the points on BC are in the order B, E, F, C. ∠BAE = ∠CDF and ∠EAF = ∠EDF. Show that ∠CAF = ∠BDE.
10. Four pieces A, B, C, D are placed on the plane lattice. A move is to select three pieces and to move the first by the vector between the other two. For example, if A is at (1, 2), B at (-3, 4) and C at (5, 7), then one could move A to (9, 5). Show that one can always make a series of moves which brings A and B onto the same node.
11. Find powers of 3 which can be written as the sum of the kth powers (k > 1) of two relatively prime integers.
12. a₁, a₂, ... , a_m are non-zero integers such that a₁ + a₂2^k + a₃3^k + ... + a_mm^k = 0 for k = 0, 1, 2, ... , n (where n < m - 1). Show that the sequence a_i has at least n+1 pairs of consecutive terms with opposite signs.
13. A different number is placed at each vertex of a cube. Each edge is given the greatest common divisor of the numbers at its two endpoints. Can the sum of the edge numbers equal the sum of the vertex numbers?
14. Three sergeants A, B, C and some soldiers serve in a platoon. The first day A is on duty, the second day B is on duty, the third day C, the fourth day A, the fifth B, the sixth C, the seventh A and so on. There is an infinite list of tasks. The commander gives the following orders: (1) the duty sergeant must issue at least one task to a soldier every day, (2) no soldier may have three or more tasks, (3) no soldier may be given more than one new task on any one day, (4) the set of soldiers receiving tasks must be different every day, (5) the first sergeant to violate any of (1) to (4) will be jailed. Can any of the sergeants be sure to avoid going to jail (strategies that involve collusion are not allowed)?
15. No two sides of a convex polygon are parallel. For each side take the angle subtended by the side at the point whose perpendicular distance from the line containing the side is the largest. Show that these angles add up to 180^o.
16. Two players play a game. The first player writes ten positive real numbers on a board. The second player then writes another ten. All the numbers must be distinct. The first player then arranges the numbers into 10 ordered pairs (a, b). The first player wins iff the ten quadratics x² + ax + b have 11 distinct real roots between them. Which player wins?
17. The numbers from 1 to n > 1 are written down without a break. Can the resulting number be a palindrome (the same read left to right and right to left)? For example, if n was 4, the result would be 1234, which is not a palindrome.
18. n people move along a road, each at a fixed (but possibly different) speed. Over some period the sum of their pairwise distances decreases. Show that we can find a person such that the sum of his distances to the other people is decreasing throughout the period. [Note that people may pass each other during the period.]
19. n > 4. Show that no cross-section of a pyramid whose base is a regular n-gon (and whose apex is directly above the center of the n-gon) can be a regular (n+1)-gon.
20. Do there exist three integers each greater than one such that the square of each less one is divisible by both the others?
21. ABC is a triangle with circumcenter O and AB = AC. The line through O perpendicular to the angle bisector CD meets BC at E. The line through E parallel to the angle bisector meets AB at F. Show that DF = BE.
22. Do there exist two finite sets such that we can find polynomials of arbitrarily large degree with all coefficients in the first set and all roots real and in the second set?
23. The integers from 1 to 100 are permuted in an unknown way. One may ask for the order of any 50 integers. How many such questions are needed to deduce the permutation?