\documentclass{article}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{epsf}
\title{February 2002 Exam 1 Solutions}
\date{A four hour examination. Iranian Olympaid 2001.}
\author{}
\begin{document}
\maketitle

\begin{enumerate}
\item Consider $n \times n$ matrices. A set of matrix positions
containing exactly one position from each row and column 
of such a matrix is called a {\em generalized diagonal}. Let $A$ be
an $n \times n$ matrix all entries of which are either 0 or 1. 
Suppose that $A$ has exactly one generalized diagonal with the
property that all its entries are 1. Prove that by permuting 
rows and permuting columns one can obtain
an upper triangular matrix from $A$ (i.e. all entries below the leading
diagonal are 0).\newline
\noindent{\bf Solution} {\em Permuting either row or column entries
allows us to assume that the leading diagonal consists of 1's, i.e.
$a_{ii} = 1$ for all $i$ where $1 \leq i \leq n$. Now construct
a digraph (directed graph) $\Gamma$ with $n$ vertices $v_1, v_2, \ldots, v_n$ 
in $\mbox{Vert}(\Gamma)$ and join $v_i$ to $v_j$ by a 
directed edge iff $a_{ij} = 1$.
We claim that this graph does not have any directed cycle, for if
it did then 
\[ a_{i_1i_2} = a_{i_2i_3} = \cdots = a_{i_mi_1} = 1\]
and we obtain a second generalized diagonal (in addition to the 
leading diagonal) by using the positions of these entries
together with diagonal positions other than $(i_t,i_t)$ as $t$ 
ranges between $1$ and $m$. Since $V$ has no directed cycle
there is a map $\varphi : \mbox{Vert}(\Gamma) \rightarrow \{1,2, \ldots,n\}$
such that if $a_ia_j$ is an edge of $\Gamma$, then $\varphi(i) < \varphi(j)$
(draw the digraph and squash it flat so that the vertices are in
a straight line with the ordering in the line
consistent with the digraph ordering). Define $\pi$ 
a permutation of $1, 2, \ldots, n$
by $\pi(i) = \varphi(v_i)$. Apply $\pi$ to both rows and
columns of the matrix.} 

\item Suppose that $\Delta ABC$ has circumcentre $O$, and that
$N$ is the centre of its nine-point circle. Choose a point
$N'$ so that 
\[ \angle N'BA = \angle NBC,\ \ \ \ \angle N'AB = \angle NAC.\]
Suppose that the perpendicular bisector of $OA$ meets $BC$ in $A'$.
Define $B', C'$ in a  similar fashion. Prove that $A', B', C'$ 
are on a line $\mathfrak l$ which is perpendicular to 
$ON'$.\newline
\noindent{\bf Solution }{\em My commentary multiplies 
the length of the model answer by a factor of about
4.
I will
copy out the answer (and correct it where I can, editorializing
in an intrusive and offensive manner as usual, and no doubt
introducing further errors). Consider 
inversion with respect to the circle with centre at $A$
and radius $\sqrt{AB \cdot AC/2}$ (well the model answer 
doesn't mention the square root; you need it for two reasons,
first because what follows is rubbish otherwise, and second because
the dimension police will have you banged to rights if 
you don't have it there), 
and denote it by $\mathcal I$. Let $\mathcal R$ denote 
reflection in the angle bisector of $\angle BAC$. Let
$\mathcal T = \mathcal R \circ \mathcal I$, and they don't 
say which way round the composition is meant, but happily
these operations commute so we can press on.  Let $M$ denote
the midpoint of $AC$ and $K$ the midpoint of $AB$.
Thanks to a similar triangles argument $\mathcal T(B)= M$ and 
you needn't repeat the argument, we also get $\mathcal T(C) =K$.
Of course $\mathcal T$ is an involution (that is posh for
``if you do it twice, you get the identity'') so
$\mathcal T(M) = B$ and $\mathcal T(K) = C$. 
Let $AD$ be the altitude of triangle $ABC$. 
Then $\mathcal T(O) = D$ and $\mathcal T(D) = O$, 
it says here. Well, this isn't too hard. A certain
pair of similar right-angled triangles do the trick
(showing you that the angles are right and the distances
from $A$ are right). It follows that $\mathcal T$ sends the
circumcircle of $MKD$ to the circumcircle of $OBC$
(inversions and reflections send circles and lines
to circles and lines). Let $P$ be the circumcentre 
of $\Delta OBC$. Note that the nine-point circle of $\Delta ABC$
is the circumcircle of $\Delta MKP$. Thus $AN$ and $AP$ are
symmetric with respect to the angle bisector of $\angle A$
(that is clear because the ray $AN$ produced is mapped to the ray
$AP$ produced and {\em vice versa} by our map $\mathcal T$ which
does indeed involve reflection in the angle bisector of $\angle A$).
Thus $N'$ (hitherto ignored, but see the question) lies
on $AP$. Similarly if $Q, R$ denote the circumcentres
of $\Delta OAC$ and $\Delta OBC$ then $N'$ lies on $BQ$
and $CR$ so we learn that $AP, BQ$ and $CR$ are concurrent
at $N'$ which is very interesting. This actually explains
why $N'$ is an interesting and important point. The 
loopy definition of $N'$ given in the question rather
disguises the symmetry.

Let $A'', B''$ and $C''$ denote the midpoints
of $OA, OB$ and $OC$\footnote{Well actually 
the model answer defines $A''$
to be the midpoint of $O$ but that is too zen}.
Since $PR, RQ$ and $QP$ are tangent to the circle of 
radius $r = OA'' = OB'' = OC''$ centred at $O$
centred at $O$ (it says glibly), it follows that 
$B''C''$ is the polar of $P$ (this is jargon to say
that $B''C''$ is the chord of this circle 
joining the points of contact of the tangent lines from $P$).
Why does it follow? Well, $OB$ is a chord of 
the circumcircle of $\Delta BOC$ centred at $P$, and 
the line segment $PB''$  joins the centre of a circle to
the midpoint of a chord, so hits at right-angles.
Now $A''$ is the midpoint of $OA$, so the polar of $A$
is the line segment perpendicular to $OA$ and through
the midpoint of $OA''$ (a little exercise in similar triangles).

Let the polars of $A$ and $P$ meet at $P'$ so that the polar
of $P'$ will be the line $AP$. This is clearly the application
of a standard theorem of which I was hitherto shamefully
unaware.\footnote{It is easy. Just invert in the
relevant circle and the result falls out. How pretty.} 
Now we apply a homothety 
centred at $O$ with scale factor 2. The polar of $P$ is sent to
$BC$, and the polar of $A$ is sent to the perpendicular bisector
of $OA$. Now $Q', R'$ (which I assume stand in relation to
$Q$ and $R$ as $P'$ stands to $P$, but the model answer
maintains a dignified silence) are the midpoints of $OB'$
and $OC'$. Now since $AP, BQ, CR$ are concurrent,
then $P', Q', R'$ are colinear so $A', B', C'$ are colinear
and on the line 
$\mathfrak l'$. We have $\mathfrak l \parallel \mathfrak l''$ 
(remember $\mathfrak l$? -- look at the question). Since $N'$
lies on the polars of $P'$, $Q'$ and $R'$, so the polar
of $N'$ passes through these points which shows that $\mathfrak l'$
is the polar of $N'$. Since $ON'$ is perpendicular to
$\mathfrak l'$, we have $\mathfrak l \perp ON'$ and we are done.
I don't really follow the final paragraph, but it is late
on Sunday night 17/3/2002. Watch out for later editions
when I have the time. Perhaps one our specialist geometers
would care to help?  
}
\item Let $A$ be the set of sequences $(x_1, x_2, \ldots)$ with integer
entries. Let $\phi: A \rightarrow \mathbb Z$ be a function such that
\begin{enumerate}
\item[(i)] $\phi(s+t) = \phi(s) + \phi(t)$ for all $s,t \in A$ and 
\item[(ii)] $\phi(0,0, \ldots, 1, 0, \ldots ) = 1$ (i.e. $\phi$ assumes the value 
$1$ at all sequences which have one entry $1$, and all other entries $0$.)
\end{enumerate}
\begin{enumerate}
\item[(a)] Prove that $\phi(1,2,4,8,16, \ldots) = 0$.
\item[(b)] Prove that $\phi \equiv 0$ (i.e. $\phi$ is the function
on $A$ which always assumes the value $0$).
\end{enumerate}
\noindent{\bf Solution}{\em 
\begin{enumerate}
\item[(a)] Let $p$ be a prime number and 
$a_1, a_2, \ldots \in \mathbb Z$. Let
\[ n = \phi(a_1p, a_2p^2, a_3p^3, \ldots).\] Then for every every integer
$k \geq 1$ we have 
\[ n = \phi(a_1p_1, \ldots, a_kp^k, 0, 0, \ldots)
+ p^{k+1}\phi(0,0,\ldots, o, a_{k+1}, a_{k+2}p, \ldots)\]
using condition (i). Now conditions (i) and (ii) ensure that the 
first term on the right-hand side of this equation vanishes, and
so $n$ is divisible by $p^{k+1}$ for all $k$ so $n = 0$.
In particular using $p=2$ and $a_i = 1$ for every $i$ we obtain the
required result.
\item[(b)] Given and sequence $(x_i)$ choose $a_i, b_i \in \mathbb Z$
such that $a_i 2^i + b_i 3^i = x_i$, using Euclid's algorithm.
Now using the result of part (a) and condition (i) to deduce that
$\phi(x_1, x_2, \ldots) = 0.$ 
\end{enumerate}}
\end{enumerate}
\end{document}