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

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

{\bf 1.} Determine all functions $f\colon \R\rightarrow \R$ satisfying
the
following
two conditions:

(i) $f(x+y)+f(x-y)=2f(x)f(y)$ for all $x,y\in \R$;

(ii) $\lim_{x\rightarrow \infty}f(x)=0$.
\medskip

{\bf 2.} In the tetrahedron $ABCD$ points $A^{'}$, $B^{'}$, $C^{'}$,
$D^{'}$ are
located strictly inside the faces $BCD$, $CDA$, $DAB$, $ABC$,
respectively.
It is
known that every pair of these four points lie in a plane containing two
vertices of
the tetrahedron. Prove that the four lines $AA^{'}$, $BB^{'}$, $CC^{'}$,
$DD^{'}$ are
concurrent.
\medskip

{\bf 3.} Prove that equation
$$
x^2+x+1=py
$$
has integer solutions $(x,y)$ for infinitely many primes $p$.
\medskip

{\bf 4.} Two players, $A$ and $B$, play a game. They are given a pile of
$n$ matches
and, starting with $A$, they alternate removing these matches so that
$A$ can
remove up to $n{-}1$ matches, and after that each player can remove at
most
as many
matches as the previous player (but at least one). The player who
removes
the last
match wins. For which $n$ can the player $A$ win playing perfectly?

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

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

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

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

{\bf 1.} Let $a$ be any number. Set $y=x-a$. We get 
$$
f(2x-a)+f(a)=2f(x)f(x-a)\quad \mbox{for all $x\in \R$}.
$$
Thus
$$
f(a)=2f(x)f(x-a)-f(2x-a)\rightarrow 0\quad \mbox{for  $x\rightarrow
\infty $}.
$$
It is possible only if $f(a)=0$. The only function satisfying these
conditions is
the zero function.
\bigskip 

{\bf 2.} Let us take points $B^{'}$ and $D^{'}$. As it is easy to see
they
can lie in
a plane only with the vertices $B$ and $D$. Let us call this plane
$\alpha
$.\par
\begin{figure}[h]
\centerline{\picture 2.35in by 2in (fig3 scaled 800)}
\caption{}
\end{figure}

Thus $BB^{'}$ and $DD^{'}$ intersect at a point of $\alpha $. Similarly
$AA^{'}$
intersects with $BB^{'}$ and $DD^{'}$. But since $AA^{'}$ can have only
one
common point
with $\alpha $ these points must coincide and $AA^{'}$, $BB^{'}$ and
$DD^{'}$ are
concurrent. The same argument shows that $CC^{'}$ intersects $\alpha $
at
the same
point as $AA^{'}$. \par
\bigskip  

{\bf 3.} Suppose that we have only a finite number of such primes. Let
them
be $\row
pn$. Let us consider the number $P=p_1p_2\ldots ,p_n$. Then $P^2+P+1$ is
relatively
prime to all of $\row pn$ and has a prime divisor $q$ different from
these
primes.
Thus $P^2+P+1=qQ$ for some positive integer $Q$, i.e., $(P,Q)$ is an
integer solution
to the equation $x^2+x+1=qy$, the contradiction. 
\bigskip 

{\bf 4.} {\bf Answer:} $A$ can win for all $n$ except those which are
powers of
$2$.\par
\smallskip

Let us denote by
$e(m)$ the even part in the prime factorization of $m$. That is, if
$m=2^sq$, where
$q$ is odd, then
$e(m)=2^s$. Also, we introduce some more games. By $(n,k)$ we will
denote
the game
in which there are $n$ matches in the pile and the first player can take
no more
than $k$ matches. And the condition that each player can remove at most
as many
matches as the previous player remains. 

By induction on $n$ we prove that $(n,k)$ is a winning game for the
first
player if
and only if $k\ge e(n)$. Suppose that it is known that the condition
$k\ge
e(n^{'})$
is necessary and sufficient for the game $(n^{'},k)$ to be winning for
all
$n^{'}<n$. 

Suppose that we have a game $(n,k)$ and $e(n)=2^s$, that is $n=2^sq$,
where $q$ is
odd. \par
\smallskip

(i) $k\ge e(n)=2^s$. Then the first player takes $2^s$ matches and then
his
opponent
is left in the position $(n^{'},2^s)$, where
$n^{'}=n-2^s=2^s(q+1)=2^{s+a}q{'}$,
where
$a>0$ since $q+1$ is even. By the induction hypothesis this position is
losing as
$e(n^{'})=2^{s+a}>2^s$. \par
\smallskip

(ii) $k< e(n)=2^s$. Suppose that the first player takes $\ell \le k$
matches. Then
the even part of $\ell$ is smaller that that of $n$ since $e(\ell )\le
\ell \le
k<2^s=e(n)$. The second player will be left in the position $(n^{'},\ell
)$ with
$n^{'}=n-\ell $ matches. It is clear that $e(n^{'})=e(\ell )\le \ell $.
By the
induction hypothesis all these positions are winning ones. \par
\smallskip

Thus our hypothesis is proved by induction. \par
\smallskip

Returning to the original game which is in our notation $(n,n{-}1)$ we
see that
the only losing positions for $A$ will be those for which $n=e(n)=2^s$
is a
power of
$2$. 

\end{document}