%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%ÀÌ ÆÄÀÏ¿¡ ¼ö·ÏµÈ ¼öÇй®Á¦¿Í ±Û¿¡ ´ëÇÑ ÀúÀÛ±ÇÀº ´ëÇѼöÇÐȸ¿¡ ÀÖ½À´Ï´Ù.%
%°³ÀÎÀûÀÎ »ç¿ë¸¸ Çã¿ëµÇ¾î ÀÖ½À´Ï´Ù.                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[10pt]{article} 
\usepackage{hangul}
\usepackage{amstex} 
\usepackage{amssymb}
\usepackage{ctfonts}
\textheight20.1cm
\textwidth15.1cm 

\begin{document}     

\begin{center}
\Large{The 8th Korean Mathematical Olympiad}
\end{center} 

\vskip 0.3 true cm

\begin{center}
\Large{[ First round ]}
\end{center}                                              

\vskip 1 true cm
                                                                                                 
\def\B#1{\Bbb #1}
\def\ld{\lambda}
\def\ap{\alpha}
\def\gm{\gamma}
\def \ci #1{ #1\hskip-8.9pt\bigcirc  }
\def\back#1{\noalign{\vskip #1pt}}
\def\hsp#1{\hskip #1pt}
\def\udl#1{\hsp{-15}\underline{\ #1\ }\hsp{-15}}
\def\vline#1{\vrule height #1pt depth 5pt   } 
 
{\bf Morning session ($2\frac 12$ hours)}

\bigskip

\begin{enumerate}
\item[1.] Consider a finitely many points in a plane such that, if 
we choose  any three  points $A, B,  C$ among them,  the area  of $\triangle 
ABC$ is always less  than $1$.  Show that all  of these finitely many  
points lie  within the  interior or on the boundary of a triangle with area
less than $4$. 
\bigskip
\item[2.] For  a given positive integer $m$,  find all pairs $(n, x,  y)$ 
of positive
integers such  that $m,  n$ are  relatively prime and  $(x^2+y^2)^m=(xy)^n$, 
where
$n, x, y$ can be represented by functions of $m$.
\bigskip
\item[3.] Let  $A, B, C$ be three points  lying on a circle, and let  $P, 
Q, R$
be midpoints  of arcs  $BC, CA,  AB,$ respectively.  $AP, BQ,  CR$ intersect 
$BC, CA, AB$
at $L, M, N$, respectively. Show that
$$\frac {AL}{PL}+\frac {BM}{QM}+\frac {CN}{RN}\ge 9.$$
For which triangle $ABC$ does equality hold ?
\bigskip
\item[4.]  A partition of  a positive integer  $n$ is a  sequence
$(\ld_1,  \ld_2, \cdots  ,  \ld_k)$   of  positive  integers  such   that 
$\ld_1+\ld_2+\cdots  +\ld_k=n$ and $\ld_1\ge  \ld_2 \ge \cdots  \ge \ld_k\ge
1$.  Each $\ld_i$ is  called a  summand. For example, $(4, 3, 1)$  is a
partition of 8 whose summands are distinct.  Show that, for a  positive
integer $m$ with  $n>\frac 12 m(m+1)$, the number  of  all partitions  of
$n$ into distinct $m$  summands is  equal to  the number  of all 
partitions of $n-\frac 12 m(m+1)$ into $r$ summands $(r\le m)$. 
\end{enumerate}

\newpage

{\bf fternoon session ($2\frac 12$ hours)}
\bigskip

\begin{enumerate}
\item[5.]  If we select at  random three points  on a given  circle, find 
the probability
that these three points lie on a semicircle.
\bigskip
\medskip
\item[6.] Show  that any positive integer  $n(>1)$ can be expressed by  a 
finite sum
of numbers satisfying the following conditions:

(i) they do not have factors exept 2 or 3.

(ii) any two of them are neither a factor nor a multiple each other.

That is,  $n=\sum_{i=1}^N 2^{\ap_i}  3^{\beta_i}$, where  $\ap_i, \beta_i\ 
\  (i=1, 2,
\cdots  , N)$  nonnegative  integers and 
$(\ap_i-\ap_j)(\beta_i-\beta_j)<0$  whenever
$i\ne j$.
\bigskip
\medskip
\item[7.]  Find all real  valued functions $f$  defined on real numbers 
except  $0$ such
that
$$\frac 1x f(-x)+f(\frac 1x) =x,\qquad x\ne 0.$$
\bigskip
\medskip
\item[8.] Two circles $O_1, O_2$ of radii $r_1, r_2\ \, (r_1<r_2)$,
respectively, intersect at two points  $A$ and $B$. $P$ is any point on a
circle  $O_1$.
Lines $PA, PB$ and a circle $O_2$ intersect at $Q$ and $R$, respectively.

(1) Express $y=QR$ in terms of $r_1, r_2$, and $\theta=\angle APB$.

(2)  Show that  $y=2r_2$  is a  necessary  and sufficient  condition  that a 
circle
$O_1$ is orthogonal to a circle $O_2$.
\end{enumerate} 

\newpage

\begin{center}
\Large{[ Final round ]}
\end{center}
\medskip
\bigskip

{\bf First day session ($4\frac 12$ hours)}
\bigskip

\begin{enumerate}
\item[1.] For  any positive integer $m$,  show that there exist  integers 
$a, b$ satisfying 
$$|a|  \le m,  \qquad   |b|  \le  m, \qquad 0< a+b\sqrt  2 \le  \frac 
{1+\sqrt  2}{m+2}.$$
\medskip
\bigskip
\item[2.] Let $A$ be the set of all non-negative integers. Find all
functions $f: A\to A$ satisfying the following two conditions:

(i) for any $m, n \in A,$

$$2f(m^2+n^2)=\{f(m)\}^2+\{f(n)\}^2$$

(ii) for any $m, n \in A$ with $m\ge n,$

$$f(m^2) \ge f(n^2).$$
\medskip
\bigskip
\item[3.] Let $\triangle ABC$ be an equilateral triangle of side length
$1, D$ a point on $BC$, and let $r_1, r_2$, be inradii of triangles $ABD,
ADC$, respectively. Express $r_1r_2$ in terms of $p=BD$, and find the
maximum of $r_1r_2$. 
\end{enumerate}

\newpage

{\bf Second day session ($4\frac 12$ hours)}
\bigskip

\begin{enumerate}
\item[4.] Let $O$ and $R$ be the circumcenter and the circumradius of
$\triangle ABC$, respectively, and let $P$ be any point on the plane $ABC$.
Let perpendiculars $PA_1, PB_1, PC_1$, be dropped to the three sides $BC,
CA, AB$. Express $\frac {(\triangle A_1B_1C_1)}{(\triangle ABC)}$ in terms
of $R$ and $d=OP$, where $(\triangle ABC)$ is the area of $\triangle ABC$. 

\medskip
\bigskip
\item[5.] Let $p$ be a prime number such that 

(i) $p$ is the greatest common divisor of $a$ and $b$;

(ii) $p^2$ is a divisor of $a$. Prove that the polynomial
$x^{n+2}+ax^{n+1}+bx^n+a+b$ cannot be decomposed into the product of two
polynomials with integeral coefficients, whose degrees are greater tham one.
\medskip 
\bigskip 
\item[6.] Let $m, n$ be positive integers with $1\le n\le m-1$. A box
is locked with several padlocks, all of which must be opened to open the
box, and all of which have different keys. $m$ people each have keys to
some of the locks. No $n$ people of them can open the box but any $n+1$
people can open the box. Find the smallest number $l$ of locks and then the
number of keys for which this is possible.
\end{enumerate}

\newpage

\begin{center}
\Large{The 8th Korean Mathemtical Olympiad\\
Solutions}
\end{center}

\bigskip

\begin{center}
\Large{[First round]}
\end{center}
\bigskip

\begin{enumerate}
\item[1.] Consider a finitely many points in a plane such that, if 
we choose  any three  points $A, B,  C$ among them,  the area  of $\triangle 
ABC$ is always less  than $1$.  Show that all  of these finitely many  
points lie  within the  interior or on the boundary of a triangle with area
less than $4$. 
\end{enumerate}

{\bf Solution}

We can take $\triangle ABC$ having the maximum area among triangles whose
vertices are chosen from the given finitely many points. Then $(\triangle
ABC)\le 1$. Here $(\triangle ABC)$ denotes the area of $\triangle ABC$.
\newline  
\noindent Let $\triangle LMN$ be the triangle \newline
\noindent whose medial triangle is \newline
\noindent $\triangle ABC$. Then
$$(\triangle LMN)=4(\triangle ABC)\le 4.\qquad\qquad\qquad\qquad\qquad
\qquad\qquad$$
We may prove that the given finitely many points lie within the interior or
on the boundary of $\triangle LMN$. Suppose a point $P$ lies on the
exterior of $\triangle LMN$. We may assume that a point $P$ locates at the
opposite side of $N$ with respect to a line $ML$. Then the length of a
perpendicular of $P$ dropping to $AB$ is larger than that of $C$ dropping
to $AB$.

It follows that $(\triangle PAB)>(\triangle CAB)=(\triangle ABC)$ and $P$
is never included in the given finitely many points. This completes the
proof. 

\bigskip
\begin{enumerate} 
\item[2.] For  a given positive integer $m$,  find all pairs $(n, x,  y)$ 
of positive integers such  that $m,  n$ are  relatively prime and 
$(x^2+y^2)^m=(xy)^n$,  where $n, x, y$ can be represented by functions of
$m$. 
\end{enumerate}

{\bf Solution}

If $(n, x, y)$ is a solution of the given equation, then from $x^2+y^2\ge
2xy$ we have $(xy)^n=(x^2+y^2)^m>(xy)^n$. It follows that $n>m$.

Let $p$ be a common prime divisor of $x$ and $y$, and let $p^a\Vert x,
p^b\Vert y$. Here $p^a\Vert x$ means that $p^a\vert x$ but $p^{a+1}
\nmid y$. Then $p^{(a+b)n}\Vert (xy)^n=(x^2+y^2)^m$. Suppose $b>a$.  Since
$p^{2a}\Vert x^2, p^{2b}\Vert y^2$, we see that $p^{2a} \Vert x^2+y^2$ and
$p^{2am}\Vert (x^2+y^2)^m$. It follows that $2am=(a+b)n>2an$ and $m>n$.
This is a contradiction.  Similarly, $a>b$ gives a contradiction. It
concludes that $a=b$ and $x=y$. Now we have $x^{2n}=(2x^2)^m=2^mx^{2n}$ and
$x^{2(n-m)}=2^m$. Thus, $x=2^t$ for some integer $t$. From
$2^{2(n-m)t}=2^m$ we have $2t(n-m)=m$. Since $2nt=(2t+1)m$ and $m, n$ are
relatively prime, we obtain $m=2t, n=2t+1$. 
\medskip
Answer. \qquad $(n, x, y)=(m+1, 2^{m/2}, 2^{m/2})$\qquad (m: even)

\bigskip
\begin{enumerate}
\item[3.] Let  $A, B, C$ be three points  lying on a circle, and let  $P, 
Q, R$
be midpoints  of arcs  $BC, CA,  AB,$ respectively.  $AP, BQ,  CR$ intersect 
$BC, CA, AB$
at $L, M, N$, respectively. Show that
$$\frac {AL}{PL}+\frac {BM}{QM}+\frac {CN}{RN}\ge 9.$$
For which triangle $ABC$ does equality hold ?
\end{enumerate} 

{\bf Solution}

Since $P$ is a midpoint \newline
\noindent of arc $BC$, we have \newline
\noindent $\angle BAP=\angle CAP=\frac 12\angle A$. \newline
\noindent It follows that $BL:CL=c:b$, \newline
\noindent and $BL=\frac{ca}{b+c}, \ CL=\frac {ba}{b+c}$. \newline
\noindent Now we have  
$$AL\cdot PL=BL\cdot CL=\frac {a^2bc}{(b+c)^2}\leqno{(1)}$$
Since $(\triangle ABL)+(\triangle ALC)=(\triangle ABC)$, we obtain $\frac
12 c AL \sin\frac A2=\frac 12 b AL \sin\frac A2=\frac 12bc \sin A$ and 
$$AL=\frac {bc}{b+c} \frac {\sin A}{\sin \frac A2}=\frac {2bc}{b+c} \cos
\frac A2.$$
Form (1) we have 
\begin{eqnarray*}
PL&=&\frac {a^2bc}{(b+c)^2}\cdot \frac {b+c}{2bc}\cdot \frac
1{\cos \frac A2}=\frac {a^2}{2(b+c)}\cdot\frac 1{\cos \frac
A2}\quad \text{and}\\  
\frac {AL}{PL}&= &\frac {4bc}{a^2}\cos^2\frac A2=\frac{2bc}{a^2}
(1+\cos A)=\frac {2bc}{a^2}\Bigl (1+\frac
{b^2+c^2-a^2}{2bc}\Bigr )=\Bigl (\frac{b+c}a\Bigr )^2-1. 
\end{eqnarray*}
Similarly, 
%$$\frac {BM}{QM}=(\frac {c+a}b)^2-1 \  \ \text{and}\ \  \frac
%{CN}{RN}=(\frac {a+b}c)^2-1.$$ 
$$\frac {BM}{QM}=\Bigl (\frac {c+a}b\Bigr )^2-1\ \ \text{and}\ \ \frac
{CN}{RN}=\Bigl (\frac {a+b}c\Bigr )^2-1.$$ 
Finally, 
\begin{eqnarray*}
& &\frac {AL}{PL}+\frac {BM}{QM}+\frac {CN}{RN}=\Bigl (\frac
{b+c}a\Bigr )^2+\Bigl (\frac {c+a}b\Bigr )^2+\Bigl (\frac
{a+b}c\Bigr )^2-3\\ 
& = & \Bigl (\frac ba-\frac ab\Bigr )^2+\Bigl (\frac cb-\frac
bc\Bigr )^2+\Bigl (\frac ac-\frac ca\Bigr )^2+2abc\Bigl (\frac 1{a^3}+\frac
1{b^3}+\frac 1{c^3}\Bigr )+3\\ 
& = & \Bigl (\frac ba-\frac ab\Bigr )^2+\Bigl (\frac cb-\frac
bc\Bigr )^2+\Bigl (\frac ac-\frac ca\Bigr )^2\\
& &+(ab+bc+ca) \Bigl \{\Bigl (\frac 1a-\frac 1b\Bigr )^2+\Bigl (\frac 1b-\frac
1c\Bigr )^2+\Bigl (\frac 1c-\frac 1a\Bigr )^2\Bigr \}+9\ge 9,
\end{eqnarray*}
equality holds for $a=b=c$. 

\bigskip
\begin{enumerate}
\item[4.]  A partition of  a positive integer  $n$ is a  sequence
$(\ld_1,  \ld_2, \cdots  ,  \ld_k)$   of  positive  integers  such   that 
$\ld_1+\ld_2+\cdots  +\ld_k=n$ and $\ld_1\ge  \ld_2 \ge \cdots  \ge \ld_k\ge
1$.  Each $\ld_i$ is  called a  summand. For example, $(4, 3, 1)$  is a
partition of 8 whose summands are distinct.  Show that, for a  positive
integer $m$ with  $n>\frac 12 m(m+1)$, the number  of  all partitions  of
$n$ into distinct $m$  summands is  equal to  the number  of all 
partitions of $n-\frac 12 m(m+1)$ into $r$ summands $(r\le m)$. 
\end{enumerate}

{\bf Solution}

Since a partition of $n$ into distinct $m$ summands is of the form
$\ld_1+\ld_2+\cdots +\ld_m=n, \  \ld_1>\ld_2>\cdots >\ld_m\ge 1$, we have
$\ld_m\ge 1, \ \ld_{m-1}\ge 2,\ \ld_{m-2}\ge 3,\cdots , \ld_1\ge m$. It
follows that $n=\ld_1+\ld_2+\cdots +\ld_m\ge 1+2+\cdots +m={m(m+1)}/2$.
This partition can be represented geometrically. Consider the array of
points having $\ld_1$ points in the top row, $\ld_2$ in next row, and so on
down to $\ld_m$ in the bottom row.  
\begin{equation}
\begin{alignedat}{3}
&\ld_1\\
&\ld_2\\
&\cdots\\ 
&\ld_{m-1}\\
&\ld_m  \\
\end{alignedat}
\ \ \begin{alignedat}{2}
&\bullet\ \ \bullet\ \ \bullet\ \ \bullet\ \cdots \ \bullet \
\cdots \ \bullet\\
&\bullet\ \ \bullet\ \ \bullet\ \ \bullet\ \cdots\ \bullet \\
&\cdots\cdots\cdots\\
&\bullet \ \ \bullet \ \ \cdots\\
&\bullet\ \ \cdots \\
\end{alignedat}
\ \ \begin{alignedat}{1}
&\text{more than $m$ points}\\ 
&\text{more than $m-1$ points}\\  
& \ \\
&\text{more than $2$ points}\\ 
&\text{more than $1$ point}\\ 
\end{alignedat}
\end{equation}
In the first row, we divide $\ld_1$ points into $m$ points and $\ld_1-m$
points, and in the second row, we divide $\ld_2$ points into $m-1$ points
and $\ld_2-(m-1)$ points, etc.
\begin{equation}
\begin{alignedat}{5}
\ld_1 \ &: \\
\ld_2 \ &: \\
\ \     &  \\
\ld_{m-1} \ &: \\
\ld_{m} \ &: 
\end{alignedat}
\ \ \begin{alignedat}{4}
&\bullet\ \ \bullet\ \ \bullet\ \cdots \ \bullet \ \ \bullet \\
&\bullet\ \ \bullet\ \ \bullet\ \cdots \ \bullet\\
&\cdots\cdots\\
&\bullet\ \ \bullet\\
&\bullet
\end{alignedat}
\ \ \begin{alignedat}{3}
&m\ \text{points}\\
&m-1\ \text{points}\\
& \ \\
&2\ \text{points}\\
&1\ \text{points}
\end{alignedat}
\ \ \begin{alignedat}{2}
&\cdots\cdots\\
&\cdots\cdots\\
&\cdots\cdots\\
&\cdots\cdots\\
&\cdots\cdots\\
\end{alignedat}
\ \ \begin{alignedat}{1}
&(\ld_1-m)\ \text{points}\\  
&(\ld_2-(m-1))\ \text{points}\\
&\ \\   
&(\ld_{m-1}-2)\ \text{points}\\  
&(\ld_{m}-1)\ \text{points}  
\end{alignedat}
\end{equation} 
\begin{eqnarray*}
\qquad\qquad\qquad\qquad\qquad\text{---------------}
\qquad\qquad\qquad\text{------------------}\qquad\qquad \\
\qquad\qquad\qquad\qquad\qquad\quad\text{total:}\ \ \frac {m(m+1)}2\
\text{points}\qquad\text{total:}\ \ n-\frac 12m(m+1)\ \text{points}
\end{eqnarray*}
Since $\ld_i-(m+1-i)\ge 0$ and $\sum_{i=1}^m
\{\ld_i-(m+1-i)\}=\sum_{i=1}^n\ld_i-\frac {m(m+1)}2=n-\frac {m(m+1)}2$,
the right part of the array of points represents a partition of $n-\frac
12m(m+1)$ into $r$ summands $(r\le n)$. This completes the proof.

\bigskip
\begin{enumerate}
\item[5.]  If we select at  random three points  on a given  circle, find 
the probability
that these three points lie on a semicircle.
\end{enumerate}

{\bf Solution}

Let $A, B, C$ be selected points on \newline
\noindent a given circle, and let \newline
\noindent $\angle AOB=x, \angle BOC=y, \angle COA=z$. \newline
\noindent Then 
$$
x+y+z=2\pi \qquad x\ge 0,\ y\ge 0,\ z\ge 0.\leqno{(1)}$$ 
Three points $A, B, C$ lie on a semicircle if and only if one of $x+y\le
z, y+z\le x$ or $z+x\le y$ holds, that is, 
$$x\ge \pi, \ y\ge \pi\ \ \text{or}\ \  z\ge \pi .\leqno{(2)}$$

In space, the region of (1) is the union of \newline
\noindent the interior and the boundary of $\triangle ABC$\newline
\noindent and the region of (2) is the union of\newline
\noindent the interiors and the boundaries of\newline
\noindent $\triangle A'B'C, \ \triangle AB'C'$ and $\triangle BC'A'$.\newline
\noindent It follows that the required probability is $\frac 34$. 
\medskip
Answer.\qquad $\frac 34$.

\medskip
cf. The required probability is equal to the probability that $\triangle
ABC$ becomes obtuse.

\bigskip
\begin{enumerate}
\item[6.] Show  that any positive integer  $n(>1)$ can be expressed by 
a  finite sum of numbers satisfying the following conditions:

(i) they do not have factors exept 2 or 3.

(ii) any two of them are neither a factor nor a multiple each other.

That is,  $n=\sum_{i=1}^N 2^{\ap_i}  3^{\beta_i}$, where  $\ap_i, \beta_i\ 
\  (i=1, 2,\cdots  , N)$  nonnegative  integers and 
$(\ap_i-\ap_j)(\beta_i-\beta_j)<0$  whenever $i\ne j$.
\end{enumerate}

{\bf Solution}

Note that $2=2^1, 3=3^1, 4=2^2, 5=2^1+3^1, 6=2^1\cdot 3^1, 7=2^2+3^1,
8=2^3, 9=3^2, 10=2^2+2^1\cdot 3^1$, etc. So if $n\le 10$, then the required
representation is possible. 

We use induction on $n$.

Suppose that, for every $m(\le n)$, the required representation of $m$ is
possible.

i) $n$ is odd;

Since $n+1$ is even and $\frac {n+1}2<n$, we have $\frac
{n+1}2=\sum_{i=1}^N 2^{\ap_i}\cdot 3^{\beta_i}$, where
$(\ap_i-\ap_j)(\beta_i-\beta_j)<0$ whenever $i\ne j$. Then
$n+1=\sum_{i=1}^N 2^{\ap_i+1}\cdot 3^{\beta_i}$ and
$\{(\ap_i+1)-(\ap_j+1)\}
(\beta_i-\beta_j)=(\ap_i-\ap_j)(\beta_i-\beta_j)<0$ whenever $i\ne j$. 

ii) $n$ is even ;

If $n+1=3^k$, we have done.

If $n+1\ne 3^k$, we can take a positive integer $k$ such that
$3^k<n+1<3^{k+1}$. 

Since $3^k$ is odd, $n+1-3^k$ is even, and ${(n+1-3^n)}/2<n$, we have
${(n+1-3^k)}/2$ $=\sum_{i=1}^N 2^{\ap_i}\cdot 3^{\beta_i}$, where 
$(\ap_i-\ap_j)(\beta_i-\beta_j)<0$ whenever $i\ne j$. 

Then $n+1=3^k+\sum_{i=1}^N 2^{\ap_i+1}\cdot 3^{\beta_i}$. Since
$\ap_i+1>0, \beta_i<k \ \ (i=1, 2,\cdots , N)$, we have $3^k$ and
$2^{\ap_i+1}\cdot 3^{\beta_i}\ \ (i=1, 2, \cdots , N)$ are neither a
factor nor a multiple each other. From i) and ii) we know that the required
representation of $n+1$ is possible. This completes the proof.

\bigskip
\begin{enumerate}
\item[7.]  Find all real  valued functions $f$  defined on real numbers 
except  $0$ such that
$$\frac 1x f(-x)+f(\frac 1x) =x,\qquad x\ne 0.$$
\end{enumerate}

{\bf Solution}

Letting $x=-y$ in the given equation, we have 
$$-\frac 1y f(y)+f(-\frac 1y)=-y\leqno{(1)}$$
and letting $x=1/y$, we have
$$yf(-\frac 1y) +f(y)=\frac 1y.\leqno{(2)}$$
Eliminating $f(-\frac 1y)$ in (1) and (2), we have 
$$f(y)=\frac 12(y^2+\frac 1y).$$
Conversely, if $f(x)=\frac 12(x^2+ 1/x)$, then
$$\frac 1x f(-x) +f(\frac 1x)=\frac 1x\cdot\frac {-x^3+1}{-2x}+\frac {\frac
1{x^3}+1}{2\cdot\frac 1x}=x.$$
Answer.\qquad $f(x)=\frac 12(x^2+ 1/x),\qquad x\ne 0.$

\bigskip
\begin{enumerate}
\item[8.] Two circles $O_1, O_2$ of radii $r_1, r_2\ \, (r_1<r_2)$,
respectively, intersect at two points  $A$ and $B$. $P$ is any point on a
circle  $O_1$.
Lines $PA, PB$ and a circle $O_2$ intersect at $Q$ and $R$, respectively.

(1) Express $y=QR$ in terms of $r_1, r_2$, and $\theta=\angle APB$.

(2)  Show that  $y=2r_2$  is a  necessary  and sufficient  condition  that a 
circle
$O_1$ is orthogonal to a circle $O_2$.
\end{enumerate}

{\bf Solution} 

(1) Case I. \quad $P$ lies in the exterior of a circle $O_2$;

Let $\angle PAB=\ap$ and $AB=a$. Then $a=2r_1\sin\theta$, 
\begin{eqnarray*}
& &\frac {PR}{PA}=\frac {PQ}{PB}=\frac {QR}{AB}=\frac ya,\ \
\frac{BQ}{\sin\ap}=2r_2,\ \ \text{and}\qquad\qquad\qquad\qquad\\
& &\frac {PB}{\sin\ap}=\frac a{\sin\theta}=\frac {PA}{\sin
(\theta+\ap)}=2r_1.
\end{eqnarray*}
In $\triangle PBQ$, we have 
$$BQ^2=PB^2+PQ^2-2PB\cdot PQ \cos (\angle BPQ)=PB^2\Bigl [1+\frac
{y^2}{a^2}-2\frac ya\cos (\angle BPQ)\Bigr ].$$
It follows that 
\begin{eqnarray*}
& &4 r^2_2\sin^2\ap=4r_1^2\sin^2\ap[\{\frac ya-\cos(\angle
BPQ)\}^2+\sin^2(\angle BPQ)]\ \ \text{and}\\
& &y=a\cos\theta+\frac an\sqrt{r_2^2-r_1^2\sin^2\theta}=2\sin\theta\Bigl
\{r_1\cos \theta+\sqrt{r_2^2-r_1^2\sin^2\theta}\Bigr \}.
\end{eqnarray*}

Case II.  $P$ lies in the interior of a circle $O_2$;

Similarly, 
$$y=2\sin\theta \Bigl \{r_1 \cos
(\pi-\theta)+\sqrt{r_2^2-r_1^2\sin^2\theta}\Bigr \},
\qquad\qquad\qquad\qquad\qquad\qquad$$  
where
$$\angle BPQ=\pi - \angle APB=\pi -\theta.\qquad\qquad\qquad\qquad
\qquad\qquad\qquad\qquad$$

(2) If a circle $O_1$ is orthogonal to a circle $O_2$, then
$r_2=r_1\tan\theta$ (Case I); 

$r_2=r_1\tan (\pi-\theta)$ \ \ (Case II). It follows that $y=2r_2$.
Conversely, if $y=2r_2$, then $r_2=r_1\tan\theta$ (Case I);
$r_2=r_1\tan(\pi-\theta)$ \ \ (Case II).  This completes the proof.
\smallskip
Answer of (1);
\begin{eqnarray*}
y &=& 2\sin\theta\{r_1\cos\theta+\sqrt{r_2^2-r_1^2\sin^2\theta}\}\\
& & \ (P\ \ \text{lies in the exterior of a circle}\ \ O_2),\\
y &=&2\sin\theta\{r_1\cos(\pi-\theta)+\sqrt{r_2^2-r_1^2\sin^2\theta}\}\\
& & \ (P\ \ \text{lies in the interior of a circle}\ \ O_2).
\end{eqnarray*}

\newpage

\begin{center}
\Large{The 8th Korean Mathemtical Olympiad \\
Solutions}
\end{center}

\bigskip

\begin{center}
\Large{[ Final round ]}
\end{center}
\bigskip

\begin{enumerate}
\item[1.] For  any positive integer $m$,  show that there exist  integers 
$a, b$ satisfying 
$$|a|  \le m,  \qquad   |b|  \le  m, \qquad 0< a+b\sqrt  2 \le  \frac 
{1+\sqrt  2}{m+2}.$$
\end{enumerate}

{\bf Solution}

Let $f(x, y)=x+y\sqrt 2$ and $S=\{f(a, b)| a, b\ \text{integers with}\
0\le a\le m\ \text{and}\ 0\le b\le m\}$. If $f(a, b)=f(a', b')$, then
$a+b\sqrt 2=a'+b'\sqrt 2$ and $a=a', b=b'$. It follows that the number of
elements in $S$ is $(m+1)^2$. The maximum of $S$ is $m+m\sqrt 2=(1+\sqrt
2)m$, and so if $f(a, b)\in S$, then $0\le f(a, b)\le (1+\sqrt 2)m$. Devide
the interval $[0, (1+\sqrt 2)m]$ into equal $m^2+2m$ small intervals. Then
the lengths of small intervals are $\frac {(1+\sqrt 2)m}{m^2+2m}=\frac
{1+\sqrt 2}{m+2}$. Since the number of elements in $S$ is
$(m+1)^2=(m^2+2m)+1$, by peogion hole principle there exist $f(a_1, b_1),
f(a_2, b_2) \in S$ such that $f(a_1, b_1), f(a_2, b_2)$ lie on the same
small interval. We may assume that $f(a_1, b_1) > f(a_2, b_2)$. Then
$0<f(a_1, b_1)-f(a_2, b_2)< \frac {1+\sqrt 2}{m+2}$. 

Let $a=a_1-a_2$ and $b=b_1-b_2$. Then 
$$f(a_1, b_1)-f(a_2, b_2)=f(a_1-a_2, b_1-b_2)=f(a, b)$$
$0<f(a,b)\le \frac {1+\sqrt 2}{m+2}$, and $|a| \le m, |b| \le m.$ This
completes the proof.

\bigskip
\begin{enumerate}
\item[2.] Let $A$ be the set of all non-negative integers. Find all
functions $f: A\to A$ satisfying the following two conditions:

(i) for any $m, n \in A,$
$$2f(m^2+n^2)=\{f(m)\}^2+\{f(n)\}^2$$

(ii) for any $m, n \in A$ with $m\ge n,$
$$f(m^2) \ge f(n^2).$$
\end{enumerate} 

{\bf Solution}

From (i) we have
\begin{eqnarray*}
& &2f(m^2)=\{f(m)\}^2+\{f(0)\}^2\\
& &2f(n^2)=\{f(n)\}^2+\{f(0)\}^2
\end{eqnarray*}
and substrating two equations, we obtain
$$\{f(m)\}^2-\{f(n)\}^2=2\{f(m^2)-f(n^2)\}.$$
It follows that if $m\ge n$, then by (ii)  we  see that
$$f(m)\ge f(n).\leqno{(1)}$$
Meauwhile, if $m=n=0$, then we have $2 f(0)=\{f(0)\}^2$ and, $f(0)=0$ or
$f(0)=1$.

\medskip
Case I. \qquad $f(0)=1$.

From $2f(m^2)=\{f(m)\}^2+1$, we have 
$$f(2^{2^n})=\frac 12 [\{f(2^{2^{n-1}})\}^2+1].\leqno{(2)}$$
From $2f(1)=\{f(1)\}^2+1$ we have $\{f(1)-1\}^2=0$ and $f(1)=1$. From (2)
we have 
$$ f(2)=1,\ \ f(2^2)=1, \cdots , \ \text{etc.}$$
In general, $f(2)=f(2^2)=\cdots =f(2^{2^n})=1\ \ (n\ge 0)$.

For any positive integer $m$, there exists an integer $n$ such that
$2^{2^{n-1}} \le m<2^{2^n}$.

From (1) we have $1=f(2^{2^{n-1}}) \le f(m)\le f(2^{2^n})=1$ and
finally $f(m)=1$. 

\medskip
Case II.  $f(0)=0$.

From $2f(m^2)=\{f(m)\}^2$ we have 
$$\frac {f(m^2)}2=\{\frac {f(m)}2\}^2.\leqno{(3)}$$
Meanwhile, $f(2)=\{f(1)\}^2$. It follows that 
$$\frac {f(2^{2^n})}2=\Bigl \{\frac
{f(2^{2^{n-1}})}2\Bigr \}^2=\Bigl \{\frac
{f(2^{2^{n-2}})}2\Bigr \}^{2^2}=\cdots =\Bigl \{\frac
{f(2)}2\Bigr \}^{2^n}=\frac {\{f(1)\}^{2^{n+1}}}{2^{2^n}}\leqno{(4)}$$ 
From $2f(1)=\{f(1)\}^2$ we have $f(1)=0$ or $f(1)=2$. 

(i) $f(1)=0$.

From (4) we have $f(2^{2^n})=0\ \ (n\ge 0)$. Similarly, $f(n)=0\ \ (n\ge
0)$.

(ii) $f(1)=2$.

From (4) we have $f(2^{2^n})=2\cdot 2^{2^n}\ \ (n\ge 0)$. By (3) we
have $f(m)$ is even.
\begin{eqnarray*}
\{f(m+1)\}^2=\ &2 f((m+1)^2)\ge 2f(m^2+1)=\{f(m)\}^2+\{f(1)\}^2 \\
> & \{f(m)\}^2\\
& \ \text{implies that}\ \ f(m+1)>f(m).
\end{eqnarray*}

It follows that $f(m+1)-f(m)-2\ge 0$, and
$\sum_{m=0}^{2^{2^{n-1}}}\{f(m+1)-f(m)-2\}=f(2^{2^n})-f(0)-2\cdot
2^{2^n}=0$.  Now we have $f(m+1)-f(m)-2=0$ for all $m=0, 1, \cdots
2^{2^n}-1$. Since $n$ is arbitrary, we obtain $f(m+1)=f(m)+2$ for all $m=0,
1, 2, \cdots $. It follows that $f(m)=2m$. 
\smallskip
Answer. \qquad $f(n)\equiv 1;\ \ f(n)\equiv 0;\ \ f(n)\equiv 2n.$

\bigskip
\begin{enumerate}
\item[3.] Let $\triangle ABC$ be an equilateral triangle of side length
$1, D$ a point on $BC$, and let $r_1, r_2$, be inradii of triangles $ABD,
ADC$, respectively. Express $r_1r_2$ in terms of $p=BD$, and find the
maximum of $r_1r_2$. 
\end{enumerate}

{\bf Solution} 

Let $l=AD$. In $\triangle ABD$, we have \newline
\noindent $l^2=1+p^2-2p \cos {60}^\circ =p^2-p+1$. \newline
\noindent Since the area of $\triangle ABC$ is ${\sqrt 3}/4$, \newline
\noindent in $\triangle ABD$ and $\triangle ADC$, we obtain 
$$r_1 \frac{1+p+l}2=\frac {\sqrt 3}4p,\  \ r_2\frac {2-p+l}2=\frac {\sqrt
3}4(1-p).\qquad\qquad\qquad\qquad\quad $$ 
Now we have 
\begin{eqnarray*}
r_1r_2&=& \frac 34\frac {p(1-p)}{(1+p+l)(2-p+l)}=\frac 34\frac
1{(1+p)(2-p)+l^2+3l}\\
&=& \frac 34 \frac {p(1-p)}{2-p-p^2+p^2-p+1+3l}=\frac 14\frac
{p(1-p)}{1+l}\\
&=& \frac 14 \frac {p(1-p)(1-l)}{4(1-l^2)}=\frac 14 \frac
{p(1-p)(1-l)}{1-p^2+p-1}=\frac 14 (1-l)\\
&=& \frac 14 \left (1-\sqrt {p^2-p+1}\right )=\frac 14 \left (1-\sqrt {(p-
1/2)^2+ 3/4}\right )\\
&\le & \frac 14 \Bigl (1-\frac {\sqrt 3}2\Bigr )=\frac {2-\sqrt 3}8.
\end{eqnarray*}

Answer.\qquad $r_1r_2=\frac 14 (1-\sqrt {p^2-p+1})$; 
the maximum of $r_1r_2$ is $\frac {2-\sqrt 3}8$ when $p=\frac 12$. 

\bigskip
\begin{enumerate}
\item[4.] Let $O$ and $R$ be the circumcenter and the circumradius of
$\triangle ABC$, respectively, and let $P$ be any point on the plane $ABC$.
Let perpenticulars $PA_1, PB_1, PC_1$, be dropped to the three sides $BC,
CA, AB$. Express $\frac {(\triangle A_1B_1C_1)}{(\triangle ABC)}$ in terms
of $R$ and $d=OP$, where $(\triangle ABC)$ is the area of $\triangle ABC$. 
\end{enumerate}

{\bf Solution}

A quadrilateral $PA_1CB_1$ is inscribed in a circle of a diameter $CP$. It
follows that $A_1B_1=PC\cdot \sin C$. Similarly, in a quadrilateral
$PB_1AC_1$ we have $B_1C_1=AP\cdot\sin A$. 

Let $D$ be the intersection point between\newline
\noindent a line $CP$ and the circumcircle of $\triangle ABC$.\newline
\noindent Since $\angle PB_1C_1=\angle PCA_1=\angle DAB$ and \newline
\noindent $\angle PB_1C_1=\angle PAC$, we see that \newline
\noindent $\angle A_1B_1C_1=\angle PB_1A_1+\angle PB_1C_1=\angle DAB+\angle
PAC_1=\angle PAD$. \newline
\noindent From $\triangle PAD$ we have ${AP}/{\sin B}={DP}/{\sin(\angle
PAD)}={DP}/{\sin\angle A_1B_1C_1}$ because $\angle PDA=\angle B$. 

It follow that $AP\cdot \sin(\angle A_1B_1C_1)=DP\sin B$. Now we have
\begin{eqnarray*}
(\triangle A_1B_1C_1)&= & \frac 12 A_1B_1\cdot B_1C_1\cdot \sin (\angle
A_1B_1C_1)\\
&= &\frac 12 (PC\cdot \sin C)\cdot (AP\cdot \sin A)\cdot \sin(\angle
A_1B_1C_1)\\
&= &\frac 12 PC\cdot \sin C\cdot \sin A\cdot DP\sin B\\
&= &\frac 12 PC\cdot DP\cdot \sin A\sin B\sin C.
\end{eqnarray*}
Since $(\triangle ABC) =2R^2\sin A\sin B\sin C$, we obtain
$$\frac {(\triangle A_1B_1C_1)}{(\triangle ABC)}=\frac 1{4R^2}\ PC\cdot
DP.$$
If $P$ lies in the interior of a circle $O$, then $PC\cdot DP=R^2-d^2$,
and if $P$ lies in the exterior of a circle $O$, then $PC\cdot
DP=d^2-R^2$. Finally, if $P$ lies on the circle $O$, then $A_1, B_1, C_1$
are collinear (Simson's line) and $(\triangle A_1B_1C_1)=0$. 
In summary, we obtain
$$\frac {(\triangle A_1B_1C_1)}{(\triangle ABC)}=\frac {|R^2-d^2|}{4R^2}.$$

\medskip
\begin{enumerate}
\item[5.] Let $p$ be a prime number such that 

(i) $p$ is the greatest common divisor of $a$ and $b$;

(ii) $p^2$ is a divisor of $a$. Prove that the polynomial
$x^{n+2}+ax^{n+1}+bx^n+a+b$ cannot be decomposed into the product of two
polynomials with integeral coefficients, whose degrees are greater tham one.
\end{enumerate}

{\bf Solution}

(Eisenstein Theorem) 
Let $f(x)=c_0 x^n+c_1 x^{n-1}+\cdots +c_{n-1}x+c_n$ be a polynomial  with
integral coefficients. If there exists a prime number $p$ so that
$p\nmid c_0, p| c_i\ \ (i=1, 2, \cdots , n)$, and $p^2\nmid c_n$, then
$f(x)$ cannot be decomposed into the product of two polynomials with of
lower degrees with integral coefficients.

(Proof) Let 
$$\Bigl (\sum_{i=0}^{n+1} a_i x^i\Bigr )\Bigl (\sum_{j=0}^{n+1}
b_jx^j\Bigr )=c_0x^n+c_1x^{n-1}+\cdots +c_{n-1} x+c_n.$$
From $a_0b_0=c_n, p^2\nmid c_n$ we have $p| a_0, p\nmid b_0$ or
$p\nmid a_0, p|b_0$. 

\bigskip
Without loss of generality, we may assume that $p| a_0, \ p\nmid b_0$. 

Comparing the coefficients of $x$, we have $a_0b_1+a_1b_0=c_1$. It follows
that $p|a_1b_0$ and $p|a_1$. Suppose $p|a_0, p|a_1, \cdots , p|a_{k-1}$.
Then comparing the coefficients of $x^k$, we have $p|\sum_{i=0}^k a_i
b_{k-i}$ and $p|a_kb_0$. It follows that $p|a_k$. Now we have $p| a_i
(i=0, 1, 2, \cdots , n)$. If  $\text{deg} (\sum_{i=0}^{n+1} a_i)=s$, then
$\text{deg} (\sum_{i=0}^{n+1} b_ix^i)=n-s$. Now we have $a_sb_{n-s}=c_0$
and $p|c_0$. This is a contradiction, completing proof.

\medskip
Since $p\nmid 1, p| a, p| b, p^2\nmid (a+b)$, by Eisenstein Theorem we
see that the required proposition holds.

\medskip
\begin{enumerate}
\item[6.] Let $m, n$ be positive integers with $1\le n\le m-1$. A box
is locked with several padlocks, all of which must be opened to open the
box, and all of which have different keys. $m$ people each have keys to
some of the locks. No $n$ people of them can open the box but any $n+1$
people can open the box. Find the smallest number $l$ of locks and then the
number of keys for which this is possible.
\end{enumerate}

{\bf Solution}

Let $m$ people be denoted by $A_1, A_2, \cdots , A_m$ and write on each
lock the symbols of people who do not hold a key for that lock. Since any
$n+1$ people can open the box, no lock has over $n+1$ symbols on it. For
any $n$ people, there is at least one lock with the corresponding $n$
symbols. Thus the smallest number $l$ of locks is ${}_mC_n$ and any people
must have the same number of keys ($k={}_{m-1}C_n$).


\end{document}