\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 1}

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

\begin{enumerate}

\item The diagonals $AC$ and $BD$ of a convex quadrilateral $ABCD$ are
perpendicular. Through the midpoints of $AB$ and $AD$ the lines
perpendicular to the
corresponding opposite sides $CD$ and $BC$ are drawn. Prove that these
lines
intersect at a point on the line $AC$.

\item Prove that, for each positive integer $n$, there exists an integer
$k$
which can be expressed as the sum of two squares of integers and such
that
${n\le k<n+3\sqrt[4]{n}}$.

\item Let $\row xn$ be nonnegative real numbers such that 
$${x_1+\cdots +x_n=n}.$$
Prove that
$$
\frac{x_1}{1+x_1^2}+\cdots +\frac{x_n}{1+x_n^2}\le 
\frac{1}{1+x_1}+\cdots +\frac{1}{1+x_n}.
$$

\item A finite set $S$ of congruent squares is situated in the plane so
that each 
side of each square is parallel to one of the coordinate axes. It is
known that
among any $k{+}1$ of the squares there are two intersecting ones.  Show
that the set
$S$ can be divided into no more than $2k{-}1$ subsets so that all
squares
in each
subset have a point in common.

\end{enumerate}
\newpage
%============================

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

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

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

{\bf 1.} Let $M$, $N$, $K$ be the midpoints of $AB$, $AC$, $AD$,
respectively. Then
the sides $MN$, $NK$, $KM$ of the triangle $MNK$ are parallel to $BC$,
$CD$, $BD$,
respectively. Thus, the two drawn perpendicular lines and $AC$ are
continuations of
the altitudes of the triangle $MNK$ and meet at its orthocentre.\par
\begin{figure}[h]
\centerline{\picture 2.25in by 2.2in (fig1 scaled 800)}
\caption{}
\end{figure}
{\bf 2.} Let us represent $n$ in the form $n=k^2+m$, where $0\le m \le
2k$
and note
that $k=[\sqrt{n}\,]$. Let us represent $m$ in this way also: $m=s^2+t$,
where 
$0\le t \le 2s$, where $s=[\sqrt{m}\,]$. Note that if $t=0$, then there
is
nothing to
prove as $n$ itself is a sum of two squares. Suppose $t\ge 1$. 

Let us consider now the number $N=k^2+(s+1)^2$. We have
$$
N-n=2s+1-t\le 2s\le 2\sqrt{2[\sqrt{n}\,]}\le 2\sqrt{2}\cdot
\sqrt[4]{n}<3\sqrt[4]{n}.
$$
\medskip

{\bf 3.} Moving all terms of the inequality to the left we get
$$
\frac{x_1-1}{(1+x_1^2)(1+x_1)}+\cdots +
\frac{x_n-1}{(1+x_n^2)(1+x_n)}\le
0. \eqno(1)
$$
Let us show that for each $k$ 
$$
\frac{x_k-1}{(1+x_k^2)(1+x_k)}\le \frac{x_k-1}{4}.\eqno(2)
$$
Indeed, if $x_k\ge 1$, then this is true because $(1+x_k^2)(1+x_k)\ge
4$. If
$x_k< 1$, then
$$
\frac{1}{(1+x_k^2)(1+x_k)}\ge \frac{1}{4},
$$
from which (2) also follows. Thus,
$$
\frac{x_1-1}{(1+x_1^2)(1+x_1)}+\cdots +
\frac{x_n-1}{(1+x_n^2)(1+x_n)}\le 
\frac{x_1-1}{4}+\cdots +\frac{x_n-1}{4}
$$
$$
\le \frac{x_1+\cdots +x_n-n}{4}=0.
$$
\medskip

{\bf 4.} Let us consider the leftmost square $s$ or one of them if there
are
several such squares. Let us consider its right upper corner $A$ and its
right lower
corner
$B$. Every square intersecting $s$ covers either $A$ or $B$ and thus
they can
be divided into two subsets with each subset having a point in common.
The set
$S^{'}$ of squares which do not intersect $s$ have the property that
among every $k$ squares of $S^{'}$ there are two intersecting ones. To
see this
we add $s$  to any subset of $k$ squares of $S^{'}$ and use the given
property. 
Now by the induction hypothesis all squares of $S^{'}$ can be divided
into no
more than $2k-3$ subsets. Adding the two subsets mentioned above we get
at
most $2k-1$ subsets as required.
\end{document}