%%
%% This is a LaTeX document
%%

\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amssymb}

%%
%% The margins I prefer
%%

\textwidth      = 15cm
\textheight     = 23cm
\oddsidemargin  = 0.46cm
\evensidemargin = 0.46cm
\topmargin      = -1cm
\parskip        = 6pt
\parindent      = 20pt
\pagestyle{empty}

%%
%% German letters (doubled)
%%

\def\aa{{\mathfrak a}} 
\def\bb{{\mathfrak b}} 
\def\cc{{\mathfrak c}} 
\def\dd{{\mathfrak d}} 
\def\ee{{\mathfrak e}} 
\def\ff{{\mathfrak f}} 
\def\gg{{\mathfrak g}} 
\def\hh{{\mathfrak h}} 
\def\ii{{\mathfrak i}} 
\def\jj{{\mathfrak j}} 
\def\kk{{\mathfrak k}} 
\def\ll{{\mathfrak l}} 
\def\mm{{\mathfrak m}} 
\def\nn{{\mathfrak n}} 
\def\oo{{\mathfrak o}} 
\def\pp{{\mathfrak p}} 
\def\qq{{\mathfrak q}} 
\def\rr{{\mathfrak r}} 
\def\ss{{\mathfrak s}} 
\def\tt{{\mathfrak t}} 
\def\uu{{\mathfrak u}} 
\def\vv{{\mathfrak v}} 
\def\ww{{\mathfrak w}} 
\def\xx{{\mathfrak x}} 
\def\yy{{\mathfrak y}} 
\def\zz{{\mathfrak z}} 

\def\AA{{\mathfrak A}}
\def\BB{{\mathfrak B}}
\def\CC{{\mathfrak C}}
\def\DD{{\mathfrak D}}
\def\EE{{\mathfrak E}}
\def\FF{{\mathfrak F}}
\def\GG{{\mathfrak G}}
\def\HH{{\mathfrak H}}
\def\II{{\mathfrak I}}
\def\JJ{{\mathfrak J}}
\def\KK{{\mathfrak K}}
\def\LL{{\mathfrak L}}
\def\MM{{\mathfrak M}}
\def\NN{{\mathfrak N}}
\def\OO{{\mathfrak O}}
\def\PP{{\mathfrak P}}
\def\QQ{{\mathfrak Q}}
\def\RR{{\mathfrak R}}
\def\SS{{\mathfrak S}}
\def\TT{{\mathfrak T}}
\def\UU{{\mathfrak U}}
\def\VV{{\mathfrak V}}
\def\WW{{\mathfrak W}}
\def\XX{{\mathfrak X}}
\def\YY{{\mathfrak Y}}
\def\ZZ{{\mathfrak Z}}

%%
%% Blackboard Bold (triple)
%%

\def\AAA{{\mathbb A}} 
\def\BBB{{\mathbb B}} 
\def\CCC{{\mathbb C}} 
\def\DDD{{\mathbb D}} 
\def\EEE{{\mathbb E}} 
\def\FFF{{\mathbb F}} 
\def\GGG{{\mathbb G}} 
\def\HHH{{\mathbb H}} 
\def\III{{\mathbb I}} 
\def\JJJ{{\mathbb J}} 
\def\KKK{{\mathbb K}}
\def\LLL{{\mathbb L}} 
\def\MMM{{\mathbb M}} 
\def\NNN{{\mathbb N}} 
\def\OOO{{\mathbb O}} 
\def\PPP{{\mathbb P}} 
\def\QQQ{{\mathbb Q}} 
\def\RRR{{\mathbb R}} 
\def\SSS{{\mathbb S}} 
\def\TTT{{\mathbb T}} 
\def\UUU{{\mathbb U}} 
\def\VVV{{\mathbb V}} 
\def\WWW{{\mathbb W}} 
\def\XXX{{\mathbb X}} 
\def\YYY{{\mathbb Y}} 
\def\ZZZ{{\mathbb Z}} 

%%
%% Caligraphic letters (single)
%%

\def\A{{\cal A}} 
\def\B{{\cal B}} 
\def\C{{\cal C}} 
\def\D{{\cal D}} 
\def\E{{\cal E}} 
\def\F{{\cal F}} 
\def\G{{\cal G}} 
\def\H{{\cal H}} 
\def\I{{\cal I}} 
\def\J{{\cal J}}
\def\K{{\cal K}}
\def\L{{\cal L}} 
\def\M{{\cal M}} 
\def\N{{\cal N}} 
\def\O{{\cal O}} 
\def\P{{\cal P}} 
\def\Q{{\cal Q}} 
\def\R{{\cal R}} 
\def\S{{\cal S}} 
\def\T{{\cal T}} 
\def\U{{\cal U}} 
\def\V{{\cal V}} 
\def\W{{\cal W}} 
\def\X{{\cal X}} 
\def\Y{{\cal Y}} 
\def\Z{{\cal Z}} 

%%
%% Parentheses
%%

\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\left\langle}
\def\>{\right\rangle}

%%
%% Renamings
%%

\def\of{\circ}
\def\union{\cup}
\def\intersect{\cap}
\def\d{\partial}

%%
%% Extras
%%

\def\smallmatrix#1#2#3#4{%
	\left({#1\atop #3}\;{#2\atop #4}\right)}
\def\mathllap#1{\mathchoice
{\llap{$\displaystyle #1$}}%
{\llap{$\textstyle #1$}}%
{\llap{$\scriptstyle #1$}}%
{\llap{$\scriptscriptstyle #1$}}}
\def\set#1#2{\left\{\,#1\mathllap{\phantom{#2}}\mathrel{}\right|\left.#2\mathllap{\phantom{#1}}\,\right\}}

\def\sgn{\mathop{\rm sgn}\nolimits}
\def\mod{\hbox{ mod }}

%%
%% Proof stuff
%%

\def\qed{\hfill\(\Box\)\smallskip}
\def\proof{{\bf Proof.\ \ }}

%%
%% Theorem types
%%

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}

%%
%% MAIN DOCUMENT
%%

\begin{document}
\begin{center}
\Large {\bf BMOC Mentoring Scheme}\\
\large Advanced Level -- Sheet 2\\
Possible Solutions\\
\end{center}
\vskip 40pt
\begin{enumerate}
\item {\it Show that there are no non-zero integer solutions to the
equation}
$$x^2+y^2+z^2 = 2xyz$$

Looking at the equation modulo $2$ we see that either $x$,$y$ and $z$
are all even or two are odd and one even.  In the second case, looking
at the equation modulo $4$ shows this isn't possible.  So, we can
write $x=2x'$,$y=2y'$ and $z=2z'$.  This gives a new equation
$$x'^2 + y'^2 + z'^2 = 4x'y'z'$$
Even though the $2$ has become a $4$ the same reasoning as before
works (it isn't too hard to see that it will work for any even number
appearing on the right hand side).  So, we can remove another factor
of two.  Hence, if there is a non-zero solution then we will be able
to repeatedly remove factors of $2$ from it.  This will eventually
lead to non-integer solutions which is a contradiction.  So, there are
no non-zero solutions.  This idea of repeatedly removing factors is
known as {\bf Fermat's method of infinite descent}.
\item {\it Find infinitely many integer solutions to the equation}
$$x^2+y^2+z^2 = 3xyz$$

Note that the number on the right hand side is odd, so the reasoning
for question 1 will not work.  There is an obvious solution:
$x=y=z=1$.  Because we have to find infinitely many solutions we
really have only two choices: find some easy to describe values of
$x$,$y$ and $z$ which give a solution or find a way to get new
solutions from old ones.  We use the second method.

Suppose that $x$,$y$ and $z$ satisfy $x^2+y^2+z^2 = 3xyz$.  Let us fix
two of the variables, say $y$ and $z$.  This gives a quadratic
equations that $x$ satisfies: $x^2 - (3yz)x + (y^2+z^2) = 0$.  Call
the other solution to the quadratic $x'$.  Because $x+x' = 3yz$ we see
that $x'$ is an integer.  So, if $(x,y,z)$ is a solution we have seen
that $(3yz-x,y,z)$ is a solution too (you can check this by
multiplying out if you are skeptical!).  The only remaining thing to
check is that this method gives infinitely many solutions.

If we always fix the bigger two numbers then it is easy to see that
$3yz-x$ is strictly bigger than $x$.  Hence, the minimum of $x$, $y$
and $z$ can always be increased using this method and so we can
generate infinitely many solutions.
\item {\it Let $M$ lie on $AB$ between $A$ and $B$, and construct
semicircles on diameters $AM$, $MB$, $AB$, all on the same side of the
line $AB$. Let the inscribed circle of these three semicircles be
$S$. $S$ is tangent to semicircle $AM$ at $b$, to semicircle $MB$ at
$a$, and to semicircle $AB$ at $m$. Construct three circles orthogonal
to $AB$ passing through $a$ and $b$, $a$ and $m$, $b$ and $m$,
respectively. Show that the angles between pairs of these circles (at
$a$, $b$ and $m$) are equal.}

As there are lots of circles and lines around, trying inversion seems
like a good idea.  If we invert about $A$ then we get a (horizontal)
line $BM$ with two perpendicular lines, one through $B$ and one
through $M$.  On $BM$ is drawn a semicircle.  $S$ is constructed to be
tangent to the semicircle and two vertical lines.  Points $m$, $a$ and
$b$ are given as before.  If we invert about $B$ then we get an
identical diagram apart from the order of $m$, $a$ and $b$.  Similarly
if we invert about $M$.  Because inversion preserves angles the angles
at $m$, $a$ and $b$ must be the same.
\item
\begin{enumerate}
\item {\it Show that $3^n$ divides $2^{3^n} + 1$ for all $n$.}

Let's do this by induction.  For $n=1$ it is true because $3$ divides
$8+1$.  Now, suppose that for some $n$ we know $3^n$ divides
$2^{3^n}+1$.  Looking at this modulo $3^{n+1}$ we see
$$2^{3^n} \equiv -1, 3^n-1\hbox{ or }2\cdot 3^n-1 \mod 3^{n+1}$$
Raising both sides to the power $3$ (using $(x-1)^3 = x^3 - 3x^2 + 3x
- 1$ on the right hand side) we see
$$2^{3^{n+1}} \equiv -1 \mod 3^{n+1}$$
This is what we needed to show to finish the induction.

\item {\it Find an $n$ which is not a power of $3$ such that $n$ divides
$2^n+1$.}

Let us hope that things are not too far from a power of $3$.  So, we
will first try to see if there is a solution with $n = 3p$ ($p$ a
prime not equal to $3$).  Substituting this in gives two congruences
$$\(2^3\)^p + 1 \equiv 0 \mod 3 \qquad \(2^p\)^3 + 1 \equiv 0 \mod p$$
The first is true for any odd $p$ and the second shows (after using
Fermat's little theorem) that $p$ divides $2^3 + 1 = 9$.
Unfortunately this isn't possible as $p$ is not $3$.  So, now we try
$n = 9p$.  The first congruence is again satisfied for odd $p$ and the
second shows that $p$ divides $2^9 + 1 = 513$.  Hence $p=19$ will do
and so $n=9*19 = 171$ will do.
\end{enumerate}
\item {\it Show that the distance from the circumcentre to the orthocentre
of a triangle is less than three times the circumradius.}

We do this question with vectors.  WLOG we can assume that the
circumcentre is at the origin and the circumradius is $1$.  The three
vertices of the triangle are now represented by three unit vectors
${\mathbf a}$, ${\mathbf b}$ and ${\mathbf c}$.  A little
experimentation then gives (you can write down the equations for the
orthocentre, intelligently guess, ...) the orthocentre as being at
$\mathbf{a} + \mathbf{b}+\mathbf{c}$.  The inequality is now obvious.

\item {\it If $x$,$y$,$z \ge 0$ and $x+y+z=1$ prove that
$$4(xy+yz+zx) - 9xyz \le 1$$
When does equality occur?}

{\bf Method 1.}  After a little fiddling the following (almost)
factorisation of the inequality can be found:
$$(2x-1)(2y-1)(2z-1) \ge -xyz$$
As the RHS is negative the inequality trivially holds when the LHS is
positive.  It is easy to see that this is when exactly one of
$x$,$y$,$z$ is at least ${1 \over 2}$.  So, assume that $0\le x,y,z
\le {1\over 2}$.  Setting $u=1-2x$, $v=1-2y$, $w=1-2z$ we get the
following
$$8uvw \le (1-u)(1-v)(1-w)\quad\hbox{given that}\quad 0\le u,v,w \le
1, u+w+v=1$$
Expanding this gives
$$9uvw \le (1-u-v-w) + (uv+vw+wu) = uv+vw+wu$$
Provided that $uvw\ne 0$ we can divide by $uvw$ and use the {\bf
arithmetic--harmonic mean inequality} to finish.  If $uvw=0$ then WLOG
we can assume $u=0$.  This gives $0 \le vw$ which is clearly true.

Putting all this together we see that equality holds if $x=y=z={1\over
3}$ or $x=y=0, z=1$ (and cyclic permutations thereof).

{\bf Method 2.}  From the factorisation
$$(2x-1)(2y-1)(2z-1) \ge -xyz$$
we can substitute in the boundary equation $x+y+z = 1$ to obtain
$$(x+y-z)(y+z-x)(z+x-y) \le xyz$$
As before, we can assume everything in sight is positive (otherwise
the inequality is trivial).  We can now use AM--GM on the pairs of
terms on the LHS to prove the inequality.
\end{enumerate}
\end{document}