32nd VTRMC, 2010, Solutions

1. It is easily checked that 101 is a prime number (divide 101 by the primes whose square is less than 101, i.e. the primes ≤7). Therefore for 1≤r≤100, we may choose a positive integer q such that rq≡1 mod 101. Since (I + A + ... + A100)(I - A) = I - A101, we see that A101 = I, in particular A is invertible with inverse A100. Suppose < n≤100 and set r = 101 - n. Then 1≤r≤100 and An + ... + A100 is invertible if and only if I + ... + Ar-1 is invertible. We can think of I + ... + Ar-1 as (I - Ar)/(I - A), which should have inverse (I - A)/(I - Ar). However A = (Ar)q and so (I - A)/(I - Ar) = I + Ar + ... + (Ar)q-1. It is easily checked that

(I + ... + Ar-1)(I + Ar + ... + (Ar)q-1) = I.

It follows that An + ... + A100 is invertible for all positive integers n≤100. We conclude that An + ... + A100 has determinant ±1 for all positive integers n < 100.

2. First we will calculate fn(75)mod 16. Note that if a, b are odd positive integers and ab mod 16, then aabbmod 16. Also 33≡11 mod 16 and 1111≡3 mod 16. We now prove by induction on n that f2n-1(75)≡11 mod 16 for all nN. This is clear for n = 1 so suppose f2n-1(75)≡11 mod 16 and set k = f2n-1(75) and m = f2n(75). Then

 f2n(75)≡kk≡1111 ≡3 mod 16 f2n+1(75)≡mm≡33 ≡11 mod 16

and the induction step is complete. We now prove that fn(a)≡fn+2(a)mod 17 for all a, nN with a prime to 17 and n even. In fact we have

fn+1(a)≡a3mod 17,    fn+2(a)≡(a3)11a mod 17.

Thus f100(75)≡f2(75)mod 17. Therefore f100(75)≡711≡14 mod 17.

3. First note the e2πi/7 satisfies 1 + x + ... + x6 = 0, so by taking the real part, we obtain n=0n=6cos 2nπ/7 = 0. Since cos 2π/7 = cos 12π/7, cos 4π/7 = cos 10π/7 = - cos 3π/7 and cos 6π/7 = cos 8π/7 = - cosπ/7, we see that 1 - 2 cosπ/7 + 2 cos 2π/7 - 2 cos 3π/7 = 0.

Observe that if 1 - 2 cosθ +2 cos 2θ -2 cos 3θ = 0, then by using cos 2θ = 2 cos2θ - 1 and cos 3θ = 4 cos3θ -3 cosθ, we find that cosθ satisfies 8x3 -4x2 - 4x + 1 = 0. Thus in particular cosπ/7 satisfies this equation. Next note that 1 - 2 cos 3π/7 + 2 cos 6π/7 - 2 cos 9π/7 = 1 - 2 cos 3π/7 - 2 cosπ/7 + 2 cos 2π/7, so cos 3π/7 is also a root of 8x3 -4x2 - 4x + 1. Finally since the sum of the roots of this equation is 1/2, we find that -cos 2θ is also a root. Thus the roots of 8x3 -4x2 - 4x + 1 are cosπ/7, -cos 2π/7, cos 3π/7.

4. The equation 4A + 3C = 540o tells us that A = 3B. Let D on BC such that ADC = 3B, and then let E on BD such that AED = 2B.

Since triangles ABD and AED are similar, we see that

Also BE = AE because B = ∠BAE, and BE = BD - BE. We deduce that BD2 = AD2 + AB·AD. Since BD = BC - CD, we conclude that (BC - CD)2 = AD2 + AB·AD.

Next triangles ABC and ADC are similar, consequently

Thus AD = AB·AC/BC and CD = AC2/BC. We deduce that

(a - b2/a)2 = c2b2/a2 + c2b/a.

Therefore (a2 - b2)2 = bc2(a + b) and the result follows.

5. Let X denote the center of A, let Y denote the center of B, let Z be where A and B touch (so X, Y, Z are collinear), and let θ = ∠PXY. Note that YQ makes an angle 2θ downwards with respect to the horizontal, because QYZ = 3θ.

Choose (x, y)-coordinates such that X is the origin and XP is on the line y = 0. Let (x, y) denote the coordinates of Q. Then we have

 x = 2 cosθ + cos 2θ y = 2 sinθ - sin 2θ.

By symmetry the area above the x-axis equals the area below the x-axis (we don't really need this observation, but it may make things easier to follow). Also θ goes from 2π to 0 as circle B goes round circle A. Therefore the area enclosed by the locus of Q is

 2∫π0y(dx/dθ) dθ = 2∫π0(2 sinθ - sin 2θ)(- 2 sinθ -2 sin 2θ) dθ = 2∫0π(4 sin2θ +2 sinθsin 2θ -2 sin22θ) dθ = ∫0π(4 - 4 cos 2θ +2 cosθ -2 cos 3θ -2 + 2 cos 4θ) dθ = 2π.

6. Note that if 0 < x, y < 1, then 0 < 1 - y/2 < 1 and 0 < x(1 - y/2) < 1, and it follows that (an) is a positive monotone decreasing sequence consisting of numbers strictly less that 1. This sequence must have a limit z where 0≤z≤1. In particular an+2 - an+1 = anan+1/2 has limit 0, so limn-> ∞anan+1 = 0. It follows that z = 0.

Set bn = 1/an. Then bn+2 = bn+1/(1 - an/2) = bn+1(1 + an/2 + O(an2)). Therefore bn+2 - bn+1 = bn+1(an/2 + O(an2)). Also

an/an+1 = (1 - an-1/2)-1 = 1 + O(an)

and we deduce that bn+2 - bn+1 = bn(1 + O(an))(an/2 + O(an2)). Therefore bn+2 - bn+1 = 1/2 + O(an). Thus given ε > 0, there exists NN such that | bn+1 - bn -1/2| < ε for all n > N. We deduce that if k is a positive integer, then | bn+k/k - bn/k - 1/2| < ε. Thus for k sufficiently large, | bn+k/(n + k) - 1/2| < 2ε. We conclude that limn-> ∞bn/n = 1/2 and hence limn-> ∞nan = 2.

7. It will be sufficient to prove that n=1n2/(1/a12 + ... +1/an2) is convergent. Note we may assume that (an) is monotonic decreasing, because rearranging the terms in series an does not affect its convergence, whereas the terms of the above series become largest when (an) is monotonic decreasing. Next observe that if n=1an = S, then anS/n for all positive integers n. Now consider (2n)2/(1/a12 + ... +1/a2n2). This is ≤(2n)2S/(1/a1 +2/a2 + ... +2n/a2n)≤4n2S/(n2/an) = 4San. The result follows.

Peter Linnell 2010-11-04