\documentclass[a4paper,12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[dvips]{graphicx}
\newenvironment{answer}{\begin{em}Answer.~}{\end{em}}
\let\divides=\mid
\def\notdivides{\not\,\mid}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\abs}[1]{\lvert#1\rvert}
%\addtolength{\topmargin}{-2.5cm}
%\addtolength{\textheight}{3cm}
\pagestyle{empty}
\begin{document}
\title{
\vspace*{-3cm}
\mbox{\includegraphics[width=4cm]{tcdarms.ps}}\\[5mm]
Irish Intervarsity Mathematics Competition}
\author{Trinity College Dublin 1997}
\date{9.30--12.30 Saturday 22\textsuperscript{nd} February 1997}
\maketitle
\thispagestyle{empty}
\begin{center}
\sl Answer as many questions as you can;
all carry the same mark.
Give reasons in all cases.
Tables and calculators are not allowed.
\end{center}
\begin{enumerate}
\item
Compute
\[
\sum_{n=1}^\infty \frac{n^2}{2^n}.
\]
\begin{answer}
First solution:
Let
\begin{eqnarray*}
f(x) &=& \sum_0^\infty \frac{x^n}{2^n}\\
&=& 1 + \frac{x}{2} + \frac{x^2}{2^2} + \cdots\\
&=& \frac{1}{1-x/2}\\
&=& \frac{2}{2-x}.
\end{eqnarray*}
Differentiating,
\[
\sum_1^\infty \frac{nx^{n-1}}{2^n} = \frac{2}{(2-x)^2}.
\]
Multiplying by $x$,
\[
\sum_1^\infty \frac{nx^n}{2^n} = \frac{2x}{(2-x)^2}.
\]
Differentiating again,
\[
\sum_1^\infty \frac{n^2x^{n-1}}{2^n} = \frac{2}{(2-x)^2} + \frac{4x}{(2-x)^3}.
\]
Substituting $x = 1$,
\[
\sum_1^\infty \frac{n^2}{2^n} = 2 + 4 = 6.
\]
Second solution:
Let
\[
S = \sum_1^\infty \frac{n^2}{2^n}
\]
Then
\begin{eqnarray*}
2S &=& \sum_1^\infty \frac{n^2}{2^{n-1}}\\
&=& \sum_0^\infty \frac{(n+1)^2}{2^n}\\
&=& S + 2T + \sum_0^\infty \frac{1}{2^n},
\end{eqnarray*}
where
\[
T = \sum_1^\infty \frac{n}{2^n}.
\]
Thus
\[
S = 2T + 2.
\]
Similarly,
\begin{eqnarray*}
2T &=& \sum_1^\infty \frac{n}{2^{n-1}}\\
&=& \sum_0^\infty \frac{n+1}{2^n}\\
&=& T + 2.
\end{eqnarray*}
It follows that
\[
T = 2, \quad S = 6.
\]
\end{answer}
\item
A stick is broken in random in 2 places
(the 2 break-points being chosen independently).
What is the probability that the 3 pieces form a triangle?
\begin{answer}
We may suppose the stick has length 1.
Let the 2 breaks occur at distance $x$ and $y$ along the stick.
We can represent this case by the point $(x,y)$
in the square $0 \le x,y \le 1$.
The probability will be given by the area in this square
corresponding to breaks which give pieces that can form a triangle.
The condition for this is
\[
x < 1/2, \quad y < 1/2, \quad 1 - x - y < 1/2.
\]
These inequalities define a triangle in the square,
of area 1/4.
Hence the probability is 1/4.
\end{answer}
\item
For which real numbers $x > 0$ is there a real number $y > x$ such that
\[
x^y = y^x\;?
\]
\begin{answer}
Taking logs (to base $e$),
\[
y \log x = x \log y.
\]
Thus
\[
\frac{\log x}{x} = \frac{\log y}{y}.
\]
Consider the function
\[
f(x) = \frac{\log x}{x}.
\]
Differentiating,
\[
f'(x) = \frac{1 - \log x}{x^2}.
\]
As $x \to 0+,\; f(x) \to -\infty$;
and as $x \to \infty,\; f(x) \to 0$.
Thus $f(x)$ increases from 0 to $e$,
where it takes the value $e^{-1}$,
and then decreases to 0.
Also $f(x) < 0$ for $0 < x < 1$,
and $f(x) > 0$ for $x > 1$
It follows that there is a $y > x$
with $f(y) = f(x)$
if and only if
\[
1 < x < e.
\]
\end{answer}
\item
Show that there are an infinity of natural numbers $n$
such that when the last digit of $n$ is moved to the beginning
(as eg $1234 \mapsto 4123$)
$n$ is multiplied by 3.
\begin{answer}
Let
\[
\begin{array}{c c c c c}
a_n & a_{n-1} & \dots & a_1 & a_0\\
&&&&3\\
\hline
a_0 & a_n & \dots & a_2 & a_1
\end{array}
\]
First solution:
it is clear that $a_0 \ge 3$,
since it appears as the first digit on the bottom.
Let us try $a_0 = 3$.
Then $a_1 = 9$, and our sum starts
\[
\begin{array}{c c c}
\dots & 9 & 3\\
&&3\\
\hline
\dots & & 9
\end{array}
\]
But then $a_2 = 7$:
\[
\begin{array}{c c c c}
\dots & 7 & 9 & 3\\
&&&3\\
\hline
\dots & & 7 & 9
\end{array}
\]
Continuing in this way,
we determine $a_3,a_4,\dots$, successively.
After a long time we find we have completed a cycle,
and are back where we started:
\[
\begin{array}{r}
1034482758620689655172413793\\
3\\
\hline
3103448275862068965517241379
\end{array}
\]
This number with 28 digits is a solution to our problem;
and we see that the cycle could be repeated any number of times
to give an infinity of solutions with $2\times28, 3\times28, \dots$ digits.
Second proof: Let
\[
n = 10b + a,
\]
where
\[
a = a_0, \quad b = 10^{n-1}a_n + 10^{n-2}a_{n-1} + \cdots + a_1.
\]
Then
\[
3 (10b + a) = 10^n a + b.
\]
Thus
\[
29a = (10^n - 3)b.
\]
Hence
\[
29 \divides 10^n - 3.
\]
On the other hand, if this is true
then it is easy to see that we get a solution
with
\[
a = \frac{10^n - 3}{29}, \quad b = 1.
\]
(We will also have solutions with $b = 2$ and $b = 3$.)
Thus we have to show that there are an infinity of solutions $n$ of
\[
10^n \equiv 3 \bmod 29.
\]
This follows by a little group theory,
applied to the multiplicative group $(\mathbb{Z}/29)^\times$
formed by the 28 non-zero remainders modulo 29.
By Lagrange's Theorem, the order of 10 in this group
divides 28, and is thus 2, 4, 7, 14 or 28.
But
\[
10^2 = 100 \equiv -12 \bmod 29,\quad 10^4 \equiv 12^2 = 144 \equiv 3 \bmod 29.
\]
Thus
\[
10^{28q + 4} \equiv 3 \bmod 29,
\]
giving an infinity of solutions to our problem.
\end{answer}
\item
What is the whole number part of
\[
1 +
\frac{1}{\sqrt{2}} +
\frac{1}{\sqrt{3}} + \cdots +
\frac{1}{\sqrt{1997}}\;?
\]
\begin{answer}
I was surprised no-one made a serious effort at this,
as the basic idea ---
to approximate the sum $\sum f(n)$,
where $f(x)$ is an increasing or decreasing function,
by the integral $\int f(x)\; dx$ ---
is quite often used.
It is the basis for example of the standard derivation
of Stirling's approximation to $n!$,
which on taking logs reduces to approximating $\sum \log n$.
In our case we can approximate
\[
S = \sum_{n=1}^N \frac{1}{\sqrt{n}}
\]
by
\[
\int \frac{1}{\sqrt{x}}\; dx = [2\sqrt{X}].
\]
Since $1/\sqrt{x}$ is decreasing,
\[
\int_1^{N+1} \frac{1}{\sqrt{x}}\; dx \le
\sum_{n=1}^N \frac{1}{\sqrt{n}} \le
1 + \int_1^N \frac{1}{\sqrt{x}}\; dx.
\]
But is that good enough?
Almost certainly not, since the 2 values differ by almost 1.
However, it cannot be out by more than 1.
Thus
\[
2(\sqrt{(1998)} - 1) < I < 1 + 2(\sqrt{(1997)} - 1).
\]
Now
\[
45^2 = 81 \times 25 = 2025, \quad 44^2 = 45^2 - 90 + 1 = 1936.
\]
Thus
\[
\sqrt{(1997)} \approx 44.7
\]
and so
\[
[S] = 87 \mbox{ or } 88.
\]
There are two ways of improving the estimate.
We could start further into the sum,
which would bring the bounds together;
for example
\[
\int_4^{N+1} \frac{1}{\sqrt{x}}\; dx \le
I -1 -\frac{1}{\sqrt{2}} - \frac{1}{\sqrt{3}} \le
\frac{1}{2} + \int_4^N \frac{1}{\sqrt{x}}\; dx.
\]
An alternative way --- which we shall follow ---
is to take the integral
\[
\int_{n-1/2}^{n+1/2} f(x)\; dx
\]
as an estimate for $f(n)$.
In our case this means taking
\[
2\sqrt{(n=1/2)} - 2\sqrt{(n-1/2)}
\]
as an approximation to $1/\sqrt{n}$.
Since the function $f(x) = 1/\sqrt{x}$ is concave,
it follows that
\begin{eqnarray*}
\frac{1}{\sqrt{n}} &<&
\int_{n-1/2}^{n+1/2} \frac{1}{\sqrt{x}}\;dx\\
&=& 2 \left(\sqrt{(n+1/2)} - \sqrt{(n-1/2)}\right).
\end{eqnarray*}
It follows that
\begin{eqnarray*}
S &>& 1 + 2(\sqrt{1997.5} - \sqrt{1.5})\\
&\approx& 1 + 2(44.7 - 1.2)\\
&\approx& 88.
\end{eqnarray*}
We conclude that
\[
[S] = 88.
\]
\end{answer}
\item Prove that
\[
n(n+1)(n+2) > \left(n + \frac89 \right)^3
\]
for any integer $n \ge 3$.
\begin{answer}
This is the easiest question on the paper,
even if it is stated in a slightly misleading way,
since the result has nothing to do with integers.
In effect it concerns the polynomial
\begin{eqnarray*}
f(x) &=& x(x+1)(x+2) - \left(x+\frac{8}{9}\right)^3\\
&=& \left(3 - \frac{2^3}{3}\right) x^2 +
\left(2 - \frac{2^6}{3^3}\right) x - \frac{2^9}{3^6}.
\end{eqnarray*}
This is a quadratic, and $f(x) \to \infty$ as $x \to -\infty$
and as $x \to \infty$.
It follows that $f(x)$ has a minimum where $f'(x) = 0$,
ie where
\[
\frac{2}{3} x = \frac{10}{27},
\]
that is,
\[
x = \frac{5}{9}.
\]
It follows that $f(x)$ is increasing for $x \ge 3$;
so it is sufficient to show that
\[
f(3) > 0,
\]
ie
\[
3 \cdot 4 \cdot 5 \ge \left(\frac{35}{9}\right)^3,
\]
ie
\[
3^7 \cdot 4 \ge 7^3 \cdot 5^2,
\]
ie
\[
8748 \ge 8575.
\]
\end{answer}
\item
Show that the determinant of the $3 \times 3$ matrix
\[
A = \begin{pmatrix}
\sin(x_1+y_1) & \sin(x_1+y_2) & \sin(x_1 + y_3)\\
\sin(x_2+y_1) & \sin(x_2+y_2) & \sin(x_2 + y_3)\\
\sin(x_3+y_1) & \sin(x_3+y_2) & \sin(x_3 + y_3)
\end{pmatrix}
\]
is zero for all real numbers $x_1, x_2, x_3, y_1, y_2, y_3$.
\begin{answer}
This problem can be solved by computing the determinant $\Delta$ directly.
But the following argument is quicker.
Consider $\Delta$ as a function of $x_1$.
Evidently
\[
\Delta = A \sin x_1 + B \cos x_1,
\]
where $A,B$ are functions of $x_2,x_3,y_1,y_2,y_3$.
The determinant vanishes if $x_1 = x_2$,
since the first 2 rows are then equal.
Similarly it vanishes if $x_1 = x_3$.
It follows that
\[
A \sin x_2 + B \cos x_2 = 0 = A \sin x_3 + B \cos x_3.
\]
This implies that either $A = B = 0$,
in which case $\Delta = 0$,
or else
\[
\sin x_2 \cos x_3 = \sin x_3 \cos x_2,
\]
ie
\[
\tan x_2 = \tan x_3,
\]
ie
\[
x_2 - x_3 = n\pi
\]
for some $n \in \mathbb{N}$.
We can write this
\[
x_2 \equiv x_3 \bmod \pi.
\]
Similarly, if $\Delta \neq 0$ then
\[
x_3 \equiv x_1 \bmod \pi,\quad x_1 \equiv x_2 \bmod \pi.
\]
It follows that 2 (at least) of $x_1,x_2,x_3$
differ by a multiple of $2\pi$, say
\[
x_1 \equiv x_2 \bmod 2\pi.
\]
But then the first 2 rows of $\Delta$ are equal,
and $\Delta$ vanishes.
\end{answer}
\item
Let
\[
A(m,n) = \frac{m!(2m+2n)!}{(2m)!n!(m+n)!}
\]
for non-negative integers $m$ and $n$.
Show that
\[
A(m,n) = 4A(m,n-1) + A(m-1,n)
\]
for $m \ge 1,\; n \ge 1$.
Hence or otherwise show that $A(m,n)$ is always an integer.
\begin{answer}
If $m,n \ge 1$,
\begin{eqnarray*}
4A(m,n-1) + A(m-1,n) &=&
4 \frac{m!(2m+2n-2)!}{(2m)!(n-1)!(m+n-1)!}
+ \frac{(m-1)!(2m+2n-2)!}{(2m-2)!n!(m+n-1)!}\\
&=& \frac{(m-1)!(2m+2n-2)!}{(2m)!n!(m+n-1)!}
\left(4mn + 2m(2m-1)\right)\\
&=& \frac{m!(2m+2n-2)!}{(2m)!n!(m+n-1)!}
\left(2(2n + 2m-1)\right)\\
&=& \frac{m!(2m+2n-1)!}{(2m)!n!(m+n-1)!} 2\\
&=& \frac{m!(2m+2n)!}{(2m)!n!(m+n)!}\\
&=& A(m,n).
\end{eqnarray*}
On the other hand,
\[
A(m,0) = \frac{m!(2m)!}{(2m)!m!} = 1,
\]
while
\[
A(0,n) = \frac{(2n)!}{n!n!} = C^{2n}_n,
\]
an integer.
But now it follows by induction on $d=m+n$ that $A(m,n)$ is an integer.
This is true when $d=0$, since $A(0,0)=1$ as we have seen.
Now suppose it true for all $m,n$ with $m+n=d$.
Then if $m+n=d+1$, the terms on the right in
the recursion formula $A(m,n) = 4A(m,n-1) + A(m-1,n)$
have already been proved integral,
and so $A(m,n)$ is also integral.
\end{answer}
\item
Let $P(x) = a_0 + a_1x + \cdots + a_n x^n$ be a real polynomial
of degree $n \geq 2$ such that
\[
0 < a_0 < - \sum_{k=1}^{[n/2]} \frac{1}{2k+1} a_{2k}
\]
(where $[n/2]$ denotes the integer part of $n/2$).
Prove that the equation $P(x) = 0$ has at least one solution
in the range $-1 < x < 1$.
\begin{answer}
The conditions can be written
\[
a_0 > 0, \quad a_0 + \frac{1}{3} \_3 + \frac{1}{5} \_5 + \cdots < 0.
\]
But
\[
\int_{-1}^1 P(x)\; dx =
2 \left(a_0 + \frac{1}{3} \_3 + \frac{1}{5} \_5 + \cdots\right).
\]
Thus
\[
f(0) > 0, \quad \int_{-1}^1 f(x)\; dx < 0.
\]
From the second condition, $f(x) < 0$ for some $x \in (-1,1)$.
Thus $f(x)$ changes sign in $(-1,1)$,
and so has a zero there.
\end{answer}
\item
Suppose $a_1, a_2, a_3, \dots $ is an infinite sequence of real
numbers satisfying $0 < a_n \leq 1$ for all $n$.
Let $S_n = a_1 + a_2 + \cdots + a_n$ and $T_n = S_1 + S_2 + \cdots + S_n$.
Show that
\[
\sum_{n=1}^\infty \frac{a_n}{T_n} < \infty.
\]
\end{enumerate}
\begin{answer}
The idea is to ``bunch together'' the $a_n$'s,
and treat each bunch as one element.
More precisely, if $\sum a_n$ converges then the result is immediate,
since $T_n \ge a_1$ and so
\[
\sum \frac{a_n}{T_n} \le \frac{1}{a_1} \sum a_n.
\]
We may assume therefore that
\[
\sum a_n = \infty.
\]
Now let us divide the $a_n$'s successively into bunches,
each with sum $\ge 1$ but $< 2$, say
\[
1 \le a_1 + a_2 + \cdots + a_{m_1} < 2, \quad
1 \le a_{m_1+1} + \cdots + a_{m_2} < 2,
\]
and so on.
Then
\[
S_{m_1} \ge 1,\; S_{m_2} \ge 2,\; S_{m_3} \ge 3, \dots
\]
and
\[
T_{m_1} \ge 1,\; T_{m_2} \ge 3,\; S_{m_3} \ge 6, \dots.
\]
In general
\[
S_{m_r} \ge r, \quad T_{m_r} \ge \frac{r(r+1)}{2}.
\]
But now
\begin{eqnarray*}
\frac{a_{m_r+1}}{T_{m_r+1}} + \cdots +
\frac{a_{m_{r+1}}}{T_{m_{r+1}}}
&\le& \frac{a_{m_r+1} + \cdots + a_{m_{r+1}}}{T_{m_r}}\\
&\le& \frac{2}{T_{m_r}}.
\end{eqnarray*}
Thus
\begin{eqnarray*}
\sum \frac{a_n}{T_n} &\le&
2 \left( \frac{1}{T_{m_1}} + \frac{1}{T_{m_2}} + \cdots \right)\\
&\le& \sum \frac{1}{r(r+1)} < \infty
\end{eqnarray*}
\end{answer}
\end{document}
\item Let $\omega(k)$ denote the number of distinct prime factors of
the positive integer $k$ and let $\gcd(i,n)$ denote the greatest
common divisor of the positive integers $i$ and $n$. Show that
\[
\sum_{i=1}^n 2^{\omega(\gcd(i,n))} = n \prod_{p|n} \left( 1 + \frac 1p
\right)
\]
(where the product is over all prime divisors $p$ of $n$).
\begin{answer}
\end{answer}