---

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+2x_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(u-v)$ (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)(u-w)$. 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)(1-a+a^2)=(b+c)(b^2-\mathrm{bc}+c^2)$, and since $1-a+a^2$ and $b^2-\mathrm{bc}+c^2$ are positive, we have that

$1+a<b+c\&lrArr;1-a+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 1-a+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}(b-c){}^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

$(1-a+a^2)-(b^2-\mathrm{bc}+b^2)=(1+a^2)-(b^2+c^2)+(\mathrm{bc}-a)>0$
so that

$(1-a+a^2)>(b^2-\mathrm{bc}+c^2)\hspace{1em}.$
However

$(1+a)(1-a+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 $(a-b)(a-c)>0$, whence $a^2+\mathrm{bc}>a(b+c)$. Therefore

$\begin{array}{cc}(b+c-a){}^3\hfill & =b^3+c^3-a^3+3b^{2}c+3{\mathrm{bc}}^2-3{\mathrm{ab}}^2-3{\mathrm{ac}}^2+3a^{2}b+3a^{2}c-6\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{b-1}{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=(u-v)/u$ in the definition of concavity, we have that

$f(v)\ge \frac{\mathrm{vf}(u)+(u-v)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}\sin 2\theta =i(b+c)\sin \theta$, whence $\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}\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}^{ˆ}-\angle \mathrm{BCS}={90}^{ˆ}-\angle \mathrm{BCP}=\angle \mathrm{BDP}+\angle \mathrm{CDP}$
and

$\angle \mathrm{ABT}+\angle \mathrm{BDT}={90}^{ˆ}-\angle \mathrm{DAT}={90}^{ˆ}-\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^{ˆ}$ 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.