\documentclass[a4paper,12pt]{article}
%\documentclass[a4paper,14pt]{article}
%\usepackage{extsizes}
%\addtolength{\textheight}{20mm}
%\addtolength{\topmargin}{-10mm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage[dvips]{graphicx}
\usepackage{graphicx}
\usepackage{verbatim}
\newenvironment{question}{\item}{}
\ifx\answers\undefined
\newenvironment{answer}{\comment}{\endcomment}
\pagestyle{empty}
\else
\newenvironment{answer}{\textbf{Answer:}\em}{}
\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 2008}
%\author{Timothy Murphy}
\author{National University of Ireland, Maynooth}
\date{11.00--14.00 Saturday 19\textsuperscript{th} April 2008}
\maketitle
%\ifanswers
%\thispagestyle{empty}
%\else
%\thispagestyle{turnover}
%\fi
\begin{enumerate}
\begin{question}
Consider a regular $n$-gon inscribed inside a circle of radius 1.
Each of the vertices of the $n$-gon lies on the circle.
Draw a line between each pair of the $n$ vertices.
Prove that the sum of the squares of the lengths of these lines in $n^2$.
\end{question}
\begin{answer}
Let $\omega = e^{2\pi/n}$.
Then we can take the vertices of the $n$-gon to be
\[
\omega^i \quad (0 \le i \le n-1).
\]
The square of the length of the line joining $\omega^i,\omega^j$ is
\begin{align*}
\abs{\omega^i - \omega^j}^2 &= (\omega^i - \omega^j)(\omega^{-i} - \omega^{-j})\\
&= 2 - (\omega^{i-j} + \omega^{j-i}).
\end{align*}
If we sum over $0 \le i \le n-1,\; 0 \le j \le n-1$ we will get
twice the required sum (as the line joining $\omega^i,\omega^j$ will occur twice).
Also $\omega^{i-j}$ will take each of the values $1,\omega,\dots,\omega^{n-1}$ $n$ times.
Hence the sum will be
\[
2n^2 - 2n(1 + \omega + \dots + \omega^{n-1}) = 2n^2.
\]
We conclude that the required sum is $n^2$.
\end{answer}
\begin{question}
There are 63 coins, all identical in appearance,
and all identical in weight except that one coin is slightly heavier
than the others.
\end{question}
\begin{answer}
Number the coins 1--63.
Write each number to base 4, $n=abc$.
For the first weighing, divide the coins according to the first digit:
15 coins starting with 0 (as there is no coin 000),
and 16 starting with 1,2 and 3.
Weigh the last 3 sets against one another.
That will determine the first digit of the heavy coin.
Do the same with second and third digits.
That will determine all the digits of the the heavy coin.
\end{answer}
\begin{question}
Given positive numbers $a_1 \ge a_2 \ge a_3,\;b_1 \ge b_2 \ge b_3$ and $c_1 \ge c_2 \ge c_3$,
and three permutations $\alpha,\beta,\gamma$ of the set $\{1,2,3\}$, prove that
\[
a_1 b_1 c_1 + a_2 b_2 c_2 + a_3 b_3 c_3 \ge
a_{\alpha(1)} b_{\beta(1)} c_{\gamma(1)} +
a_{\alpha(2)} b_{\beta(2)} c_{\gamma(2)} +
a_{\alpha(3)} b_{\beta(3)} c_{\gamma(3)}.
\]
\end{question}
\begin{answer}
We may suppose (for simplicity) that
\[
a_1 > a_2 > a_3,\;b_1 > b_2 > b_3,\;c_1 > c_2 > c_3,
\]
since the given result follows from this by continuity.
We may also suppose
(re-arranging the terms on the right if necessary)
that $\alpha$ is the identity permutation,
so that the right hand reads
\[
a_1 b_{\beta(1)} c_{\gamma(1)} +
a_2 b_{\beta(2)} c_{\gamma(2)} +
a_3 b_{\beta(3)} c_{\gamma(3)}.
\]
Let us suppose $\beta,\gamma$ chosen
so that the right-hand side is maximized.
Suppose $i < j$;
and suppose
\[
\beta(i) < \beta(j) \text{ but } \gamma(i) > \gamma(j).
\]
Then swapping $c_{\gamma(i)} \text{ with } c_{\gamma(j)}$
will increase the sum by
\[
(c_{\gamma(j)} - c_{\gamma(i)}) (a_i b_{\beta(i)} - a_j b_{\beta(j)}).
\]
Thus
\[
\beta(i) < \beta(j) \implies \gamma(i) < \gamma(j).
\]
Similarly
\[
\gamma(i) < \gamma(j) \implies \beta(i) < \beta(j).
\]
On the other hand, if $i < j$ but
\[
\beta(i) > \beta(j) \text{ and } \gamma(i) > \gamma(j),
\]
then the sum will be increased if we swap
$b_{\gamma(i)} c_{\gamma(i)} \text{ with } b_{\gamma(j)} c_{\gamma(j)}$.
We conclude that
\[
i < j \implies
\beta(i) < \beta(j) \text{ and } \gamma(i) < \gamma(j).
\]
Thus $\beta$ and $\gamma$ are both the identity permutation,
and the result follows.
\end{answer}
\begin{question}
Let $F(n)$ denote the usual Fibonacci sequence,
which is defined by the properties $F(1) = F(2) = 1$
and $F(n+2) = F(n+1) + F(n)$ for $n > 0$.
Let $(a(n))$ denote the \emph{iterated Fibonacci sequence},
which is given by the equation $a(n) = F(F(n))$ for each $n > 0$.
Prove that $a(n)$ is a multiple of 144
whenever $a(n)$ is a multiple of 14.
\end{question}
\begin{answer}
Note that for any modulus $m$, $F(n) \bmod m$ will be a recurring sequence.
Taking $m = 2$ we have
\[
1,1,0,1,1,0,1,\dots.
\]
Thus
\[
2 \mid F(n) \iff 3 \mid n.
\]
Taking $m = 3$ we have
\[
1,1,2,0,2,2,1,0,1,1,2,0,\dots.
\]
Thus
\[
3 \mid F(n) \iff 4 \mid n.
\]
We deduce that
\[
2 \mid a(n) \iff 4 \mid n.
\]
Taking $m = 7$ we have
\[
1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,\dots.
\]
Thus
\[
7 \mid F(n) \iff 8 \mid n.
\]
Taking $m = 8$ we have
\[
1,1,2,3,5,0,5,5,2,7,1,0,1,1,\dots
\]
Thus
\[
8 \mid F(n) \iff 6 \mid n.
\]
We deduce that
\[
7 \mid a(n) \iff 6 \mid n.
\]
Hence
\[
14 \mid a(n) \iff 12 \mid n.
\]
So we have to show that
\[
12 \mid n \implies 2^43^2 \mid a(n).
\]
Taking $m = 16$ we have
\[
1,1,2,3,5,8,13,5,2,7,9,0,9,9,\dots.
\]
We see now that once we get a 0,
we will get the same sequence multiplied (in this case) by 9,
and then by $9^2 = 1 \bmod 16$.
Hence
\[
16 \mid F(n) \iff 12 \mid n.
\]
Taking $m = 9$ we have
\[
1,1,2,3,5,8,4,3,7,1,8,0,8,8,\dots
\]
Again, we will get the same sequence multiplied by 8,
and then by $8^2 = 1 \bmod 9$.
Hence
\[
9 \mid F(n) \iff 12 \mid n.
\]
We conclude that
\[
14 \mid a(n) \implies 12 \mid n \implies 144 \mid a(n).
\]
\end{answer}
\begin{question}
Take a positive integer $N$ that ends in the digit 2.
Move the 2 to the beginning of the number,
and subtract 1 to get a new number, $M$.
For example, if $N = 52$ then we move the 2 to the beginning of $N$ to get 25,
and then subtract 1 to obtain $M = 24$.
What is the smallest value of $N$ such that $M = 2N$?
\end{question}
\begin{answer}
Suppose $N$ has $r$ digits.
We have
\[
N = 10a + 2,
\]
where $a$ is the number formed by removing the last digit.
Then
\[
M = 2 \cdot 10^r + a.
\]
Hence
\begin{gather*}
2 \cdot 10^r + a - 1 = 2(10a + 2),\\
\intertext{ie}
19a = 2\cdot10^r - 5.
\end{gather*}
It follows that
\[
2 \cdot 10^r \equiv 5 \bmod 19.
\]
Multiplying by 10, this is equivalent to
\[
10^r \equiv 12 \bmod 19.
\]
Now
\[
10,10^2,10^3,\dots \equiv 10,5,12,\dots \bmod 19.
\]
We conclude that the smallest possible value of $r$ is 3.
(The general value is $3 \bmod 18$.)
Taking $r = 3$, we have
\begin{gather*}
19a = 2 \cdot 10^3 - 5,\\
\intertext{ie}
a = 1995/19 = 105.
\end{gather*}
We conclude that the smallest solution is
\[
N = 1052,\; N = 2105.
\]
\end{answer}
\begin{question}
For $n = 1,2,\dots$ let
\[
a_n = n(n+1),\quad b_n = n + 1.
\]
What is the value of the convergent sequence
\[
\frac{a_1}{b_1},\;
\frac{a_1}{b_1 + \frac{a_2}{b_2}},\;
\frac{a_1}{b_1 + \frac{a_2}{b_2 + \frac{a_3}{b_3}}}, \dots ?
\]
\end{question}
\begin{answer}
Let the $n$th convergent
(expressed as a fraction without reducing to simple terms)
be $p_n/q_n$.
Thus
\begin{align*}
p_1 &= a_1,\; q_1 = b_1,\\
p_2 &= a_1b_2,\; q_2 = b_1b_2 + a_2.
\end{align*}
It follows by induction, on substituting $b_n + a_{n+1}/b_{n+1}$ for $b_n$, that
\begin{align*}
p_n &= b_n p_{n-1} + a_n p_{n-2},\\
q_n &= b_n q_{n-1} + a_n q_{n-2}.
\end{align*}
With these formulae, we can even go back to
\begin{align*}
p_0 &= 0,\; q_0 = 1,\\
p_{-1} &= 1,\; q_{-1} = 0.
\end{align*}
In our case we see that the sequences $p_n,q_n$
both satisfy the recurrence relation
\[
x_n = (n+1) x_{n-1} + n(n+1) x_{n-2}.
\]
Dividing by $(n+1)!$ this can be written
\[
\frac{x_n}{(n+1)!} = \frac{x_{n-1}}{n!} + \frac{x_{n-2}}{(n-1)!}.
\]
Thus if we set
\[
z_n = \frac{x_n}{(n+1)!},
\]
then $z_n$ satisfies the linear recurrence relation
\[
z_n = z_{n-1} + z_{n-2}
\]
(like the Fibonnaci numbers).
The solution to this is
\[
z_n = A \lambda^n + B \mu^n,
\]
where $\lambda,\mu$ are the roots of
\[
t^2 - t - 1 = 0,
\]
ie
\[
\lambda, \mu = (1 \pm \sqrt5)/2.
\]
For $z_n=p_n/(n+1)!$, taking $n = 0,-1$
and noting that $\lambda\mu = -1$,
\[
A + B = 0,\; - A\mu - B\lambda = 1.
\]
Thus
\begin{gather*}
A(\lambda - \mu) = 1,\\
\intertext{ie}
A = 1/\sqrt5,\; B = -1/\sqrt5.
\end{gather*}
Similarly, for $z_n=q_n/(n+1)!$, taking $n = 0,-1$ gives
\[
A + B = 1,\; - A\mu - B\lambda = 0.
\]
Thus
\begin{gather*}
A(1 - \mu^2) = 1,\\
\intertext{ie}
-A\mu = 1,\\
\intertext{ie}
A = \lambda,\; B = \mu.
\end{gather*}
So finally, since $\lambda^n \to \infty,\; \mu^n \to 0$,
and the factors $1/(n+1)!$ cancel out,
\begin{align*}
\frac{p_n}{q_n} &\to \frac{1/\sqrt5}{\lambda}\\
&= -\mu/\sqrt5\\
&= (5 - \sqrt5)/10.
\end{align*}
\end{answer}
\begin{question}
Let a triangle $ABC$ have sides of length
$\abs{AB} = 5, \abs{BC} = 6, \abs{CA} = 7$,
and let the lengths of the perpendiculars from a point $P$ inside the triangle
to the sides $AB,\;BC \text{ and } CA$ be $x,\;y \text{ and } z$, respectively.
Find the minimum value of the sum $x^2 + y^2 + z^2$.
\end{question}
\begin{answer}
If $\Delta$ is the area of the triangle then
\begin{align*}
\Delta^2 &= s(s-a)(s-b)(s-c)\\
&= 9 \cdot 4 \cdot 3 \cdot 2\\
&= 2^3 3^3.
\end{align*}
Hence
\[
5x + 6y + 7z = 2\Delta = 12 \sqrt6.
\]
Thus we have to minimize
\[
f(x,y,z) = x^2 + y^2 + z^2
\]
subject to the constraint
\[
g(x,y,z) = 5x + 6y + 7z - 2\Delta = 0.
\]
Applying the method of Lagrange multipliers,
we have to solve
\[
2x = 5\lambda,\;
2y = 6\lambda,\;
2z = 7\lambda,\;
g(x,y,z) = 0.
\]
These give
\begin{gather*}
5^2\lambda/2 + 6^2\lambda/2 + 7^2\lambda/2 = 24 \sqrt6.\\
\intertext{ie}
110 \lambda = 48 \sqrt6.\\
\intertext{ie}
\lambda = \frac{24}{55}\sqrt6.\\
\end{gather*}
Thus the minimal point is
\[
P = (x,y,z) = \frac{\lambda}{2}(5,6,7),
\]
and the minimal value of $x^2 + y^2 + z^2$ is
\begin{align*}
\frac{\lambda^2}{4}(5^2 + 6^2 + 7^2) &= \frac{24^2 \cdot 6 \cdot 110}{55^2 \cdot 6 \cdot 4}\\
&= \frac{288}{55}.
\end{align*}
\end{answer}
\begin{question}
Let $(a_n)$ be a sequence of non-negative integers such that
\[
a_{n+2} = \binom{a_{n+1}}{a_n},
\]
where
\[
\binom{m}{k} =
\begin{cases}
\frac{m!}{k! (m-k)!} \text{ if $m \ge k$}\\
0 \text{ otherwise}
\end{cases}
\]
\end{question}
\begin{answer}
If $a_n = 0$ for some $n$ then the sequence continues
\[
\begin{cases}
a_{n+1},1,1,\dots \text{ if $a_{n+1} \le 1$}\\
a_{n+1},1,0,0,1,1,\dots \text{ if $a_{n+1} \ge 2$}
\end{cases}
\]
So we may assume that $a_n \neq 0$.
If $a_n = 1$ for some $n$ then the sequence continues
\[
\begin{cases}
a_{n+1},a_{n+1},1,1,\dots \text{ if $a_{n+1} \le 1$}\\
a_{n+1},a_{n+1},1,0,\dots \text{ if $a_{n+1} \ge 2$}
\end{cases}
\]
So we may assume that $a_n \neq 1$.
In particular $2 \le a_1$ and $a_2 > a_1$.
If $a_2 = a_1 + 1$ then the sequence continues
\[
a_1,a_2,a_2,1,0,\dots
\]
So we may assume that $2 \le a_1 \le a_2 - 2$.
Suppose this is so.
Recall that the binomial coefficients $\binom{n}{r}$
increase as $r$ runs from 0 to $[n/2]$ and then decrease until $r = n$.
Hence
\[
a_3 = \binom{a_2}{a_1} \ge \binom{a_2}{2} = \frac{1}{2} a_2(a_2-1) \ge \frac{3}{2}a_2
\]
since $a_2 \ge 4$.
We show by induction that
\[
a_{n+1} \ge \frac{3}{2} a_n
\]
for all $n$.
If this is true for $r \le n$ then certainly $2 \le a_r \le a_{r+1} - 2$ for $\le n$.
Hence
\[
a_{n+2} = \binom{a_{n+1}}{a_n} \ge \binom{a_{n+1}}{2} \ge \frac{3}{2}a_{n+1}.
\]
Hence the sequence tends to infinity.
\end{answer}
\begin{question}
Show that there does not exist a differentiable function $f:\R \to \R$
which satisfies the following equation for all real values $x$:
\[
f'(x) \ge 1 + \abs{f(x)}^2.
\]
\end{question}
\begin{answer}
Evidently $f(x)$ is monotone increasing
from $-\infty$ to $+\infty$ (since $f'(x) \ge 1$ for all $x$).
Hence
\[
f(c) = 0
\]
for some $c$, and
\[
x > c \implies f(x) > 0.
\]
Let $g(x)$ be the function defined for $x \ge c$
by $g(c) = 0$ and
\[
g'(x) = \frac{1}{2}(1 + g(x)^2).
\]
Thus
\[
\frac{g'(x)}{1 + g(x)^2} = 2.
\]
Integrating,
\begin{gather*}
\tan^{-1}(g(x)) = 2x + C,\\
\intertext{ie}
g(x) = tan(2x+C).
\end{gather*}
Since $g(c) = 0$ we can take $2c + C = 0$, ie
\[
g(x) = tan(2(x-c)).
\]
Hence $g(x) \to \infty$ as $x \to c + \pi$.
But it is easy to see that
\[
g(x) \le f(x)
\]
for $x \ge c$.
This is certainly true for $x$ slightly $> c$,
since $g'(c) = 1/2 < f'(c)$.
Suppose the two graphs cross at $x_0 > c$.
On applying the Mean Value Theorem to $f(x) - g(x)$ on $[c,x_0]$
it would follow that $f'(\xi) = g'(\xi)$ for some $\xi \in (c,x_0)$,
which we have seen is not possible.
We conclude that $f(x) \to \infty$ for some $x < c + \pi$,
contrary to hypothesis.
\end{answer}
\begin{question}
In a room there are 2008 bulbs and 2008 buttons,
and both are numbered from 1 to 2008.
For each integer $1 \le i \le 2008$,
pressing Button $i$ changes the on or off status of Bulb $i$
and one other bulb (the same bulb each time).
Assuming that all bulbs are initially off,
prove that by pressing the appropriate combination of buttons
we can turn on at least 1340 of them simultaneously on.
Prove also that if the effects of the buttons are chosen appropriately,
1340 is the largest number of bulbs that can be simultaneously on.
\end{question}
\begin{answer}
Let $S = \{1,2,\dots,2008\}$,
and let
\[
f:S \to S
\]
be the map defined by the property
that pressing Switch $i$ turns on Bulbs $i$ and $f(i)$.
We do the last part of the question first.
Partition $S$ into 669 triplets, leaving one element over.
For each triplet $\{a,b,c\}$ let
\[
f(a) = b,\; f(b) = c,\; f(c) = a.
\]
Then it is clear that whichever of the switches $a,b,c$ is or are on,
at most 2 of the bulbs will be on.
This ignores the singlet $\{d\}$.
Set $f(d) = e$.
Then it is clear that all the bulbs in the triplet containing $e$
can be on at the same time.
Thus the maximum number of bulbs on is
\[
668 \cdot 2 + 3 + 1 = 1340.
\]
Turning to the first part of the question,
let
\[
S_r = f^r(S)
\]
(where eg $f^2(S) = f(f(S))$).
Then
\[
S = S_0 \supset S_1 \supset S_2 \supset \cdots.
\]
The sequence must become stationary: say
\[
S_n = S_{n+1} = \cdots.
\]
Let
\[
T_r = S_r \setminus S_{r+1}.
\]
Then
\[
f(T_r) = T_{r+1}.
\]
Now turn on the switches in $T_0, T_2, T_4, \dots$
and leave off those in $T_1, T_3, T_5, \dots$.
Suppose $i \in T_{2r+1}$.
Consider the set
\[
X(i) = \{j \in T_{2r}: f(j) = i\}.
\]
Then $X(i) \neq \emptyset$.
Suppose there are $m$ numbers in $X(i)$.
Then bulb $i$ will be off or on according as $m$ is even or odd.
Now consider the union
\[
Y(i) = X(i) \cup \{i\},
\]
associating the switches in $X(i)$ with switch $i$.
In this set there are $m+1$ bulbs out of $m+1$ on if $m$ is odd,
and $m$ out of $m+1$ on if $m$ is even.
In all cases the proportion is $\ge 2/3$.
Hence the overall number of bulbs on is
\[
\ge \frac{2}{3} \times 2008 = 1339\frac{2}{3}.
\]
Hence at least 1340 bulbs are on.
\end{answer}
\end{enumerate}
\end{document}