PART II   2001 Solutions

1. A band of pirates unloaded some number of treasure chests from their ship. The number of pirates was between 60 and 69 (inclusive). Each pirate handled exactly 11 treasure chests, and each treasure chest was handled by exactly 7 pirates. Exactly how many treasure chests were there? Show that your answer is the only solution.

Answer: Let P be the number of pirates, and let C be the number of chests. Then, by counting the number of `treasure chest handlings' in 2 different ways yields 11P=7C. Since P and C are integers, it follows that P must be divisible by 7. Since 60< = P < = 69, P must equal 63. So C=11*63/7=99.

2. Let a and b be the lengths of the legs of a right triangle, let c be the length of the hypotenuse, and let h be the length of the altitude drawn from the vertex of the right angle to the hypotenuse. Prove that c+h>a+b.

Answer: First, note that the area of the triangle can be expressed as (1/2)ch AND (1/2)ab. Thus, ch=ab. Also, note that a 2 + b 2 = c 2 by the Pythagorean Theorem. So (c+h) 2 = c 2 + 2ch + h 2 = a 2 + b 2 + 2ab 2 + h 2 > (a+b) 2 since h>0. Thus, since all the lengths are positive, it follows that c+h>a+b.

3. Prove that 1/70< (1/2)(3/4)(5/6)...(2001/2002) < 1/40.

Answer: Let x=(1/2)(3/4)(5/6)...(2001/2002), let y=(2/3)(4/5)...(2002/2003), and let z=(1/2)(2/3)(4/5)...(2000/2001). Now y>x since 2/3>1/2, 4/5>3/4, etc. But xy=1/2003, hence x<(1/2003) 1/2 < (1/1600) 1/2=1/40. Similarly, z< x, and xz=(1/2)(1/2002)=1/4004. Thus, x>(1/4004) 1/2 > (1/4900) 1/2=1/70.

4. Given a positive integer a 1 we form a sequence a 1 , a 2 , a 3 ... as follows: a 2 is obtained from a 1 by adding together the digits of a 1 raised to the 2001 st power; a 3 is obtained from a 2 using the same rule, and so on. For example, if a 1 =25, then a 2 =2 2001+52001, which is a 1399-digit number containing 106 0's, 150 1's, 124 2's, 157 3's, 148 4's, 141 5's, 128 6's, 150 7's, 152 8's, 143 9's, So

a 3 = 106 x 0 2001+ 150 x 1 2001+ 124 x 2 2001+ 157 x 3 2001+...+ 143 x 9 2001
which is a 1912-digit number, and so forth. Prove that if any positive integer a 1 is chosen to start the sequence, then there is a positive integer M (which depends on a 1 ) that is so large that a n < M for all n=1,2,3,...

Answer: As notation for a given positive integer x we let x * be the number obtained by raising the digits of x to the power 2001 and totaling the results. For example, the number a=10 k -1=999... (k digits) transforms to a * = k 9 2001. It is easy to prove by induction that k< 2k for all k>= 1, so if 5k > 92001, then
a * < 2k 92001 < 2 k · 5 k = 10 k Thus a * < = 10k -1. Now observe that if x< a=10k -1, then x * < a * Given the seed value a1 , choose k so that 1) 5k > 9 2001 and 2) 10k -1> a1 . Let M= 10k -1. It follows by induction that a_n< M for all n=1,2,3,...

5. Let P(x) be a polynomial with integer coefficients. Suppose that there are integers a, b, and c such that P(a)=0, P(b)=1, and P(c)=2. Prove that there is at most one integer n such that P(n)=4.

Answer: Let P'(x)=P(x-b)-1. Then P'(0)=0 and there are integers c and d such that P'(c)=1 and P'(d)=-1. Moreover, if P attains the value 4 at two different integers, then P' would attain the value 3 at two different integers. We will show that this is impossible. Since P'(0)=0 we can write P'(x)=xQ(x), where Q(x) also is a polynomial with integer coefficients. Now P'(c)=1=cQ(c), so c=1 or -1. Similarly, P'(d)=-1=dQ(d), so d=1 or -1. Clearly, c is not equal to d, so we have two cases: Either P'(1)=1 and P'(-1)=-1; or P'(-1)=-1 and P'(1)=1. In the first case, Q(1)=Q(-1)=1, and in the second case Q(1)=Q(-1)=-1. Now suppose by way of contradiction that there are two integers e and f such that P'(e)=3=P'(f). Then P'(e)=eQ(e)=3, so Q(e)=1 or -1 and e is 3 or -3. (Because if Q(e)=3 or -3, then e would be 1 or -1, but we know that P(1) and P(-1) are not equal to 3). Similarly, Q(f)=1 or -1 and f is 3 or -3. In summary, we have shown that the values of Q on -3,-1,1,3 are EITHER -1,1,1,1 OR -1,-1,-1,1 respectively. By replacing Q(x) by -Q(x), we may assume that the first possibility holds. Let R(x)=-Q(x-1)+1. Then R attains the values of 2,0,0,0 at the integers -2,0,2,4, respectively. Thus, R(x)=x(x-2)(x-4)S(x) for some polynomial S, also with integer coefficients. But then R(-2)=-48·S(-2), which is certainly not equal to 2.