\documentclass[a4paper,12pt]{article}
\addtolength{\textheight}{20mm}
\addtolength{\topmargin}{-10mm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{ifpdf}
\ifpdf
\usepackage[pdftex]{graphicx}
\DeclareGraphicsRule{*}{mps}{*}{}
\else
\usepackage[dvips]{graphicx}
\fi
\usepackage{verbatim}
\ifx\answers\undefined
\newenvironment{answer}{\comment}{\endcomment}
\pagestyle{empty}
\else
\newenvironment{answer}{\textbf{Answer:}\em}{}
%\thispagestyle{turnover}
\fi
\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]
Irish Intervarsity Mathematics Competition 2007}
%\author{Timothy Murphy}
\author{Trinity College Dublin}
\date{11.00--14.00 Saturday 14\textsuperscript{th} April 2007}
\maketitle
\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
Does the number $2007^n$ end with the digits $2007$ for any $n > 1$?
\begin{answer}
The answer is Yes.
The multiplicative group $(\Z/10000)^\times$ has order
\begin{align*}
\phi(10000) &= \phi(2^4 5^4)\\
&= \phi(2^4) \phi(5^4)\\
&= 2^3 \cdot 4 \cdot 5^3\\
&= 4000.
\end{align*}
Hence, by Lagrange's Theorem,
\[
2007^{4000} \equiv 1 \bmod 10000,
\]
and so
\[
2007^n \equiv 2007 \bmod 1000
\]
if
\[
n = 2000m + 1.
\]
\end{answer}
\question
Does the number $2007^n$ begin with the digits $2007$ for any $n > 1$?
\begin{answer}
The answer is Yes.
The result follows if we can find $n$ such that
\begin{gather*}
2007^n = 10000000000\dots,\\
\intertext{ie}
2007^n = 10^m (1 + \epsilon),
\end{gather*}
where $0 < \epsilon < 0.00000000001$;
for then
\[
2007^{n+1} = 2007\dots,
\]
Taking logarithms to base 10,
and setting $\alpha =log_{10} 2007$,
\begin{gather*}
n \alpha = m + \log_{10}(1 + \epsilon),\\
\intertext{which will hold if}
0 \le [n \alpha] \le \epsilon,
\end{gather*}
We can find such an $n$ for any real number $\alpha$.
(This is Kronecker's Theorem.)
For if we consider the remainders $[n\alpha]$,
two must differ by less than $\epsilon$
(by the Pigeon Hole Principle), say
\begin{gather*}
0 \le [r\alpha] - [s\alpha] \le \epsilon,\\
\intertext{and so}
0 \le [n\alpha] \le \epsilon,
\end{gather*}
for $n = r - s$.
\end{answer}
\question
Three ants A,B,C start at the vertices of an equilateral triangle.
Ant A pursues B, B pursues C, and C pursues A
(each moving always in the direction of its target).
If the sides of the triangle are 1 metre in length,
and the ants move at 1mm/sec,
how long does it take them to meet at the centroid of the triangle?
\begin{answer}
The 3 ants will always lie at the vertices
of an equilateral triangle $A(t)B(t)C(t)$,
with the same centroid $O$.
The angle
\[
\angle O A(t) B(t) = \pi/6.
\]
Hence the component of the velocity of ant $A$ towards $O$ is
\[
v = 1 \cdot \cos (\pi/6) = \sqrt3/2.
\]
Initially
\[
AO = \frac{2}{3} \cdot \frac{\sqrt3}{2} \cdot 1000.
\]
Hence the time taken for the ants to reach $O$ is
\[
T = \frac{2000}{3} \text{ seconds}.
\]
\end{answer}
\question
Is the circle the only convex figure with the property
that every inscribed equilateral triangle is of the same size?
\begin{answer}
Hopefully a contestant will give a better proof than the following,
which I only sketch.
Suppose $ABC$ is one position of the triangle, with centroid $O$.
By considering neighbouring triangles,
we deduce that the angles between the tangents at $A,B,C$ and the lines $OA,OB,OC$ (respectively)
must be equal.
But then the centroid $G$ must be fixed, to first order;
and so it must be fixed.
\end{answer}
\question
A triangle $ABC$ is given.
\begin{enumerate}
\item
What point $P$ minimizes $AP + BP + CP$?
\item
What point $P$ minimizes $AP^2 + BP^2 + CP^2$?
\end{enumerate}
\begin{answer}
\begin{enumerate}
\item
The point $P$ minimizing $AP+BP+CP$ is the unique point $P$
such that
\[
A\hat{P}B = B\hat{P}C = C\hat{P}A = \frac{2\pi}{3} (= 120^\circ).
\]
(To construct this point, draw a circular arc on $AB$
such that $A\hat{P}B = 2\pi/3$ for all points $P$ on the arc;
and a similar circular arc on $BC$ such that $B\hat{P}C = 2\pi/3$
for all point on the arc.
Then the required point $P$ is the 2nd point---%
apart from the point $B$---%
where these 2 arcs meet.)
Suppose that $P$ minimizes $AP+BP+CP$.
Keep $CP$ fixed,
allowing $P$ to vary on a circle centred on $C$.
Draw the tangent $t$ to this circle at $P$.
A small variation $dP$ of $P$ along the tangent $t$
must leave $AP+BP$ unchanged, to the first order in $dP$.
It follows that $P$ must be the point on $t$ minimizing $AP+BP$.
But by the Law of Reflection,
this will occur when $AP$ and $BP$ make the same angle $\theta$ with $t$.
(To see this, let $B'$ be the reflection of $B$ in $t$.
Then
\[
AP + BP = AP + PB'
\]
will be minimized when $APB'$ is a straight line.)
But now
\[
A\hat{P}C = \theta + \frac{\pi}{2} = B\hat{P}C.
\]
Thus at the minimizing point,
\[
A\hat{P}C = B\hat{P}C.
\]
By the same argument with $B$ in place of $C$,
\[
A\hat{P}B = C\hat{P}B.
\]
Hence all 3 angles $A\hat{P}B, B\hat{P}C, C\hat{P}A$ are equal;
and since they add up to $2\pi$ ($360^\circ$),
each must be equal to $2\pi/3$ ($120^\circ$).
\item
The point minimizing $AP^2+BP^2+CP^2$ is the centroid $G$ of $ABC$.
For suppose $Q$ is the minimal point.
Let $A'$ be mid-point of $BC$.
Then
\[
AQ^2 + BQ^2 = 2A'Q^2 + 2A'B^2.
\]
So we have to minimize
\[
2A'Q^2 + QA^2.
\]
Evidently this will be minimal when $AQA'$ lie in a straight line.
Thus $Q$ must lie on the median $AA'$.
Similarly it must lie on the other 2 medians.
Hence it lies at the centroid $G$ of $ABC$.
\end{enumerate}
\end{answer}
\question
Does there exist a map $f:\Z \to \Z$
(where $\Z$ is the set of integers) such that
\[
f(f(x)) = x^2
\]
for all $x \in \Z$?
\begin{answer}
The answer is Yes.
Note that if we set
\[
s(x) = x^2
\]
then
\begin{gather*}
f^2 = s \implies sf = fs,\\
\intertext{ie}
f(x^2) = f(x)^2.
\end{gather*}
In particular,
\[
f(0)^2 = f(0),\; f(1)^2 = f(1).
\]
It follows that either
\[
f(0) = 0, f(1) = 1 \text{ or } f(0) = 1,f(1) = 0.
\]
More generally, if
\[
f(a) = b
\]
then
\[
f(b) = a^2,\; f(a^2) = b^2,\; f(b^2) = a^3, \dots.
\]
Let us divide the integers $n > 1$ into chains
\[
C(r) = \{r, r^2, r^4, r^8, \dots\}.
\]
Thus $\N\setminus\{0,1\}$ is partitioned into
\[
C(2),C(3),C(5),C(6),\dots,
\]
with a chain $C(r)$ starting with each non-square $r$.
Divide the chains into pairs $(C(2),C(3)),\;(C(5),C(6)),\dots$
Suppose $C(r),C(s)$ is one pair.
Then we can set
\[
f(r^i) = s^i,\; f(s^i) = r^{i+1}.
\]
We can extend the definition to $\Z$ by setting
\[
f(-n) = f(n).
\]
\end{answer}
\question
Suppose $x,y$ are positive integers.
Show that if
\[
\frac{x^2 + y^2}{xy + 1}
\]
is an integer then it is a perfect square.
\begin{answer}
Let
\[
\frac{x^2 + y^2}{xy + 1} = m.
\]
Then
\[
x^2 - mxy + y^2 - m = 0.
\]
We can regard this as a quadratic equation for $x$, with $y$ fixed.
Since one root $x$ is an integer, so is the other root $x'$, say;
for
\[
x + x' = my.
\]
Also
\[
xx' = y^2 - m,
\]
from which it follows that
\[
x > y \implies x' < y.
\]
But we can also regard the equation as a quadratic equation for $y$;
and in the same way this gives a second solution $(x,y')$ for which
\[
y > x \implies y' < x.
\]
Thus we get a sequence of solutions, say
\[
(x,y) = (x_0,y_0),\; (x_1,y_0),\; (x_1,y_1), \dots
\]
with decreasing $xy$.
This must end with $x = 0$ or $y = 0$,
in which case it is clear that $m$ is a square.
\end{answer}
\question
Show that every rational number $x \in (0,1)$
can be represented uniquely in the form
\[
x = \frac{a_1}{1!} +\frac{a_2}{2!}+...+\frac{a_k}{k!},
\]
where $a_1,\dots,a_k$ are integers with $0 \le a_i < i$ for $1 \le i \le k$.
\begin{answer}
Notice that $a_1 = 0$, since $0 \le 1_1 < 1$.
Let
\[
a_2 = [2x],
\]
and let
\[
x_2 = 2x - a_2.
\]
Then
\[
0 \le a_2 < 2,
\]
and
\[
0 \le x_2 < 1.
\]
Let
\[
a_3 = [3x_2],
\]
and let
\[
x_3 = 3x_2 - a_3.
\]
Then
\[
0 \le a_3 < 3,
\]
and
\[
0 \le x_3 < 1.
\]
Continuing in this way, the process will end if and when
\[
x_{k+1} = 0.
\]
It is easy to see that this will happen when
\[
k!x \in \N,
\]
which must be true for some $k$.
\end{answer}
\question
What is the greatest number of parts into which the plane can be divided
by $n$ straight lines?
\begin{answer}
One line divides the plane into 2 parts;
2 lines divides it into 4 (assuming they are not parallel).
Suppose $n$ lines divide the plane into $N(n)$ parts.
If now we add a new line then it will cut the existing lines
in at most $n$ points,
and there will in fact be exactly $n$ new points
if the line is not parallel to any of the existing lines
and does not go through any of the existing intersection points.
This will create $n+1$ new regions. Hence
\[
N(n+1) = N(n) + n + 1.
\]
It follows that
\begin{align*}
N(n) &= 2 + 2 + 3 + \cdots + n\\
&= 1 + \frac{1}{2} n(n+1)\\
&= \frac{n^2 + n + 2}{2}.
\end{align*}
\end{answer}
\question
Three points $A,B,C$ are chosen at random on the circumference of a circle.
What is the probability that the centre of the circle
lies inside $ABC$?
\begin{answer}
Suppose the angle subtended by $AB$ at the centre is $\theta$.
Then $C$ must lie on an arc subtending the same angle at the centre.
(In fact $C$ must lie in the reflection of the arc $AB$ in the centre.
The probability of this is $\theta/2\pi$.
Thus the probability that the centre lies in $ABC$ is
\begin{align*}
p &= \frac{1}{\pi} \int_0^{\pi} \frac{\theta}{2\pi}\; d\theta\\
&= \frac{1}{2\pi^2} \left[ \frac{\theta^2}{2} \right]_0^\pi\\
&= \frac{1}{4}.
\end{align*}
\end{answer}
\question
For which real numbers $x$ does the sequence
\[
x,\; \sin x,\; \sin(\sin x),\; \sin(\sin(\sin x)), \dots
\]
converge?
\begin{answer}
If the sequence converges to c then
\[
\sin c = c,
\]
to which the only solution is $c = 0$.
So if the sequence converges, it converges to 0.
Suppose $\sin x \ge 0$.
Then
\[
0 \le \sin x \le 1.
\]
But
\[
\sin x \le x
\]
for $0 \le x \pi/2$.
It follows that the sequence is decreasing if $x \ge 0$,
and so is convergent.
Similarly if $\sin x < 0$ then
\[
\frac{\sin x}{x} < 1;
\]
so the sequence is increasing, and again is convergent.
\end{answer}
\question
A circular hole of diameter 1 is drilled
through the centre of a sphere of radius 1.
What is the surface area of the drilled sphere?
\begin{answer}
Let
\[
\theta = A\hat{O}P,
\]
where $O$ is the centre of the sphere, $A$ is the point on the sphere
at the centre of the hole, and $P$ is a point on the sphere on the edge of the hole.
Then
\[
\sin\theta = \frac{1}{2},
\]
and so
\[
\theta = \frac{\pi}{6}.
\]
The length of the cylinder removed is
\[
2\cos\theta = \sqrt{3};
\]
so its surface area is
\[
2\pi rh = \sqrt{3}\pi.
\]
Recall a famous theorem from the Ancient Greeks,
that the area of a section of a sphere cut out by two parallel planes
is equal to the area cut out
on the circumscribed cylinder perpendicular to the planes.
It follows from this that the surface area of each cap removed from the sphere is
\[
2\pi(1 - \cos\theta) = (2 - \sqrt{3})\pi.
\]
The area of the sphere is $4\pi$.
Hence the surface area of the drilled sphere is
\[
4\pi - 2(2-\sqrt{3})\pi + \sqrt{3}\pi = 3 \sqrt{3} \pi.
\]
\end{answer}
\end{enumerate}
\end{document}