|
|
Algebra
|
|
|
A2. The numbers 1 to n2 are arranged in the squares of an n x n board (1 per square). There are n2 (n-1) pairs of numbers in the same row or column. For each such pair take the larger number divided by the smaller. Then take the smallest such ratio and call it the minrat of the arrangement. So, for example, if n2 and n2 - 1 were in the same row, then the minrat would be n2/(n2 - 1). What is the largest possible minrat?
|
|
|
A3. Each of n > 1 girls has a doll with her name on it. Each pair of girls swaps dolls in some order. For which values of n is it possible for each girl to end up (1) with her own doll, (2) with another girl's doll? [For example, if n = 4, denote girls by A, B, C, D and dolls by a, b, c, d. So the initial position is Aa Bb Cc Dd. If the swaps are in the order AB, CD, AC, BD, AD, BC, then the successive positions are Ab Ba Cc Dd, Ab Ba Cd Dc, Ad Ba Cb Dc, Ad Bc Cb Da, Aa Bc Cb Dd and Aa Bb Cc Dd. So for n = 4, (1) is possible.]
|
|
|
A4. Show that we cannot partition the positive integers into three non-empty parts, so that if a and b belong to different parts, then a2 - ab + b2 belongs to the third part.
|
|
A6. Given real numbers x1 ≤ x2 <= ... <= xn (with n > 2), carry out the following procedure:
(1) arrange the numbers in a circle;
(2) delete one of the numbers;
(3) if just two numbers are left, then take their sum. Otherwise replace each number by the sum of it and the number on its right. Go to step 2.
Show that the largest sum that can be achieved by this procedure is (n-2)C0 x2 + (n-2)C0 x3 + (n-2)C1 x4 + (n-2)C1 x5 + (n-2)C2 x6 + ... + (n-2)C( [n/2]-1 ) xn, where mCk represents the binomial coefficient.
|
|
Combinatorics
|
|
|
C1. A low path from the lattice point (0, 0) to the lattice point (n, n) is a sequence of 2n moves, each one point up or one point to the right, starting at (0, 0) and ending at (n, n) such that all points of the path satisfy y <= x. A step is two consecutive moves, the first right and the second up. Show that the number of low paths from (0, 0) to (n, n) with just k steps is 1/k (n-1)C(k-1) nC(k-1), where mCk is the binomial coefficient.
|
|
C2. A tile is made of 5 unit squares as shown. Show that if a 5 x n rectangle can be covered with n tiles, then n is even. [Tiles can be turned over and rotated.] Show that a 5 x 2n rectangle can be tiled in at least 3n-12 ways.
|
|
|
C3. A chameleon repeatedly rests and then catches a fly. The first rest is for a period of 1 minute. The rest before catching the fly 2n is the same as the rest before catching fly n. The rest before catching fly 2n+1 is 1 minute more than the rest before catching fly 2n. How many flies does the chameleon catch before his first rest of 9 minutes? How many minutes (in total) does the chameleon rest before catching fly 98? How many flies has the chameleon caught after 1999 total minutes of rest?
|
|
|
C4. Let A be any set of n residues mod n2. Show that there is a set B of n residues mod n2 such that at least half of the residues mod n2 can be written as a + b with a in A and b in B.
|
|
|
C6. Every integer is colored red, blue, green or yellow. m and n are distinct odd integers such that m + n is not zero. Show that we can find two integers a and b with the same color such that a - b = m, n m + n or m - n.
|
|
|
C7. Let p > 3 be a prime. Let h be the number of sequences a1, a2, ... , ap-1 such that a1 + 2a2 + 3a3 + ... + (p-1)ap-1 is divisible by p and each ai is 0, 1 or 2. Let k be defined similarly except that each ai is 0, 1 or 3. Show that h ≤ k with equality iff p = 5.
|
|
Geometry
|
|
|
G1. P is a point inside the triangle ABC. k = min(PA, PB, PC). Show that k + PA + PB + PC ≤ AB + BC + CA.
|
|
|
G2. Given any 5 points, no three collinear and no four concyclic, show that just 4 of the 10 circles through 3 points contain just one of the other two points.
|
|
|
G4. ABC is a triangle. The point X on the side AB is such that AX/XB = 4/5. The point Y on the segment CX is such that CY = 2 XY, and the point Z on the ray CA is such that ∠CXZ + ∠B = 180o. Also ∠XYZ = 45o. Show that the angles of ABC are determined and find the smallest angle.
|
|
|
G5. ABC is a triangle with inradius r. The circle through A and C orthogonal to the incircle meets the circle through A and B orthogonal to the incircle at A and A'. The points B' and C' are defined similarly. Show that the circumradius of A'B'C' is r/2.
|
|
|
G7. P is a point inside the convex quadrilateral ABCD such that PA = PC, ∠APB = ∠PAD + ∠PCD, and ∠CPD = ∠PCB + ∠PAB. Show that AB·PC = BC·PD and CD·PA = DA·PB.
|
|
|
G8. X is a variable point on the arc AB of the circumcircle of ABC which does not contain C. I' is the incenter of AXC and I" is the incenter of BXC. Show that the circumcircle of XI'I" passes through a fixed point of the circumcircle of ABC.
|
|
Number theory
|
|
|
N2. Prove that every positive rational number can be written as (a3 + b3)/(c3 + d3) for some positive integers a, b, c, d.
|
|
|
N3. Show that there exist two strictly increasing sequences a1, a2, a3, ... and b1, b2, b3, ... such that an(an + 1) divides bn2 + 1 for each n.
|
|
|
N4. Show that there are infinitely many primes p such that 1/p has its shortest period divisible by 3: 1/p = 0.a1a2 ... a3ka1a2... . Amongst such primes find the largest possible value for ai + ai+k + ai+2k. For example, 1/7 = 0.142857... So the possible values for p = 7 are 1+2+5 = 8 and 4+8+7 = 19.
|
|
|
N5. Show that for any n not divisible by 3 and k >= n, there is a multiple of n which has sum of digits k.
|
|
|
N6. Show that for any k > 0 we can find an infinite arithmetic progression of positive integers each of which has sum of digits greater than k and where the common difference is not a multiple of 10.
|
|
|
Note: problems A1, A5, C5, G3, G6 and N1 were used in the Olympiad and are not shown here.
|
|
