\documentclass{article}
\title{December Exam 1}
\author{This is a 4 hour paper}
\date{Various questions from Ukraine}
\begin{document}
\maketitle
\begin{enumerate}
\item Consider the collection of 5-digit (base 10) integers with digits increasing
from left to right. Is it possible to erase a digit (and close up if necessary)
from each of these 5-digit integers, and obtain the collection of all
4-digit integers with digits increasing from left to right? \newline
\noindent {\bf Solution} {\em Each of the sets in question has size
$(^9_5) = (^9_4)$ so such a bijection is not out of the question. Jacob
Shepherd uniquely supplied an answer to this question, and he also supplied
an explicit bijection in the form of a matrix:
\[
\begin{array}{ccccccccc}
0 & 0 & 0 & 0 & X & \cdot & \cdot & \cdot & \cdot \\
0 & 0 & 0 & \cdot & 0 & X & \cdot & \cdot & \cdot \\
0 & 0 & 0 & X & \cdot & 0 & \cdot & \cdot & \cdot \\
0 & 0 & 0 & X & \cdot & \cdot & 0 & \cdot & \cdot \\
0 & 0 & 0 & X & \cdot & \cdot & \cdot & 0 & \cdot \\
0 & 0 & \cdot & 0 & 0 & X & \cdot & \cdot & \cdot \\
0 & 0 & \cdot & \cdot & 0 & 0 & X & \cdot & \cdot \\
0 & 0 & \cdot & 0 & \cdot & 0 & X & \cdot & \cdot \\
0 & 0 & \cdot & 0 & X & \cdot & 0 & \cdot & \cdot \\
0 & 0 & \cdot & 0 & X & \cdot & \cdot & 0 & \cdot \\
0 & 0 & X & \cdot & 0 & \cdot & 0 & \cdot & \cdot \\  
0 & 0 & X & \cdot & 0 & \cdot & \cdot & 0 & \cdot \\ 
0 & 0 & X & \cdot & \cdot & 0 & \cdot & 0 & \cdot \\
0 & \cdot & 0 & \cdot & 0 & \cdot & 0 & X & \cdot  
\end{array}
\]
which says it all really. The first row of this matrix
corresponds to the following 4-digit numbers (focus on the zeros):
\[ 1234, 2345, 3456, 4567, 5678, 6789, 1789, 1289, 1239\]
where the digits from 1 to 9 are written in cyclic order
starting in each of the 9 possible places, and the digits
falling in positions marked by a zero are put in ascending order.
There are 14 rows giving rise to all $14 \times 9 = (^9_4)$
ascending strings of digits of length 4. If you read each $X$ as a 
$0$ you get the $(^9_5)$ ascending strings of digits of length
5. Erasing the digit in position $X$ yields the required bijection.} 

\item Let $I$ denote the incentre of triangle $ABC$. Let the bisector
of $\angle BAC$ meet $BC$ at $A_1$, and the bisector of $\angle BCA$
meet $AB$ at $C_1$. Let $M$ be an arbitrary point on the line
segment $AC$. Lines through $M$ parallel to the given bisector lines
meet $AA_1$, $CC_1$, $AB$, $CB$ at points $H, N, P$ and $Q$
respectively. Let the lengths of $BC$, $AC$ and $AB$ be $a,b$ and $c$
respectively. Let $d_1, d_2$ and $d_3$ be the respective 
distances from $H, I, N$ to the line $PQ$. Prove the following
inequality.
\[ \frac{d_1}{d_2} + \frac{d_2}{d_3} + \frac{d_3}{d_1} \geq
\frac{2ab}{a^2+bc} + \frac{2ca}{c^2 + ab} + \frac{2bc}{b^2 + ca}.\]
\noindent {\bf So far no solution has been offered.}

\item Let $a_1, a_2, \ldots, a_n$ be real numbers such that
$a_1 + a_2 + \cdots + a_n \geq n^2$,
$a_1^2 + a_2^2 + \cdots  + a_n^2 \leq n^3 +1$.
Prove that $n-1 \leq a_k \leq n+1$ for all $k$.\newline
\noindent {\bf Solution} We are given that 
$\sum_i a_i \geq n^2$ and $\sum_i a_i^2 \leq n^3 + 1$.
Now
\[ \sum_i (a_i -n)^2 = \sum_i a_i^2 -2n \sum_i a_i + n^3 \leq n^3 +1 - 2n^3 + n^3 =1.\]
Thus $|a_i - n| \leq 1$ for every $i$ in the range $1 \leq i \leq n$.
{\bf Notice that this is a mean and variance question, and uses the same trick
which gives rise to the method of variance in proving geometric theorems.}

\item There are $n$ mathematicians in each of three countries.
Each mathematician corresponds with at least $n+1$ foreign
mathematicians. Prove that there exist three mathematicians 
who correspond with each other. \newline
{\bf Solution} {\em We assume (for contradiction) that no triple
of mutually corresponding mathematicians. We prove that for all $k$
in the range $1 \leq k \leq n$, each mathematician corresponds with
at least $k$ mathematicians from each other country. The 
hypothesis of the question ensures that the result holds when
$k=1$ and we proceed by induction. Suppose the result holds when
$1 \leq k = r < n$ and consider a mathematician from country $A$
and the situation regarding his (or her) corresponents in country $B$.
There must be at least $1$ of them, and each one
of them corresponds with at least $k$ mathematicians from country $C$,
none of which can be a correspondent of $A$ else wwould form a triangle.
Thus $A$ corresponds with at most $n-k$ mathematicians from country $C$,
and therefore must correspond with at least $k+1$ mathematicians from
country $B$. We are done. Thus every mathematician corresponds with
every mathematician outside his or her own country, and this violates the 
{\em no triangle} condition. {\bf There are other ways to cast this,
but this version is very clear and has comedy value.}}
\end{enumerate}
\end{document}