Irish Intervarsity Mathematics Competition 1994

University College Dublin

1. Find the sum of the series

∑_{n=1}^{∞} \frac{n}{n^{4} + 4}.

Answer: These questions can nearly always be solved by using partial fractions, if they have a solution. But sometimes a little subtlety shortens the calculation.

In this case

n^{4} + 4 = (n − \sqrt{2}ω)(n − \sqrt{2}ω^{3})(n − \sqrt{2}ω^{5})(n − \sqrt{2}ω^{7})

where ω = e^{2π/8}.

We can combine conjugate factors to give 2 real quadratics

x^{4} + 4 = (x^{2} + ax + b)(x^{2} + cx + d).

From the coefficients of x^{3} and x, we must have c = −a, b = d.

x^{4} + 4 = (x^{2} + ax + b)(x^{2} − ax + b).

Thus

−a^{2} + 2b = 0, b^{2} = 4.

Hence b = 2, a = 2, yielding

x^{4} + 4 = (x^{2} + 2x + 2)(x^{2} − 2x + 2).

Now

\frac{1}{n^{2} − 2n + 2} − \frac{1}{n^{2} + 2n + 2} = \frac{4n}{n^{4} + 4}

Hopefully, the 2 terms will cancel out in some way. In fact

(n + 2)^{2} − 2(n + 2) + 2 = n^{2} + 2n + 2.

Thus the first term with n + 2 cancels out the second term with n. We are left with the first term for n = 1, 2.

∑ \frac{n}{n^{4} + 4} = \frac{1}{4} (\frac{1}{1} + \frac{1}{2}) = \frac{3}{8}.

2. Prove that there exist infinitely many positive integers n such that 2n + 1 and 3n + 1 are both perfect squares.

Answer: Suppose

2n + 1 = x^{2}, 3n + 1 = y^{2}.

Then

3x^{2} − 2y^{2} = 1.

Conversely, if x, y satisfy this equation then x is odd and

n = \frac{x^{2} − 1}{2}

satisfies the original problem. Thus the question reduces to the solution of the above diophantine equation.

This is closely related to Pell’s equation

u^{2} − 6v^{2} = 1,

which is solved by considering

z = u + v\sqrt{6}.

For if we set

z̃ = u − v\sqrt{6},

then Pell’s equation can be written

zz̃ = 1.

Now suppose we have one solution u, v. Then we get an infinity of solutions by considering

z^{n} = (u + v\sqrt{6})^{n} = U + V \sqrt{6}.

For then

z̃^{n} = U − V \sqrt{6},

and so

U^{2} − 6V^{2} = (zz̃)^{n} = 1.

Going back to our equation for x, y, we see that we can write this

(3x)^{2} − 6y^{2} = 3,

say

X^{2} − 6Y^{2} = 3,

In other words,

(X + Y \sqrt{6})(X − Y \sqrt{6}) = 3.

Now suppose we have one solution (eg X = 3, y = 1). Then we can get an infinity of solutions by taking

z = (X + Y \sqrt{6})(U + V \sqrt{6})

where U^{2} − 6V^{2} = 1.

(This is the classical number theory of a real quadratic number field.)

3. Let A, C be points in the plane and B the midpoint of [AC]. Let S be the circle with centre A and radius |AB| and T the circle with centre C and radius |AC|. Suppose S and T intersect in R, R′. Let S′, T′ be the circles with centres R, R′ and radii AR = AR′. Suppose S′ and T′ intersect in A and C′. Prove that C′ is the midpoint of [AB].

Answer: Let us choose euclidean coordinates with

A = (0, 0), B = (1, 0), C = (2, 0).

Then S has equation

x^{2} + y^{2} − 1 = 0,

and T has equation

(x − 2)^{2} + y^{2} − 4 ≡ x^{2} − 4x + y^{2} = 0.

The equation of the line RR′ is obtained by subtracting the equations of S and T:

4x − 1 = 0.

This meets the line AB at the point

D = (1/4, 0).

Evidently RR′ is the perpendicular bisector of AC′. It follows that

C′ = (1/2, 0),

ie C′ is the midpoint of [AC].

4. Let P (x) = a_{0}+a_{1}x+⋯+a_{n}x^{n} be a polynomial with integer coefficients a_{i}. Suppose that z is an integer and that

P (P (P (P (z)))) = z.

Prove that P (P (z)) = z.

Answer: Let

z_{0} = z, z_{1} = f(z), z_{2} = f(z_{1}), z_{3} = f(z_{2}), z_{4} = f(z_{3}).

We have to show that

z_{4} = z_{0} ⟹ z_{2} = z_{0}.

We may suppose therefore that z_{2} ≠ z_{0}. This implies that z_{1} ≠ z_{0}.

Any change of coordinates x ↦ x − n (where n ∈ ℤ) will replace P (x) by another polynomial P (x + n) − n with integral coefficients. Thus we may suppose that z = 0.

Then

z_{1} = a_{0}.

It is easy to see that

a_{0} | z_{1}, z_{2}, z_{3}.

On the other hand

0 = f(z_{3}) = a_{0} + z_{3}(a_{1} + a_{2}z_{3} + ⋯)

implies that

z_{3} | a_{0}.

It follows that

z_{3} = ±a_{0}.

Since z_{3} = a_{0} = z_{1} ⟹ z_{4} = z_{2} ≠ 0, we must have

z_{3} = −a_{0}.

Thus our cycle is

0 ↦ a_{0} ↦ z_{2} ↦ −a_{0} ↦ 0.

We have shown therefore that

z_{3} + z_{1} = 0 = 2z_{0}.

We have written the equation in this form so that it will remain true under any change of coordinate x ↦ x − n. Thus if we start our cycle with z_{2} we deduce that

z_{1} + z_{3} = 2z_{1} ⟹ z_{1} = 0.

[This last trick is not essential. The result can be proved by pursuing the previous argument, showing that z_{2} = ±2a_{0}, and deducing that a_{0} = ±1, ±2 or ± 4.]

5. Let a, b, c (a < b < c) be the lengths of the sides of a triangle opposite the interior angles A, B and C, respectively. Prove that if a^{2}, b^{2}, c^{2} are in arithmetic progression, then so are cot(A), cot(B), cot(C).

Answer: We have to show that

a^{2} + c^{2} = 2b^{2} ⟹ cot A + cot C = 2 cot B.

By the ‘sine law’ for the triangle,

a : b : c = sin A : sin B : sin C.

Thus a^{2} + c^{2} = 2b^{2} if and only if

sin^{2} A + sin^{2} C = 2 sin^{2} B
= 2 sin^{2}(A + C)
= 2 sin^{2} A cos^{2} C + 2 cos^{2} A sin^{2} C + 4 sin A sin C cos A cos C
= 2 sin^{2} A + 2 sin^{2} C − 4 sin^{2} A sin^{2} C + 4 sin A sin C cos A cos C,

that is, if and only if

sin^{2} A + sin^{2} C = 4 sin^{2} A sin^{2} C + 4 sin A sin C cos A cos C On the other hand cot A + cot C = 2 cot B if and only if

cot A + cot C = −2 cot(A + C),

that is,

\frac{cos A}{sin A} + \frac{cos C}{sin C} = −2\frac{cos(A + C)}{sin(A + C)},

which simplifies to

sin^{2}(A + C) = −2 sin A sin C(cos A cos C − sin A sin C). Expanding,

sin^{2} A cos^{2} C + sin^{2} C cos^{2} A + 2 sin A sin C cos A cos C =

−2 sin A sin C(cos A cos C − sin A sin C),

which reduces to the same condition as before:

sin^{2} A + sin^{2} C = 4 sin^{2} A sin^{2} C + 4 sin A sin C cos A cos C.

6. Let

A = ( \begin{matrix}1994 & 1993 \\ 1995 & 1994 \end{matrix} ) .

Prove that A can be written as the product X_{1}X_{2} ⋯ X_{r} where r ≥ 1 and each

X_{i} ∈ \{( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) , ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} )\} (i = 1, 2, …, r)

in exactly one way.

Answer: The matrix A is unimodular, ie det A = 1. It is well-known that the unimodular group

SL(2, ℤ) = \{( \begin{matrix}a & b \\ c & d \end{matrix} ) : ad − bc = 1\}

is generated by the matrices

U = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) , V = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) .

One can show this by multiplying successively on the right by U^{±1}, V^{±1}.

In our case, suppose

X = ( \begin{matrix}a & b \\ c & d \end{matrix} ) (ad − bc = 1)

with a, b, c, d > 0. Consider

XU^{−1} = ( \begin{matrix}a & b − a \\ c & d − c \end{matrix} ) and XV^{−1} = ( \begin{matrix}a − b & b \\ c − d & d \end{matrix} ) .

If b ≥ a then XU^{−1} has non-negative entries and is ‘smaller’ than X, as measured say by the sum of the entries a + b + c + d. If b < a then XV^{−1} has non-negative entries and is ‘smaller’ than X. Thus by successively multiplying by U^{−1} or V^{−1} (ensuring at each stage that the entries are non-negative) we must finally arrive at the identity matrix I. In other words,

AX_{1}^{−1}X_{2}^{−1} ⋯ X_{r}^{−1} = I,

where each X_{i} is either U or V. Thus

A = X_{1}X_{2} ⋯ X_{r}.

7. Noah had 8 species of animals to fit into 4 cages of the ark. He planned to put two species in each cage. It turned out that for each species, there were at most three other species with which it could not share a cage. Could Noah have carried out his plan while arranging that each species shares with a compatible species?

Answer: There is probably a ‘smarter’ way of solving this than the following ‘proof by cases’.

There are 28 possible pairings, of which 16 are compatible.

Take any species X. Let the species with which X is compatible form the set

S = {A, B, C, D};

and let the remaining species from the set

T = {a, b, c}.

Consider the possible pairings inside T. There are 4 cases, according as there are 0, 1, 2 or 3 pairings.

If there are no pairings inside T, then each of a, b, c must be compatible with all of S = {A, B, C, D}. Thus we can pair off (a, A), (b, B), (c, C), (X, D).

Suppose there is one pairing inside T, say (a, b). Then c is compatible with all of S while a and b are each compatible with 3 of S. Thus we know of 4 + 3 + 3 + 4 pairings; so there must be 2 pairings within S. If (A, B) is one of these pairings, thus we can pair off (A, B), (c, C), (X, D), (a, b).

Suppose there are two pairings inside T, say (a, b), (b, c). Then a and b are each compatible with 3 of S, while c is compatible with 2. Thus we know of 4+3+3+2 pairings; so there must be 4 pairings within S. If these contain a triangle they can be taken in the form (A, B), (B, C), (C, A), (A, D). If not, they can be taken as (A, B), (B, C), (C, D), (A, B). In either case, D must be compatible with a or b. We may suppose it is compatible with a; and then we can pair off (A, B), (X, C), (a, D), (b, c).

Finally, suppose there are three pairings inside T. Then a, b, c are each compatible with 2 of S. Thus we know of 4 + 2 + 2 + 3 pairings; so there must be 5 pairings within S. There are 6 possible pairings in S, so there is 1 ‘non-pairing’, say (A, B). Then B must be paired with one element of T, say a; and we can pair off (X, A), (B, a), (C, D), (b, c).

8. The function

∑_{n=1}^{∞} \frac{nx^{n}}{1 − x^{n}} (|x| < 1)

is expanded as a power-series ∑_{k=1}^{∞} a_{k}x^{k}. Prove that n = 1994 is the largest even integer with a_{n} = n + 1000.

Answer: This is almost trivial if I have the correct question.

The term

\frac{nx^{n}}{1 − x^{n}} = nx^{n} + nx^{2n} + nx^{3n} + ⋯)

will contribute n to each a_{k} with n | k. In other words, a_{k} is just the sum of the factors of k:

a_{k} = S(k).

But if k = 2m then certainly k has factors 1, 2, m, k. Thus

S(k) ≥ k + 3 + m.

So if k > 1994, ie m > 997 then

S(k) > k + 1000.

Hence k = 1994 is the largest number with S(k) = k + 1000.

9. Let a, b, c be positive real numbers. Prove that

[(a + b)(b + c)(c + a)]^{1/3} ≥ \frac{2}{\sqrt{3}}(ab + bc + ca)^{1/2}.

Answer: This is a straightforward exercise in partial differentiation.

Let

f(a, b, c) = \frac{[(a + b)(b + c)(c + a)]^{1/3}}{(ab + bc + ca)^{1/2}} .

We want to determine the minimum of f(a, b, c). At such a minimum,

\frac{∂f}{∂a} = \frac{∂f}{∂b} = \frac{∂f}{∂c} = 0.

But on differentiating log f,

\frac{1}{f} \frac{∂f}{∂a} = \frac{(b + c)(2a + b + c)}{3(a + b)(b + c)(c + a)} − \frac{b + c}{2(ab + bc + ca)}.

Thus

2a + b + c = \frac{3(a + b)(b + c)(c + a)}{2(ab + bc + ca)}.

Similarly

a + 2b + c = a + b + 2c = \frac{3(a + b)(b + c)(c + a)}{2(ab + bc + ca)}.

Thus

2a + b + c = a + 2b + c = a + b + 2c,

from which we deduce that

a = b = c.

Since

f(a, a, a) = \frac{2}{\sqrt{3}},

the result follows.

10. Let n > 1 be a positive integer. Prove that

∑_{j=1}^{n−1} j cosec^{2} (\frac{πj}{n} ) = \frac{n(n^{2} − 1)}{6}.

Answer: The factor j is somewhat misleading, since

cosec (\frac{π(n − j)}{n}) = cosec (\frac{πj)}{n}) .

Thus the jth and (n − j)th terms combine to give

n cosec^{2} (\frac{πj)}{n}) .

Hence

S = ∑_{j=1}^{n−1} j cosec^{2} (\frac{πj}{n} )
= \frac{n}{2} ∑_{j=1}^{n−1} cosec^{2} (\frac{πj}{n} )
= \frac{n}{2}S′,

say. Now we are on more familiar ground. Sums like S′ can usually be calculated in the following way. Consider the equation

tan nθ = 0.

We can express tan nθ as a rational function in cot θ:

tan nθ = \frac{P (cot θ)}{Q(cot θ)},

where P (x), Q(x) are polynomials. But

tan nθ = 0 ⟺ nθ = jπ

for some integer j. It follows that the polynomial P (x) vanishes when

x = cot \frac{jπ}{n} = γ_{j},

say, for j = 1, …, n−1. These roots are distinct; so if P (x) has degree n − 1 we must have

P (x) = c(x − γ_{1}) ⋯ (x − γ_{n−1}).

Thus we should be able to calculate symmetric functions of the γ’s from the coefficients of P (x).

Let

u = cot θ, z = e^{iθ}.

Then

u = i\frac{z + z^{−1}}{z − z^{−1}} = i\frac{z^{2} − 1}{z^{2} + 1};

and so

z^{2} = \frac{u − i}{u + i}.

But

tan nθ = \frac{1}{i} \frac{z^{n} − z^{−n}}{z^{n} − z^{−n}}
= \frac{1}{i} \frac{z^{2n} − 1}{z^{2n} + 1}
= \frac{1}{i} \frac{u − i))^{n} − (u + i)^{n}}{(u − i)^{n} + (u + i)^{n}} .

It follows that (up to a scalar multiple)

P (x) = \frac{1}{i} ((u − i)^{n} − (u + i)^{n})
= −2nu^{n−1} + 2\frac{n(n − 1)(n − 2)}{6}u^{n−3} + · · · .

Thus

∑ γ_{j} = 0, ∑ γ_{j}γ_{k} = −\frac{(n − 1)(n − 2)}{6}.

Now

cosec^{2} (\frac{jπ}{n} ) = 1 + γ_{j}^{2}.

Thus

S = \frac{n}{2} (n − 1 + ∑ γ_{j}^{2})
= \frac{n}{2} (n − 1 + (∑ γ_{j})^{2} − 2 ∑ γ_{j}γ_{k})
= \frac{n}{2} (n − 1 + \frac{n − 1)(n − 2)}{3})
= \frac{n}{6} (3n − 3 + (n − 1)(n − 2))
= \frac{n(n^{2} − 1)}{6}.