Solutions for JulyAugust, 2002 problems

157.

Prove that if the quadratic equation
${x}^{2}+\mathrm{ax}+b+1=0$ has nonzero integer solutions, then
${a}^{2}+{b}^{2}$ is a composite
integer.
Solution. Suppose that the integer roots are
$u$ and
$v$.
Then
$u+v=a$ and
$\mathrm{uv}=b+1$, whence
$\begin{array}{cc}{a}^{2}+{b}^{2}\hfill & =(u+v){}^{2}+(\mathrm{uv}1){}^{2}={u}^{2}+{v}^{2}+{u}^{2}{v}^{2}+1\hfill \\ \multicolumn{0}{c}{}& =({u}^{2}+1)({v}^{2}+1)\hspace{1em}.\hfill \end{array}$
Since each factor exceeds 1,
${a}^{2}+{b}^{2}$ is composite.
Comment. You should make sure that you are familiar with the
relationship between the coeffients and roots of polynomials; a
poor way to solve this problem is to use the quadratic formula.
Note that, if, say,
$u=0$, then
${a}^{2}+{b}^{2}$ can be prime; for
example, you get the value 5 when
$(u,v)=(0,2)$.

158.

Let
$f(x)$ be a polynomial with real coefficients for
which the equation
$f(x)=x$ has no real solution. Prove that the
equation
$f(f(x))=x$ has no real solution either.
Solution 1. Let
$g(x)=f(x)x$. Then,
$g(x)$ is a polynomial
that never vanishes. We argue that it must always have the same sign.
Suppose if possible that
$g(a)<0<g(b)$ for some reals
$a$ and
$b$. Since
$g(x)$, being a polynomial, is continuous, the Intermediate
Value Theorem applies and there must be a number
$c$ between
$a$ and
$b$ for which
$g(c)=0$, yielding a contradition.
Thus, either
$g(x)>0$ for all
$x$ or else
$g(x)<0$ for all
$x$. Then
$\begin{array}{cc}f(f(x))x\hfill & =f(f(x))f(x)+f(x)x\hfill \\ \multicolumn{0}{c}{}& =g(f(x))+g(x)\hfill \end{array}$
for all real
$x$. Since
$g$ never changes sign, both
$g(x)$ and
$g(f(x))$ have the same sign (either positive or negative) and
so their sum cannot vanish. Hence
$f(f(x))\ne x$ for any real
$x$.
Solution 2. Suppose, if possible, that
$f(f(a))=a$.
Let
$b=f(a)$. Then
$f(b)=a$. By hypothesis,
$b\ne a$.
Wolog, suppose that
$a<b$. Then
$f(a)a>0$ and
$f(b)b<0$. Since
$f(x)x$ is a polynomial, it is
continuous and so the Intermediate Value Theorem applies on
the closed interval
$[a,b]$. As it has opposite signs at the
endpoints of
$[a,b]$, it must vanish somewhere in the interior
of the interval. But then this contradicts the hypothesis.
Hence
$f(f(x))=x$ can have no real solutions.
Comment. It is important to highlight that
$f(x)$ is
a continuous function, as this is key to the result. (Can you
construct a counterexample where it is not assumed that
$f$ is a polynomial or continuous?) Several of you tried to
give a geometric argument for this, and apart from mangling
the terminology (e.g., not distinguishing between
a function and its graph, points and values), operated at too
intuitive a level. Notice that the statement
``
$f(x)>0$ or
$f(x)<0$ for all
$x$''
lacks a certain precision, as it
could be interpreted to mean that at any individual point
$x$,
one of the two alternatives occurs (the function does not vanish),
but that different alternative might occur at different points.

159.

Let
$0\le a\le 4$. Prove that the area of the
bounded region enclosed by the curves with equations
$y=1\Vert x1\Vert $
and
$y=\Vert 2xa\Vert $
cannot exceed
$\frac{1}{3}$.
Solution. In the situation that
$0\le a\le 1$,
the two curves intersect in the points
$(a/3,a/3)$ and
$(a,a)$, and the bounded region is the triangle with these
two vertices and the vertex
$(a/2,0)$. This triangle is
contained in the triangle with vertices
$(0,0)$,
$(1/2,0)$
and
$(1,1)$ with area
$1/4$. Hence, when
$0\le a\le 1$,
the area of the bounded region cannot exceed
$1/4$.
Let
$1\le a\le 3$. In this case, the bounded region is a
quadrilateral with the four vertices
$(a/3,a/3)$,
$(a/2,0)$,
$((a+2)/3,(4a)/3)$ and
$(1,1)$. Noting that
this quadrilateral is the result of removing two smaller
triangles from a larger one (draw a diagram!), we find that
its area is
$\begin{array}{cc}1\frac{1}{2}\xb7\frac{a}{3}\xb7\frac{a}{2}\hfill & \frac{1}{2}\xb7\frac{(4a)}{3}\xb7(2\frac{a}{2})\hfill \\ \multicolumn{0}{c}{}& =1\frac{{a}^{2}}{12}\frac{1}{12}(4a){}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{{a}^{2}4a+2}{6}=\frac{1}{3}\frac{(a2){}^{2}}{6}\hspace{1em},\hfill \end{array}$
whence we find that the area does not exceed
$1/3$ and is equal to
$1/3$ exactly when
$a=2$.
The case
$3\le a\le 4$ is the symmetric image of the case
$0\le a\le 1$ and we find that the area of the bounded region
cannot exceed
$1/4$.
Comment. This is not a difficult problem, but it does require
a lot of care in keeping the situation straight and the computations
sound. Always keep in mind completion of the square when it is a
matter of optimizing a quadratic. Use of calculus is more cumbersome
in such situations, and begs the question as to whether the optimum
is a maximum or a minimum. (You can lose points for not explicitly
resolving this issue.) R. Barrington Leigh solved the problem
by looking at the area between the graph of
$y=1\Vert x1\Vert \Vert 2xa\Vert $ and the
$x$axis. The equation of this curve with the absolute value signs
is equal to
$y=3xa$ for
$x\le a/2$, to
$y=ax$ when
$a/2\le x\le 1$ and
$a+23x$ when
$x\le 1$, with suitable modification when
$a\ge 2$. Because
at each value of
$x$, the difference in the ordinates remains the
same as in the original problem, the area here is the same as
the area between the two graphs of the problem. You might want
to try the problem in this way.

160.

Let
$I$ be the incentre of the triangle
$\mathrm{ABC}$ and
$D$ be the point of contact of the inscribed circle with the side
$\mathrm{AB}$. Suppose that
$\mathrm{ID}$ is produced outside of the triangle
$\mathrm{ABC}$ to
$H$ so that the length
$\mathrm{DH}$ is equal to the semiperimeter
of
$\Delta \mathrm{ABC}$. Prove that the quadrilateral
$\mathrm{AHBI}$
is concyclic if and only if angle
$C$ is equal to
${90}^{\u02c6}$.
Note. In the solutions that follow, we use the standard
notation that
$a$,
$b$,
$c$ are the respective lengths of the
sides
$\mathrm{BC}$,
$\mathrm{CA}$,
$\mathrm{AB}$,
$r$ is the inradius of the triangle and
$s$ is its semiperimeter (so that
$2s=a+b+c$). We note that
the area of the triangle is
$\mathrm{rs}$, that the distances from
the vertices
$A$,
$B$,
$C$ to the tangent points of the incircle
are respectively
$sa$,
$sb$,
$sc$, and that
$r=(sc)\mathrm{tan}(C/2)$.
If you are not familiar with these relationships, then regard them
as exercises.
Solution 1. The quadrilateral
$\mathrm{AHBI}$ is concyclic if and
only if
$\mathrm{DI}:\mathrm{DH}=\mathrm{DB}:\mathrm{DA}$, or equivalently,
$\mathrm{rs}=(sa)(sb)={s}^{2}s(a+b)+\mathrm{ab}={s}^{2}s(2sc)+\mathrm{ab}=s(cs)+\mathrm{ab}\hspace{1em}.$
The area of the triangle is
$\mathrm{rs}=\frac{1}{2}\mathrm{ab}\mathrm{sin}C=\mathrm{abt}(1+{t}^{2}){}^{1}$ and
$r=(sc)t$, where
$t=\mathrm{tan}C/2$.
Then the concylic condition is equivalent to
$\mathrm{rs}=\frac{\mathrm{rs}}{t}+\frac{\mathrm{rs}(1+{t}^{2})}{t}=\mathrm{rst}\hspace{1em},$
or
$t=1$. This is equivalent to
$C/2={45}^{\u02c6}$, and the
result follows.
Solution 2. The concyclic condition is equivalent to
$\mathrm{rs}=(sa)(sb)\&lrArr;4\mathrm{rs}=(c+ba)(c+ab)={c}^{2}{b}^{2}{a}^{2}+2\mathrm{ab}\hspace{1em}.$
We have, for any triangle, that
$2\mathrm{ab}\mathrm{sin}C=4\mathrm{rs}$ (four times the
area) and
${c}^{2}={a}^{2}+{b}^{2}2\mathrm{ab}\mathrm{cos}C$. Hence the concyclic
condition is equivalent to
$2\mathrm{ab}\mathrm{sin}C=2\mathrm{ab}(1\mathrm{cos}C)\&lrArr;\mathrm{sin}C+\mathrm{cos}C=1\hspace{1em}.$
If
$\mathrm{sin}C+\mathrm{cos}C=1$, then, by squaring,
$1+2\mathrm{sin}C\mathrm{cos}C=1\Rightarrow \mathrm{sin}2C=0$ so that
$C={90}^{\u02c6}$. On the other hand, if
$C={90}^{\u02c6}$, then
$\mathrm{sin}C+\mathrm{cos}C=1$. The result follows.
Comment. We can end the solution, keeping the equivalences to
the end, by noting that
$\mathrm{sin}C+\mathrm{cos}C=1\&lrArr;\mathrm{sin}(C+{45}^{\u02c6})=\sqrt{2}\&lrArr;C={90}^{\u02c6}\hspace{1em}.$
Solution 3. [A. Feizmohammadi]
$\angle \mathrm{AIB}={180}^{\u02c6}(\angle \mathrm{BAI}+\angle \mathrm{ABI})={180}^{\u02c6}\frac{\angle A+\angle B}{2}={90}^{\u02c6}+\frac{\angle C}{2}\hspace{1em}.$
Also,
$\mathrm{tan}\angle \mathrm{AHB}=\frac{(sa)/s+(sb)/s}{1(sa)(sb)/{s}^{2}}=\frac{(2sab)s}{(a+b)s\mathrm{ab}}=\frac{\mathrm{cs}}{(2sc)s\mathrm{ab}}=\frac{\mathrm{cs}}{2{s}^{2}\mathrm{cs}\mathrm{ab}}\hspace{1em}.$
Suppose that
$\angle C$ is right. Then
$\angle \mathrm{AIB}={135}^{\u02c6}$ and
${c}^{2}={a}^{2}+{b}^{2}\Rightarrow (a+b){}^{2}{c}^{2}=2\mathrm{ab}\Rightarrow (a+bc)(a+b+c)=2\mathrm{ab}\Rightarrow \mathrm{ab}=2s(sc)\hspace{1em},$
so that
$\mathrm{tan}\angle \mathrm{AHB}=\frac{\mathrm{cs}}{2{s}^{2}\mathrm{cs}2{s}^{2}+2\mathrm{cs}}=1\Rightarrow \angle \mathrm{AHB}={45}^{\u02c6}\hspace{1em}.$
Since angles
$\mathrm{AHB}$ and
$\mathrm{AIB}$ are supplementary,
$\mathrm{AHBI}$ is concyclic.
On the other hand, suppose that
$\mathrm{AHBI}$ is concyclic. Then
$\begin{array}{cc}\sqrt{s(sa)(sb)(sc)}\hfill & =(sa)(sb)=\mathrm{rs}\Rightarrow (sa)(sb)=s(sc)\hfill \\ \multicolumn{0}{c}{}& \Rightarrow \mathrm{ab}=(a+bc)s\Rightarrow 2\mathrm{ab}=(a+b){}^{2}{c}^{2}\hfill \\ \multicolumn{0}{c}{}& \Rightarrow {a}^{2}+{b}^{2}={c}^{2}\hspace{1em},\hfill \end{array}$
so that
$\angle \mathrm{ACB}$ is right.

161.

Let
$a,b,c$ be positive real numbers for which
$a+b+c=1$. Prove that
$\frac{{a}^{3}}{{a}^{2}+{b}^{2}}+\frac{{b}^{3}}{{b}^{2}+{c}^{2}}+\frac{{c}^{3}}{{c}^{2}+{a}^{2}}\ge \frac{1}{2}\hspace{1em}.$
Solution. Observe that, by the arithmeticgeometric means
inequality
$\mathrm{ab}\le \frac{1}{2}({a}^{2}+{b}^{2})$, so that
$\frac{{a}^{3}}{{a}^{2}+{b}^{2}}=ab\frac{\mathrm{ab}}{{a}^{2}+{b}^{2}}\ge a\frac{b}{2}$
with a similar inequality for the other two terms on the left side.
Adding these inequalities and using
$a+b+c=1$ yields the desired
result.
Comment. R. Furmaniak noted that
$\frac{2{a}^{3}}{{a}^{2}+{b}^{2}}2a+b=\frac{b(ba){}^{2}}{{a}^{2}+{b}^{2}}\ge 0\hspace{1em},$
which again yields the result by concluding as in the
solution.

162.

Let
$A$ and
$B$ be fixed points in the plane.
Find all positive integers
$k$ for which the following assertion
holds:


among all triangles
$\mathrm{ABC}$ with
$\Vert \mathrm{AC}\Vert =k\Vert \mathrm{BC}\Vert $, the one with the largest area is isosceles.
Solution 1. In the case that
$k=1$, all triangles
satisfying the condition are isosceles with
$\mathrm{AC}=\mathrm{BC}$, the locus
of
$C$ is the right bisector of
$\mathrm{AB}$ and there is no triangle with
largest area (the area can be arbitrarily large). Hence
$k\ge 2$.
Since, by the triangle inequality,
$\Vert \mathrm{AB}\Vert +\Vert \mathrm{BC}\Vert >\Vert \mathrm{AC}\Vert =k\Vert \mathrm{BC}\Vert \ge 2\Vert \mathrm{BC}\Vert \hspace{1em},$
we must have that
$\Vert \mathrm{AB}\Vert >\Vert \mathrm{BC}\Vert $. Therefore,
the only way a triangle satisfying the condition can be isosceles
is for
$\Vert \mathrm{AB}\Vert =\Vert \mathrm{AC}\Vert =k\Vert \mathrm{BC}\Vert $.
Since
$\Vert \mathrm{BC}\Vert <\Vert \mathrm{AC}\Vert $,
$\angle \mathrm{CAB}$ cannot
exceed
${60}^{\u02c6}$, so that when
$k\ge 2$, there is no
isosceles triangle in the set.
Solution 2. As in Solution 1, we need consider only the
case that
$k\ge 1$, and we can dispose of the case
$k=1$.
Let
$D$ be the foot of the perpendicular from
$C$ to
$\mathrm{AB}$ (possibly produced; note that
$D$ and
$B$ lie on
the same side of
$A$) and let the respective lengths
of
$\mathrm{AB}$,
$\mathrm{AD}$ and
$\mathrm{CD}$ be
$c$,
$x$ and
$v$. We wish to maximize
$v$. The given condition implies that
${x}^{2}+{v}^{2}=k((xc){}^{2}+{v}^{2})$
so that
${v}^{2}={x}^{2}+\frac{2{k}^{2}c}{{k}^{2}1}x\frac{{k}^{2}{c}^{2}}{{k}^{2}1}\hspace{1em}.$
The maximum value of
$v$ is equal to
$\frac{\mathrm{kc}}{{k}^{2}1}$
assumed when
$x=\frac{{k}^{2}c}{{k}^{2}1}>c\hspace{1em}.$ If this maximum value of
$v$ is assumed when
$\Vert \mathrm{AC}\Vert =\Vert \mathrm{AB}\Vert $, then we have
${x}^{2}+{v}^{2}={c}^{2}$
which leads to
$k=1/\sqrt{3}$. If the maximum is assumed when
$\Vert \mathrm{BC}\Vert =\Vert \mathrm{AB}\Vert $, then
$(xc){}^{2}+{v}^{2}={c}^{2}$,
which leads to
$k=\sqrt{3}$. As both solutions are extraneous,
there is no positive integer value of
$k$ for which the area is
maximized when the triangle is isosceles.
Solution 3. As before, we can deal with the
$k=1$ case.
Let
$k\ne 1$.
Let the sides of the triangle be
$(a,\mathrm{ka},c)$ where
$c$ is the length
of
$\mathrm{AB}$; let
$C$ be the angle opposite
$c$. Then
${c}^{2}=({k}^{2}+1){a}^{2}2{\mathrm{ka}}^{2}\mathrm{cos}C$
whence
${a}^{2}={c}^{2}({k}^{2}+12k\mathrm{cos}C){}^{1}$.
The area of the triangle is equal to
$\frac{1}{2}{\mathrm{ka}}^{2}\mathrm{sin}C=\frac{1}{2}{\mathrm{kc}}^{2}({k}^{2}+12k\mathrm{cos}C){}^{1}\mathrm{sin}C\hspace{1em}.$
The derivative of
$\mathrm{sin}C({k}^{2}+12k\mathrm{cos}C){}^{1}$
with respect to
$C$ is equal to
$[(\mathrm{cos}C)({k}^{2}+1)2k][{k}^{2}+12k\mathrm{cos}C]{}^{2}$, from
which we can read off that area is maximized when
$\mathrm{cos}C=2k({k}^{2}+1){}^{1}$. At this maximum value,
$({k}^{2}+1){c}^{2}=({k}^{2}1){}^{2}{a}^{2}$. The triangle maximizing the
area can be isosceles in two ways. The case
$c=a$ occurs when
$k=\sqrt{3}$, and the case
$c=\mathrm{ka}$ occurs when
$k=1/\sqrt{3}$. Neither of these is an integer.
Alternatively, the case
$c=a$ corresponds to
$\mathrm{cos}C=k/2$,
and equating
$k/2$ and
$2k/({k}^{2}+1)$ leads to
${k}^{2}=3$.
The case
$c=\mathrm{ka}$ corresponds to
$\mathrm{cos}C=1/2k$, and this
leads to
${k}^{2}=1/3$. We conclude as before.
Solution 4. Dispose of the
$k=1$ case as before. Let
$k\ne 1$. Let
$c=\Vert \mathrm{AB}\Vert $ be fixed, and let the
other two sides have length
$a$ and
$\mathrm{la}$. Sixteen times the
square of the area of the triangle is, by Heron's rule,
$\begin{array}{cc}[(1+k)a+c][(1+k)ac]\hfill & [c+(1k)a][c(1k)a]\hfill \\ \multicolumn{0}{c}{}& =[(1+k){}^{2}{a}^{2}{c}^{2}][{c}^{2}(1k){}^{2}{a}^{2}]=2{a}^{2}{c}^{2}(1+{k}^{2})({k}^{2}1){}^{2}{a}^{4}{c}^{4}\hfill \\ \multicolumn{0}{c}{}& =[\frac{({k}^{2}+1){}^{2}}{({k}^{2}1){}^{2}}{c}^{4}{c}^{4}][({k}^{2}1){a}^{2}\frac{({k}^{2}+1)}{({k}^{2}1)}{c}^{2}{]}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{4{k}^{2}{c}^{4}}{({k}^{2}1){}^{2}}({k}^{2}1)[{a}^{2}\frac{{k}^{2}+1}{({k}^{2}1){}^{2}}{c}^{2}]\hspace{1em}.\hfill \end{array}$
The maximum area occurs when
$({k}^{2}1){}^{2}{a}^{2}=({k}^{2}+1){c}^{2}$.
This occurs when
$a=c$ exactly when
$({k}^{2}1){}^{2}={k}^{2}+1$,
so
${k}^{2}=3$, and occurs when
$\mathrm{ka}=c$ exactly when
$({k}^{2}1){}^{2}={k}^{4}+{k}^{2}$, so
$3{k}^{2}=1$. We conclude as before.
Comments. Several students committed the fallacy of setting,
for example,
$\mathrm{AC}=\mathrm{AB}$, noting that the locus of
$C$ in this case
was a circle with diameter containing
$\mathrm{AB}$, claiming that the
area was maximized when
$\angle C={90}^{\u02c6}$ and so
$\mathrm{BC}$ was equal to
$\sqrt{2}\mathrm{AC}$. They deduced that
$\sqrt{2}$
and
$1/\sqrt{2}$ were the only values of
$k$ that allowed the
area to be maximized by an isosceles triangle. However, this
puts things the wrong way around. The value
$k$ is fixed, and
then we look at all appropriate triangles. All the solvers did
was to maximize the area over all isosceles triangles for which
$\mathrm{AC}=\mathrm{AB}$; as
$C$ traces out the set of points satisfying these
conditions, of course, the ratio of the lengths of
$\mathrm{AC}$ and
$\mathrm{BC}$
vary. Those solvers who made this mistake are invited to
investigate the case
$k=\sqrt{2}$ in more detail, and this will
help them understand where they went wrong.
If we coordinatize the situation with
$A~(0,0)$ and
$B~(1,0)$, we see that the locus of
$C$ is given by
$({k}^{2}1)({x}^{2}+{y}^{2})2{k}^{2}x+{k}^{2}=0\hspace{1em}.$
This is the equation of a circle (of Apollonius) with centre
at
$({k}^{2}/({k}^{2}1),0)$ and with radius
$k({k}^{2}1){}^{2}$.
Thus, the area is maximized when
$C$ is located at the point
$({k}^{2}({k}^{2}1){}^{1},k({k}^{2}1){}^{1})$. Checking when this
yields an isosceles triangle leads to the two values of
$k$
that we have already seen:
$\sqrt{3}$ and
$1/\sqrt{3}$

163.

Let
${R}_{i}$ and
${r}_{i}$ re the respective circumradius and
inradius of triangle
${A}_{i}{B}_{i}{C}_{i}$ (
$i=1,2$). Prove that, if
$\angle {C}_{1}=\angle {C}_{2}$ and
${R}_{1}{r}_{2}={r}_{1}{R}_{2}$, then the two
triangles are similar.
Solution. Let
$\Gamma $ be the circumcircle of
$\Delta {A}_{1}{B}_{1}{C}_{1}$.
Scale
$\Delta {A}_{2}{B}_{2}{C}_{2}$ so that
${A}_{2}={A}_{1}=A$,
${B}_{2}={B}_{1}=A$
and
${C}_{2}$ and
${C}_{1}$ lie on the same side of
$\mathrm{AB}$. Then
$\Gamma $ is
the circumcircle of
${\mathrm{ABC}}_{2}$, so that
${R}_{1}={R}_{2}$ and
${r}_{1}={r}_{2}$.
Using the conventional notation, we have that
$({s}_{1}{c}_{1})\mathrm{cot}({C}_{1}/2)={r}_{1}={r}_{2}=({s}_{2}{c}_{2})\mathrm{cot}({C}_{2}/2)$
whence, as
${c}_{1}={c}_{2}$ and
${C}_{1}={C}_{2}$,
${s}_{1}={s}_{2}$. Therefore
${a}_{1}+{b}_{1}={a}_{2}+{b}_{2}$. Since
${r}_{1}{s}_{1}={r}_{2}{s}_{2}$, the two
triangles have the same area, so that
${a}_{1}{b}_{1}\mathrm{sin}{C}_{1}={a}_{2}{b}_{2}\mathrm{sin}{C}_{2}$ and thus
${a}_{1}{b}_{1}={a}_{2}{b}_{2}$. Since the
pairs
$({a}_{1},{b}_{1})$ and
$({a}_{2},{b}_{2})$ have the same sum and
product, they are roots of the same quadratic equation, and so
we must have that
$({a}_{1},{b}_{1})=({a}_{2},{b}_{2})$ or
$({a}_{1},{b}_{1})=({b}_{2},{a}_{2})$. In either case, the triangles are congruent, so that
triangle
${A}_{1}{B}_{1}{C}_{1}$ is a scaled version of the original
triangle
${A}_{2}{B}_{2}{C}_{2}$. The result follows.
Comment. There were many variations using various
trigonometric identities.

164.

Let
$n$ be a positive integer and
$X$ a set with
$n$ distinct elements. Suppose that there are
$k$ distinct subsets
of
$X$ for which the union of any four contains no more that
$n2$ elements. Prove that
$k\le {2}^{n2}$.
Solution 1. [R. Furmaniak] We may assume that
$n\ge 2$.
We give a proof by contradiction. Suppose the
$S$ is a family of
$k$ subsets of
$X$, where
$k>{2}^{n2}$. Let
$X=\{{x}_{1},{x}_{2},\dots ,{x}_{n}\}$ where the first element is
selected so that
${x}_{1}$ belongs to some member of
$S$ but not to
all. (Why can you do this?) For each
$i$,
$1\le i\le n1$,
let
${A}_{i}$ be the class of all subsets of
$\{{x}_{1},{x}_{2},\dots ,{x}_{i}\}$
which are contained in some subset of
$S$, and
${B}_{i}$ be the class
of all subsets of
$\{{x}_{i+1},\dots ,{x}_{n}\}$ which are contained
in some subset of
$S$.
Note that
${2}^{n2}<k\le \Vert {A}_{i}\Vert \Vert {B}_{i}\Vert $, since
each set of
$S$ is the union of a set in
${A}_{i}$ and a set in
${B}_{i}$.
(
$\Vert \xb7\Vert $ refers to the number of elements.) Therefore,
either
$\Vert {A}_{i}\Vert >{2}^{i1}$ or
$\Vert {B}_{i}\Vert >{2}^{ni1}$.
In the former case,
${A}_{i}$ must contain a complementary pair of
subsets (use the pigeonhole principle on complementary pairs of sets)
of
$\{{x}_{1},\dots ,{x}_{i}\}$; the the latter,
${B}_{i}$ must contain
a complementary pair of sets of
$\{{x}_{i+1},\dots ,{x}_{n}\}$.
By our choice of
${x}_{1}$, we see that
${A}_{1}=\{\varnothing ,{x}_{1}\}$,
so that
$\Vert {A}_{1}\Vert =2$. Therefore there are values of the
index
$i$ for which
$\Vert {A}_{i}\Vert >{2}^{i1}$. If it turns out
that
$\Vert {A}_{n1}\Vert >{2}^{n2}$, then
${A}_{n1}$ contains
two sets whose union is
$\{{x}_{1},\dots ,{x}_{n1}\}$ and so
$S$ contains two sets whose union has at least
$n1$ elements.
In this case,
$S$ fails to satisfy the hypotheses of the problem.
Suppose that
$\Vert {A}_{n1}\Vert \le {2}^{n2}$. Then select the
smallest index
$k$ for which
$\Vert {A}_{k}\Vert \le {2}^{k1}$.
Then
$k\ge 2$ and
$\Vert {A}_{k1}\Vert >{2}^{k2}$ while
$\Vert {B}_{k}\Vert >{2}^{nk1}$. Therefore,
${A}_{k1}$ contains
two sets whose union is
$\{{x}_{1},{x}_{2},\dots ,{x}_{k1}\}$ and
${B}_{k}$ contains two sets whose union is
$\{{x}_{k+1},\dots ,{x}_{n}\}$. We conclude that
$S$ must contain four sets whose
union contains the
$n1$ elements of
$X$ apart from
${x}_{k}$,
and so
$S$ again fails to satisfy the hypothesis of the problem.
We conclude that any family of more than
${2}^{n2}$ sets fails
so satisfy the hypothesis of the problem, and so that every family
that does satisfy the hypothesis must have at more
${2}^{n2}$ elements.
Solution 2. Let
$P$ be a class of
$k$ subsets for which the
union of no four contains more than
$n2$ elements. Suppose that
${A}_{1}$ and
${A}_{2}$ are two members for which the cardinality
$m=\Vert {A}_{1}\cup {A}_{2}\Vert $ of the union of a pair is maximum. Since
$m<n$, we can construct a set
$Y={A}_{1}\cup {A}_{2}\cup \{y\}$,
where
$y\backslash not\in {A}_{1}\cup {A}_{2}$; thus
$\Vert Y\Vert =m+1$.
Let
$Q=\{Y\cap A:A\in P\}$. No two subsets in
$Q$ are
complementary (i.e. have union equal to
$Y$), so that
$\Vert Q\Vert \le {2}^{m}$. Let
$Z=X\setminus Y$ and
$R=\{Z\cap A:A\in P\}$. Then
$\Vert Z\Vert =n(m+1)=nm1$. We prove that
$R$ has no two sets
that are complementary, i.e., whose union is
$Z$.
For, otherwise, suppose that
$({A}_{3}\cap Z)\cup ({A}_{4}\cap Z)=Z$, for two sets
${A}_{3}$ and
${A}_{4}$ in
$P$.
Then
$Z=({A}_{3}\cup {A}_{4})\cap Z$, so that
$Z\subseteq {A}_{3}\cup {A}_{4}\Rightarrow {A}_{1}\cup {A}_{2}\cup {A}_{3}\cup {A}_{4}\supseteq (Y\cup Z)\setminus \{y\}$
, whence we see that
$\Vert {A}_{1}\cup {A}_{2}\cup {A}_{3}\cup {A}_{4}\Vert =n1$, contrary to hypothesis. Hence
$\Vert R\Vert \le {2}^{nm2}$.
Since each set in
$P$ is uniquely determined by its intersections
with
$Y$ and
$Z$, we have that
$k=\Vert P\Vert \le \Vert Q\Vert \Vert R\Vert \le {2}^{m}{2}^{nm2}={2}^{n}2\hspace{1em},$
as desired.
Comment. Several solvers pointed out that if you took all
the subsets of
$n2$ of the elements of
$X$, then we got an
``extreme'' case of a family of sets that satisfied the hypothesis
and the conclusion, and essentially said that if we tried to stuff
in any more sets, we would contradict the hypothesis. However, this
begs the question as to whether you could drop some of these sets
and replace than by a larger number of sets while still keeping the
hypothesis.

165.

Let
$n$ be a positive integer. Determine all
$n$tples
$\{{a}_{1},{a}_{2},\dots ,{a}_{n}\}$ of positive integers for which
${a}_{1}+{a}_{2}+\dots +{a}_{n}=2n$ and there is no subset of them
whose sum is equal to
$n$.
Solution 1. Let
${s}_{k}={a}_{1}+{a}_{2}+\dots +{a}_{k}$ for
$1\le k\le n$, By hypothesis, all of these are incongruent
modulo
$n$. Now let
${t}_{1}={a}_{2}$,
${t}_{k}={s}_{k}$ for
$2\le k\le n$.
Again, the hypothesis forces all to be incongruent. Hence the
sets
$\{{s}_{k}\}$ and
$\{{t}_{k}\}$ both consitute a complete set
of residues, modulo
$n$, so it must happen that
${s}_{1}\equiv {t}_{1}\equiv {a}_{1}$ (mod
$n$).
A similar argument can be marshalled when the pair
$({a}_{1},{a}_{2})$
is replaced by any other pair of elements. Hence, each of the
terms in the set
$\{{a}_{i}\}$ is congruent to some number
$m$
(mod
$n$), where
$0\le m\le n1$. Now
$\mathrm{mn}\le {a}_{1}+{a}_{2}+\dots +{a}_{n}=2n$
from which either
$m=2$,
$n$ is odd, and the
$n$tple
is
$\{2,2,2,\dots ,2\}$ or else
$m=1$ and the
$n$tple is
$\{1,1,1,\dots ,1,n+1\}$.
Solution 2. [J.Y. Jin] Wolog, suppose that
${a}_{1}\le {a}_{2}\le \dots \le {a}_{n}$. Note that
${a}_{1}$ cannot exceed 2. If
${a}_{1}=2$,
then each
${a}_{i}$ is equal to 2 and
$n$ is odd. Suppose that
${a}_{1}=1$. Then
${a}_{n}\ge 3$. Let
${s}_{k}={a}_{1}+\dots +{a}_{k}$
for
$1\le k\le n$. Then
${s}_{n1}=2n{a}_{n}\le 2n3$.
By the hypothesis, we see that the set of the
${s}_{k}$
with
$1\le k\le n1$ contains
at most one member from each of the
$n1$ sets:
$\{1,n+1\},\{2,n+2\},\{3,n+3\},\dots ,\{n3,2n3\},\{n2\},\{n1\}$
so it must contain exactly one from each set.
In particular, the values
$n2$ and
$n1$ are assumed, so that
for some
$i$,
${s}_{i}=n2$ and
${s}_{i+1}=n1$. Thus
${a}_{i+1}=1$,
and
${a}_{1}={a}_{2}=\dots ={a}_{i+1}=1$. But this means that
$i=n2$, so that
${a}_{n1}=1$ and
${a}_{n}=n+1$.
Comment. Some of the solvers tried an induction argument.
However, the process was faulty, since they generally started with
an
$n$tple and then tried to build from that an
$(n+1)$tple.
However, for an induction argument to work, you need to start with
a general
$(n+1)$tple that satisfies the condition, and then
indicate how to reduce it to the result for a smaller set.

166.

Suppose that
$f$ is a realvalued function defined on
the reals for which
$f(\mathrm{xy})+f(yx)\ge f(y+x)$
for all real
$x$ and
$y$. Prove that
$f(x)\ge 0$ for all real
$x$.
Solution. Suppose
$x\ne 1$; let
$y=x(x1){}^{1}$. Then
$\mathrm{xy}=y+x$, so that
$f(\frac{{x}^{2}2x}{1x})=f(yx)\ge f(x+y)f(\mathrm{xy})=0\hspace{1em}.$
For each real
$z$, the equation
$z=({x}^{2}2x)(1x){}^{1}$ is
equivalent to
${x}^{2}+(z2)xz=0$. This quadratic equation
(in
$x$) has a discriminant
${z}^{2}+4$ which is positive and therefore
it is solvable for all real
$z$. (Note that in no case is
$x=1$ a
solution.) Hence
$f(z)\ge 0$ for all real
$z$.
Comment. O. Bormashenko noted that when
$2x=\sqrt{{z}^{2}+4}+2z$ and
$2y=\sqrt{{z}^{2}+4}+2+z$,
then
$\mathrm{xy}=x+y$ and
$yx=z$.

167.

Let
$u=(\sqrt{5}2){}^{1/3}(\sqrt{5}+2){}^{1/3}$
and
$v=(\sqrt{189}8){}^{1/3}(\sqrt{189}+8){}^{1/3}$. Prove
that, for each positive integer
$n$,
${u}^{n}+{v}^{n+1}=0$.
Solution. Observe that, if
$c=ab$, then
${c}^{3}={a}^{3}{b}^{3}3\mathrm{abc}$, so that
${c}^{3}+3\mathrm{abc}({a}^{3}{b}^{3})=0$.
Applying this to
$u$ and
$v$ in place of
$c$, we obtain that
$0={u}^{3}+3u+4=(u1)({u}^{2}u+4)=(u+1)[(u\frac{1}{2}{)}^{2}\frac{15}{4}]$
and
$0={v}^{3}+15v+16=(v+1)({v}^{2}v+16)=(v+1)[(v\frac{1}{2}{)}^{2}\frac{63}{4}]\hspace{1em}.$
Since the expresseions in square brackets are negative, we must have
that
$u=v=1$, from which the result follows.
Comment. Some students observed that
$(\frac{\sqrt{5}\pm 1}{2}{)}^{3}=\sqrt{5}\pm 2$
and
$(\frac{\sqrt{21}\pm 1}{2}{)}^{3}=\sqrt{189}\pm 8\hspace{1em},$
and this immediately leads to the result.

168.

Determine the value of
$\mathrm{cos}{5}^{\u02c6}+\mathrm{cos}{77}^{\u02c6}+\mathrm{cos}{149}^{\u02c6}+\mathrm{cos}{221}^{\u02c6}+\mathrm{cos}{293}^{\u02c6}\hspace{1em}.$
Preliminary work. Before getting into the solution, we
will discuss how to obtain the trigonometric ratios of certain
angles related to
${36}^{\u02c6}$. It is useful for you to know some
of these techniques, as these angles tend to come up in problems,
and to be on the safe side in a contest, you should try to include
a justification for assertions that you make about these angles.
Here is one way to evaluate
$t=\mathrm{cos}{36}^{\u02c6}$. Observe that
$\begin{array}{cc}t\hfill & =\mathrm{cos}{144}^{\u02c6}=12\mathrm{cos}{}^{2}{72}^{\u02c6}\hfill \\ \multicolumn{0}{c}{}& =12(2{t}^{2}1){}^{2}=8{t}^{4}+8{t}^{2}1\hfill \end{array}$
from which we see that
$0=8{t}^{4}8{t}^{2}+t+1=(2t1)(t+1)(4{t}^{2}2t1)\hspace{1em}.$
Since
$t$ is equal to neither 1 nor
$\frac{1}{2}$, we must have
that
$4{t}^{2}=2t+1$. Solving this equation will give you an
actual numerical value (can you justify your choice of root?).
A very useful relation is
$4\mathrm{cos}{36}^{\u02c6}\mathrm{cos}{72}^{\u02c6}=1$.
This can be checked geometrically. Let
$\mathrm{PQS}$ be a triangle for
which
$\angle P=\angle S={36}^{\u02c6}$ and
$\angle \mathrm{PQS}={108}^{\u02c6}$.
Let
$R$ be a point on the side
$\mathrm{PS}$ for which
$\angle \mathrm{PQR}={72}^{\u02c6}$
and
$\angle \mathrm{SQR}={36}^{\u02c6}$. Then
$\mathrm{PQ}=\mathrm{PR}$,
$\mathrm{PQ}=\mathrm{QS}$
and
$\mathrm{QR}=\mathrm{RS}$; let
$r$ be the common length of
$\mathrm{PQ}$,
$\mathrm{PR}$,
$\mathrm{QS}$ and
let
$s$ be the common length of
$\mathrm{QR}$ and
$\mathrm{RS}$. Then
$\mathrm{cos}{72}^{\u02c6}=s/2r$ and
$\mathrm{cos}{36}^{\u02c6}=r/2s$ and the desired result follows.
An algebraic derivation of this result can also be given.
$\begin{array}{cc}4\mathrm{cos}{36}^{\u02c6}\mathrm{cos}{72}^{\u02c6}\hfill & =\frac{4\mathrm{sin}{36}^{\u02c6}\mathrm{cos}{36}^{\u02c6}\mathrm{cos}{72}^{\u02c6}}{\mathrm{sin}{36}^{\u02c6}}\hfill \\ \multicolumn{0}{c}{}& =\frac{2\mathrm{sin}{72}^{\u02c6}\mathrm{cos}{72}^{\u02c6}}{\mathrm{sin}{36}^{\u02c6}}\hfill \\ \multicolumn{0}{c}{}& =\frac{\mathrm{sin}{144}^{\u02c6}}{\mathrm{sin}{36}^{\u02c6}}=1\hspace{1em}.\hfill \end{array}$
We can make use of complex numbers. Let
$\zeta =\mathrm{cos}{72}^{\u02c6}+i\mathrm{sin}{72}^{\u02c6}$ so that
$\zeta $ is a nonreal root of
$0={x}^{5}1=(x1)({x}^{4}+{x}^{3}+{x}^{2}+x+1)\hspace{1em}.$
Hence
$1+\zeta +{\zeta}^{2}+{\zeta}^{3}+{\zeta}^{4}=0$; using
de Moivre's theorem, and taking the real part of this
equation, we find that
$1+\mathrm{cos}{72}^{\u02c6}+\mathrm{cos}{144}^{\u02c6}+\mathrm{cos}{216}^{\u02c6}+\mathrm{cos}{288}^{\u02c6}=1+2\mathrm{cos}{72}^{\u02c6}2\mathrm{cos}{36}^{\u02c6}=0\hspace{1em}.$
(Note that taking the imaginary part yields a triviality.)
Another way to look at this result is to note that the vectors
represented by the five roots of unity sum bound a closed regular
pentagon and so sum to zero.
Solution 1. Let
$\mathrm{cos}{36}^{\u02c6}=t$. Then
$\begin{array}{cc}\mathrm{cos}{5}^{\u02c6}\hfill & +\mathrm{cos}{77}^{\u02c6}+\mathrm{cos}{149}^{\u02c6}+\mathrm{cos}{221}^{\u02c6}+\mathrm{cos}{293}^{\u02c6}\hfill \\ \multicolumn{0}{c}{}& =[\mathrm{cos}{5}^{\u02c6}+\mathrm{cos}{293}^{\u02c6}]+[\mathrm{cos}{77}^{\u02c6}+\mathrm{cos}{221}^{\u02c6}]+\mathrm{cos}{149}^{\u02c6}\hfill \\ \multicolumn{0}{c}{}& =\mathrm{cos}{149}^{\u02c6}[2\mathrm{cos}{144}^{\u02c6}+2\mathrm{cos}{72}^{\u02c6}+1]\hfill \\ \multicolumn{0}{c}{}& =\mathrm{cos}{149}^{\u02c6}[2\mathrm{cos}{36}^{\u02c6}+2\mathrm{cos}{72}^{\u02c6}+1]=0\hspace{1em}.\hfill \end{array}$
Alternatively, this is seen to be equal to
$\mathrm{cos}{149}^{\u02c6}[2t+2(2{t}^{2}1)+1]=\mathrm{cos}{149}^{\u02c6}[2t+4{t}^{2}1]=0\hspace{1em}.$
Solution 2. [C. Huang]
$\begin{array}{cc}\mathrm{cos}{5}^{\u02c6}\hfill & +\mathrm{cos}{77}^{\u02c6}+\mathrm{cos}{149}^{\u02c6}+\mathrm{cos}{221}^{\u02c6}+\mathrm{cos}{293}^{\u02c6}\hfill \\ \multicolumn{0}{c}{}& =\mathrm{cos}{5}^{\u02c6}+2\mathrm{cos}{185}^{\u02c6}\mathrm{cos}{108}^{\u02c6}+2\mathrm{cos}{185}^{\u02c6}\mathrm{cos}{36}^{\u02c6}\hfill \\ \multicolumn{0}{c}{}& =\mathrm{cos}{5}^{\u02c6}[1+2(\mathrm{cos}{72}^{\u02c6}\mathrm{cos}{36}^{\u02c6})]=\mathrm{cos}{5}^{\u02c6}[14\mathrm{sin}{18}^{\u02c6}\mathrm{sin}{54}^{\u02c6}]\hfill \\ \multicolumn{0}{c}{}& =\mathrm{cos}{5}^{\u02c6}[14\mathrm{cos}{72}^{\u02c6}\mathrm{cos}{36}^{\u02c6}]=0\hspace{1em}.\hfill \end{array}$
Comment. There were other solutions with similar manipulations.
A quick solution can also be realized using complex numbers. The
given expression is equal to the real part of
$(\mathrm{cos}\theta +i\mathrm{sin}\theta )(1+\zeta +{\zeta}^{2}+{\zeta}^{3}+{\zeta}^{4})=0\hspace{1em},$
where
$\zeta $ is an imaginary fifth root of unity and
$\theta $ is
the angle whose degree measure is
${5}^{\u02c6}$.

169.

Prove that, for each positive integer
$n$ exceeding 1,
$\frac{1}{{2}^{n}}+\frac{1}{{2}^{1/n}}<1\hspace{1em}.$
Solution 1. For positive integer
$n>1$ and
$1<x$,
$x\ne 0$,
we have that
$(1+x){}^{n}>1+\mathrm{nx}$ (use induction). Hence, for
$n\ge 2$,
$(1\frac{1}{{2}^{n}}{)}^{n}>1\frac{n}{{2}^{n}}\ge \frac{1}{2}\hspace{1em}.$
(The latter inequality is left as an an easy induction exercise.)
Hence
$1\frac{1}{{2}^{n}}>\frac{1}{{2}^{1/n}}$
and the result follows.
Solution 2. [R. Furmaniak] By the arithmeticgeometric means
inequality, we have that
$1\frac{1}{{2}^{n}}=\frac{1}{2}\xb71+\frac{1}{4}\xb71+\dots +\frac{1}{{2}^{n1}}\xb71+\frac{1}{{2}^{n1}}\xb7\frac{1}{2}>(\frac{1}{2}{)}^{1/({2}^{n1})}\hspace{1em}.$
Now,
${2}^{n1}=1+1+2+\dots +{2}^{n2}\le 1+1+1+\dots +1=n$, so that
$1/({2}^{n1})<1/n$ and
$(1/2){}^{1/({2}^{n1})}>(1/2){}^{1/n}=1/({2}^{1/n})$. The result follows.
Solution 3. [S. Wong] By the arithmeticgeometric means
inequality
$\frac{1}{{2}^{1/n}}=(\frac{1}{2}\xb71\xb71\dots 1{)}^{1/n}<\frac{n1+\frac{1}{2}}{n}=1\frac{1}{2n}$
$\Rightarrow \frac{1}{{2}^{n}}+\frac{1}{{2}^{1/n}}<1+\frac{1}{{2}^{n}}\frac{1}{2n}\hspace{1em}.$
When
$n=2$,
$2n={2}^{n}$, while if
$n\ge 3$,
${2}^{n}=(1+1){}^{n}=1+n+\dots +\left(\genfrac{}{}{0ex}{}{n}{n1}\right)+1>2n\hspace{1em}$
The desired inequality follows.

170.

Solve, for real
$x$,
$x\xb7{2}^{1/x}+\frac{1}{x}\xb7{2}^{x}=4\hspace{1em}.$
Solution 1. If
$x<0$, the left side is negative and so there
is no negative value of
$x$ which satisfies the equation. If
$x=0$,
then the left side is undefined. Suppose that
$x>0$. Then by the arithmeticgeometric means inequality, we have that
$4=x\xb7{2}^{1/x}+\frac{1}{x}\xb7{2}^{x}\ge 2\sqrt{{2}^{(1/x)+x}}\ge 2\sqrt{{2}^{2}}=4\hspace{1em},$
since
$(1/x)+x\ge 2$. Since the outside members of this
inequality are equal, we must have equality everywhere, and this
occurs if and only if
$x=1$. Hence,
$x=1$ is the sole solution
of the equation.
Solution 2. As before, we see that
$x$ must be positive.
The equation is equivalent to
$\begin{array}{cc}0\hfill & ={x}^{2}{2}^{1/x}4x+{2}^{x}\hfill \\ \multicolumn{0}{c}{}& =(x\xb7{2}^{1/(2x)}2\xb7{2}^{1/(2x)}){}^{2}(4\xb7{2}^{(1/x)}{2}^{x})\hspace{1em}.\hfill \end{array}$
Since the first member of the right side is nonnegative, we must
have that
$4\xb7{2}^{1/x}\ge {2}^{x}$, which is equivalent to
$4\ge {2}^{x+(1/x)}$ or
$x+(1/x)\le 2$. But the last can
occur if and only if
$x=1$. Indeed,
$x=1$ satisfies the
equation.