
\documentstyle[12pt]{article}
\def\Z{\hbox{\rm Z \kern-.65em Z}}
\def\R{\hbox{\rm I \kern-5.5pt R}}
\def\row#1#2{{#1}_1,{#1}_2,\ldots {#1}_{#2}}
\def\picture #1 by #2 (#3){
  \vbox to #2{
     \hrule width #1 height 0pt depth 0pt
      \vfill
       \special{picture #3}
  }
}
                      
\begin{document}

\centerline{\large \bf New Zealand Mathematical Olympiad Camp}
\bigskip
\medskip

\centerline{\large \bf Christchurch, 1998}
\bigskip
\medskip

\centerline{\Large \bf Problem Set 2}

\vspace{1cm}
\centerline{\Large \bf Problems}
\vspace{1cm}



{\bf 1.} Let $ ABCD$ be a convex quadrilateral inscribed in a semicircle
$\Sigma $ of
diameter $AB$. The lines $AC$ and
$BD$ intersect at $E$ and the lines $AD$ and $BC$ at $F$. The line $EF$
intersects the semicircle
$\Sigma $ at
$G$ and the line $AB$ at $H$. Prove that $E$ is the midpoint of line
segment $GH$ if and only if $G$
is the midpoint of line segment $FH$. 
\bigskip

{\bf 2.} Is it possible for the product of five consecutive positive
integers to be a
perfect square?
\bigskip
 
{\bf 3.} Let $S$ be the set of all real numbers strictly greater than
$-1$.
Find all
functions $f\colon S\rightarrow S$ satisfying the two conditions:
\smallskip

(a) $f(x+f(y)+xf(y))=y+f(x)+yf(x)$ for all $x,y\in S$;\par
\smallskip

(b) $f(x)/x$ is strictly increasing on each of the two intervals
$-1<x<0$
and $0<x$.
\bigskip

{\bf 4.} A certain graph has $mn$ edges and it is known that its edges
can be
painted in $m$ colours in such a way that, for any vertex all edges
adjacent to 
this vertex have different colours. Prove that the edges can be painted
in
such a
way that, for any vertex all edges adjacent to 
this vertex have different colours and that there exist exactly $n$
edges
of each
colour.


\newpage
%============================

\centerline{\large \bf New Zealand Mathematical Olympiad Camp}
\bigskip
\medskip

\centerline{\large \bf Christchurch, 1998}
\bigskip
\medskip

\centerline{\Large \bf Problem Set 2}
\vspace{1cm}
\centerline{\Large \bf Solutions}
\vspace{1cm}

{\bf 1.} Since $AC$ and $BD$ are altitudes in the triangle $ABF$, $E$ is
the
orthocentre of this triangle, so $FE$ is perpendicular to $AB$.
Triangles
$HEB$ and
$HAF$ are similar, so
$HE/HA=HB/HF$. Hence 
$$
HE\cdot HF = HA\cdot HB = HG^2,
$$ 
by power-of-a-point, and the equivalence is now clear.\par
\begin{figure}[h]
\centerline{\picture 2.25in by 2in (fig2 scaled 800)}
\caption{}
\end{figure}

{\bf 2.} {\bf Answer:} No, it is impossible.\par 
\smallskip
 Suppose that 
$$
x_1x_2x_3x_4x_5=y^2,
$$
where $x_1,x_2,x_3,x_4,x_5$ are consecutive integers and $y$ is an
integer.
For any
prime $p\ge 5$ only one of the numbers $x_1,x_2,x_3,x_4,x_5$ can be a
multiple of
$p$, thus $p$ enters their prime factorizations with even exponents. The
primes $2$
and $3$ have special roles. The numbers $x_1,x_2,x_3,x_4,x_5$ can be
divided into $4$
groups:\par 
\smallskip
(a) those for which both $2$ and $3$ enter their prime factorizations
with even
exponents (they are squares);\par 
\smallskip

(b) those for which both $2$ and $3$ enter their prime factorizations
with odd
and even exponents, respectively (each of them is twice a square);\par 
\smallskip

(c) those for which both $2$ and $3$ enter their prime factorizations
with even
and odd exponents, respectively (each of them is three times a
square);\par 
\smallskip

(d) those for which both $2$ and $3$ enter their prime factorizations
with odd
exponents (each of them is six times a square).\par 
\smallskip

According to the Pigeonhole Principle there exist two numbers out of
five, say
$x_m$ and $x_n$, which appear in the same group. Their difference is
less
than $4$.
The difference between two consecutive squares is greater than $4$ with
one
exception: $1^2$ and $2^2$. Thus, $x_m$ and $x_n$ belong to the first
group,
furthermore $x_m=1$, $x_n=4$. Then our five numbers are $1,2,3,4,5$. But
$120$ is
not a perfect square.
\medskip


{\bf 3.} The last condition implies that the equation $f(x)=x$ has at
most three
solutions, one in $(-1,0)$, another might be equal to $0$, and the third
can be in
$(0,\infty )$. Suppose that $f(u)=u$ for some $u$ in $(-1,0)$. Setting
$x=y=u$ in
the given functional equation, we have $f(u^2+2u)=u^2+2u$. Moreover, $u$
in
$(-1,0)$, the number $u^2+2u$ must be in the same interval. Hence
$u^2+2u=u$ but
this means that $u$ is not in $(-1,0)$. Similarly, $f(v)=v$ for $v$ in
$(0,\infty
)$ leads to a contradiction. However, 
$$
f(x+(1+x)f(x))=x+(1+x)f(x)\quad \mbox{for all $x$ in $S$}.
$$
We must have therefore $x+(1+x)f(x)=0$, so that 
$$
f(x)=-{x\over 1+x}.
$$
It is now easy to check that this function indeed satisfies both
conditions.


{\bf 4.} Let us paint the edges of the graph in $m$ colours in such a
way
that, for
any vertex all edges adjacent to this vertex have different colours. We
know that
is possible. Now we will show that this colouring can be ``improved'' in
such a
way that exactly $n$ edges of each colour exist. Suppose that our
initial
colouring
does not have this property, say we have $p>n$ green edges and $q<n$
blue ones. 

We start at an arbitrary vertex $V_1$ where a green edge originates and
we
go to a
vertex $V_2$ along this edge. Let us agree not to use edges twice and
walk along
either green or blue edges only. From $V_2$ we can continue to move
further
only if a
blue edge originates from it, since there cannot be another green edge
from
$V_2$,
and we move this way until no longer possible. If such blue edge does
not
exist at
some stage we stop and look for another vertex with a green edge which
has
not been used before. When we use all green edges in this way, we will
get
a number
of cycles with equal number of green and blue edges, a number of chains
where we have
equal number of green and blue edges and a number of chains where we
have
$s$ green edges and either $s-1$ or $s+1$ blue ones. Since we had more
green edges
than blue, there exists a chain where we have
$s$ green edges and $s-1$ blue ones. Take this chain and paint all green
edges blue
and all blue ones green. The new colouring will again satisfy the
condition
that, for
any vertex all edges adjacent to this vertex have different colours and
have a more
equal distribution of colours. Indeed, we have now $p-1$ green edges and
$q+1$ blue
ones with the numbers of edges of all other colours unchanged. If there
are
still
some colours with more than
$n$ edges, then there will be colours with less than $n$ edges. Choose
any
pair of
colours where one colour is from the first group and the second colour
is
from the
second. We can repeat the process described above. Eventually we will
get the
required colouring. 

In a more formal way this proof can be organized as follows. For each
colouring
$\gamma $ we define  a number
$$
N(\gamma )= |N_1-n|+|N_2-n|+\cdots + |N_m-n|,
$$
where $N_i$ is the number of the edges of the $i$th colour in $\gamma $.
We see
that the operation described above reduces $N(\gamma )$ by $2$ if this
number were
not zero. Also by the definition it is non-negative. Thus by induction
we
can prove
that this operation allows us to transform any colouring $\gamma $ into
a
colouring
$\alpha $ with
$N(\alpha )=0$. 


\end{document}