%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Fail BW08SOL.TEX -- "Baltic Way 2008" problems with solutions
%
\documentclass[alfa,fleqn]{eeolymp_a4}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{graphicx}
\usepackage{a4wide}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\newcounter{theproblem}
\newcommand{\problem}[1]{\addtocounter{theproblem}1\noindent {\bf Problem \arabic{theproblem}. }#1 %\hspace{1em}#1 %\bigskip
}
\setlength{\mathindent}{4em}
\setlength{\topmargin}{0cm}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{24cm}
\setlength{\arraycolsep}{2pt}
\setlength{\footskip}{16mm}
\begin{document}
\vspace{-3em}
\begin{center}
%\sffamily\bfseries
\huge Baltic Way 2008\\
\Large Gda\'nsk, November 8, 2008
\large Problems and solutions
\end{center}
\problem{Determine all polynomials $p(x)$ with real coefficients such that
\begin{equation*}
p((x+1)^3) = (p(x)+1)^3
\end{equation*}
and
\begin{equation*}
p(0) = 0.
\end{equation*}
}
\textbf{Answer:} $p(x)=x$.
\textbf{Solution:} Consider the sequence defined by
\begin{equation*}
\begin{cases}
a_0 = 0 \\
a_{n+1} = (a_n+1)^3 .
\end{cases}
\end{equation*}
It follows inductively that $p(a_n)=a_n$. Since the polynomials
$p$ and $x$ agree on infinitely many points, they must be equal,
so $p(x)=x$.
\problem{Prove that if the real numbers $a$, $b$ and $c$ satisfy $a^2+b^2+c^2=3$ then
\begin{equation*}
\frac{a^2}{2+b+c^2}+\frac{b^2}{2+c+a^2}+\frac{c^2}{2+a+b^2}
\ge\frac{(a+b+c)^2}{12}\,.
\end{equation*}
When does equality hold?}
\textbf{Solution:} Let $2+b+c^2=u$, $2+c+a^2=v$, $2+a+b^2=w$. We
note that it follows from $a^2+b^2+c^2=3$ that $a,b,c\ge-\sqrt{3}>-2$.
Therefore, $u$, $v$ and $w$ are positive. From the Cauchy-Schwartz
inequality we get then
\begin{align*}
(a+b+c)^2&=\left(\frac a{\sqrt{u}}\sqrt{u}+\frac b{\sqrt{v}}\sqrt{v}
+\frac c{\sqrt{w}}\sqrt{w}\right)^2\\
&\le\left(\frac{a^2}u+\frac{b^2}v+\frac{c^2}w\right)(u+v+w)\,.
\end{align*}
Here,
\[
u+v+w=6+a+b+c+a^2+b^2+c^2=9+a+b+c\,.
\]
Invoking once more the Cauchy-Schwartz inequality, we get
\[
(a+b+c)^2=(a\cdot1+b\cdot1+c\cdot1)^2
\le(a^2+b^2+c^2)(1+1+1)=9\,,
\]
whence $a+b+c\le3$ and $u+v+w\le12$. The proposed inequality follows.
In the second application above of the Cauchy-Schwartz inequality,
equality requires $a=b=c$. If this is satified, $u+v+w=12$, which is
equivalent to $a+b+c=3$, requires $a=b=c=1$. It is seen by a direct
check that equality holds in the proposed inequality in this case.
\problem{Does there exist an angle $\alpha\in(0,\pi/2)$
such that $\sin\alpha$, $\cos\alpha$, $\tan\alpha$ and $\cot\alpha$,
taken in some order, are consecutive terms of an arithmetic progression?}
\textbf{Answer:} No.
\textbf{Solution:} Suppose that there is an $x$ such that $0\sin x$, we can reduce by $\cos
x-\sin x$ and get
\[
1=\frac{\cos x+\sin x}{\cos x\sin x}=\frac{1}{\sin
x}+\frac{1}{\cos x}\mbox{.}
\]
But $0<\sin x<1$ and $0<\cos x<1$, hence $\frac{1}{\sin x}$ and
$\frac{1}{\cos x}$ are greater than $1$ and their sum cannot equal
$1$, a contradiction.
If $x>\frac{\pi}{4}$ then $0<\frac{\pi}{2}-x<\frac{\pi}{4}$. As the sine,
cosine, tangent and cotangent of $\frac{\pi}{2}-x$ are equal to the sine,
cosine, tangent and cotangent of $x$ in some order, the
contradiction carries over to this case, too.
\textbf{Solution 2:} The case $x\le\frac{\pi}{4}$ can also be handled
as follows. Consider two cases according to the order of the
intermediate two terms.
If the order is $\sin x<\tan x<\cos x<\cot x$ then using AM-GM
gives
\[
\cos x=\frac{\tan x+\cot x}{2}>\sqrt{\tan x\cdot\cot x}=\sqrt{1}=1
\]
which is impossible.
Suppose the other case, $\sin x<\cos x<\tan x<\cot x$. From
equalities
\[
\frac{\sin x+\tan x}{2}=\cos x\quad \mathrm{and} \quad\frac{\cos x+\cot
x}{2}=\tan x,
\]
one gets
\begin{align*}
&\tan x(\cos x+1)=2\cos x\mbox{,}\\
&\cot x(\sin x+1)=2\tan x\mbox{,}
\end{align*}
respectively. By multiplying the corresponding sides, one obtains
$(\cos x+1)(\sin x+1)=4\sin x$, leading to $\cos x\sin x+\cos
x+1=3\sin x$. On the other hand, using $\cos x>\sin x$ and AM-GM
gives
\[
\cos x\sin x+\cos x+1>\sin^2x+\sin x+1\ge 2\sin x+\sin x=3\sin
x\mbox{,}
\]
a contradiction.
\problem{The polynomial $P$ has integer coefficients and $P(x)=5$ for five different integers $x$.
Show that there is no integer $x$ such that $-6\le P(x)\le4$ or $6\le P(x)\le16$.}
\textbf{Solution:} Assume $P(x_k)=5$ for different integers $x_1$, $x_2$,
\dots, $x_5$. Then $$P(x)-5=\prod_{k=1}^5(x-x_k)Q(x),$$ where $Q$
is a polynomial with integral coefficients. Assume $n$ satisfies
the condition in the problem. Then $|n-5|\le 11$. If $P(x_0)=n$
for some integer $x_0$, then $n-5$ is a product of six non-zero
integers, five of which are different. The smallest possible
absolute value of a product of five different non-zero integers is
$1^2\cdot 2^2\cdot 3=12$.
\problem{Suppose that Romeo and Juliet each have a regular
tetrahedron to the vertices of which some positive real numbers are
assigned. They associate each edge of their tetrahedra
with the product of the two numbers assigned to its end points. Then
they write on each face of their tetrahedra the sum of the
three numbers associated to its three edges.
The four numbers written on the faces of Romeo's
tetrahedron turn out to coincide with the four numbers written on Juliet's
tetrahedron. Does it follow that the four
numbers assigned to the vertices of Romeo's tetrahedron are
identical to the four numbers assigned to the vertices of
Juliet's tetrahedron?}
\textbf{Answer:} Yes.
\textbf{Solution:} Let us prove that this conclusion can in fact be
drawn. For this purpose we denote the numbers assigned to the
vertices of Romeo's tetrahedron by $r_1$, $r_2$, $r_3$, $r_4$ and
the numbers assigned to the vertices of Juliette's tetrahedron by
$j_1$, $j_2$, $j_3$, $j_4$ in such a way that
\begin{align}
r_2r_3+r_3r_4+r_4r_2 &= j_2j_3+j_3j_4+j_4j_2 \\
r_1r_3+r_3r_4+r_4r_1 &= j_1j_3+j_3j_4+j_4j_1 \\
r_1r_2+r_2r_4+r_4r_1 &= j_1j_2+j_2j_4+j_4j_1 \\
r_1r_2+r_2r_3+r_3r_1 &= j_1j_2+j_2j_3+j_3j_1
\end{align}
We intend to show that $r_1=j_1$, $r_2=j_2$, $r_3=j_3$ and
$r_4=j_4$, which clearly suffices to establish our claim. Now let
\[
R=\{i\,|\,r_i>j_i\}
\]
denote the set indices where Romeo's corresponding number is
larger and define similarly
\[
J=\{i\,|\,r_i2$, then w.l.o.g. $\{1, 2, 3\}\subseteq R$, which
easily contradicted $(4)$. Therefore $|R|\le2$, so let us
suppose for the moment that $|R|=2$. Then w.l.o.g. $R=\{1, 2\}$,
i.e. $r_1>j_1$, $r_2>j_2$, $r_3\le j_3$, $r_4\le j_4$. It
follows that $r_1r_2-r_3r_4>j_1j_2-j_3j_4$, but $(1)+(2)-(3)-(4)$
actually tells us that both sides of this strict inequality are
equal. This contradiction yields $|R|\le 1$ and replacing the
roles Romeo and Juliet played in the argument just performed we
similarly infer $|J|\le 1$. For these reasons at least two of
the four desired equalities hold, say $r_1=1_1$ and $r_2=j_2$. Now
using $(3)$ and $(4)$ we easily get $r_3=j_3$ and $r_4=j_4$ as
well.
\problem{Find all finite sets of positive integers with at least two elements such that for
any two numbers $a$, $b$ ($a>b$) belonging to the set, the number
$\frac{b^2}{a-b}$ belongs to the set, too.}
\textbf{Answer:} $X=\{a,2a\}$, where $a$ is an arbitrary nonnegative
integer.
\textbf{Solution:} Let $X$ be a set we seek for, and $a$ be its minimal element. For
each other element $b$ we have $\frac{a^2}{b-a}\ge a$, hence
$b\le 2a$. Therefore all the elements of $X$ belong to the
interval $[a,2a]$. So the quotient of any two elements of $X$ is
at most 2.
Now consider two biggest elements $d$ and $c$, $c 1040$ and
$12\cdot79<1001$.
\item $13\cdot k \in A$ for $k\ge 80$. As $13\cdot k\ge
13\cdot 80=1040$, we are done.
\end{itemize}
Now take $A=\left\{1001, 1008, 1012, 1035, 1040\right\}$. The prime
factorizations are $1001=7\cdot11\cdot13$, $1008=7\cdot2^4\cdot3^2$,
$1012=2^2\cdot11\cdot23$, $1035=5\cdot3^2\cdot23$, $1040=2^4\cdot5\cdot13$. The sum
of exponents of each prime occurring in these representations is
even. Thus the product of elements of $A$ is a perfect square.
\problem{Suppose that the positive integers $a$ and $b$ satisfy the
equation
\begin{equation*}
a^b - b^a = 1008.
\end{equation*}
Prove that $a$ and $b$ are congruent modulo $1008$.\\
}
\textbf{Solution:} Observe that $1008= 2^4\cdot 3^2\cdot 7$. First we show that $a$
and $b$ cannot both be even. For suppose the largest of them were
equal to $2x$ and the smallest of them equal to $2y$, where $x\ge
y\ge 1$. Then
\[
\pm 1008 = (2x)^{2y} - (2y)^{2x},
\]
so that $2^{2y}$ divides 1008. It follows that $y\le 2$. If
$y=2$, then $\pm 1008 = (2x)^4 - 4^{2x}$, and
\[
\pm 63 = x^4 - 4^{2x-2} = (x^2 + 4^{x-1})( x^2-4^{x-1}).
\]
But $x^2-4^{x-1}$ is easily seen never to divide 63; already at
$x=4$ it is too large. Suppose that $y=1$. Then $\pm
1008=(2x)^2-2^{2x}$, and
\[
\pm 252 = x^2 - 2^{2x-2} = (x+2^{x-1})(x-2^{x-1}).
\]
This equation has no solutions. Clearly $x$ must be even.
$x=2,4,6,8$ do not work, and when $x\ge 10$, then
$x+2^{x-1}>252$.
We see that $a$ and $b$ cannot both be even, so they must both be
odd. They cannot both be divisible by 3, for then $1008=a^b-b^a$
would be divisible by 27; therefore neither of them is. Likewise,
none of them is divisible by 7.
Everything will now follow from repeated use of the following
fact, where $\phi$ denotes Euler's totient function:
\emph{If $n\mid 1008$, $a$ and $b$ are relatively prime to both
$n$ and $\phi(n)$, and $a\equiv b \mod \phi(n)$, then also
$a\equiv b\mod n$.}
To prove the fact, use Euler's Totient Theorem: $a^{\phi(n)}\equiv
b^{\phi(n)}\equiv 1 \mod n$. From $a\equiv b\equiv d \mod\phi(n)$,
we get
\[
0\equiv 1008 = a^b-b^a \equiv a^d - b^d \mod n,
\]
and since $d$ is invertible modulo $\phi(n)$, we may deduce that
$a\equiv b\mod n$.
Now begin with $a\equiv b\equiv 1\mod 2$. From $\phi(4)=2$,
$\phi(8)=4$ and $\phi(16)=8$, we get congruence of $a$ and $b$
modulo 4, 8 and 16 in turn. We established that $a$ and $b$ are
not divisible by 3. Since $\phi(3)=2$, we get $a\equiv b\mod 3$,
then from $\phi(9)=6$, deduce $a\equiv b\mod 9$. Finally, since
$a$ and $b$ are not divisible by 7, and $\phi(7)=6$, infer
$a\equiv b\mod 7$.
Consequently, $a\equiv b\mod 1008$. We remark that the equation
possesses at least one solution, namely $1009^1-1^{1009}=1008$. It
is unknown whether there exist others.
\problem{For a positive integer $n$, let $S(n)$ denote the sum of its digits.
Find the largest possible value of the expression
$\displaystyle\frac{S(n)}{S(16n)}$.
}
\textbf{Answer:} 13
\textbf{Solution:} It is obvious that $S(ab)\le S(a)S(b)$ for all positive integers $a$ and $b$. From here we get
\[
S(n)=S(n\cdot 10000)=S(16n\cdot 625)\le S(16n)\cdot 13;
\]
so we get $\displaystyle\frac{S(n)}{S(16n)}\le 13$.
For $n = 625$ we have an equality. So the largest value is $13$.
\problem{Consider a subset $A$ of 84 elements of the set
$\{1,\,2,\,\dots,\,169\}$ such that no two elements in the set
add up to 169. Show that $A$ contains a perfect
square.}
\textbf{Solution:} If $169\in A$, we are done. If not, then
\[
A\subset\bigcup_{k=1}^{84}\{k,\,169-k\}.
\]
Since the sum of the
numbers in each of the sets in the union is 169, each set contains
at most one element of $A$; on the other hand, as $A$ has 84
elements, each set in the union contains exactly one element of
$A$. So there is an $a\in A$ such that $a\in\{25,\,144\}$. $a$ is
a perfect square.
\problem{In a school class with $3n$ children,
any two children make a common present to exactly one other child.
Prove that for all odd $n$ it is possible that the following holds:\vspace{-0.5em}
For any three children $A$, $B$ and $C$ in the class,
if $A$ and $B$ make a present to $C$ then $A$ and $C$ make a present to $B$.}
\textbf{Solution:} Assume there exists a set $\mathcal{S}$ of sets of three children such
that any set of two children is a subset of exactly one member of
$\mathcal{S}$, and assume that the children $A$ and $B$ make a common
present to $C$ if and only if $\{A,B,C\}\in\mathcal{S}$. Then it is
true that any two children $A$ and $B$ make a common present to exactly
one other child $C$, namely the unique child such that
$\{A,B,C\}\in\mathcal{S}$. Because $\{A,B,C\}=\{A,C,B\}$ it is also
true that if $A$ and $B$ make a present to $C$ then $A$ and $C$ make a
present to $B$. We shall construct such a set $\mathcal{S}$.
Let $A_1$, \ldots , $A_n$, $B_1$, \ldots $B_n$, $C_1$, \ldots , $C_n$
be the children, and let the following sets belong to $\mathcal{S}$.
(1) $\{A_i,B_i,C_i\}$ for $1\le i\le n$. (2) $\{A_i,A_j,B_k\}$,
$\{B_i,B_j,C_k\}$ and $\{C_i,C_j,A_k\}$ for $1\le i 2008.
\begin{center}
%\includegraphics[width=.4\textwidth]{problem15-1}
\includegraphics{problem15-1}
\end{center}
The square $76\times 76$ is not enough. If it was, consider the "circumferences" of the 1004 dominoes of size $2\times 3$, see figure; they should fit inside $77\times 77$ square without overlapping. But
$6\cdot 1004=6024>5929=77\cdot 77$.
\begin{center}
\includegraphics[width=.15\textwidth]{problem15-2}
\end{center}
\problem{Let $ABCD$ be a parallelogram. The circle with diameter $AC$
intersects the line $BD$ at points $P$ and $Q$. The perpendicular to the
line $AC$ passing through the point $C$ intersects the lines $AB$ and
$AD$ at points $X$ and $Y$, respectively. Prove that the points $P$,
$Q$, $X$ and $Y$ lie on the same circle.}
\textbf{Solution:} If the lines $BD$ and $XY$ are parallel the statement is trivial.
Let $M$ be the intersection point of $BD$ and $XY$.
By Intercept Theorem $MB/MD=MC/MY$ and $MB/MD=MX/MC$, hence
$MC^2=MX\cdot MY$. By the circle property $MC^2=MP\cdot MQ$ (line
$MC$ is tangent and line $MP$ is secant to the circle). Therefore
we have $MX\cdot MY=MP\cdot MQ$ and the quadrilateral $PQYX$ is
inscribed.
\problem{Assume that $a$, $b$, $c$ and $d$ are the sides of a
quadrilateral inscribed in a given circle. Prove that the product
$(ab+cd)(ac+bd)(ad+bc)$ acquires its maximum when the quadrilateral
is a square.}
\textbf{Solution:} Let $ABCD$ be the quadrilateral, and let
$AB=a$, $BC=b$, $CD=c$, $AD=d$, $AC=e$, $BD=f$. Ptolemy's Theorem
gives $ac+bd=ef$. Since the area of triangle $ABC$ is $abe/4R$, where
$R$ is the circumradius, and similarly the area of triangle $ACD$, the
product $(ab+cd)e$ equals $4R$ times the area of quadrilateral $ABCD$.
Similarly, this is also the value of the product $f(ad+bc)$, so
$(ab+cd)(ac+bd)(ad+bc)$ is maximal when the quadrilateral has maximal
area. Since the area of the quadrilateral is equal to $\frac12ef\sin
u$, where $u$ is one of the angles between the diagonals $AC$ and
$BD$, it is maximal when all the factors of the product $de\sin u$ are
maximal. The diagonals $d$ and $e$ are maximal when they are diagonals
of the circle, and $\sin u$ is maximal when $u=90^\circ$. Thus,
$(ab+cd)(ac+bd)(ad+bc)$ is maximal when $ABCD$ is a square.
\problem{Let $AB$ be a diameter of a circle $S$, and let $L$ be the tangent at $A$.
Furthermore, let $c$ be a fixed, positive real, and consider
all pairs of points $X$ and $Y$ lying on $L$, on opposite sides of $A$, such
that
$|AX|\cdot |AY|=c$. The lines $BX$ and $BY$
intersect $S$ at points $P$ and $Q$, respectively. Show that all the
lines $PQ$ pass through a common point.}
\textbf{Solution:} Let $S$ be the unit circle in the $xy$-plane with origin $O$, put
$A=(1,0)$, $B=(-1,0)$, take $L$ as the line $x=1$, and suppose
$X=(1,2p)$ and $Y=(1,-2q)$, where $p$ and $q$ are positive real
numbers with $pq=\frac{c}{4}$. If $\alpha= \angle ABP$ and $\beta=
\angle ABQ$, then $\tan \alpha=p$ and $\tan \beta=q$.
Let $PQ$ intersect the $x$-axis in the point $R$. By the Inscribed
Angle Theorem, $\angle ROP= 2\alpha$ and $\angle ROQ=2\beta$. The
triangle $OPQ$ is isosceles, from which $\angle OPQ=\angle
OQP=90^\circ-\alpha-\beta$, and $\angle
ORP=90^\circ-\alpha+\beta$. The Law of Sines gives
\[
\frac{OR}{\sin\angle OPR} = \frac{OP}{\sin \angle ORP} ,
\]
which implies
\begin{align*}
OR &= \frac{\sin\angle OPR}{\sin \angle ORP} = \frac{\sin
(90^\circ-\alpha-\beta)}{\sin(90^\circ-\alpha+\beta)} =
\frac{\cos (\alpha+\beta)}{\cos(\alpha-\beta)} \\
&= \frac{\cos \alpha\cos\beta -
\sin\alpha\sin\beta}{\cos\alpha\cos\beta + \sin\alpha\sin\beta} =
\frac{1-\tan\alpha\tan\beta}{1+\tan\alpha\tan\beta} \\
& = \frac{1-pq}{1+pq} = \frac{1-\frac c4}{1+\frac c4} =
\frac{4-c}{4+c}.
\end{align*}
Hence the point $R$ lies on all lines $PQ$.
\textbf{Solution 2:} Perform an inversion in the point $B$. Since angles are
preserved under inversion, the problem transforms into the
following: Let $S$ be a line, let the circle $L$ be tangent to it
at point $A$, with $\infty$ as the diametrically opposite point.
Consider all points $X$ and $Y$ lying on $L$, on opposite sides of
$A$, such that if $\alpha=\angle ABX$ and $\beta=\angle ABY$, then
$\tan\alpha\tan\beta=\frac{c}{4}$. The lines $X\infty$ and
$Y\infty$ will intersect $S$ in points $P$ and $Q$, respectively.
Show that all the circles $PQ\infty$ will pass through a common
point.
To prove this, draw the line through $A$ and $\infty$, and define
$R$ as the point lying on this line, opposite to $\infty$, and at
distance $\frac{cr}{2}$ from $A$, where $r$ is the radius of $L$.
Since
\[
\tan \alpha = \frac{|AP|}{2r}, \qquad \tan\beta = \frac{|AQ|}{2r},
\]
we have
\[
\frac{c}{4} = \tan\alpha\tan\beta = \frac{|AP||AQ|}{4r^2},
\]
so that $|AP|=\frac{cr^2}{|AQ|}$, whence
\[
\tan \angle \infty RP = \frac{|AP|}{|AR|} =
\frac{\frac{cr^2}{|AQ|}}{\frac{cr}{2}} = \frac{2r}{|AQ|} = \tan
\angle\infty QP.
\]
Consequently, $\infty$, $P$, $Q$, and $R$ are concyclic.
\problem{In a circle of diameter $1$, some chords are drawn. The sum of
their lengths is greater than $19$. Prove that there is a diameter
intersecting at least $7$ chords.}
\textbf{Solution:} For each hord consider the smallest arc subtended by it and the symmetric image of this arc accordingly to the center. The sum of lengths of all these arcs is more than $19\cdot2=38$. As $\frac{38}{\pi\cdot1}>12$, there is a point on the circumference belonging to $>\frac{12}{2}$ original arcs, so it belongs to $\ge 7$ original arcs. We can take a diameter containing this point.
\problem{Let $M$ be a point on $BC$ and $N$ be a point on $AB$ such
that $AM$ and $CN$ are angle bisectors of the triangle $ABC$. Given that
\begin{equation*}
\frac{\angle BNM}{\angle MNC} = \frac{\angle BMN}{\angle NMA},
\end{equation*}
prove that the triangle $ABC$ is isosceles.}
\begin{center}
\includegraphics[width=.4\textwidth]{problem20}
\end{center}
\textbf{Solution:} Let $O$ and $I$ be the incentres of $ABC$ and $NBM$, respectively; denote angles as in the figure. We get
\[
\alpha+\beta=\varepsilon+\phi,\quad \gamma+\delta=2\alpha+2\beta,\quad \gamma=k\cdot\varepsilon,\quad \delta=k\cdot\phi.
\]
From here we get $k=2$. Therefore $\triangle NIM=\triangle NOM$, so $IO\,\bot\,NM$. In the triangle $NBM$ the bisector coincides with the altitude, so $BN=BM$. So we get
\[
\frac{AB\cdot BC}{AC+BC}=\frac{BC\cdot AB}{AB+AC}
\]
and $AB=BC$.
\end{document}