Solutions and Comments

---

37.

Let $\mathrm{ABC}$ be a triangle with sides $a$, $b$, $c$, inradius $r$ and circumradius $R$ (using the conventional notation). Prove that

Solution.

$\begin{array}{cc}{a}^2\hfill & -(b^2+c^2)(1-\cos A)=b^2+c^2-2\mathrm{bc}\cos A-(b^2+c^2)+(b^2+c^2)\cos A\hfill \\ \multicolumn{0}{c}{}& \ge (b-c){}^2\cos A\ge 0\hfill \end{array}$

$\Rightarrow a^2\ge (b^2+c^2)(1-\cos A)=2(b^2+c^2)\sin {}^2(A/2)\hspace{1em}.$
With similar inequalities for $b$ and $c$, we find that

$a^2{b}^2{c}^2\ge 8(a^2+b^2)(b^2+c^2)(c^2+a^2)\sin {}^2(A/2)\sin {}^2(B/2)\sin {}^2(C/2)\hspace{1em}.$
Since $r=4R\sin (A/2)\sin (B/2)\sin (C/2)$, the desired result follows. Equality holds if and only if the triangle is equilateral.

Comment. The identity in the solution can be obtained as follows. Let $2s=a+b+c$. Then

$\frac{r}{s-a}=\tan \frac{A}{2}=\frac{\sin \frac{A}{2}}{\cos \frac{A}{2}}$
while

$a=2R\sin A=4R\sin \frac{A}{2}\cos \frac{A}{2}\hspace{1em}.$
Hence

$\frac{\mathrm{ar}}{s-a}=4R\sin {}^2\frac{A}{2}\hspace{1em}.$
Using similar identities for the other sides, we find that

$\frac{{\mathrm{abcr}}^3}{(s-a)(s-b)(s-c)}=64R^3\sin {}^2\frac{A}{2}\sin {}^2\frac{B}{2}\sin {}^2\frac{C}{2}\hspace{1em}.(*)$
Note that the area $\Delta$ of the triangle is given by

$\Delta =\mathrm{rs}=\frac{\mathrm{abc}}{4R}=\sqrt{s(s-a)(s-b)(s-c)}\hspace{1em},$
so that the left side of $(*)$ becomes $4R\Delta r^2(\mathrm{rs}){\Delta }^{-2}=4{\mathrm{Rr}}^2\hspace{1em}.$ Substituting this in, dividing by $4R$ and taking the square root yields

$r=4R\sin \frac{A}{2}\sin \frac{B}{2}\sin \frac{C}{2}\hspace{1em}.$

---

38.

Let us say that a set $S$ of nonnegative real numbers if hunky-dory if and only if, for all $x$ and $y$ in $S$, either $x+y$ or $\Vert x-y\Vert$ is in $S$. For instance, if $r$ is positive and $n$ is a natural number, then $S(n,r)=\{0,r,2r,\dots ,\mathrm{nr}\}$ is hunky-dory. Show that every hunky-dory set is $\{0\}$, is of the form $S(n,r)$ or has exactly four elements.

Solution 1. $\{0\}$ and sets of the form $\{0,r\}$ are clearly hunky-dory. Let $S$ be a nontrivial hunky-dory set with largest postive element $z$. Then $2z\backslash not\in S$, so $0=z-z\in S$. Thus, every hunky-dory set contains 0. Suppose that $S$ has at least three elements, with least positive element $a$.

Suppose, if possible, that $S$ contains an element that is not a positive integer multiple of $a$. Let $b$ be the least nonmultiple of $a$. Then $0<b-a<b$. Since $b-a$ cannot be a multiple of $a$ (why?), we must have $b-a\backslash not\in S$ and $b+a\in S$. Since $z$ is the largest element of $S$, $z-a$ and $z-b$ belong to $S$. However, $(z-a)-(z-b)=b-a$ does not belong to $S$, so $2z-(a+b)=(z-a)+(z-b)\in S$. Therefore, $2z-(a+b)\le z$, whence $z\le a+b$, so that $z=a+b$. Thus, $S$ contains $\{0,a,b,a+b\}$, with $a+b$ the largest element. This subset is already hunky-dory. But suppose, if possible, $S$ contains more elements. Let $c$ be the smallest such element. Then $0<(a+b)-c\in S\Rightarrow a\le (a+b)-c\Rightarrow c<b\Rightarrow c=\mathrm{ma}$ for some positive integer $m\ge 2$. Since $b+\mathrm{ma}>b+a$, $b-\mathrm{ma}$ must belong to $S$, and so be a multiple of $a$. This yields a contradiction. Hence, $S$ must be equal to $\{0,a,b,a+b\}$.

The only remaining case is that $S$ consists solely of nonnegative multiples of some element $a$. Let $\mathrm{na}$ be the largest such multiple. If $n=2$, then $S=S(2,a)$. Suppose that $n>2$. Then $(n-1)a\in S$, so $S$ contains $\{0,a,(n-1)a,\mathrm{na}\}$, which is hunky-dory.

Suppose $S$ contains a further multiple $\mathrm{ma}$ with $2\le m\le n-2$. Since $a\in S$ and $\mathrm{na}+a>\mathrm{na}$, $(n-1)a\in S$, so that $n-(m+1)a=(n-1)a-\mathrm{ma}\in S\Rightarrow (m+1)a=n-[n-(m+1)a]\in S$. By induction, it can be shown that $\mathrm{ka}\in S$ for $m\le k\le n$. In particular, $(n-2)a\in S$ so that $2a=\mathrm{na}-(n-2)a\in S$. But then $3a,4a,\dots ,\mathrm{na}$ are in $S$ and so $S=S(n,a)$. The desired result follows,

Solution 2. [S. Niu] Let $S=\{a_0,a_1,\dots ,a_n\}$, with $a_0<a_1<\dots <a_n$. The elements $a_n-a_n$, $a_n-a_{n-1}$, $\dots$, $a_n-a_0$ are $n+1$ distinct elements of $S$ listed in increasing order, and so $a_0=0$, and for each $i$ with $0\le i\le n$, we must have that $a_n-a_i=a_{n-i}$. Let $i\le \frac{n}{2}$. Then $i\le n-i$ and so $a_i\le a_{n-i}$; thus, $a_i\le (a_n)/2\le a_{n-i}$. Thus, if $j>k\ge n/2$, $a_j-a_k\in S$.

Since $0<a_{n-1}-a_{n-2}<a_n-a_{n-2}=a_2$, it follows that $a_{n-1}-a_{n-2}=a_1$. Also, $0<a_{n-1}-a_{n-2}=a_1<a_{n-1}-a_{n-3}<a_n-a_{n-3}=a_3$, so that $a_{n-1}-a_{n-3}=a_2$. Continuing on in this way, we find that, for $i\ge n/2$,

$0<a_{n-1}-a_{n-2}<a_{n-1}-a_{n-3}<\dots <a_{n-1}-a_{n-i}<a_n-a_{n-i}=a_i,$
whence $a_{n-1}-a_{n-j}=a_{j-1}$ for $1\le j\le (n/2)$.

Now $0<a_{n-2}-a_{n-3}<a_{n-1}-a_{n-3}=a_2$ so $a_{n-2}-a_{n-3}=a_1$. We can proceed in this fashion to obtain that, for $j\ge n/2$, $a_{j+1}-a_j=a_1$. Hence, for $i\le (n/2)-1$, $a_{i+1}-a_i=(a_n-a_{n-i-1})-(a_n-a_{n-i})=a_{n-i}-a_{n-i-1}=a_1$.

Let $n=2m$. Then $a_i={\mathrm{ia}}_1$ and $a_{n-i}=a_n-{\mathrm{ia}}_1$ for $1\le i\le m$, so that $a_m={\mathrm{ma}}_1$ and $a_n=a_m+{\mathrm{ma}}_1={\mathrm{na}}_1$. It follows that $a_k={\mathrm{ka}}_1$ for $1\le k\le n$ and $S=S(n,a_1)$.

Let $n=2m+1$. If $m=0$, then $S=\{0,a_1\}=S(1,a_1)$. If $m=1$, then $S=\{0,a_1,a_3-a_1,a_3\}=\{0,a_1,a_2,a_1+a_2\}$ is a 4-element hunky-dory set. Let $m\ge 2$. Then, for $1\le i\le m$, $a_i={\mathrm{ia}}_1$ and $a_{n-i}=a_n-{\mathrm{ia}}_i$. Now $a_{m+1}=a_n-a_m>a_{n-1}-a_m>\dots \ge a_{m+2}-a_m>a_{m+1}-a_m\ge a_1$. Since $\{a_n-a_m=a_{m+(m+1)}-a_m,a_{n-1}-a_m,\dots ,a_{m+2}-a_m,a_{m+1}-a_m\}$ contains $m+1$ elements, we must have $a_{m+j}-a_m=a_j$ for $1\le j\le n-m=m+1$. Therefore, $a_i={\mathrm{ia}}_i$ for $1\le i\le n$. (Why does this last statement fail to follow when $m=1$?)

---

39.

(a) $\mathrm{ABCDEF}$ is a convex hexagon, each of whose diagonals $\mathrm{AD}$, $\mathrm{BE}$ and $\mathrm{CF}$ pass through a common point. Must each of these diagonals bisect the area?

(b) $\mathrm{ABCDEF}$ is a convex hexagon, each of whose diagonals $\mathrm{AD}$, $\mathrm{BE}$ and $\mathrm{CF}$ bisects the area (so that half the area of the hexagon lies on either side of the diagonal). Must the three diagonals pass through a common point?

Solution 1. (a) No, they need not bisect the area. Let the vertices of the hexagon have coordinates $(-1,0)$, $(-1,-1)$, $(1,-1)$, $(1,0)$, $(-t,t)$, $(t,-t)$ with $t>0$ but $t\ne 1$. The diagonals with equations $y=0$, $y=x$ and $y=-x$ intersect in the origin but do not bisect the area of the hexagon.

(b) Let the hexagon be $\mathrm{ABCDEF}$ and suppose that the intersection of the diagonals $\mathrm{AD}$ and $\mathrm{BE}$ is on the same side of $\mathrm{CF}$ as the side $\mathrm{AB}$. Thus, $\mathrm{AB}$, $\mathrm{CD}$ and $\mathrm{EF}$ border on triangles whose third vertices form a triangle at the centre of the hexagon (we will show this triangle to be degenerate). Let $a$, $b$, $c$, $d$, $e$, $f$ be the lengths of the rays from the respective vertices $A$, $B$, $C$, $D$, $E$, $F$ to the vertices of the central triangle, whose sides are $x$, $y$, $z$ so that the lengths of $\mathrm{AD}$, $\mathrm{BE}$ and $\mathrm{CF}$ are respectively $a+x+d$, $b+y+e$, $c+z+f$. All lower-case variables represent nonnegative real numbers.

Let the areas of the bordering on $\mathrm{FA}$, $\mathrm{AB}$, $\mathrm{BC}$, $\mathrm{CD}$, $\mathrm{DE}$, $\mathrm{EF}$ be respectively $\alpha$, $\beta$, $\gamma$, $\delta$, $\epsilon$, $\phi$, and let the area of the central triangle be $\lambda$. Then, since each diagonal bisects the area of the hexagon, we have that

$\alpha +\beta +\gamma +\lambda =\delta +\epsilon +\phi$

$\epsilon +\phi +\alpha +\lambda =\beta +\gamma +\delta$

$\gamma +\delta +\epsilon +\lambda =\phi +\alpha +\beta \hspace{1em}.$
>From the first two equations, we find that $\delta =\alpha +\lambda$. Similarly, $\phi =\gamma +\lambda$ and $\beta =\epsilon +\lambda$.

Using the fact that the area of a trangle is half the product of adjacent sides and the sine of the angle between them, and the equality of opposite angles, we find that

$1=\frac{\alpha +\lambda }{\delta }=\frac{(a+x)(f+z)}{\mathrm{cd}}$

$1=\frac{\gamma +\lambda }{\phi }=\frac{(b+y)(c+z)}{\mathrm{ef}}$

$1=\frac{\epsilon +\lambda }{\beta }=\frac{(d+x)(e+y)}{\mathrm{ab}}\hspace{1em}.$
Multiplying these three equations together yields that

$\mathrm{abcdef}=(a+x)(b+y)(c+z)(d+x)(e+y)c+z)\hspace{1em},$
whence $x=y=z=0$. Thus, the central triangle degenerates and the three diagonals intersect in a common point.

Solution 2. (a) No. Let $\mathrm{ABCDEF}$ be a regular hexagon. The diagonals $\mathrm{AD}$, $\mathrm{BE}$, $\mathrm{CF}$ intersect and each diagonal does bisect the area. Let $X$ be any point other than $F$ on the diagonal $\mathrm{CF}$ for which $\mathrm{ABCDEX}$ is still a convex hexagon. The diagonals of this hexagon are the same as those of the regular hexagon, and so have a common point of intersection. However, the diagonals $\mathrm{AD}$ and $\mathrm{BE}$ no longer intersect the area of the hexagon.

(b) [X. Li] Let $\mathrm{ABCDEF}$ be a given convex hexagon, each of whose diagonals bisect its area. Suppose that the diagonals $\mathrm{AD}$ and $\mathrm{CF}$ intersect at $G$. As in Solution 1, we can determine that the areas of triangles $\mathrm{AGF}$ and $\mathrm{DGC}$ are equal, whence $\mathrm{AG}·\mathrm{GF}=\mathrm{CG}·\mathrm{GD}$, or $\mathrm{AG}/\mathrm{GD}=\mathrm{CG}/\mathrm{GF}$. Therefore, $\Delta \mathrm{AGC}~\Delta \mathrm{DGF}$ (SAS). It follows that $\mathrm{AC}/\mathrm{DF}=\mathrm{AG}/\mathrm{GD}=\mathrm{CG}/\mathrm{GF}$, $\angle \mathrm{CAG}=\angle \mathrm{FDG}$, and so $\mathrm{AC}\mathrm{DF}$. In a similar way, we find that $\mathrm{BF}\mathrm{CE}$ and $\mathrm{AE}\mathrm{BD}$, so that $\Delta \mathrm{ACE}~\Delta \mathrm{DFB}$ and $\mathrm{AC}/\mathrm{DF}=\mathrm{CE}/\mathrm{FB}=\mathrm{EA}/\mathrm{BD}$.

Suppose diagonals $\mathrm{AD}$ and $\mathrm{BE}$ intersect at $H$. Then, as above, we find that $\mathrm{AG}/\mathrm{GD}=\mathrm{AC}/\mathrm{DF}=\mathrm{EA}/\mathrm{BD}=\mathrm{EH}/\mathrm{HB}=\mathrm{AH}/\mathrm{HD}$, so that $H=G$. Hence, the three diagonals have the point $G$ in common.

---

40.

Determine all solutions in integer pairs $(x,y)$ to the diophantine equation $x^2=1+4y^3(y+2)$.

Solution 1. Clearly, $(x,y)=(\pm 1,0),(\pm 1,-2)$ are solutions. When $y=-1$, the right side is negative and there is no solution. Suppose that $y\ge 1$; then

$(2y^2+2y){}^2=4y^4+8y^3+4y^2>4y^4+8y^3+1$
and

$(2y^2+2y-1){}^2=4y^4+8y^3-4y+1<4y^4+8y^3+1$
so that the right side is between two consecutive squares, and hence itself cannot be square.

Suppose that $y\le -3$. We first observe that for a given product $p$ of two positive integers, the sum of these positive integers has a minium value of $2\sqrt{p}$ (why?) and a maximum value of $1+p$. This follows from the fact that, for integers $u$ with $1\le u\le p$, 

$(1+p)-(u+p/u)=(u-1)[(p/u)-1]\ge 0\hspace{1em}.$
We have that

$\begin{array}{cc}[(2y^2+2y-1)+x]\hfill & [(2y^2+2y-1)-x]=(2y^2+2y-1){}^2-x^2\hfill \\ \multicolumn{0}{c}{}& =(4y^4+8y^3-4y+1)-(4y^4+8y^3+1)\hfill \\ \multicolumn{0}{c}{}& =-4y\hspace{1em}.\hfill \end{array}$
Since $2y^2+2y-1=y^2+(y+1){}^2-2$ is positive, at least one of the factors on the left is positive. Since the product is positive, both factors are positive. By our observation on the sum of the factors, we find that

$4y^2+4y-2\le 1-4y\hspace{1em},$
which is equivalent to

$4(y-1){}^2\le 7\hspace{1em}.$
However, this does not hold when $y\le -3$. Therefore, the only solutions are the four that we identified at the outset.

Solution 2. Since $x$ must be odd, we can let $x=2z+1$ for some integer $z$, so that the equation becomes $z(z+1)=y^4+2y^3$. We can deal with the cases that $y=0,-1,-2$ directly to obtain the solutions $(x,y,z)=(1,0,0),(-1,0,-1),(1,-2,0),(-1,-2,-1)$. Henceforth, suppose that $y\ge 1$ or $y\le -3$, so that $y^4+2y^3$ is positive. Let $\phi (t)=t(t+1)$. Then $\phi (t)$ is increasing for $t\ge 0$ and $\phi (-t)=\phi (t-1)$ for every integer $t$; thus, we need check only that $y^4+2y^3$ does not coincide with a value taken by $\phi (t)$ for nonnegative values of $t$.

Now

$\phi (y^2+y)=y^4+2y^3+2y^2+y>y^4+2y^3\hspace{1em}\hspace{1em};$

$\phi (y^2+y-1)=y^4+2y^3-y\ne y^4+2y^3\hspace{1em}\hspace{1em};$

$\begin{array}{cc}\phi (y^2+y-2)\hfill & =y^4+2y^3-2y^2-3y+2\hfill \\ \multicolumn{0}{c}{}& =y^4+2y^3-(2y+1)(y+1)+3<y^4+2y^3\hspace{1em}\hspace{1em}.\hfill \end{array}$
It follows that $\phi (t)$ can never assume the value $y^4+2y^3$ for any positive $t$, and hence for any $t$. Thus, the solutions already listed comprise the complete solution set.

---

41.

Determine the least positive number $p$ for which there exists a positive number $q$ such that

Comments. Recall the binomial expansion

$(1+x){}^n=1+\mathrm{nx}+\frac{n(n-1)}{2!}{x}^2+\frac{n(n-1)(n-2)}{3!}{x}^3+\dots +\frac{n(n-1)\dots (n-r+1)}{r!}{x}^r+\dots \hspace{1em}.$
When $n$ is not a nonnegative integer, this is an infinite series that converges when $0\le \Vert x\Vert <1$ to $(1+x){}^n$. The partial sums constitute a close approximation. When $n=\frac{1}{2}$, we have that

$(1\pm x){}^{\frac{1}{2}}=1\pm \frac{1}{2}x-\frac{1}{8}{x}^2\pm \frac{1}{16}{x}^3-\frac{5}{128}{x}^4\pm \dots$
so that

$(1+x){}^{\frac{1}{2}}+(1-x){}^{\frac{1}{2}}~2-\frac{x^2}{4}-\frac{x^4}{8}\le 2-\frac{x^4}{4}\hspace{1em}.$
This suggests that we are looking for $(p,q)=(2,4)$. However, the approximation approach is not sufficiently rigorous, and we need to find an argument in finite terms that will work.

Solution 1. Observe that, for $0\le x\le 1$,

$\sqrt{1\pm x}\le 1\pm \frac{1}{2}x-\frac{1}{8}{x}^2\pm \frac{1}{16}{x}^3$

$\&lrArr;1\pm x\le 1\pm x+\frac{5}{64}{x}^4\mp \frac{1}{64}{x}^5+\frac{1}{256}{x}^6$

$\&lrArr;0\le 5\mp x+4x^2\hspace{1em}.$
The last inequality clearly holds, so the first must as well. Hence

$\sqrt{1+x}+\sqrt{1-x}\le 2(1-\frac{1}{8}{x}^2)=2-\frac{1}{4}{x}^2$
so the pair $(p,q)=(2,4)$ works for all $x\in [0,1]$.

Suppose, for some constants $p$ and $c$ with $0<p<2$ and $c>0$,

$\sqrt{1+x}+\sqrt{1-x}\le 2-2{\mathrm{cx}}^p$
for $0\le x\le 1$. For this range of $x$, this is equivalent to

$2+2\sqrt{1-x^2}\le 4-8{\mathrm{cx}}^p+4c^2{x}^{2p}$

$\&lrArr;\sqrt{1-x^2}\le 1-4{\mathrm{cx}}^p+2c^2{x}^{2p}$

$\&lrArr;1-x^2\le 1-8{\mathrm{cx}}^p+20c^2{x}^{2p}-16c^3{x}^{3p}+4c^4{x}^{4p}$

$8c\le x^{2-p}+4c^2{x}^p(5-4{\mathrm{cx}}^{2p}+c^3{x}^{3p})\hspace{1em}.$
However, for $x$ sufficiently small, the right side can be made less than $8c$, yielding a contradiction. Hence, when $0<p<2$, there is no value that yields the desired inequality.

Now we look at the situation when $p=2$ and $q>0$. For $0\le x\le 1$,

$\sqrt{1+x}+\sqrt{1-x}\le 2-\frac{x^2}{q}$

$\&lrArr;2(1+\sqrt{1-x^2})\le 4-\frac{4x^2}{q}+\frac{x^4}{q^2}$

$\&lrArr;\sqrt{1-x^2}\le 1-\frac{2x^2}{q}+\frac{x^4}{2q^2}$

$\&lrArr;1-x^2\le 1-\frac{4x^2}{q}+\frac{5x^4}{q^2}-\frac{2x^6}{q^3}+\frac{x^8}{4q^4}$

$\&lrArr;0\le x^2[(1-\frac{4}{q})+\frac{x^2}{q^2}(5-\frac{2x^2}{q}+\frac{x^4}{4q^2})]\hspace{1em}.$
If $q<4$, then the quantity in square brackets is negative for small values of $x$. Hence, for the inequality to hold for all $x$ in the interval $[0,1]$, we must have $q\ge 4$. Hence, $p$ must be at least 2, and for $p=2$, $q$ must be at least 4.

Solution 2. [R. Furmaniak] The given inequality is equivalent to

$\begin{array}{cc}q\hfill & \ge \frac{x^p}{2-\sqrt{1+x}-\sqrt{1-x}}\hfill \\ \multicolumn{0}{c}{}& =\frac{x^p(2+\sqrt{1+x}+\sqrt{1-x})}{4-(2+2\sqrt{1-x^2})}\hfill \\ \multicolumn{0}{c}{}& =\frac{x^p(2+\sqrt{1+x}+\sqrt{1-x})}{2(1-\sqrt{1-x^2})}\hfill \\ \multicolumn{0}{c}{}& =\frac{x^p(2+\sqrt{1+x}+\sqrt{1-x})(1+\sqrt{1-x^2})}{2x^2}\hspace{1em}.\hfill \end{array}$
If $p<2$, then the right side becomes arbitrarily large as $x$ gets close to zero, so the inequality becomes unsustainable for any real $q$. Hence, for the inequality to be viable, we require $p\ge 2$. When $p=2$, we can cancel $x^2$ and see by taking $x=0$ that $q\ge 4$. It remains to verify the inequality when $(p,q)=(2,4)$. We have the following chain of logically equivalent statements, where $y=\sqrt{1-x^2}$ (note that $0\le x\le 1$):

$\sqrt{1+x}+\sqrt{1-x}\le 2-\frac{x^2}{4}$

$\&lrArr;2+2\sqrt{1-x^2}\le 4-x^2+\frac{x^4}{16}$

$\&lrArr;32\sqrt{1-x^2}\le x^4-16x^2+32$

$\&lrArr;32y\le 1-2y^2+y^4-16+16y^2+32$

$\&lrArr;$

$0\le y^4+14y^2-32y+17=(y-1){}^2(y^2+2y+17)=(y-1){}^2[(y+1){}^2+16]\hspace{1em}.$
Since the last inequality is clearly true, the first holds and the result follows.

---

42.

$G$ is a connected graph; that is, it consists of a number of vertices, some pairs of which are joined by edges, and, for any two vertices, one can travel from one to another along a chain of edges. We call two vertices adjacent if and only if they are endpoints of the same edge. Suppose there is associated with each vertex $v$ a nonnegative integer $f(v)$ such that all of the following hold:

(1) If $v$ and $w$ are adjacent, then $\Vert f(v)-f(w)\Vert \le 1$.

(2) If $f(v)>0$, then $v$ is adjacent to at least one vertex $w$ such that $f(w)<f(v)$.

(3) There is exactly one vertex $u$ such that $f(u)=0$.

Prove that $f(v)$ is the number of edges in the chain with the fewest edges connecting $u$ and $v$.

Solution. We prove by induction that $f(x)=n$ if and only if the shortest chain from $u$ to $x$ has $n$ members. This is true for $n=0$ (and for $n=1$). Suppose that this holds for $0\le n\le k$.

Let $f(x)=k+1$. There exists a vertex $y$ adjacent to $x$ for which $h=f(y)<k+1$. By the induction hupothesis, $y$ can be connected to $u$ by a chain of $h$ edges, so $x$ can be connected to $u$ by a chain of $h+1$ edges. Hence, $h+1\ge k+1$. From these two inequalities, we must have $h=k$, so $x$ can be connected to $u$ by a chain of $k+1$ edges. There cannot be a shorter chain, as, by the induction hypothesis, this would mean that $f(x)$ would have to be less than $k+1$.

Let the shortest chain connecting $x$ to $u$ have $k+1$ edges. Following along this chain, we can find an element $z$ adjacent to $x$ connected to $u$ by $k$ edges. This must be one of the shortest chains between $u$ and $z$, so that $f(z)=k$. By hypothesis (1), $f(x)$ must take one of the values $k-1$ and $k+1$. The first is not admissible, since there is no chain with $k-1$ edges connecting $u$ and $x$. Hence $f(x)=k+1$.