24th USA Mathematical Olympiad 1995 Problems
1. The sequence a0a1, a2, ... of non-negative integers is defined as follows. The first p-1 terms are 0, 1, 2, 3, ... , p-2. Then an is the least positive integer so that there is no arithmetic progression of length p in the first n+1 terms. If p is an odd prime, show that an is the number obtained by writing n in base p-1, then treating the result as a number in base p. For example, if p is 5, to get the 5th term one writes 5 as 11 in base 4, then treats this as a base 5 number to get 6.
2. A trigonometric map is any one of sin, cos, tan, arcsin, arccos and arctan. Show that given any positive rational number x, one can find a finite sequence of trigonometric maps which take 0 to x. [So we need to show that we can always find a sequence of trigonometric maps ti so that: x1 = t0(0), x2 = t1(x1), ... , xn = tn-1(xn-1), x = tn(xn).]
3. The circumcenter O of the triangle ABC does not lie on any side or median. Let the midpoints of BC, CA, AB be L, M, N respectively. Take P, Q, R on the rays OL, OM, ON respectively so that ∠OPA = ∠OAL, ∠OQB = ∠OBM and ∠ORC = ∠OCN. Show that AP, BQ and CR meet at a point.
4. a0, a1, a2, ... is an infinite sequence of integers such that an - am is divisible by n - m for all (unequal) n and m. For some polynomial p(x) we have p(n) > |an| for all n. Show that there is a polynomial q(x) such that q(n) = an for all n.
5. A graph with n points and k edges has no triangles. Show that it has a point P such that there are at most k(1 - 4k/n2) edges between points not joined to P (by an edge).
Solution
24th USA Mathematical Olympiad 1995
Problem 1
The sequence a0a1, a2, ... of non-negative integers is defined as follows. The first p-1 terms are 0, 1, 2, 3, ... , p-2. Then an is the least positive integer so that there is no arithmetic progression of length p in the first n+1 terms. If p is an odd prime, show that an is the number obtained by writing n in base p-1, then treating the result as a number in base p. For example, if p is 5, to get the 5th term one writes 5 as 11 in base 4, then treats this as a base 5 number to get 6.
Solution
Let bn be the number obtained by writing n in base p-1 and then treating the result as a number in base p. The resulting sequence bn is all those non-negative integers whose base p representation does not have a digit p-1. We show that bn cannot contain an arithmetic progression of length p. For suppose there was such a progression with difference d. Suppose the last non-zero digit of d in base p is k. Suppose the first term of the progression has digit h in that position, then the terms of the progression have digit h, h+k, h+2k, ... h+(p-1)k mod p in that position. But these must be a complete set of residues mod p, so one of them must be p-1 mod p. So the corresponding term has a digit p-1 in this position. Contradiction.
Now to show that an = bn we use induction on n. Evidently, it is true for n < p-1. Suppose it is true for all m < n. It is sufficient to show that if bn < m < bn+1, then {b1, b2, ... , bn, m} contains an arithmetic progression. m must contain a digit p-1, for otherwise it would be bk for some k > n. Let m1 be the number obtained from m by reducing every digit p-1 in m by 1. Then m has no digit p-1s, so it must be some bk and hence one of b1, ... , bn. Now take m2 to be the number obtained by reducing the same digits by another 1. Similarly, define m3, ... , mp-1. Then each mi is in {b1, ... , bn} and mp-1, ... , m1, m is a progression of length p. Problem 2
A trigonometric map is any one of sin, cos, tan, arcsin, arccos and arctan. Show that given any positive rational number x, one can find a finite sequence of trigonometric maps which take 0 to x. [So we need to show that we can always find a sequence of trigonometric maps ti so that: x1 = t0(0), x2 = t1(x1), ... , xn = tn-1(xn-1), x = tn(xn).]
Solution
We have cos2t + sin2t = 1. Hence cos t = cos t/(√(cos2t + sin2t)) = 1/(√(1 + tan2t)). So if we put tan t = √x, then cos tan-1√x = 1/√(1 + x). We also have cos(p/2 - x) = sin x and tan(p/2 - x) = 1/tan x. So tan cos-1 sin tan-1 x = 1/x (1). Hence also tan cos-1 sin tan-1 cos tan-1 √x = √(x + 1) (2). These two relations solve the problem.
Using (2) and iterating we can get √n for any positive integer n. Hence in particular we can get n for any positive integer n. Now suppose we want m/n with m and n relatively prime. We show that m/n can be achieved by induction on n. We have just dealt with the case n = 1. Suppose we have dealt with all a/b with b < n. If m > n, then we can write m = qn + r with 0 < r < n and use (2) to reduce the problem to getting r/n. If m < n, then put r = m. Now use (1) to reduce the problem to n/r, which is solved by induction.
The circumcenter O of the triangle ABC does not lie on any side or median. Let the midpoints of BC, CA, AB be L, M, N respectively. Take P, Q, R on the rays OL, OM, ON respectively so that ∠OPA = ∠OAL, ∠OQB = ∠OBM and ∠ORC = ∠OCN. Show that AP, BQ and CR meet at a point.
Solution
We show that the circumcircle ABC is the incircle of PQR. Then (AR/AQ) (CQ/CP) (BP/BR) = 1 since AR = BR, AQ = CQ, BP = CP (equal tangents) and hence PA, QB, RC are concurrent by Ceva's theorem.
So let the tangents to the circumcircle at B and C meet at P'. It is sufficient to show that ∠OP'A = ∠OAL, for then it follows that P' = P (since there is obviously a unique point on the ray OL at which the segment OA subtends the ∠OAL).
This is curiously difficult to prove. Let LP' meet the circle at K. Then ∠KCP' = ∠KBC (P'C tangent) = ∠KCB (KO perpendicular to BC, since L midpoint) = ∠KCL (same angle). So KC bisects ∠P'CL. Hence KP'/KL = CP'/CL. But obviously CP'/CL = BP'/BL. So K, C and B lie on the circle of Apollonius, the points X such that XP'/XL is constant. But A also lies on the circle of Apollonius. Hence KA bisects ∠P'AL. (See Canada 71/9 if you are not familiar with the circle of Apollonius.) But ∠OP'A + ∠KAP' = ∠OKA = ∠OAK (OA and OK radii) = ∠OAL + ∠KAL. So ∠OP'A = ∠OAL.
a0, a1, a2, ... is an infinite sequence of integers such that an - am is divisible by n - m for all (unequal) n and m. For some polynomial p(x) we have p(n) > |an| for all n. Show that there is a polynomial q(x) such that q(n) = an for all n.
Solution
Clearly for any finite N, we can find a polynomial q(n) of degree N such that q(n) = an for n = 0, ... , N. Also, once a0, a1, ... , aN are fixed, am is somewhat constrained for m > N, because we require am to be a0 mod m, a1 mod m-1, ... , aN mod m-N. Put M = lcm(m, m-1, ... , m-N). Then am is determined mod M.
We would like to argue that q(m) is known to satisfy the congruences (because m - n divides q(m) - q(n) ), that q(m) and am are bounded so that they cannot differ by as much as M and hence must be equal. The snag is that q(x) does not necessarily have integer coeffcients, so it is not necessarily true that m - n divides q(m) - q(n). [The argument is that m - n divides mk - nk for any integer k and hence divides q(m) - q(n) for any polynomial with integer coefficients.]
However, the coefficients of q(x) are rational. So let Q be the lcm of the denominators. Then Q q(x) does have integer coefficients and m - n does divide Q( q(m) - q(n) ). So Q q(m) = Q q(0) = Q a0 = Q am mod m, and similarly Q q(m) = Q am mod m-1 and so on. Hence Q q(m) = Q am mod M.
But we know that |q(m)| < c mN for some constant c, since q(x) has degree N. Similarly, we know that |am| is bounded by a polynomial of degree N and hence |am| < c' mN for some constant c'. Now M certainly exceeds the product of the N+1 numbers m, m-1, ... , m-N divided by the greatest common divisor for each of the N(N+1)/2 pairs (m - i, m - j). But each gcd is at most N, so M is more than c" mN+1 for some (small) constant c" which does not depend on m. Hence for m ≥ some N' we have M > |Q q(m)| + |Q am| and hence q(m) = am.
So we have q(m) = am for m ≤ N and for m ≥ N'. Suppose N < m < N'. Then for any m' > N' we have that (m' - m) divides Q q(m') - Q q(m) and Q am' - Q am. So it must divide their difference. But q(m') = am', so it divides Q(q(m) - am). But we can choose m' so that (m' - m) is prime to Q and larger than (q(m) - am). Hence q(m) = am. So we have established that q(m) = am for all m.
Thanks to Nghi Nguyen for showing that we need Q in the last paragraph also.
A graph with n points and k edges has no triangles. Show that it has a point P such that there are at most k(1 - 4k/n2) edges between points not joined to P (by an edge).
Solution
Given a point P, the edges of the graph can be divided into three categories: (1) edges PQ, (2) edges QQ', where Q is joined to P, and (3) edges Q'Q", where Q' and Q" are not joined to P. Note that if Q is joined to P and there is an edge QQ', then Q' cannot be joined to P, or PQQ' would be a triangle. So the total number of edges in categories (1) and (2) is ∑' deg Q, where ∑' indicates that the sum is taken over points Q which are joined to P (by an edge). Thus the total number of edges in category (3) is k - ∑' deg Q. So we have to show that for some P, ∑' deg Q ≥ 4k2/n2.
The total for all points P is ∑P∑' deg Q. If we invert the order of the summations, this becomes ∑ deg2Q, where the sum is over all points Q. Now by Cauchy, (∑ deg Q)2 ≤ (∑ 12)(∑ deg2Q) = n ∑ deg2Q. But ∑ deg Q = 2k, so ∑ deg2Q ≥ 4k2/n and hence ∑P∑' deg Q ≥ 4k2/n. But if a sum of n terms is at least 4k2/n, then at least one for the terms must be at least 4k2/n2. In other words, there is a point P such that ∑' deg Q ≥ 4k2/n2, as required.
Labels:
USAMO
Previous Article
