

Algebra


A1. x_{1}, x_{2}, ... , x_{n} are positive reals with sum less than 1. Show that n^{n+1}x_{1}x_{2} ... x_{n}(1  x_{1}  ...  x_{n}) ≤ (x_{1} + x_{2} + ... + x_{n})(1  x_{1})(1  x_{2}) ... (1  x_{n}).


A2. x_{1}, x_{2}, ... , x_{n} are reals not less than 1. Show that 1/(1 + x_{1}) + 1/(1 + x_{2}) + ... + 1/(1 + x_{n}) ≥ n/(1 + (x_{1}x_{2} ... x_{n})^{1/n}).


A3. x, y, z are positive reals with product 1. Show that x^{3}/( (1 + y)(1 + z) ) + y^{3}/( (1 + z)(1 + x) ) + z^{3}/( (1 + x)(1 + y) ) ≥ 3/4.


A4. Define the numbers c(n, k) for k = 0, 1, 2, ... , n by c(n, 0) = c(n, n) = 1, c(n+1, k) = 2^{k}c(n, k) + c(n, k1). Show that c(n, k) = c(nk, k).


Combinatorics


C1. An m x n array of real numbers has the sum of each row and column integral. Show that each nonintegral element x can be changed to [x] or [x] + 1, so that the row and column sums are unchanged.


C2. n is a fixed positive integer. An odd nadmissible sequence a_{1}, a_{2}, a_{3}, ... satisfies the following conditions: (1) a_{1} = 1; (2) a_{2k} = a_{2k1} + 2 or a_{2k1} + n; (3) a_{2k+1} = 2a_{2k} or n a_{2k}. An even nadmissible sequence satisfies (1) a_{1} = 1; (2) a_{2k} = 2a_{2k1} or n a_{2k1}; (3) a_{2k+1} = a_{2k} + 2 or a_{2k} + n. An integer m > 1 is nattainable if it belongs to an odd nadmissible sequence or an even nadmissible sequence. Show that for n > 8 there are infinitely many positive integers which are not nattainable. Show that all positive integers except 7 are 3attainable.


C3. The numbers from 1 to 9 are written in an arbitrary order. A move is to reverse the order of any block of consecutive increasing or decreasing numbers. For example, a move changes 916532748 to 913562748. Show that at most 12 moves are needed to arrange the numbers in increasing order.


C4. If A is a permutation of 1, 2, 3, ... , n and B is a subset of {1, 2, ... , n}, then we say that A splits B if we can find three elements of A such that the middle element does not belong to B, but the outer two do. For example, the permutation 13542 of 12345 splits {1, 2, 3} (because, for example, 4 appears between 3 and 2) but it does not split {3, 4, 5}. Show that if we take any n2 subsets of {1, 2, ... , n}, each with at least 2 and at most n1 elements, then there is a permutation of 1, 2, ... , n which splits all of them.


C6. G is the complete graph on 10 points (so that there is an edge between each pair of points). Show that we can color each edge with one of 5 colors so that for any 5 points we can find 5 differently colored edges all of whose endpoints are amongst the 5 points. Show that we cannot color each edge with one of 4 colors so that for any 4 points we can find 4 differently colored edges with all endpoints amongst the 4 points.


C7. Some cards have one side white and the other side black. A card is placed on each square of an m x n board. All cards are white side up, except for the card in the top left corner. A move is to remove any black card and to turn over any cards on squares which share an edge with the square from which the card was taken. For which m, n can one remove all the cards from the board by a sequence of moves.


Geometry


G2. ABCD is a cyclic quadrilateral. E and F are variable points on the sides AB and CD respectively, such that AE/EB = CF/FD. P is a point on the segment EF such that EP/PF = AB/CD. Show that area APD/area BPC does not depend on the positions of E and F.


G4. M and N are points inside the triangle ABC such that ∠MAB = ∠NAC and ∠MBA = ∠NBC. Show that AM·AN/(AB·AC) + BM·BN/(BA·BC) + CM·CN/(CA·CB) = 1.


G5. ABC is a triangle with circumcenter O, orthocenter H and circumradius R. The points D, E, F are the reflections of A, B, C respectively, in the opposite sides. Show that they are collinear iff OH = 2R.


G6. ABCDEF is a convex hexagon with ∠B + ∠D + ∠F = 360^{o} and AB·CD·EF = BC·DE·FA. Show that BC·DF·EA = EF·AC·BD.


G7. ABC is a triangle with angle C = 2 ∠B. D is a point on the side BC such that DC = 2 BD. E is a point on the line AD such that D is the midpoint of AE. Show that ∠ECB + 180^{o} = 2 ∠EBC.


G8. ABC is a triangle with angle A = 90^{o}. The tangent at A to the circumcircle meets the line BC at D. E is the reflection of A in BC. X is the foot of the perpendicular from A to BE. Y is the midpoint of AX. The line BY meets the circumcircle again at Z. Show that BD is tangent to the circumcircle of ADZ.


Number theory


N2. Find all pairs of real numbers (x, y) such that x [ny] = y [nx] for all positive integers n.


N3. Find the smallest n such that given any n distinct integers one can always find 4 different integers a, b, c, d such that a + b = c + d mod 20.


N4. The sequence a_{1}, a_{2}, a_{3}, ... is defined as follows. a_{1} = 1. a_{n} is the smallest integer greater than a_{n1} such that we cannot find 1 ≤ i, j, k ≤ n (not necessarily distinct) such that a_{i} + a_{j} = 3a_{k}. Find a_{1998}.


N5. Find all positive integers n for which there is an integer m such that m^{2} + 9 is a multiple of 2^{n}  1.


N7. Show that for any n > 1 there is an n digit number with all digits nonzero which is divisible by the sum of its digits.


N8. The sequence 0 ≤ a_{0} < a_{1} < a_{2} < ... is such that every nonnegative integer can be uniquely expressed as a_{i} + 2a_{j} + 4a_{k} (where i, j, k are not necessarily distinct). Find a_{1998}.


Note: problems A5, C6, G1, G3, N1 and N6 were used in the Olympiad and are not shown here.

