Solutions

133.

Prove that, if
$a$,
$b$,
$c$,
$d$ are real numbers,
$b\ne c$,
both sides of the equation are defined, and
$\frac{\mathrm{ac}{b}^{2}}{a2b+c}=\frac{\mathrm{bd}{c}^{2}}{b2c+d}\hspace{1em},$
then each side of the equation is equal to
$\frac{\mathrm{ad}\mathrm{bc}}{abc+d}\hspace{1em}.$
Give two essentially different examples of quadruples
$(a,b,c,d)$,
not in geometric progression, for which the conditions are satisfied.
What happens when
$b=c$?
Solution 1. The given condition is equivalent to
$\begin{array}{cc}0\hfill & =(\mathrm{ac}{b}^{2})(b2c+d)(\mathrm{bd}{c}^{2})(a2b+c)\hfill \\ \multicolumn{0}{c}{}& =(bc)(\mathrm{ac}{b}^{2}+\mathrm{bd}{c}^{2})[(\mathrm{ac}{b}^{2})(cd)+(\mathrm{bd}{c}^{2})(ab)]\hfill \end{array}$
Note that the quantity is square brackets vanishes when
$b=c$, so
that
$(bc)$ should be a factor of it. Indeed, we have
$(\mathrm{ac}{b}^{2})(cd)+(\mathrm{bd}{c}^{2})(ab)=(bc)(\mathrm{ad}\mathrm{bc})\hspace{1em}.$
Since
$b\ne c$, we find that the given condition is equivalent to
$0=(\mathrm{ac}{b}^{2})+(\mathrm{bd}{c}^{2})(\mathrm{ad}\mathrm{bc})$
or
$(\mathrm{ac}{b}^{2})+(\mathrm{bd}{c}^{2})=\mathrm{ad}\mathrm{bc}\hspace{1em}.$
It follows that
$\begin{array}{cc}\frac{\mathrm{ac}{b}^{2}}{a2b+c}\hfill & =\frac{\mathrm{bd}{c}^{2}}{b2c+d}\hfill \\ \multicolumn{0}{c}{}& =\frac{(\mathrm{ac}{b}^{2})+(\mathrm{bd}{c}^{2})}{(a2b+c)+(b2c+d)}\hfill \\ \multicolumn{0}{c}{}& =\frac{\mathrm{ad}\mathrm{bc}}{abc+d}\hspace{1em},\hfill \end{array}$
as desired. Note that, in the event that
$abc+d=0$, we must have
$\mathrm{ad}\mathrm{bc}=0$, as well. (Explain!)
A generic example is
$(a,b,c,d)=({r}^{k1}\pm 1,{r}^{k}\pm 1,{r}^{k+1}\pm 1,{r}^{k+2}\pm 1)$, where
$r\ne 0,1$ and
$k$ is arbitrary.
Suppose that
$b=c$. If
$a\ne b$ and
$d\ne b$, then both sides
of the datum reduce to
$b$, and the condition is a tautology.
However, the final fraction need not be equal to
$b$ in this case:
an example is
$(a,b,c,d)=(2,1,1,3)$. On the other hand,
suppose that
$a=b=c\ne d$. The one side of the datum is
undefined, while we find that
$\frac{\mathrm{bd}{c}^{2}}{b2c+d}=b\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{\mathrm{ad}\mathrm{bc}}{abc+d}=\frac{\mathrm{bd}{b}^{2}}{db}=b\hspace{1em}.$
If
$a\ne b=c=d$, then we have a similar result. Finally, if
$a=b=c=d$, then all fractions are undefined.
Solution 2. [A. Mao] Let
$k=\frac{\mathrm{ac}{b}^{2}}{a2b+c}=\frac{\mathrm{bd}{c}^{2}}{b2c+d}\hspace{1em}.$
Then
$(ak)(ck)=\mathrm{ac}\mathrm{ak}\mathrm{ck}+{k}^{2}={b}^{2}2\mathrm{bk}+{k}^{2}=(bk){}^{2}$
and
$(bk)(dk)=(ck){}^{2}\hspace{1em}.$
Hence
$(ak)(dk)[(bk)(ck)]=[(bk)(ck)]{}^{2}\hspace{1em}.$
Note that
$b=k\&lrArr;c=k$. Since
$b\ne c$, then
both
$b$ and
$c$ must differ from
$k$. Hence
$(ak)(dk)=(bk)(ck)\Rightarrow \mathrm{ad}\mathrm{bc}=k(abc+d)\hspace{1em}.$
If
$abc+d=0$, then
$\mathrm{ad}\mathrm{bc}=0$ and the expression in the
conclusion is undefined. Otherwise,
$\frac{\mathrm{ad}\mathrm{bc}}{abc+d}=k$
and the result follows.
The given conditions imply that
$ak$,
$bk$,
$ck$,
$dk$ are
in geometric progresion. Conversely, pick
$u$ arbitrary and
$r\ne 0,1$, and let
$(a,b,c,d)=(k+u,k+\mathrm{ur},k+{\mathrm{ur}}^{2},k+{\mathrm{ur}}^{3})$
to obtain a generic example.
Comments. Here are some numerical examples provided by various
solvers for
$(a,b,c,d)$: (1, 2, 5, 14), (1, 5, 3, 4),
(2, 6, 12, 21), (5, 9, 1, 17), (8, 24, 12, 21). Note that,
when
$(a,b,c,d)=(a,b,a,b)$, both sides of the datum equal
$\frac{1}{2}(a+b)$, while the fraction in the conclusion is
undefined.
The given condition is equivalent to
$0=(bc)(\mathrm{ac}+\mathrm{bd}+\mathrm{bc}\mathrm{ad}{b}^{2}{c}^{2})\hspace{1em},$
from which
$(\mathrm{ac}{b}^{2})+(\mathrm{bd}{c}^{2})=\mathrm{ad}\mathrm{bc}$, and we can
proceed as in Solution 1.
Very few full marks were given for this problem, as solvers were
not careful about details. Whenever an expression appears in a
denominator or you cancel a factor out of a product, you must
consider the possibility that it might vanish. Most people ignored
this possibility. In addition, the analysis of the situation when
$b=c$ was not at all thorough.

134.

Suppose that
$a=\mathrm{zb}+\mathrm{yc}$
$b=\mathrm{xc}+\mathrm{za}$
$c=\mathrm{ya}+\mathrm{xb}\hspace{1em}.$
Prove that
$\frac{{a}^{2}}{1{x}^{2}}=\frac{{b}^{2}}{1{y}^{2}}=\frac{{c}^{2}}{1{z}^{2}}\hspace{1em}.$
Of course, if any of
${x}^{2}$,
${y}^{2}$,
${z}^{2}$ is equal to 1, then
the conclusion involves undefined quantities. Give the proper
conclusion in this situation. Provide two essentially different
numerical examples.
Solution. Suppose, say, that
${x}^{2}=1$. Then
$x=\pm 1$, whence
$\mathrm{za}=b\mp c$ and
$\mathrm{ya}=c\mp b$.
Thus
$a(y\pm z)=0$. Suppose
$a=0$; then
${b}^{2}={c}^{2}$.
If
$b=c=0$, then
${b}^{2}(1{z}^{2})={c}^{2}(1{y}^{2})$. If
$\mathrm{bc}\ne 0$, then
$\Vert \mathrm{zb}\Vert =\Vert \mathrm{yc}\Vert $ implies that
${z}^{2}={y}^{2}$, in which case
${b}^{2}(1{z}^{2})={c}^{2}(1{y}^{2})$.
On the other hand, suppose that
${x}^{2}=1$ and
$a\ne 0$. Then
$y\pm z=0$, so that
$a=z(b\pm c)={\mathrm{az}}^{2}$
whence
${z}^{2}={y}^{2}={x}^{2}=1$. Since
$a\ne 0$, it is not possible for
both
$b$ and
$c$ to vanish. Let
$b\ne 0$. Then
$c\mathrm{xb}=\mathrm{ya}=\mathrm{yzb}+{y}^{2}c=\mathrm{yzb}+c$
so that
$x=\mathrm{yz}$. In this case, all the expressions
in the conclusion are undefined.
We now suppose that none of
${x}^{2}$,
${y}^{2}$,
${z}^{2}$ is equal to 1.
>From
$b=\mathrm{xc}+\mathrm{za}$ and
$\mathrm{xc}=\mathrm{xya}+{x}^{2}b$, we deduce that
$(1{x}^{2})b=(\mathrm{xy}+z)a\hspace{1em}.$
Since
${x}^{2}\ne 1$, we have that
$\mathrm{xy}+z\ne 0$, and so
$\frac{{a}^{2}}{1{x}^{2}}=\frac{\mathrm{ab}}{\mathrm{xy}+z}\hspace{1em}.$
>From
$c=\mathrm{ya}+\mathrm{xb}$ and
$\mathrm{xb}={x}^{2}c+\mathrm{xza}$, we deduce that
$(1{x}^{2})c=(\mathrm{xz}+y)a\hspace{1em},$
whence
$\frac{{a}^{2}}{1{x}^{2}}=\frac{\mathrm{ac}}{\mathrm{xz}+y}\hspace{1em}.$
>From
$a=\mathrm{zb}+\mathrm{yc}$ and
$\mathrm{zb}=\mathrm{xzc}+{z}^{2}a$, we deduce that
$(1{z}^{2})a=(\mathrm{xz}+y)c\hspace{1em},$
whence
$\frac{{c}^{2}}{1{z}^{2}}=\frac{\mathrm{ac}}{\mathrm{xz}+y}=\frac{{a}^{2}}{1{x}^{2}}\hspace{1em}.$
>From
$a=\mathrm{zb}+\mathrm{yc}$ and
$\mathrm{yc}={y}^{2}a+\mathrm{xyb}$, we deduce that
$(1{y}^{2})a=(\mathrm{xy}+z)b\hspace{1em},$
whence
$\frac{{b}^{2}}{1{y}^{2}}=\frac{\mathrm{ab}}{\mathrm{xy}+z}=\frac{{a}^{2}}{1{x}^{2}}\hspace{1em}.$
The result now follows.
Comments. Other interesting conclusions can be drawn.
Adding and subtracting the first two equations, we have that
$(ab)(1+z)=(yx)c$
$(a+b)(1z)=(y+x)c$
so that
$({a}^{2}{b}^{2})(1{z}^{2})=({y}^{2}{x}^{2}){c}^{2}$
$\Rightarrow \frac{{c}^{2}}{1{z}^{2}}=\frac{{a}^{2}{b}^{2}}{{y}^{2}{x}^{2}}\hspace{1em}.$
Similarly
$\frac{{b}^{2}}{1{y}^{2}}=\frac{{c}^{2}{a}^{2}}{{x}^{2}{z}^{2}}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\frac{{a}^{2}}{1{x}^{2}}=\frac{{b}^{2}{c}^{2}}{{z}^{2}{x}^{2}}\hspace{1em}.$
Also, since
$(\mathrm{xy}+z)a=(1{x}^{2})b$ and
$(\mathrm{xz}+y)a=(1{x}^{2})c$, we
have that
$(1{x}^{2})a=(1{x}^{2})(\mathrm{zb}+\mathrm{yc})=(2\mathrm{xyz}+{z}^{2}+{y}^{2})a\Rightarrow a({x}^{2}+{y}^{2}+{z}^{2}+2\mathrm{xyz})=a\hspace{1em}.$
Similarly,
$b({x}^{2}+{y}^{2}+{z}^{2}+2\mathrm{xyz})=b$ and
$c({x}^{2}+{y}^{2}+{z}^{2}+2\mathrm{xyz})=c$. For each solution of the given system for which
not all of
$a,b,c$ vanish, we must have
${x}^{2}+{y}^{2}+{z}^{2}+2\mathrm{xyz}=1$.
Since
$\mathrm{xc}=b\mathrm{za}$ and
$\mathrm{xb}=c\mathrm{ya}$, it follows that
${b}^{2}\mathrm{zab}={c}^{2}\mathrm{yac}$, so that
$\mathrm{bz}\mathrm{yc}=\frac{{b}^{2}{c}^{2}}{a}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{bz}+\mathrm{yc}=a\hspace{1em}.$
Hence
$z=\frac{{a}^{2}+{b}^{2}{c}^{2}}{2\mathrm{ab}}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}y=\frac{{a}^{2}+{c}^{2}{b}^{2}}{2\mathrm{ac}}\hspace{1em}.$
Also,
$x=\frac{{b}^{2}+{c}^{2}{a}^{2}}{2\mathrm{bc}}\hspace{1em}.$
If
$a,b,c$ are the sides of a triangle
$\mathrm{ABC}$, then we have
$\mathrm{cos}{}^{2}A+\mathrm{cos}{}^{2}B+\mathrm{cos}{}^{2}C+2\mathrm{cos}A\mathrm{cos}B\mathrm{cos}C=1\hspace{1em}.$
[Can you prove this directly?]
Here are some examples of sextuples
$(a,b,c;x,y,z)$:
$(a,b,c;\mathrm{cos}A,\mathrm{cos}B,\mathrm{cos}C)$,
$(1,3,6;\frac{11}{9},\frac{7}{3},\frac{13}{3})$,
$(2,5,9;\frac{17}{15},\frac{5}{3},\frac{13}{5})$,
$(5,5,0;4,4,1)$.

135.

For the positive integer
$n$, let
$p(n)=k$ if
$n$ is divisible by
${2}^{k}$ but not by
${2}^{k+1}$. Let
${x}_{0}=0$ and define
${x}_{n}$ for
$n\ge 1$ recursively by
$\frac{1}{{x}_{n}}=1+2p(n){x}_{n1}\hspace{1em}.$
Prove that every nonnegative rational number occurs exactly
once in the sequence
$\{{x}_{0},{x}_{1},{x}_{2},\dots ,{x}_{n},\dots \}$.
Comment. This problem of Donald E. Knuth was posed in a
recent issue of the
American Mathematical Monthly.
Solution. An examination of the table of values leads to the
conjectured recursions:
${x}_{2k+1}={x}_{k}+1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}(\mathrm{for}\hspace{1em}k\ge 0)\hspace{1em},$
$\frac{1}{{x}_{2k}}=\frac{1}{{x}_{k}}+1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}(\mathrm{for}\hspace{1em}k\ge 1)\hspace{1em}.$
Since
$({x}_{0},{x}_{1},{x}_{2})=(0,1,\frac{1}{2})$, this equation holds
for the lowest value of
$k$. We use an induction argument. Suppose
$k\ge 1$ and that
${x}_{2k1}={x}_{k1}+1$.
Then
$\begin{array}{cc}\frac{1}{{x}_{2k}}\hfill & =1+2p(2k){x}_{2k1}\hfill \\ \multicolumn{0}{c}{}& =1+2[1+p(k)]({x}_{k1}+1)\hfill \\ \multicolumn{0}{c}{}& =1+(1+2p(k){x}_{k1})=1+\frac{1}{{x}_{k}}\hfill \end{array}$
and
$\frac{1}{{x}_{2k+1}}=1{x}_{2k}=1\frac{{x}_{k}}{{x}_{k}+1}=\frac{1}{{x}_{k}+1}$
so that
${x}_{2k+1}={x}_{k}+1$.
The desired recursions follow.
>From the two recursions, we see that
${x}_{n}>1$ when
$n$ is odd and exceeds
1 and
${x}_{n}<1$ when
$n$ is even and exceeds 0. Thus, the values
${x}_{0}=0$ and
${x}_{1}=1$ are assumed only once. Suppose, if possible,
that some rational is assumed twice. Let
$r$ be the smallest index
for which
${x}_{r}={x}_{s}$ for some
$s>r\ge 2$. Then
$r$ and
$s$
must have the same parity and it follows from the recursions that
${x}_{\lfloor r/2\rfloor}={x}_{\lfloor s/2\rfloor}$, contradicting
the minimality of
$r$. Hence, no value of
${x}_{n}$ is assumed more
than once.
It is straightforward to
see that, for each nonnegative integer
$m$,
${x}_{{2}^{m}1}=m\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{x}_{{2}^{m}}=\frac{1}{m+1}\hspace{1em}.$
Also, suppose that
${x}_{u}{x}_{v}=1$. Then
$\frac{1}{{x}_{2v}}=\frac{1}{{x}_{v}}+1={x}_{u}+1={x}_{2u+1}$
so that
${x}_{2u+1}{x}_{2v}=1$.
Let
$m$ be a positive integer. We show that, for
$0\le k\le {2}^{m}1$,
$i={2}^{m}+k$ and
$j={2}^{m+1}(k+1)$,
${x}_{i}{x}_{j}=1$. This is clearly true for
$m=1$, since
${x}_{2}{x}_{3}=1$.
Suppose that it has been established for some particular value of
$m\ge 1$. We show that it holds for
$m$ replaced by
$m+1$.
Let
$0\le l\le {2}^{m+1}1$,
$i={2}^{m+1}+l={2}^{m+2}({2}^{m+1}l)$ and
$j={2}^{m+2}(l+1)={2}^{m+1}+({2}^{m+1}l1)$.
Since
$i$ and
$j$ have opposite parity and can be put into either
form, we may suppose wolog that
$l=2r$ is even, whereupon
$i=2v$ is even and
$j=2u+1$ is odd.
Thus
$v={2}^{m}+r$ and
$u={2}^{m}(r+1)$, so that by
the induction hypothesis,
${x}_{u}{x}_{v}=1$, whence it follows that
${x}_{i}{x}_{j}={x}_{2v}{x}_{2u+1}=1$. The desired result follows by
induction.
This shows that the set
$S$ of positive rationals of the form
${x}_{n}$
contains 0, 1 and is closed under each of the operations
$x\to x+1$ and
$x\to 1/x$. Thus
$S$
contains all nonnegative integers. Suppose we have shown that
$S$ contains all positive rationals with denominators not exceeding
$s$. Consider a rational
$p/(s+1)$ with
$1\le p\le s$.
By the induction hypothesis,
$(s+1)/p\in S$, so that
$p/(s+1)\in S$.
Hence, for each nonnegative integer
$t$,
$\frac{p}{(s+1)}+t=\frac{p+(s+1)t}{s+1}\in S\hspace{1em},$
and so we can conclude that every positive rational with denominator
$s+1$ belongs to
$S$. Hence, by induction, we see that
$S$ contains
every rational.

136.

Prove that, if in a semicircle of radius 1, five
points
$A$,
$B$,
$C$,
$D$,
$E$ are taken in consecutive order,
then
$\Vert \mathrm{AB}\Vert {}^{2}+\Vert \mathrm{BC}\Vert {}^{2}+\Vert \mathrm{CD}\Vert {}^{2}+\Vert \mathrm{DE}\Vert {}^{2}+\Vert \mathrm{AB}\Vert \Vert \mathrm{BC}\Vert \Vert \mathrm{CD}\Vert +\Vert \mathrm{BC}\Vert \Vert \mathrm{CD}\Vert \Vert \mathrm{DE}\Vert <4\hspace{1em}.$
Comment. The inequality is strict except in certain degenerate
cases in which the points are not all distinct.
Solution 1. If
$A$ and
$E$ are shifted to the ends of the
diameter, then the left side is at least as large. Thus, it suffices
to prove the result when
$\mathrm{AE}$ is a diameter. Let
$\Vert \mathrm{AB}\Vert =a$,
$\Vert \mathrm{BC}\Vert =b$,
$\Vert \mathrm{CD}\Vert =c$,
$\Vert \mathrm{DE}\Vert =d$,
$\Vert \mathrm{AC}\Vert =u$ and
$\Vert \mathrm{CE}\Vert =v$.
Observe that
$v>c$ and
$u>b$ [why?].
Suppose
$\alpha =\angle \mathrm{CAE}$ and
$\beta =\angle \mathrm{CEA}$. Then
$\angle \mathrm{ABC}={180}^{\u02c6}\beta $ and
$\angle \mathrm{CDE}={180}^{\u02c6}\alpha $. We have
$\Vert \mathrm{AE}\Vert =2$, and
${u}^{2}={a}^{2}+{b}^{2}+2\mathrm{ab}\mathrm{cos}\beta ={a}^{2}+{b}^{2}+\mathrm{abv}>{a}^{2}+{b}^{2}+\mathrm{abc}$
and
${v}^{2}={c}^{2}+{d}^{2}+2\mathrm{cd}\mathrm{cos}\alpha ={c}^{2}+{d}^{2}+\mathrm{cdu}>{c}^{2}+{d}^{2}+\mathrm{bcd}\hspace{1em}.$
Hence
${a}^{2}+{b}^{2}+{c}^{2}+{d}^{2}+\mathrm{abc}+\mathrm{bcd}<{u}^{2}+{v}^{2}=4\hspace{1em}.$
Solution 2. [A. Mao] As in Solution 1, we reduce to the case
that
$\mathrm{AE}$ is a diameter. Use the same notation as in Solution 1,
and let
$\Vert \mathrm{AD}\Vert =p$ and
$\Vert \mathrm{BE}\Vert =q$. Note that
$\angle \mathrm{ABE}=\angle \mathrm{ACE}=\angle \mathrm{ADE}={90}^{\u02c6}$. By Ptolemy's
Theorem, we have that
$\begin{array}{cc}\Vert \mathrm{BC}\Vert \Vert \mathrm{AE}\Vert \hfill & +\Vert \mathrm{AB}\Vert \Vert \mathrm{CE}\Vert =\Vert \mathrm{AC}\Vert \Vert \mathrm{BE}\Vert \hfill \\ \multicolumn{0}{c}{}& \Rightarrow 2b+\mathrm{av}=\mathrm{uq}=\sqrt{4{v}^{2}}\sqrt{4{a}^{2}}\hfill \\ \multicolumn{0}{c}{}& \Rightarrow 4{b}^{2}+4\mathrm{bav}=164{a}^{2}4{v}^{2}\hfill \\ \multicolumn{0}{c}{}& \Rightarrow {a}^{2}+{b}^{2}+{v}^{2}+\mathrm{abv}=4\hspace{1em}.\hfill \end{array}$
Similarly,
${c}^{2}+{d}^{2}+{u}^{2}+\mathrm{cdu}=4$. Adding and using
${u}^{2}+{v}^{2}=4$, we obtain that
${a}^{2}+{b}^{2}+{c}^{2}+{d}^{2}+\mathrm{abv}+\mathrm{cdu}=4\hspace{1em}.$
Since triangles
$\mathrm{ABC}$ and
$\mathrm{CDE}$ are obtuse with the largest angles
at
$B$ and
$D$ respectively,
$c=\Vert \mathrm{CD}\Vert <\Vert \mathrm{CE}\Vert =v$
and
$a<u$, so that
${a}^{2}+{b}^{2}+{c}^{2}+{d}^{2}+\mathrm{abc}+\mathrm{bcd}<4\hspace{1em}.$

137.

Can an arbitrary convex quadrilateral be decomposed
by a polygonal line into two parts, each of whose diameters is
less than the diameter of the given quadrilateral?
Solution. No. Let
$\mathrm{ABC}$ be an equilateral triangle, and
let
$D$ be an exterior point in the region bounded by
$\mathrm{AC}$ and
the circle with centre B and radius AB. Then the diameter of the
quadrilateral
$\mathrm{ABCD}$ is
$\Vert \mathrm{AB}\Vert =\Vert \mathrm{BC}\Vert =\Vert \mathrm{CA}\Vert $. Any partition of the quadrilateral
$\mathrm{ABCD}$ into two
parts must have one of the parts containing two of the three
points
$A,B,C$; the diameter of this part is equal to that
of
$\mathrm{ABCD}$.

138.

(a) A room contains ten people. Among any three.
there are two (mutual) acquaintances. Prove that there are
four people, any two of whom are acquainted.


(b) Does the assertion hold if ``ten'' is replaced by
``nine''?
Solution. Observe that the members of any pair each not
acquainted with some third person must be acquainted with each
other. It follows that the pairs of any group of people, each
not acquainted with a particular outside person, must be
mutual acquaintances.
We first show that, if any individual, say
$A$,
is acquainted with at least six people,
$B,C,D,E,F,G$, then
the conclusion follows. Suppose,
$B$, say, does not know
$C,D,E$,
then each pair of
$A,C,D,E$ must be acquainted. On the other
hand, if
$B$ knows each of
$C,D,E$, then, as two of
$C,D,E$
know each other, say
$C$ and
$D$, then each pair of
$A,B,C,D$
must be acquainted. Since any person acquainted with
$A$
must either be acquainted with or not be acquainted with three
other people acquainted with
$A$, the result follows.
(a) When there are ten people, each person either is not acquainted
with four of the others (who then make a set of four each pair of
which are acquaintances) or must be acquainted with at least
six of the others, in which case
we get the result by the previous paragraph.
(b) The assertion holds for nine people. In this case,
each person either is not
acquainted with four of the others or must be acquainted with
at least five of the others. Suppose that each person is acquainted
with at least five of the others. Then, adding together the
number of acquaintances of each of the nine people, we get a sum
of at least
$9\times 5=45$. But, each pair of acquaintances is
counted twice, so the sum must be even and so be at least 46.
But then there must be someone with at least six acquaintances, and
we can obtain the desired result.