\documentclass[12pt,a4paper]{article}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amsfonts}
\newcommand{\Z}{\mathbb{Z}}
\ifx\answers\undefined
\newenvironment{answer}{\comment}{\endcomment}
\else
\newenvironment{answer}{\textbf{Answer:}\em}{}
\fi
\def\cosec{\mathop{\rm cosec}\nolimits}
\def\implies{\Longrightarrow}
\def\Z{\Bbb{Z}}
\let\divides=\mid
\def\SL{\mathbf{SL}}
\title{%
\includegraphics[width=4cm]{tcdarms}\\[5mm]
Irish Intervarsity Mathematics Competition 1994}
\author{University College Dublin}
\date{}
\begin{document}
\maketitle
\pagestyle{empty}
\begin{enumerate}
\item
Find the sum of the series
\[
\sum_{n=1}^\infty \frac{n}{n^4 + 4}.
\]
\begin{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}\omega)
(n - \sqrt{2}\omega^3)
(n - \sqrt{2}\omega^5)
(n - \sqrt{2}\omega^7)
\]
where $\omega = e^{2\pi/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$.
\[
\sum \frac{n}{n^4 + 4} = \frac{1}{4}\left(\frac{1}{1} + \frac{1}{2}\right) = \frac{3}{8}.
\]
\end{answer}
\item
Prove that there exist infinitely many positive integers $n$
such that $2n+1$ and $3n+1$ are both perfect squares.
\begin{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
\[
\tilde{z} = u - v\sqrt{6},
\]
then Pell's equation can be written
\[
z \tilde{z} = 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
\[
\tilde{z}^n = U - V\sqrt{6},
\]
and so
\[
U^2 - 6V^2 = (z\tilde{z})^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.)
\end{answer}
\item
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]$.
\begin{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 \equiv 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]$.
\end{answer}
\item
Let $P(x) = a_0 + a_1x + \cdots + a_nx^n$
be a polynomial with integer coefficients $a_i$.
Suppose that $z$ is an integer and that
\[
P\left(P\left(P(P(z))\right)\right) = z.
\]
Prove that $P(P(z)) = z$.
\begin{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 \implies z_2 = z_0.
\]
We may suppose therefore that $z_2 \not= z_0$.
This implies that $z_1 \not= z_0$.
Any change of coordinates $x \mapsto x-n$
(where $n\in\Z$)
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 \divides z_1, z_2, z_3.
\]
On the other hand
\[
0 = f(z_3) = a_0 + z_3(a_1 + a_2z_3 + \cdots)
\]
implies that
\[
z_3 \divides a_0.
\]
It follows that
\[
z_3 = \pm a_0.
\]
Since $z_3 = a_0 = z_1 \implies z_4 = z_2 \not= 0$,
we must have
\[
z_3 = - a_0.
\]
Thus our cycle is
\[
0 \mapsto a_0 \mapsto z_2 \mapsto -a_0 \mapsto 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 \mapsto x-n$.
Thus if we start our cycle with $z_2$ we deduce that
\[
z_1 + z_3 = 2z_1 \implies z_1 = 0.
\]
[This last trick is not essential.
The result can be proved by pursuing the previous argument,
showing that $z_2 = \pm2a_0$,
and deducing that $a_0 = \pm1,\;\pm2 \mbox{ or }\pm4$.]
\end{answer}
\item
Let $a,b,c\;(a**0$.
Consider
\[
XU^{-1} =
\left(\begin{array}{c c}a & b-a\\c & d-c\end{array}\right) \mbox{ and }
XV^{-1} =
\left(\begin{array}{c c}a-b & b\\c-d & d\end{array}\right).
\]
If $b \ge 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}\cdots X_r^{-1} = I,
\]
where each $X_i$ is either $U$ or $V$.
Thus
\[
A = X_1X_2\cdots X_r.
\]
\end{answer}
\item
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?
\begin{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)$.
\end{answer}
\item
The function
\[
\sum_{n=1}^\infty \frac{nx^n}{1-x^n}\quad (|x| < 1)
\]
is expanded as a power-series $\sum_{k=1}^\infty a_kx^k$.
Prove that $n=1994$ is the largest even integer with $a_n = n + 1000$.
\begin{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} + \cdots)
\]
will contribute $n$ to each $a_k$ with $n \divides k$.
In other words, {\em $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) \ge 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$.
\end{answer}
\item
Let $a,b,c$ be positive real numbers.
Prove that
\[
\left[(a+b)(b+c)(c+a)\right]^{1/3} \ge \frac{2}{\sqrt{3}} (ab+bc+ca)^{1/2}.
\]
\begin{answer}
This is a straightforward exercise in partial differentiation.
Let
\[
f(a,b,c) = \frac{\left[(a+b)(b+c)(c+a)\right]^{1/3}}
{(ab+bc+ca)^{1/2}}.
\]
We want to determine the minimum of $f(a,b,c)$.
At such a minimum,
\[
\frac{\partial f}{\partial a} =
\frac{\partial f}{\partial b} =
\frac{\partial f}{\partial c} = 0.
\]
But on differentiating $\log f$,
\[
\frac{1}{f}\frac{\partial f}{\partial 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.
\end{answer}
\item
Let $n>1$ be a positive integer.
Prove that
\[
\sum_{j=1}^{n-1} j \cosec^2\left(\frac{\pi j}{n}\right) = \frac{n(n^2-1)}{6}.
\]
\begin{answer}
The factor $j$ is somewhat misleading,
since
\[
\cosec\left(\frac{\pi(n-j)}{n}\right) =
\cosec\left(\frac{\pi j)}{n}\right).
\]
Thus the $j$th and $(n-j)$th terms combine to give
\[
n\cosec^2\left(\frac{\pi j)}{n}\right).
\]
Hence
\begin{eqnarray*}
S &=& \sum_{j=1}^{n-1} j \cosec^2\left(\frac{\pi j}{n}\right)\\
&=& \frac{n}{2} \sum_{j=1}^{n-1} \cosec^2\left(\frac{\pi j}{n}\right)\\
&=& \frac{n}{2}S',
\end{eqnarray*}
say.
Now we are on more familiar ground.
Sums like $S'$ can usually be calculated in the following way.
Consider the equation
\[
\tan n\theta = 0.
\]
We can express $\tan n\theta$ as a rational function in $\cot\theta$:
\[
\tan n\theta = \frac{P(\cot\theta)}{Q(\cot\theta)},
\]
where $P(x),Q(x)$ are polynomials.
But
\[
\tan n\theta = 0 \iff n\theta = j\pi
\]
for some integer $j$.
It follows that the polynomial $P(x)$ vanishes when
\[
x = \cot\frac{j\pi}{n} = \gamma_j,
\]
say, for $j = 1,\dots,n-1$.
These roots are distinct;
so if $P(x)$ has degree $n-1$ we must have
\[
P(x) = c(x - \gamma_1)\cdots(x - \gamma_{n-1}).
\]
Thus we should be able to calculate symmetric functions of the $\gamma$'s
from the coefficients of $P(x)$.
Let
\[
u = \cot\theta,\;z = e^{i\theta}.
\]
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
\begin{eqnarray*}
\tan n\theta &=& \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}.
\end{eqnarray*}
It follows that (up to a scalar multiple)
\begin{eqnarray*}
P(x) &=& \frac{1}{i} \left((u-i)^n - (u+i)^n\right)\\
&=& -2n u^{n-1} + 2\frac{n(n-1)(n-2)}{6} u^{n-3} + \cdots.
\end{eqnarray*}
Thus
\[
\sum \gamma_j = 0,\; \sum \gamma_j\gamma_k = -\frac{(n-1)(n-2)}{6}.
\]
Now
\[
\cosec^2\left(\frac{j\pi}{n}\right) = 1 + \gamma_j^2.
\]
Thus
\begin{eqnarray*}
S &=& \frac{n}{2} \left(n-1 + \sum\gamma_j^2\right)\\
&=& \frac{n}{2} \left(n-1 + (\sum\gamma_j)^2 - 2\sum\gamma_j\gamma_k\right)\\
&=& \frac{n}{2} \left(n-1 + \frac{n-1)(n-2)}{3}\right)\\
&=& \frac{n}{6} \left(3n-3 + (n-1)(n-2)\right)\\
&=& \frac{n(n^2-1)}{6}.
\end{eqnarray*}
\end{answer}
\end{enumerate}
\end{document}
**