\documentclass[a4paper,12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{verbatim}
\usepackage{ifpdf}
\ifpdf
\usepackage[pdftex]{graphicx}
\DeclareGraphicsRule{*}{mps}{*}{}
\else
\usepackage[dvips]{graphicx}
\fi
\ifx\answers\undefined
\newenvironment{answer}{\comment}{\endcomment}
\else
\newenvironment{answer}{\textbf{Answer:}\em}{}
\fi
\let\divides=\mid
\def\notdivides{\not\,\mid}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\lcm}{\operatorname{lcm}}
%\addtolength{\topmargin}{-2.5cm}
\addtolength{\textheight}{18pt}
\pagestyle{empty}
\begin{document}
\title{%
%\includegraphics[width=4cm]{tcdarms.ps}\\[5mm]
Irish Intervarsity Mathematics Competition 2003}
\author{University College Dublin}
%\date{9.30--12.30 Saturday 3\textsuperscript{rd} March 2001}
\date{Time allowed: Three hours}
\maketitle
\thispagestyle{empty}
%\enlargethispage*{13mm}
%\begin{center}
%\sl
%Calculators and Tables may be used.
%\end{center}
\begin{enumerate}
\item
Let
\[
f(x) = x^3 + Ax^2 + Bx + C,
\]
where $A,B,C$ are integers.
Suppose the roots of $f(x) = 0$
(in the field of complex numbers)
are $\alpha,\beta,\gamma$.
Prove that if
\[
\abs{\alpha} = \abs{\beta} = \abs{\gamma} = 1
\]
then
\[
f(x) \mid (x^{12} - 1)^3.
\]
\begin{answer}
One or three of the roots must be real.
But if $\alpha \in \R$ and $\abs{\alpha} = 1$
then $\alpha = \pm 1$.
If the three roots are $\pm 1$
then the result follows, since
$\pm 1$ are roots of $x^{12} - 1$.
So we may assume that one root, say $\alpha$, is $\pm 1$,
and the other two are complex conjugates $e^{\pm \theta}$.
Since $\alpha + \beta + \gamma = -A$ is an integer,
so is $\beta + \gamma = 2\cos\theta$.
Thus either $\beta + \gamma = 0$,
in which case $\beta,\gamma = \pm i$;
or else $\beta + \gamma = \pm1$,
in which case $\beta,\gamma = \omega, \omega^2 \text{ or } -\omega, -\omega^2$,
where $\omega = e^{2\pi i/3}$.
Since $\pm i, \pm\omega, \pm\omega^2$ are all roots of $x^{12} - 1$,
the result follows.
\end{answer}
\item
Let $n$ be a positive integer.
Prove that when written in decimal form (in base 10),
\[
\left( \sqrt{17} + 4 \right)^{2n+1}
\]
has at least $n$ zeroes following the decimal point.
\begin{answer}
Let
\[
x = \sqrt{17} + 4,\;
y = \sqrt{17} - 4.
\]
Then
\begin{gather*}
xy = 1;\\
\intertext{while}
x^{2n+1} - y^{2n+1} \in \Z,
\end{gather*}
since the terms involving odd powers of $\sqrt{17}$ cancel out.
It follows that the part of $x^{2n+1}$ after the decimal point
is $y^{2n+1}$.
This gives the result, since $x > 8$ and so
\[
y^{2n+1} < 64^{-n} < 10^{-n}.
\]
\end{answer}
\item
Find all integers $n$ for which
\[
n^4 - 16n^3 + 86n^2 - 176n + 169
\]
is the square of an integer.
\begin{answer}
Let the given expression be $f(n)$,
and let
\[
g(n,c) = n^2 - 8n + c,
\]
for integers $c$.
Then
\[
g(n,c)^2 = n^4 - 16n^3 + (64 + 2c)n^2 - 16cn + c^2.
\]
Thus
\begin{align*}
f(n) &= g(n,11)^2 + 48,\\
&= g(n,12)^2 - 2n^2 + 16n + 25,\\
&= g(n,13)^2 - 4n^2 + 32n.
\end{align*}
It follows that if $f(n) = m^2$
then $m > g(n,11)$.
But $m \le g(n,13) = g(n,11) + 2$ unless
\begin{gather*}
4n^2 \le 32n,\\
\intertext{ie}
0 \le n \le 8.
\end{gather*}
If $n = 0$ or $n = 8$ then $f(n) = g(n,13)^2$.
So we need only consider $1 \le n \le 7$.
We have
\[
g(n,11) = (n - 4)^2 - 5.
\]
Thus
\begin{align*}
f(1) &= g(1,11)^2 + 48 = 4^2 + 48 = 64 = 8^2,\\
f(2) &= g(2,11)^2 + 48 = (-1)^2 + 48 = 49 = 7^2,\\
f(3) &= g(3,11)^2 + 48 = (-4)^2 + 48 = 64 = 8^2,\\
f(4) &= g(4,11)^2 + 48 = (-5)^2 + 48 = 73,\\
f(5) &= g(5,11)^2 + 48 = (-4)^2 + 48 = 64 = 8^2,\\
f(6) &= g(6,11)^2 + 48 = (-1)^2 + 48 = 49 = 7^2,\\
f(7) &= g(7,11)^2 + 48 = 4^2 + 48 = 64 = 8^2.
\end{align*}
Finally, if $f(n)$ is a square for $n$ outside the range $[0,8]$
then $f(n) = g(n,12)^2$,
in which case
\[
2n^2 - 16n + 25 = 0,
\]
which is impossible since the first two terms are even
while the last is odd.
We conclude that $f(n)$ is a square if and only if
$n \in \{0,1,2,3,5,6,7,8\}$.
\end{answer}
\item
Consider the sequence
\[
1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,\dots
\]
in which each positive integer $k$ is repeated $k$ times.
Prove that its $n$\textsuperscript{th} term is
\[
\left[ \frac{1 + \sqrt{8n - 7}}{2} \right],
\]
where $[x]$ denotes the greatest integer not exceeding $x$.
\begin{answer}
Let the $n$th number in the sequence be $a_n$.
The first $n$ for which $a_n = k$ is
\[
n = 1 + 2 + \cdots + (k-1) + 1 = \frac{k(k-1)}{2} + 1 = \frac{k^2 - k + 2}{2}.
\]
The function
\[
f(x) = \frac{x^2 - x + 2}{2}
\]
is monotone increasing for $x \ge 1$.
Thus
\[
n = f(x)
\]
for a unique $x = x(n) \ge 1$;
and $a_n = k$ if
\begin{gather*}
k \le x(n) < k+1,\\
\intertext{ie}
a_n = [x(n)].
\end{gather*}
But $x(n)$ is the solution of
\[
x^2 - x + 2 = 2n.
\]
Thus
\begin{align*}
a_n
&= \left[ \frac{1 + \sqrt{1 - 4(2 - 2n)}}{2} \right]\\
&= \left[ \frac{1 + \sqrt{8n - 7}}{2} \right].
\end{align*}
\end{answer}
\item
Let $ABC$ be an acute angled triangle
and $a,b,c$ the lengths of the sides $BC, CA, AB$, respectively.
Let $P$ be a point inside $ABC$,
and let $x,y,z$ be the lengths $PA, PB, PC$, respectively.
Prove that
\[
(x + y + z)^2 \ge \frac{a^2 + b^2 + c^2}{2}.
\]
\begin{answer}
We have
\[
x + y > c,\;
y + z > b,\;
z + x > a.
\]
Thus
\begin{align*}
(y+z)^2 + (z+x)^2 + (x+y)^2
&= 2(x^2 + y^2 + z^2 + yz + zx + xy)\\
&> a^2 + b^2 + c^2.
\end{align*}
Hence
\begin{align*}
2(x + y + z)^2
&= 2(x^2 + y^2 + z^2 + 2(yz + zx + xy))\\
&> a^2 + b^2 + c^2,
\end{align*}
ie
\[
(x + y + z)^2 > (a^2 + b^2 + c^2)/2.
\]
\end{answer}
\item Let $ABCD$ be a convex quadrilateral with the lengths $AB = AC,\; AD = CD$ and angles $B\hat{A}C = 20^\circ,\; A\hat{D}C = 100^\circ$.
Prove that the lengths $AB = BC + CD$.
\begin{answer}
Since the triangle $ABC$ is isosceles,
\[
A\hat{B}C = A\hat{C}B = 80^\circ.
\]
Similarly, since the triangle $DAC$ is isosceles,
\[
D\hat{A}C = D\hat{C}A = 40^\circ.
\]
From the triangle $ABC$,
\[
\frac{BC}{\sin 20} = \frac{AB}{\sin 80}.
\]
Thus
\[
BC = \frac{\sin 20}{\sin 80} AB.
\]
Similarly, from the triangle $ACD$,
\[
\frac{AC}{\sin 100} = \frac{CD}{\sin 40}.
\]
Thus
\[
CD = \frac{\sin 40}{\sin 100} AC = \frac{sin 40}{sin 80} AB.
\]
Accordingly, we have to show that
\begin{gather*}
\frac{\sin 20}{\sin 80} + \frac{\sin 40}{\sin 80} = 1,\\
\intertext{ie}
\sin 20 + \sin 40 = \sin 80.
\end{gather*}
But
\begin{align*}
\sin 20 + \sin 40
&= \sin(30 - 10) + \sin(30 + 10)\\
&= 2 \sin 30 \cos 10\\
&= \cos 10\\
&= \sin 80,
\end{align*}
as required.
\end{answer}
\item
Let $S$ be a set of 30 positive integers less than 100.
Prove that there exists a nonempty subset $T$ of $S$
such that the product of the elements of $T$
is the square of an integer.
\begin{answer}
If we take the numbers $\{1,2,\dots,100\}$ modulo squares
we obtain an abelian group $A$,
in which eg $\bar{3} \cdot \bar{6} = \bar{2}$,
The elements of $A$ are all of order 2,
and $A$ is generated by the elements $\bar{p}$
defined by primes $p$.
There are 25 primes $p \le 100$, so
\[
A = C_2^{25}.
\]
We can regard $A$ as a 25-dimensional vector space
over the 2-element field $\F_2$.
If $s_1,\dots,s_r \in S$ then
\[
\bar{s_1} + \cdots + \bar{s_r} = 0 \iff s_1\cdots s_r \text{ is a square}.
\]
The 30 elements
\[
\{\bar{s}: s \in S\}
\]
must be linearly dependent in the vector space $A$,
ie there is some relation
\[
\bar{s_1} + \cdots + \bar{s_r} = 0
\]
But then the product
\[
s_1 \cdots s_r
\]
is a square.
\end{answer}
\item
Let
\[
f(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + e,
\]
where $a,b,c,d,e$ are integers,
and suppose that $f(x) = 0$ has no integer roots.
Suppose also that $f(x) = 0$ has roots $\alpha,\beta$
(in the field of complex numbers)
with $\alpha + \beta$ an integer.
Show that $\alpha\beta$ is an integer.
\begin{answer}
Suppose
\[
\alpha + \beta = n.
\]
Consider the factorisation of $f(x)$
into irreducible polynomials over the rationals $\Q$.
We know that any such factorisation
is in fact a factorisation into monic polynomials over $\Z$.
Since $f(x)$ has no integral root
it cannot have a factor of degree 1.
Thus either $f(x)$ is irreducible,
or else it factorises into 2 irreducible polynomials,
of degrees 2 and 3.
Suppose first that $f(x)$ is irreducible.
Then $\beta = n - \alpha$ is a root of $f(n-x)$,
as well as of $f(x)$.
It follows that
\[
f(n-x) = - f(x).
\]
Thus from the coefficients of $x^4$,
\begin{gather*}
5n + a = - a,\\
\intertext{ie}
5n = 2a.
\end{gather*}
In particular, $n$ is even.
The roots of $f(x)$ must divide into pairs $\{\theta, n - \theta\}$
with at least one root satisfying $\theta = n - \theta$.
But that is impossible, since $f(x)$ has no integral root.
It follows that $f(x)$ cannot be irreducible.
Thus $f(x)$ factorises, say
\[
f(x) = g(x) h(x),
\]
where $\alpha$ is a root of $g(x)$.
As before, $\beta = n - \alpha$ is a root of $g(n-x)$,
as well as of $f(x)$.
Thus $g(n-x)$ is (to within a factor $\pm1$)
either $g(x)$ or $h(x)$.
Since $\deg g(x) \neq \deg h(x)$,
\[
g(n-x) = \pm g(x).
\]
Suppose first that $g(x)$ is cubic,
say
\[
g(x) = x^3 + Ax^2 + Bx + C.
\]
If the third root is $\gamma$ then
\[
\alpha + \beta + \gamma = -A \implies \gamma = -(A + n),
\]
giving an integral root of $f(x)$,
contrary to assumption.
Hence $g(x)$ is quadratic, say
\[
g(x) = x^2 + Bx + C.
\]
Then $\alpha\beta = C$ is integral,
as required.
\end{answer}
\item
Let $x$ be a real number with $0 < x < 1$.
Let $\{a_n\}$ be a sequence of positive real numbers.
Prove that the inequality
\[
1 + xa_n \ge x^2 a_{n-1}
\]
holds for infinitely many positive integers $n$.
\begin{answer}
Suppose to the contrary that
\[
a_n < x a_{n-1} - \frac{1}{x}
\]
for all sufficiently large $n$, say $n \ge N$.
This implies in particular that $a_n$ is decreasing for $n \ge N$.
Hence $a_n$ converges to a limit $\ell \ge 0$,
satisfying
\[
\ell \le x \ell - \frac{1}{x}.
\]
But this implies that
\[
(1-x) \ell \le - \frac{1}{x} < 0 \implies \ell < 0,
\]
which is impossible since $a_n \ge 0$.
\end{answer}
\item
Find the least positive integer $n$ for which
\[
m^n - 1 \text{ is divisible by } 10^{2003}
\]
for all integers $m$ with greatest common divisor $\gcd(m,10) = 1$.
\begin{answer}
We have to find $n$ such that
\begin{gather*}
m^n \equiv 1 \bmod 2^{2003}\\
\intertext{and}
m^n \equiv 1 \bmod 5^{2003}.
\end{gather*}
The group $(\Z/2^n)^\times$,
ie the group of odd numbers modulo $2^n$, contains
\[
\phi(2^n) = 2^{n-1}
\]
elements.
Thus the order of any odd number in this group
is $2^r$ for some $r$.
It is not hard to show that if $n \ge 2$,
\[
(\Z/2^n)^\times \cong \Z/(2) \times \Z/(2^{n-2}).
\]
Thus every odd number has order dividing $2^{n-2}$,
and some odd numbers have this order.
The group $(\Z/5^n)^\times$,
ie the group of numbers coprime to 5 modulo $5^n$, contains
\[
\phi(5^n) = 4 \cdot 5^{n-1}
\]
elements.
is $2^r$ for some $r$.
Again, it is not hard to see that this group is cyclic.
Thus every number coprime to 5
has order dividing $4 \cdot 5^{n-1}$,
and some such numbers have this order.
It follows that the least number $n$ such that all $m$ coprime to 10
satisfy
\[
m^n \equiv 1 \bmod 10^{2003}
\]
is
\begin{align*}
n &= \lcm(2^{2000}, 4 \cdot 5^{2001})\\
&= 2^{2000} 5^{2001}\\
&= 5 \cdot 10^{2000}.
\end{align*}
\end{answer}
\end{enumerate}
\end{document}