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

\begin{enumerate}
\item Let $n = 2^m + 1$ and suppose that $f_1, \ldots, f_n$ are increasing 
functions defined on $[0,1]$ with values in $[0,1]$ which satisfy:
\[ |f_i(x) - f_i(y) | \leq |x-y| \ \forall x, y \in [0,1],\
1 \leq i \leq n\]
and $f_i(0) = 0$ for $1 \leq i \leq n$.
Prove that there exist $i \not = j$ such that
for all $x \in [0,1]$ we have
$|f_i(x) - f_j(x)| \leq 1/m.$ \newline \noindent
{\bf Solution }{\em We call a function $\phi: [0, \infty)
\rightarrow [0,\infty)]$ {\em simple} if for any integer
$n \geq 1$ we have $\phi(n) - \phi(n-1) \in \{ 0, 1\}$
and for any $n \geq 0$, the retriction of $\phi$ to
$[n, n+1]$ is a linear function.

\noindent LEMMA Suppose that $g: [0, \infty) \rightarrow \mathbb R$
is an increasing function such that $|g(0)| \leq 1/2$ and for 
every $x,y, \geq 0$ we have $|g(x) - g(y)| \leq |x-y|$, then there
exists a simple function $\phi$ such that for every $x \geq 0$
we have $|\phi(x) - g(x)| \leq 1/2.$

\noindent PROOF We will show that either {\em Case 1} For every
$x \in [0,1]$ we have $|g(x) \leq 1/2$ or {\em Case 2} for every
$x \in [0,1] $ we have $|g(x) - x| \leq 1/2$.

If we are not in Case 1, then there exists $x_0 \in [0,1]$ such that
$|g(x_r0)| > 1/2$. Since $g$ is an increasing function.
$g(x_0) > 1/2.$ If Case 2 failed to hold, there would be
$x_1 \in [0,1]$ such that $|g(x_1) - x_1| > 1/2$.
We know that $g(x_1) - g(0) \leq x_1$ so $g(x_1) - x_1 \leq 1/2$
which implies that $x_1 - g(x_1) > 1/2$. These two inequalties 
yield that 
\[ g(x_0) + x_1 - g(x_1) > 1\]
or
\[ g(x_0) - g(x_1) > 1 - x_1 \geq 0.\]
Since $g$ is an increasing function, $x_0 \geq x_1$ and it follows 
from $g(x_0) - g(x_1) \leq x_0 - x_1$ that $x_0 > 1$ which is absurd
and the Lemma is proved.

Now from this lemma it follows that there is a simple
function $\phi_0$ such that
$|g(x) - \phi_0(x)| \leq 1/2.$ It is easy to see that $\phi_0$
can be extended to the whole positive half-line. Now define
\[ g_i(x) = 
\left\{ \begin{array}{rl}
        mf_i(x/m) & 0 \leq x \leq m\\
       mf_i(1) & x \geq m. 

        \end{array}
\right.
\]
If we apply the Lemma to the functions $g_i$, then we see
that there exists a simple function $\phi_i$ such that
$g_i(x) - \phi_i(x) \leq 1/2$.
However, there are precisely
$2^m$ simple functions when restricted to the integral intervals
$[0,m]$ so there exist $i \not = j$ such that $\phi_i(x)
= \phi_j(x)$ for all $x \in [0,m]$ which shows that
$f_i(x) - f_j(x)| \leq 1/m$ for all $x \in [0,1]$.} 

\item In $\Delta ABC$ let $I$ and $I_a$ denote the 
incentre and the excentre corresponding to the side $BC$. 
Suppose that $II_a$ meets $BC$ and the circumcircle 
of $\Delta ABC$ at $A'$ and $M$ respectively.  Let 
$N$ be the midpoint\footnote{The original says
mindpoint, but I feel uneasy about this.}
of the arc $MBA$. Let $S, T$ 
be the respective intersection points of $NI, NI_a$ 
with the circumcircle of $\Delta ABC$.  Prove 
that $S, T, A'$ are colinear.  \newline
\noindent {\bf Solution }{\em
We first prove a Lemma.
\newline
\noindent LEMMA. Suppose that the circles $\Gamma_1, \Gamma_2$
are tangent at $T$. Let $I$ be a point of $\Gamma_1$ suppose that
the tangent at $I$ meets $\Gamma_2$ at $A$ and $M$.
If $TI$ meets $\Gamma_2$ at $K$, then $K$ is the midpoint
of arc $AKM$.\newline \noindent PROOF
Let $\Delta$ be a line parallel to $AM$ passing through $I$.
Since there is a homothety centred at $T$ which maps $\Gamma_1$
to $\Gamma_2$ it follows that $\Delta$ is tangent to 
$\Gamma_1$ at $K$. So $K$ is indeed the midpoint of 
arc $AKM$ and the lemma is proved.

Now let $\Gamma$ denote the circumcircle of triangle 
$ABC$ and $C_1$ be a circle which is tangent to
$AI$ and $\Gamma$. By the lemma, $T$ is the tangency point of
$C_1$ and $\Gamma$. Let $C_2$ be a circle which is tangent
to $\Gamma$ and passes through $I_a$.
Apply the lemma to deduce that $C_1, C_2$ intersect at $S$.
What! $S$? Yes, it was in the question but has been quiet lately.
Now invert centred at $N$ sending $I$ to $I_a$.
This inversion swaps $C_1, C_2$ and we deduce that $S, T', A$ are
colinear.
} 

\item We define an {\em $n$-variable formula} 
to mean a function of $n$ variables $x_1, \ldots, x_n$ 
which can be expressed as a composition
of the functions $\max\{a,b,c,\ldots\}$  
and $\min\{a,b,c, \ldots\}$. (For example,
$\max\{x_2, x_3, \min\{x_1, x_2, \max\{x_4, x_5\}\}\})$.
Suppose that $P(x_1, \ldots , x_n)$ and $Q(x_1, \ldots, x_n)$
are two $n$-variable formulas, and assume that
if $x_i \in \{0,1\}$ for every $i$, then 
\[P(x_1, \ldots, x_n) = Q(x_1, \ldots , x_n).\] 
Prove that $P \equiv Q$ (i.e. $P$ and $Q$ agree
at all real arguments $x_1, x_2, \ldots, x_n$).\newline
\noindent {\bf Solution }
{\em Suppose (for contradiction) that the result is not true.
Thus there are real numbers $x_1 < \cdots < x_n$ such that
$P(x_1, x_2, \ldots, x_n) < Q(x_1, x_2, \ldots, x_n)$.
By perturbing and relabelling we may assume that
$x_1 < x_2 < \cdots < x_n$
since min and max are continuous functions.
Thus there exist $p \not = q$ such that
$x_p = P(x_1, \ldots, x_n) < Q(x_1, \ldots, x_n) = x_q$.
Now if we replace $x_1, \ldots, x_p$ by $0$ and
$x_{p+1}, \ldots, x_n$ by 1, and induction shows that
$P(x_1', \ldots, x_n') = 0$ and $Q(x_1', \ldots, x_n') = 1$
which contradicts our assumption.} 
\end{enumerate}
\end{document}