Solutions

67.

(a)
Consider the infinite integer lattice in
the plane (i.e., the set of points with integer
coordinates) as a graph, with the edges being the
lines of unit length connecting nearby points.
What is the minimum number of colours that can be
used to colour all the vertices and edges of this
graph, so that
(i) each pair of adjacent vertices gets two distinct
colours; AND
(ii) each pair of edges that meet at a vertex get
two distinct colours; AND
(iii) an edge is coloured differently than either
of the two vertices at the ends?
(b) Extend this result to lattices in real
$n$dimensional space.
Solution 1. Since each vertex and the four edges emanating from
it must have different colours, at least five colours are
needed. Here is a colouring that will work: Let the
colours be numbered 0, 1, 2, 3, 4. Colour the point
$(x,0)$ with the colour
$x$ (mod 5); colour the point
$(0,y)$ with the colour
$2y$ (mod 5); colour the points
along each horizontal line parallel to the
$x$axis
consecutively; colour the vertical edge whose lower
vertex has colour
$m$ (mod 5) with the colour
$m+1$
(mod 5); colour the horizontal edge whose left vertex
has the colour
$n$ (mod 5) with the colour
$n+3$
(mod 5).
This can be generalized to an
$n$dimensional lattice where
$2n+1$ colours are needed by changing the strategy of
colouring. The integer points on the line and the
edges between them can be coloured
$1(3)2(1)3(2)1$ and so on, where the edge
colouring is in parenthesis. Form a plane by stacking
these lines unit distance apart, making sure that each
vertex has a different coloured vertex above and below it;
use colours 4 and 5 judiciously to colour the vertical
edges. Now go to three dimensions; stack up planar lattices
and struts unit distance apart, colouring each with the colours
1, 2, 3, 4, 5, while making sure that vertically adjacent
vertices have separate colours, and use the colours 6 and
7 for vertical struts. Continue on.
Solution 2. Consider the
$n$ dimensional lattice.
Let the colours be numbered
$0,1,2,\dots ,2n$.
Assign the vertex with coordinates
$({x}_{1},{x}_{2},\dots ,{x}_{n})$ the colour
${x}_{1}+2{x}_{2}+\dots +{\mathrm{nx}}_{n}$, modulo
$2n+1$. Adjacent vertices have distinct colours.
For each adjacent vertex has the same coordinates,
except in one position where the coordinates differ by 1;
if this is the
$i$th coordinate, then the numbers of the
two colours differ by
$\pm i$ (mod
$2n+1$).
Consider an edge joining a vertex with colour
$u$ to
one of colour
$v$; assign this edge the colour
$(n+1)(u+v)$ (mod
$2n+1$). Since
$(n+1)(u+v)v\equiv n(uv)$ (mod
$2n+1$), the greatest common
divisor of
$n$ and
$2n+1$ is 1 and
$u\backslash not\equiv v$
(mod
$2n+1$), it follows that the colour of this edge differs from
$v$; similarly, it differs from
$u$.
Finally, consider a pair of adjacent edges, with colours
$(n+1)(u+v)$ and
$(n+1)(v+w)$ (mod
$2n+1$). The difference
between these colours, modulo
$2n+1$, is equal to
$(n+1)(uw)$. If the edges are collinear, then this
difference is
$\pm 2(n+1)i$ for some
$i$ with
$1\le i\le n$,
and this is not congruent to zero modulo
$2n+1$. If the
edges are perpendicular, then this difference is nonzero and
of the form
$(n+1)(\pm i\pm j)$. This value, lying between
$2n$
and
$2n$ is not congruent to zero modulo
$2n+1$. Thus,
adjacent edges have distinct colours.
Therefore, we can achieve our goal with
$2n+1$ colours, and,
by looking at a vertex and its adjacent edges, we see that
this is minimal.

68.

Let
$a,b,c>0$,
$a<\mathrm{bc}$
and
$1+{a}^{3}={b}^{3}+{c}^{3}$.
Prove that
$1+a<b+c$.
Solution 1. Since
$(1+a)(1a+{a}^{2})=(b+c)({b}^{2}\mathrm{bc}+{c}^{2})$, and since
$1a+{a}^{2}$ and
${b}^{2}\mathrm{bc}+{c}^{2}$ are positive, we have that
$1+a<b+c\&lrArr;1a+{a}^{2}>{b}^{2}\mathrm{bc}+{c}^{2}\hspace{1em}.$
Suppose, if possible, that
$1+a\ge b+c$. Then
$\begin{array}{cc}{b}^{2}\mathrm{bc}+{c}^{2}\hfill & \ge 1a+{a}^{2}\hfill \\ \multicolumn{0}{c}{}& \Rightarrow (b+c){}^{2}3\mathrm{bc}\ge (1+a){}^{2}3a>(1+a){}^{2}3\mathrm{bc}\hfill \\ \multicolumn{0}{c}{}& \Rightarrow (b+c){}^{2}>(1+a){}^{2}\Rightarrow b+c>1+a\hfill \end{array}$
which is a contradiction.
Solution 2. [J. Chui] Let
$u=(1+a)(b+c)$.
Then
$\begin{array}{cc}(1+a){}^{3}(b+c){}^{3}\hfill & =u[(1+a){}^{2}+(1+a)(b+c)+(b+c){}^{2}]\hfill \\ \multicolumn{0}{c}{}& =u[(1+a){}^{2}+(1+a)(b+c)+{b}^{2}+2\mathrm{bc}+{c}^{2}]\hspace{1em}.\hfill \end{array}$
But also
$\begin{array}{cc}(1+a){}^{3}(b+c){}^{3}\hfill & =(1+{a}^{3})({b}^{3}+{c}^{3})+3a(1+a)3\mathrm{bc}(b+c)\hfill \\ \multicolumn{0}{c}{}& =0+3[a(1+a)\mathrm{bc}(b+c)]<3\mathrm{bcu}\hspace{1em}.\hfill \end{array}$
It follows from these that
$0>u[(1+a){}^{2}+(1+a)(b+c)+{b}^{2}\mathrm{bc}+{c}^{2}]=u[(1+a){}^{2}+(1+a)(b+c)+\frac{1}{2}(bc){}^{2}+\frac{1}{2}({b}^{2}+{c}^{2})]\hspace{1em}.$
Since the quantity in square brackets is positive, we must
have that
$u<0$, as desired.
Solution 3. [A. Momin, N. Martin] Suppose, if possible,
that
$(1+a)\ge (b+c)$. Then
$0\le (1+a){}^{2}(b+c){}^{2}=(1+{a}^{2})({b}^{2}+{c}^{2})2(\mathrm{bc}a)<(1+{a}^{2})({b}^{2}+{c}^{2})\hspace{1em}.$
Hence
$1+{a}^{2}>{b}^{2}+{c}^{2}$.
It follows that
$(1a+{a}^{2})({b}^{2}\mathrm{bc}+{b}^{2})=(1+{a}^{2})({b}^{2}+{c}^{2})+(\mathrm{bc}a)>0$
so that
$(1a+{a}^{2})>({b}^{2}\mathrm{bc}+{c}^{2})\hspace{1em}.$
However
$(1+a)(1a+{a}^{2})=1+{a}^{3}={b}^{3}+{c}^{3}+(b+c)({b}^{2}\mathrm{bc}+{c}^{2})\hspace{1em},$
from which it follows that
$1+a<b+c$, yielding a contradition. Hence, the desired
result follows.
Solution 4. [H. Pan] First, observe that
$a=c$ leads
to
$b=1$ and a contradiction of the given conditions, while
$a=b$ leads to
$c=1$ and a contradiction. Suppose,
if possible, that
that
$b>a>c$. Then
${b}^{3}+1>{a}^{3}+1={b}^{3}+{c}^{3}>{c}^{3}+1$, and
$c<1<b$. Therefore,
$\mathrm{bc}>a\Rightarrow {b}^{3}{c}^{3}>{b}^{3}+{c}^{3}1\Rightarrow ({b}^{3}1)({c}^{3}1)>0\hspace{1em},$
which contradicts
$b>1>c$. In a similar way, we see that
$c>a>b$ cannot occur.
Thus,
$a$ must be either the largest or the smallest of the
three numbers. Hence
$(ab)(ac)>0$, whence
${a}^{2}+\mathrm{bc}>a(b+c)$. Therefore
$\begin{array}{cc}(b+ca){}^{3}\hfill & ={b}^{3}+{c}^{3}{a}^{3}+3{b}^{2}c+3{\mathrm{bc}}^{2}3{\mathrm{ab}}^{2}3{\mathrm{ac}}^{2}+3{a}^{2}b+3{a}^{2}c6\mathrm{abc}\hfill \\ \multicolumn{0}{c}{}& =1+3b({a}^{2}+\mathrm{bc})+3c({a}^{2}+\mathrm{bc})3\mathrm{ab}(b+c)3\mathrm{ac}(b+c)\hfill \\ \multicolumn{0}{c}{}& =1+3(b+c)[({a}^{2}+\mathrm{bc})a(b+c)]>1\hfill \end{array}$
and the desired result follows.
Solution 5. [X. Li] If
$1+{a}^{2}<{b}^{2}+{c}^{2}$, then
$(1+a){}^{2}=1+{a}^{2}+2a<{b}^{2}+{c}^{2}+2\mathrm{bc}=(b+c){}^{2}\hspace{1em},$
whence
$b+c>1+a$.
On the other hand, if
$1+{a}^{2}\ge {b}^{2}+{c}^{2}$, then
$1+{a}^{2}a>{b}^{2}+{c}^{2}\mathrm{bc}=({b}^{3}+{c}^{3})/(b+c)>0\hspace{1em},$
whereupon,
$\begin{array}{cc}(b+c)({b}^{2}+{c}^{2}\mathrm{bc})\hfill & ={b}^{3}+{c}^{3}=1+{a}^{3}\hfill \\ \multicolumn{0}{c}{}& =(1+a)(1+{a}^{2}a)>(1+a)({b}^{2}+{c}^{2}\mathrm{bc})\hfill \end{array}$
so that
$b+c>1+a$.
Solution 6. [P. Gyrya] Let
$p(x)={x}^{3}3\mathrm{ax}$.
Checking the first derivative yields that
$p(x)$ is strictly
increasing for
$x>\sqrt{a}$. Now
$1+a\ge 2\sqrt{a}>\sqrt{a}$ and
$b+c\ge 2\sqrt{\mathrm{bc}}>2\sqrt{a}>\sqrt{a}$,
so both
$1+a$ and
$b+c$ lie in the part of the domain of
$p(x)$ where it strictly increases. Now
$p(1+a)=(1+a){}^{3}3a(1+a)=1+{a}^{3}={b}^{3}+{c}^{3}=(b+c){}^{3}3\mathrm{bc}(b+c)<(b+c){}^{3}3a(b+c)=p(b+c)$
from which it follows that
$1+a<b+c$.
Solution 7. Consider the function
$g(x)=x(1+{a}^{3}x)=x({b}^{3}+{c}^{3}x)$. Then
$g(1)=g({a}^{3})={a}^{3}$ and
$g({b}^{3})=g({c}^{3})=(\mathrm{bc}){}^{3}$.
Since
${a}^{3}<(\mathrm{bc}){}^{3}$ and the graph of
$g(x)$ is a
parabola opening down, it follows that
${b}^{3}$ and
${c}^{3}$
lie between 1 and
${a}^{3}$.
Now consider the function
$h(x)={x}^{1/3}+({b}^{3}+{c}^{3}x){}^{1/3}={x}^{1/3}+(1+{a}^{3}x){}^{1/3}$ for
$0\le x\le 1+{a}^{3}$. Then
$h(1)=h({a}^{3})=1+a$ and
$h({b}^{3})=h({c}^{3})=b+c$. The graph of
$h(x)$ resembles an
inverted parabola, so since
${b}^{3}$ and
${c}^{3}$
lie between 1 and
${a}^{3}$, it follows that
$1+a<b+c$, as desired.

69.

Let
$n$,
${a}_{1}$,
${a}_{2}$,
$\dots $,
${a}_{k}$ be positive integers for which
$n\ge {a}_{1}>{a}_{2}>{a}_{3}>\dots >{a}_{k}$ and the
least common multiple of
${a}_{i}$ and
${a}_{j}$ does not exceed
$n$ for all
$i$ and
$j$. Prove that
${\mathrm{ia}}_{i}\le n$ for
$i=1,2,\dots ,k$.
Solution 1. The result can be established by
induction. It clearly holds when
$i=1$. Suppose that
it holds for
$1\le i\le m$, so that, in particular
${\mathrm{ma}}_{m}\le n$. The least common multiple is equal to
${\mathrm{ba}}_{m+1}={\mathrm{ca}}_{m}$ for some positive integers
$b$ and
$c$ with
$c<b$. If
$b\ge m+1$, then
$(m+1){a}_{m+1}\le {\mathrm{ba}}_{m+1}\le n$ by hypothesis.
Assume that
$b\le m$. Then
$\begin{array}{cc}(m+1){a}_{m+1}\hfill & =\frac{(m+1)c}{b}\hspace{1em}{a}_{m}\le \frac{(m+1)\mathrm{cn}}{\mathrm{bm}}\hfill \\ \multicolumn{0}{c}{}& =(\frac{m+1}{m})(\frac{c}{b})n\le (\frac{m+1}{m})(\frac{b1}{b})n\hfill \\ \multicolumn{0}{c}{}& =(1\frac{1}{m})(1\frac{1}{b})n\le (1+\frac{1}{m})(1\frac{1}{m})n=(1\frac{1}{{m}^{2}})n<n\hfill \end{array}$
as desired. The result now follows.
Solution 2. We can obtain the result by induction,
it being known when
$i=1$. Suppose that the result
holds up to
$i=m$. If
$(m+1){a}_{m}\le n$, then
the desired result for
$i=m+1$ follows from
${a}_{m+1}>{a}_{m}$. On the other hand, suppose that
$(m+1){a}_{m}>n$. With
${\mathrm{ba}}_{m+1}={\mathrm{ca}}_{m}$ the least common multiple
of
${a}_{m}$ and
${a}_{m+1}$, we have that
$(m+1){a}_{m}>{\mathrm{ca}}_{m}$,
so that
${a}_{m+1}=\frac{c}{b}{a}_{m}\le \frac{c}{c+1}{a}_{m}\le \frac{m}{m+1}{a}_{m}\le \frac{n}{m+1}$
and the result follows.

70.

Let
$f(x)$ be a concave strictly increasing
function defined for
$0\le x\le 1$ such that
$f(0)=0$ and
$f(1)=1$. Suppose that
$g(x)$ is its
inverse. Prove that
$f(x)g(x)\le {x}^{2}$ for
$0\le x\le 1$.
Comment. Begin with a sketch. The graph of the function
is like a bow on top of a bowstring along the line
$y=x$.
As
$x$ increases, the slope of the chord from the origin
to
$(x,f(x))$ decreases. The solution begins with an
analytic verification of this fact, using the definition of
concavity.
Solution. Let
$0<v\le u$. Then, taking
$t=(uv)/u$ in the definition of concavity, we have that
$f(v)\ge \frac{\mathrm{vf}(u)+(uv)f(0)}{u}=\frac{\mathrm{vf}(u)}{u}\hspace{1em}.$
When
$(u,v)=(1,x)$, this yields
$f(x)\ge x$, so that
$x=g(f(x))\ge g(x)$ (since
$g(x)$ is an increasing
function). Let
$(u,v)=(x,g(x))$ to obtain, for
$x\ne 0$ that
$x=f(g(x))\ge \frac{g(x)f(x)}{x}\hspace{1em}.$
It is straightforward to verify now that
$f(x)g(x)\le {x}^{2}$ for all
$x\in [0,1]$.
Comment. A special case is that
$f(x)={x}^{k}$ for
$0<k<1$, so that
$g(x)={x}^{1/k}$. Then
$f(x)g(x)={x}^{k+(1/k)}$ and the result holds since
$0\le x\le 1$ and
$k+(1/k)\ge 2$.

71.

Suppose that lengths
$b$,
$c$ and
$i$ are given.
Construct a triangle
$\mathrm{ABC}$ for which
$\Vert \mathrm{AC}\Vert =b$.
$\Vert \mathrm{AB}\Vert =c$ and the length of the bisector
$\mathrm{AD}$ of angle
$A$ is
$i$ (
$D$ being the point where the
bisector meets the side
$\mathrm{BC}$).
Solution 1. Analysis. Let
$\mathrm{AD}$ meet the line
through
$B$ parallel to
$\mathrm{AC}$ in
$T$. Then
$\angle \mathrm{BTA}=\angle \mathrm{TAC}=\angle \mathrm{TAB}$, so that
$\Vert \mathrm{BT}\Vert =\Vert \mathrm{AB}\Vert =c$. By similar
triangles, we have that
$\Vert \mathrm{DT}\Vert =\mathrm{ic}/b$
so that
$\Vert \mathrm{AT}\Vert =i(b+c)/b$.
Construction. Construct an isosceles triangle
$\mathrm{ABT}$ with
the lengths of
$\mathrm{AB}$ and
$\mathrm{AT}$ both equal to
$c$ and the
length of
$\mathrm{AT}$ equal to
$i(b+c)/b$. Cut
$\mathrm{AD}$ off
$\mathrm{AT}$ to have
the length
$i$, and let
$C$ be the intersection of
$\mathrm{AD}$ and the line through
$A$ parallel to
$\mathrm{BT}$.
Proof of construction. Since
$\angle \mathrm{BAT}=\angle \mathrm{BTA}=\angle \mathrm{CAT}$, the segment
$\mathrm{AT}$ bisects
angle
$\mathrm{BAC}$. The length of
$\mathrm{AD}$ is
$i$ and the length
of
$\mathrm{AB}$ is
$c$, by construction. From the
similar triangles,
$\mathrm{DBT}$ and
$\mathrm{ADC}$, we find that
the length of
$\mathrm{AC}$ is
$i$ multiplied by
$c=\Vert \mathrm{BT}\Vert $ and divided by
$[i(b+c)/b]i=\mathrm{ic}/b=\Vert \mathrm{DT}\Vert $.
Feasibility. In order for the construction to
work, we require that the sum of the lengths of
$\mathrm{AB}$ and
$\mathrm{BT}$ exceed that of
$\mathrm{AT}$. This requires
$2c>i(b+c)/b$ or
$i<2\mathrm{bc}/(b+c)$.
Solution 2. Analysis. Let
$\theta $ be equal
to angles
$\mathrm{BAD}$ and
$\mathrm{CAD}$, where
$\mathrm{ABC}$ is the required triangle
with bisector
$\mathrm{AD}$. Since the area of
$\Delta \mathrm{ABC}$ is the
sum of the areas of
$\Delta \mathrm{ABD}$ and
$\Delta \mathrm{ADC}$, we have
that
$\mathrm{bc}\mathrm{sin}2\theta =i(b+c)\mathrm{sin}\theta $, whence
$\mathrm{cos}\theta =(b+c)i/2\mathrm{bc}$.
Sketch of construction and proof. By Euclidean means it is possible
to construct the lengths
$b+c$,
$(b+c)i$,
$2\mathrm{bc}$ and
$(b+c)/2\mathrm{bc}$ using proportionalities. Thus, we can obtain the
cosine of the angle
$\theta $, and so find
$\theta $ itself.
Construct triangle
$\mathrm{ABC}$ with the respective lengths of
$\mathrm{AB}$ and
$\mathrm{AC}$ equal to
$c$ and
$b$ and
$\angle \mathrm{BAC}=2\theta $.
The calculation in the analysis can be used to verify that
the length of the bisector is equal to
$2\mathrm{bc}\mathrm{cos}\theta /(b+c)$,
and so equal to
$i$. Note that for
$\theta $ to be found, it is
necessary to have
$(b+c)i\le 2\mathrm{bc}$.

72.

The centres of the circumscribed and the inscribed
spheres of a given tetrahedron coincide. Prove that the
four triangular faces of the tetrahedron are congruent.
Solution 1. Let
$O$ be the common centre of the
circumscribed and inscribed spheres of the tetrahedron
$\mathrm{ABCD}$. The plane
$\mathrm{BCO}$ bisects the dihedral angle formed by the planes
$\mathrm{BCD}$ and
$\mathrm{BCA}$, so that the circles determined by
$\mathrm{BCD}$ and
$\mathrm{BCA}$ in these planes must be congruent.
Thus,
$\angle \mathrm{BAC}=\angle \mathrm{BDC}=\alpha $, say.
Similarly, we find that
$\angle \mathrm{ABC}=\angle \mathrm{ADC}=\beta $,
$\angle \mathrm{ABC}=\angle \mathrm{ADC}=\gamma $,
$\angle \mathrm{ACB}=\angle \mathrm{ADB}=\phi $,
$\angle \mathrm{BAD}=\angle \mathrm{BCD}=\psi $, and
$\angle \mathrm{BAD}=\angle \mathrm{BCD}=\omega $. From the sum of
angles of various triangles, we find that
$\beta +\gamma =\psi +\omega $,
$\alpha +\gamma =\phi +\omega $ and
$\alpha +\beta =\psi +\phi $, whence
$\alpha =\phi $,
$\beta =\psi $,
$\gamma =\omega $.
>From this, we see that all the triangles are similar,
and congruence follows from the fact that each pair of
triangles have corresponding sides in common.
Solution 2. Let
$R$ and
$r$ be respectively the
circumradius and the inradius of
$\mathrm{ABCD}$, let the
faces
$\mathrm{BCD}$,
$\mathrm{ACD}$,
$\mathrm{ABD}$ and
$\mathrm{ABC}$ touch the insphere
in the respective points
$P$,
$Q$,
$T$,
$S$, and let
$O$ be the common centre of the insphere and the
circumsphere. Since triangle
$\mathrm{OSA}$ is right with
$\Vert \mathrm{OS}\Vert =r$ and
$\Vert \mathrm{OA}\Vert =R$, we have
that
$\Vert \mathrm{SA}\Vert =\sqrt{{R}^{2}{r}^{2}}$. Similarly,
$\Vert \mathrm{SB}\Vert =\Vert \mathrm{SC}\Vert =\sqrt{{R}^{2}{r}^{2}}$,
so that
$S$ is the centre of a circle with radius
$\sqrt{{R}^{2}{r}^{2}}$ passing through
$A$,
$B$,
$C$.
The same can be said about
$P$,
$Q$,
$T$, and the faces
that contain them.
It can be seen that
$\Delta \mathrm{ABT}\equiv \Delta \mathrm{ABS}$,
$\Delta \mathrm{ACQ}\equiv \Delta \mathrm{ACS}$,
$\Delta \mathrm{ADQ}\equiv \Delta \mathrm{ADT}$,
$\Delta \mathrm{BCP}\equiv \Delta \mathrm{BCS}$,
$\Delta \mathrm{BDP}\equiv \Delta \mathrm{BDR}$ and
$\Delta \mathrm{CDP}\equiv \Delta \mathrm{CDQ}$. Now
$\angle \mathrm{ABS}+\angle \mathrm{ACS}={90}^{\u02c6}\angle \mathrm{BCS}={90}^{\u02c6}\angle \mathrm{BCP}=\angle \mathrm{BDP}+\angle \mathrm{CDP}$
and
$\angle \mathrm{ABT}+\angle \mathrm{BDT}={90}^{\u02c6}\angle \mathrm{DAT}={90}^{\u02c6}\angle \mathrm{DAQ}=\angle \mathrm{ACQ}+\angle \mathrm{DCQ}\hspace{1em}.$
Since
$\angle \mathrm{ABS}=\angle \mathrm{ABT}$,
$\angle \mathrm{ACS}=\angle \mathrm{ACQ}$,
$\angle \mathrm{BDP}=\angle \mathrm{BDT}$ and
$\angle \mathrm{CDP}=\angle \mathrm{DCQ}$,
it follows that
$\angle \mathrm{ABS}\angle \mathrm{CDP}=\pm (\angle \mathrm{ACS}\angle \mathrm{BDP})={0}^{\u02c6}$
so
$\angle \mathrm{ABC}=\angle \mathrm{BCD}$.
Obtaining other similar angle equalities, we can determine
that the faces are equiangular. Taking note of common sides,
we can then deduce their congruence.