\documentclass[a4paper,12pt]{article}
%\addtolength{\textheight}{46mm}
%\addtolength{\topmargin}{-23mm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[dvips]{graphicx}
\usepackage{verbatim}
\newenvironment{answer}{\textbf{Answer:}\em}{}
%\newenvironment{answer}{\comment}{\endcomment}
\let\divides=\mid
\def\notdivides{\not\,\mid}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\norm}[1]{\|#1\|}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\lcm}{\mathop{lcm}}
\makeatletter
\def\ps@turnover{\def\@oddhead{}\def\@oddfoot{\hfil\emph{More questions overleaf!}}
\def\@evenhead{}\let\@evenfoot\@oddfoot}
\makeatother
\let\question=\item
\begin{document}
\title{
\vspace*{-3cm}
\mbox{\includegraphics[width=4cm]{tcdarms}}\\[5mm]
DUMS Intervarsity Team Selection Test}
%\author{Timothy Murphy}
\author{Easter 2009}
\date{Time allowed: 90 minutes}
\maketitle
\thispagestyle{turnover}
%\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}
\smallskip
\begin{enumerate}
\question %1
What are the last 3 digits of $2009^{2009}$?
\begin{answer}
It is sufficient to determine
\[
9^{2009} \bmod 1000,
\]
since $a \equiv b \mod n \implies a^n \equiv b^n \mod n$.
By the binomial theorem,
\begin{align*}
9^{2009} &= (10 - 1)^{2009}\\
&\equiv (-1)^{2009} + 2009\cdot 10 \cdot (-1)^{2008} + \binom{2009}{2} 10^2 (-1)^{2007} \bmod 1000\\
&\equiv -1 + 90 - \frac{9\cdot8}{2} 100 \bmod 1000\\
&\equiv -1 + 90 - 600 \bmod 1000\\
&\equiv 489 \bmod 1000,
\end{align*}
ie the last 3 digits are 489.
\end{answer}
\question %2
What is the first digit of $1001^{1001}$?
\begin{answer}
We know that
\[
(1 + \frac{1}{n})^n \to e
\]
as $n \to \infty$.
The first digit of $1001^{1001}$ is the same as the first digit
of $(1 + \frac{1}{1000})^{1001}$.
But
\[
(1 + \frac{1}{1000})^{1000} \approx e = 2.6\dots.
\]
The additional factor $(1 + 1/1000)$ will not affect the first digit.
Thus the first digit is 2.
[And the first 2 digits are 26.
If asked to justify the argument above
we would go back to the proof that $(1+1/n)^n \to e$,
by taking logarithms, with
\[
\log (1+1/n) = 1/n - 1/2n^2 + 1/3n^3 - \cdots,
\]
so that
\[
\log (1+1/n)^n = 1 + O(1/n).
\]
It would be a straightforward matter to verify
that the error involved in omitting the terms after the first
is not sufficient to alter the first, or even the first 2, digits.]
\end{answer}
\question %3
Show that, in any collection of 52 distinct positive integers,
there are two distinct numbers whose sum or difference is divisible by 100.
\begin{answer}
If 0 and/or 50 are among the 52 integers, ignore them.
Let the remaining integers be $x_1,\dots,x_{50}$.
Consider the 101 integers
\[
\{50,\pm x_1, \dots, \pm x_{50}\}.
\]
There are 100 residue-classes $\bmod 100$.
Hence (by the pigeon-hole principle)
two of these must lie in the same residue-class, ie
\[
x_i \equiv x_j \bmod 100 \text{ or } x_i \equiv -x_j \mod 100.
\]
In the first case $x_i - x_j$ is divisible by 100;
in the seond case $x_i + x_j$ is divisible by 100.
\end{answer}
\question %4
Six positive integers are written on the faces of a cube.
At each vertex, the numbers on the 3 adjacent faces are multiplied.
The sum of these 8 products is 105.
What is the sum of the 6 numbers on the faces?
\begin{answer}
Choose two opposite faces.
Let the numbers on these be $a,b$.
Let the numbers on the remaining 4 faces
(going round the cube) be $cdef$.
Then the sum of the products involving the first face is
\[
a(cd + de + ef + fc) = a(c+e)(d+f).
\]
Similarly, the sum of the products involving the second face is
\[
b(cd + de + ef + fc) = a(c+e)(d+f).
\]
Hence the sum of all the products is
\[
(a+b)(c+e)(d+f).
\]
But
\[
105 = 3 \cdot 5 \cdot 7.
\]
Hence
\[
a+b,c+e,d+f = 3,5,7
\]
in some order.
We conclude that
\[
a + b + c + d + e + f = 3 + 5 + 7 = 15.
\]
\end{answer}
\question %5
Find all integer solutions of
\[
8xy + 5x + 3y = 0.
\]
\begin{answer}
[There are various approaches to this very simple problem.]
Multiplying the equation by 8,
\begin{gather*}
64xy + 40x + 24y = 0,\\
\intertext{ie}
(8x + 3)(8y + 5) = 15.
\end{gather*}
Thus
\[
(8x + 3, 8y + 5) = (1,15),(-1,-15),(15,1),(-15,-1),(3,5),(-3,-5),(5,3),(-5,-3).
\]
Each of these determines $x,y$.
The only cases giving integer values to $x,y$ are
\begin{align*}
(8x + 3, 8y + 5) = (3,5) &\implies (x,y) = (0,0)\\
(8x + 3, 8y + 5) = (-5,-3) &\implies (x,y) = (-1,-1).
\end{align*}
\end{answer}
\question %6
Suppose Ireland and Wales are equally strong at rugby.
Which is more likely, that Ireland wins 3 games out of 4,
or that Wales wins 5 games out of 8?
(Ignore the possibility of draws.)
\begin{answer}
The probability of Ireland winning 3 games out of 4 is
\[
\binom{4}{3} (\frac{1}{2})^4 = \frac{1}{4}.
\]
The probability of Wales winning 5 games out of 8 is
\[
\binom{8}{5} (\frac{1}{2})^8 = \frac{7}{32}.
\]
Thus it is more likely that Ireland wins 3 games out of 4.
\end{answer}
\question %7
Given a point $P$ and a circle $\Gamma$,
suppose a line $l$ through $P$ cuts $\Gamma$ in $X,Y$.
Show that $PX.PY$ is independent of $l$.
\begin{answer}
Suppose $PXY,PX'Y'$ are two such lines.
Consider the triangles $PXY',PYX'$.
Recall that the angle $AXB$ subtended by a chord $AB$ in a circle is constant.
Hence the angles $\angle PXY' = \angle X'XY$
and $\angle PYX' = \angle Y'YX$
are equal.
The two triangles also have the angle $\angle XPX'$ in common.
Hence the two triangles have the same angles,
and so are similar.
It follows that
\begin{gather*}
\frac{PX}{PY'} = \frac{PY}{PX'}\\
\intertext{ie}
PX \cdot PX' = PY \cdot PY'.
\end{gather*}
\end{answer}
\question %8
Suppose $p(x)$ is a polynomial with integer coefficients
such that
\[
p(0) = p(1) = 2009.
\]
Show that $p(x)$ has no integer zeros.
\begin{answer}
Consider the polynomial
\[
f(x) = p(x) - 2009.
\]
We have
\[
f(0) = f(1) = 0.
\]
Hence
\[
f(x) = x (x - 1) q(x)
\]
for some polynomial $q(x)$,
ie
\[
p(x) = x(x-1)q(x) + 2009.
\]
If
\[
p(n) = 0
\]
then
\[
n(n-1) \mid 2009.
\]
But
\[
2009 = 7 \cdot 287.
\]
Thus
\[
n \in \{\pm 1, \pm 7, \pm 287, \pm 2009\}.
\]
But in none of these cases does $(n-1) \mid 2009$.
\end{answer}
\question %9
Suppose the sequence $x_n$ satisfies
\[
\lim_{n \to \infty} (x_{n+1} - x_n) = 0.
\]
Show that
\[
\lim_{n \to \infty} \frac{x_n}{n} = 0.
\]
\begin{answer}
Given $\epsilon > 0$ we can find $N$ such that
\[
\abs{x_{n+1} - x_n} < \epsilon/2 \text{ if } n \ge N.
\]
If $x \ge N$ then
\[
x_n = (x_n - x_{n-1}) + (x_{n-1} - x_{n-2}) + \cdots + (x_{N+1} - x_N) + x_N.
\]
Hence
\begin{align*}
\abs{x_n}
&\le \abs{x_n - x_{n-1}} + \abs{x_{n-1} - x_{n-2}} + \cdots + \abs{x_{N+1} - x_N} + \abs{x_N}\\
&\le (n - N)\epsilon/2 + \abs{x_N}
\end{align*}
Thus
\[
\abs{a_n/n} \le \epsilon/2 + \abs{x_N/n}.
\]
Now choose $M$ such that
\[
\abs{x_N/n} < \epsilon/2
\]
if $n \ge M$.
Then
\[
\abs{x_n/n} < \epsilon
\]
if $n \ge \max(M,N)$.
Hence
\[
x_n/n \to 0.
\]
\end{answer}
\question %10
Does there exist a differentiable function $f: \R \to \R$,
not identically zero,
such that
\[
f'(x) = f(x+1)
\]
for all $x$?
\begin{answer}
Let us try
\[
f(x) = e^{cx}.
\]
This will satisfy the given equation if
\begin{gather*}
c e^{cx} = e^{c(x+1)} = e^c e^{cx},\\
\intertext{ie if}
c = e^c.
\end{gather*}
Now it is easy to see that $c \neq e^c$ for any real number $c$;
for if $c < 0$ then $e^c > 0$,
while if $c > 0$ then $e^c > c$.
However, we may be able to find a complex number $c$ such that
\[
e^c = c;
\]
and then
\[
f(x) = \Re(e^{cx}) = \cos(cx)
\]
will satisfy the given relation.
Thus there is a solution provided the function
\[
f(z) = e^z - z
\]
has a zero.
\end{answer}
\end{enumerate}
\end{document}
z_{n+1} = z_n + d_n
where
f(z_n + d_n) = f(z_n) + d_n f'(z_n) + ...
d_n = -f(z_n)/f'(z_n)
= - (e^{z_n} - z_n)/(e^{z_n} - 1)