24th VTRMC, 2002, Solutions

1. The volume is y dydx. We put this in more familiar form by replacing x with q and y with r to obtain

r drdq.

This is simply the area in the first quadrant of r = 1, equivalently b2r2cos2q + a2r2sin2q = 1. Putting this in Cartesian coordinates, we obtain b2x2 + a2y2 = 1, so we have to find the area of a quarter ellipse which intersects the positive x and y-axes at 1/b and 1/a respectively. Therefore the volume required is (p)/(4ab).

2. The only solution is a = d = e = 0 and b = c = 1. To check this is a solution, we need to show = + . Since both sides are positive, it will be sufficient to show that the square of both sides are equal, that is 7 + = ( + )2, which is indeed true because the right hand side is 7 + 2.

3. Let s be the given integer in S, and for an arbitrary integer y in S, define f (y) = s - y if y < s and f (y) = 99 + s - y if y>s (roughly speaking, f (y) is s - y mod 99). Note that f : S - > S is a well defined one-to-one map. Let C denote the integers f (y) for y in B, a subset of S with b elements because f is one-to-one. Since a + b > 99, we see that A and C must intersect nontrivially, equivalently f (y) must be an integer x in A for some integer y in B. Then f (y) = x which yields x = s - y or s - y + 99, as required.

4. Since 23 = 32, we can rearrange a word consisting of 2's and 3's so that all the 2's appear before the 3's. An even number of 2's gives 1, and an odd number of 2's gives 2, and similarly an even number of 3's gives 1 and an odd number of 3's gives 3. From this, we see that a word consisting of just 2's and 3's can only equal 1 if there are both an even number of 2's and an even number of 3's. Thus we already have that f (n) = 0 for all positive odd integers n.

Now consider f (n) for n even. By switching the first letter between 2 and 3, we see that the number of words consisting of just 2's and 3's which have an even number of 2's is the same as the number of words with an odd number of 2's. Since the total number of words of length n is 2n, we deduce that A(n) = 2n - 1 when n is even. Therefore A(12) = 211 = 2048.

5. First we find a recurrence relation for f (n). If the first 0 is in position 1, there are 0 strings; if the first 0 is in position 2, there are f (n - 2) strings; if the first 0 is in position 3, there are f (n - 3) strings; if the first 0 is in position (n - 2) there are f (2) strings; if the first 0 is in position (n - 1) there are f (1) strings; and if there are no 0's there is 1 string. We deduce that

 f (n) = f (n - 2) + ... + f (1) + 1 f (n - 1) = f (n - 3) + ... + f (1) + 1

Therefore f (n) = f (n - 1) + f (n - 2). We now prove by induction that f (n) < 1.7n for all n. The result is certainly true for n = 1, 2. Suppose it is true for n - 2, n - 1, that is f (n - 2) < 1.7n - 2 and f (n - 1) < 1.7n - 1. Then

f (n) = f (n - 2) + f (n - 1) < 1.7n - 2 + 1.7n - 1 = 1.7n(1.7 + 1)/1.72 < 1.7n,

which establishes the induction step and the result follows.

6. Let the three matrices in T be X, Y, Z, and let I denote the identity matrix. Let us suppose by way of contradiction that there are no A, B in S such that AB is not in S. If l is an eigenvalue of X, then lr is an eigenvalue of Xr. From this we immediately see that the eigenvalues of X2 are {1, 1}. This means that the Jordan Canonical Form of X2 is

(
 1 x 0 1
)

where x = 0 or 1. If x = 1, then the matrices X2n for n>1 are all different and members of T, which is not possible because | T| = 3. Therefore X2 = I and in particular I is in T. Thus we may label are members of T as X, Y, I, where I is the identity matrix and X2 = Y2 = I. Consider XYX. We have (XYX)(XYX) = XYX2YX = XY2X = X2 = I, so the eigenvalues of XYX are ±1. This means that XYX is another member of T, so must be one of X, Y, I. We now show that this is not possible. If XYX = X, then XYXXY = XXY = Y which yields X = Y. If XYX = I, then XXYXX = XX = I which yields Y = I. Neither of these is possible because X, Y, I are distinct. Finally if XYX = Y, then (XY)(XY) = I which shows that XY is also a member of T, so we must have XY = X, Y or I, and this is easily seen to be not the case.

7. We use the fact that the arithmetic mean is at least the geometric mean, so (a1 + ... + an)/n>(a1...an)1/n. Since S1an is convergent, it has a sum M say, and then we have a1 + ... + an < M for all n. We deduce that bn < M/n and hence bn2 < M2/n2. But S1/n2 is convergent (p-series with p = 2 > 1), hence SM2/n2 is also convergent and the result follows from the comparison test.

Peter Linnell
2002-11-01