Solutions and Comments

19.

Is it possible to divide the natural numbers
$1,2,\dots ,n$ into two groups, such that the squares
of the members in each group have the same sum, if
(a)
$n=40000$; (b)
$n=40002$? Explain your answer.
Solution. [M. Holmes] (a) Yes, it is possible.
Partition the numbers into two sets
$A$ and
$B$ such that
 if
$i\equiv 1,4,6,7$ (mod 8), put
$i$ in set
$A$;
 if
$i\equiv 2,3,5,8$ (mod 8), put
$i$ in set
$B$.
Since 40000 is a multiple of 8, there are
5000 strings of eight consecutive natural numbers.
For each of them, it is straightforward to see that
$\begin{array}{cc}(8k+1){}^{2}+(8k+4){}^{2}+(8k+6){}^{2}+(8k+7){}^{2}\hfill & =4\times (8k){}^{2}+16\times (1+4+6+7)+(1+16+36+49)\hfill \\ \multicolumn{0}{c}{}& =4\times (8k){}^{2}+16\times (2+3+5+8)+(4+9+25+64)\hfill \\ \multicolumn{0}{c}{}& =(8k+2){}^{2}+(8k+3){}^{2}+(8k+5){}^{2}+(8k+8){}^{2}\hfill \end{array}$
for
$0\le k\le 4999$. So, if the numbers are put into
the sets as suggested, the squares of the numbers in
each group will have the same sum.
(b) No, it is impossible. Suppose it were possible to partition
the numbers from 1 to 40002 inclusive into two sets
$A$ and
$B$ as required. There is a wellknown formula for
the sum of the squares of the first
$n$ natural numbers,
${1}^{2}+{2}^{2}+\dots +{n}^{2}=\frac{n(n+1)(2n+1)}{6}$
which we recommend that you prove by induction. When
$n=40002$, this sum is odd, and so we cannot express
it as the sum of two equal numbers, the sums of the
squares in
$A$ and in
$B$. Hence, the desired partition
is not possible.
Comment. One does not need the formula for the sum of
squares to establish that the sum is odd; just note that
the sum has 20001 odd summands.

20.

Given any six irrational numbers, prove that
there are always three of them, say
$a$,
$b$,
$c$, for which
$a+b$,
$b+c$ and
$c+a$ are irrational.
Solution. [O. Bormashenko] Recall the result given in the solution to
Problem 9 in
Olymon 1:5 (August, 2000):
For any
six points in space, let the full graph of all fifteen
edges between two of them be coloured with two colours.
There exists a triangle of three of its vertices, each
edge of which has the same colour. Let each of the six
irrational numbers be assigned a point in space, and
colour an edge joining two points representing a
pair
$(u,v)$ red if
$u+v$ is rational and green
if
$u+v$ is irrational. Then there must be a red
triangle or a green triangle. Suppose, if possible, there
is a red triangle. Then three of the numbers,
say
$a$,
$b$,
$c$, have
$a+b$,
$b+c$,
$c+a$ all
rational. But then
$2a=(a+b)+(c+a)(b+c)$ would be rational,
contrary to hypothesis. So there is no red triangle,
and so there must be a green triangle. The triple corresponding
to the vertices of this triangle must satisfy the
requirement of the problem.

21.

The natural numbers
${x}_{1}$,
${x}_{2}$,
$\dots $,
${x}_{100}$
are such that
$\frac{1}{\sqrt{{x}_{1}}}+\frac{1}{\sqrt{{x}_{2}}}+\dots +\frac{1}{\sqrt{{x}_{100}}}=20\hspace{1em}.$
Prove that at least two of the numbers are equal.
Solution. [R. Barrington Leigh] We construct a proof by
contradiction. Assume that the natural numbers are distinct,
and, wolog, in increasing order. Thus,
$1\le {x}_{1}$,
$2\le {x}_{2}$,
$3\le {x}_{3}$,
$\dots $,
$100\le {x}_{100}$,
so that
$\frac{1}{\sqrt{{x}_{1}}}+\frac{2}{\sqrt{{x}_{2}}}+\dots +\frac{1}{\sqrt{{x}_{100}}}\le \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots +\frac{1}{\sqrt{100}}\hspace{1em}.$
On the other hand, for each natural number
$n$,
$2\sqrt{n}>\sqrt{n}+\sqrt{n1}=\frac{1}{\sqrt{n}\sqrt{n1}}$
whence
$\frac{1}{\sqrt{n}}<2(\sqrt{n}\sqrt{n1})\hspace{1em}.$
It follows that
$\begin{array}{cc}20\hfill & =\frac{1}{\sqrt{{x}_{1}}}+\frac{1}{\sqrt{{x}_{2}}}+\dots +\frac{1}{\sqrt{{x}_{100}}}\hfill \\ \multicolumn{0}{c}{}& \le \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\dots +\frac{1}{\sqrt{100}}\hfill \\ \multicolumn{0}{c}{}& <2[(\sqrt{1}\sqrt{0})+(\sqrt{2}\sqrt{1})+\dots +(\sqrt{100}\sqrt{99})]=20\hfill \end{array}$
or
$20<20$, which is palpably false. Therefore, the
assumption that the numbers
${x}_{1}$,
${x}_{2}$,
$\dots $,
${x}_{100}$ is false, and the desired result holds.

22.

Let R be a rectangle with dimensions
$11\times 12$.
Find the least natural number
$n$ for which it is possible to cover
R with
$n$ rectangles, each of size
$1\times 6$ or
$1\times 7$,
with no two of these having a common interior point.
Comment. Clearly, we can use 22 rectangles of size
$1\times 6$, so the optimum number is no greater than this.
We show in fact that the optimum value of
$n$ is 20.
First, we establish that at least 20 rectangles are needed,
and then display a case in which 20 suffice.
Solution. Let some squares be marked with
x as
in Figure 1.
It is impossible to cover more than one of the
marked squares with a small rectangle, whether
$1\times 6$
or
$1\times 7$, so we need at least as many rectangles as
marked squares,
i.e., at least 20. On the other hand,
we can achieve the covering with 12 rectangles of size
$1\times 7$ and 8 of size
$1\times 6$, as indicated in
Figure 2.

23.

Given 21 points on the circumference of a circle,
prove that at least 100 of the arcs determined by pairs of
these points subtend an angle not exceeding
${120}^{\u02c6}$ at
the centre.
Comment. Before providing the solution of this problem,
it is necessary to recall some basic concepts from graph theory
and to prove one theorem. A
graph is a topological
combination of two sets, points and line segments between
some pairs of the points. The points are referred to as the
vertices or
nodes of the graph and the line segments as
edges or
arcs. Let
$G$ be a graph. If
$A$ is a vertex
of
$G$, then the
degree,
$d(A)$, of
$A$ is the number of
edges emanating from
$A$. The number of edges is denoted by
$l(G)$. If there are three vertices,
$A$,
$B$,
$C$, of
$G$ such that any two of them are connected by an edge,
the set of vertices
$A$,
$B$,
$C$ and edges
$\mathrm{AB}$,
$\mathrm{BC}$,
$\mathrm{CA}$
is a
triangle in
$G$, and the number of triangles in
$G$ is denoted by
$t(G)$. If there are four vertices with
any pair connected by an edge, then the set of the four
vertices and their six edges is a
tetrahedron in
$G$, and the number of all tetrahedra is denoted by
$T(G)$.
The angle of an arc is the angle subtended by the arc at
the centre of the circle.
Turan's Theorem. Let
$G$ be a graph with
$n$ vertices.
If
$t(G)=0$, then
$l(G)\le \lfloor {n}^{2}/4\rfloor $.
(This theorem is named after the Eastern European mathematician
Pal Turan and is very useful in a variety of problems, for
which it is possible to model the given objects and their
relationships with a graph. In other words, it says that
in a graph with
$n$ vertices with no triangles, there are
no more than
$\lfloor {n}^{2}/4\rfloor $ edges. It is easy to
check that the result holds for
$n=3$ and
$n=4$, and you
should do this.)
Proof of Turan's theorem. In the graph
$G$, let
$A$ be the
vertex of greatest degree (i.e., the number of edges from
any other vertex does not exceed the number from
$A$).
Suppose that
$d(A)=k$ (a natural number), that
${B}_{1}$,
${B}_{2}$,
$\dots $,
${B}_{k}$ are the vertices connected to
$A$ by
an edge, and that
$G\text{'}$ is the graph that can be obtained from
$G$ by removing
$A$ and all edges emanating from
$A$.
Then,
$l(G)=d(A)+l(G\text{'})$. Obviously, there is no edge
${B}_{i}{B}_{j}$ because, otherwise, the vertices
$A$,
${B}_{i}$,
${B}_{j}$ will form a triangle. So, in
$G\text{'}$ are counted
only all edges emanating from the
$nk1$ vertices of
$G$
other than
$A$,
${B}_{1}$,
${B}_{2}$,
$\dots $,
${B}_{k}$. Since
$d(A)=k$
is the maximum number of edges emanating from any vertex,
$l(G\text{'})\le (nk1)k$. Therefore
$l(G)\le k+(nk1)k=k(nk)\hspace{1em}.$
Applying the arithmeticgeometric means inequality, we
get
$k(nk)\le [k+(nk)]{}^{2}/4={n}^{2}/4$, so that
$l(G)\le {n}^{2}/4$. Since
$l(G)$ is a natural number, the
desired result follows.
$\u2660$
Two examples show that this value can be reached, so that
it is the largest possible value of
$l(G)$.
Example 1. Let
$n=2p$ be an even number. Partition
the vertices into two sets with
$p$ vertices in each.
Draw all edges connecting a vertex from one set to the other.
There are example
${p}^{2}={n}^{2}/4$ edges, with no triangles
formed. Any additional edge will form a triangle with some
other two.
Example 2. Let
$n=2p+1$ be an odd number. Partition the
vertices into two sets with
$p$ and
$p+1$ vertices. As in Example
1, connect ay vertex from one set with one in the other to obtain
a total of
$p(p+1)=\lfloor {n}^{2}/4\rfloor $ edges, with no
triangle in the graph.
(There is a similar theorem about tetrahedra in the graph, to wit:
for a graph with
$n$ vertices with
$T(G)=0$, then
$l(G)\le \lfloor {n}^{2}/3\rfloor $. This can be proved using similar
ideas to those for the triangle case. Here is an example of
a graph with
$T(G)=0$ and
$l(G)=\lfloor {n}^{2}/3\rfloor $.
Divide the vertices of
$G$ into three ``almost equal'' sets
(the difference between the numbers of vertices in any two of
the sets is at most 1). Connect two vertices with an edge if
and only if they are from two different sets.)
Now we apply Turan's Theorem to solve Problem 23.
Solution 1. Count all arcs not exceeding
${180}^{\u02c6}$
and ending in any two of the given 21 points. There are
$210=\left(\genfrac{}{}{0ex}{}{21}{2}\right)$ arcs in all. Connect with a segment
any two points determining an arc exceeding
${120}^{\u02c6}$;
consider all such segments as edges in a graph
$G$ whose
vertices are the 21 given points. There are no triangles in
$G$ (otherwise, each of its angles would exceed
${60}^{\u02c6}$
giving an angle sum in excess of
${180}^{\u02c6}$. According to
Turan's theorem, there are no more than
$\lfloor {21}^{2}/4\rfloor =110$ such segments, so there must be at least
$210110=100$ arcs that do not exceed
${120}^{\u02c6}$.
Solution 2. [M. Tancer, O. Bormashenko] There are
210 arcs not exceeding
${180}^{\u02c6}$ for the 21 points on the
circumference of the circle, one for each pair. Given three
points on the circle, at least one of the arcs between two of them
must not exceed
${120}^{\u02c6}$. If all of the 210 arcs do not
exceed
${120}^{\u02c6}$, then the problem is solved.
Suppose that there is an arc
$\mathrm{AB}$ exceeding
${120}^{\u02c6}$. For
any third point
$C$, among the three arcs
$\mathrm{AB}$,
$\mathrm{AC}$,
$\mathrm{BC}$, at least
one must not exceed
${120}^{\u02c6}$; since it is not
$\mathrm{AB}$, it must
be one of the other two. Similarly, for each of the nineteen
points other than
$A$ and
$B$, there must be at least one
arc determined by that point and one of
$A$ and
$B$ not exceeding
${120}^{\u02c6}$. Thus, there are at least 19 arcs one of whose
endpoints is either
$A$ or
$B$ exceeding
${120}^{\u02c6}$.
Since there are
$2\times 19+1=39$ arcs with at least one
endpoint
$A$ or
$B$, the maximum number of arcs among them
exceeeding
${120}^{\u02c6}$ is 20. If there are no further arcs
exceeding
${120}^{\u02c6}$, the problem is solved.
Otherwise, let
$\mathrm{DE}$ be a second arc exceeding
${120}^{\u02c6}$, with
$D$ and
$E$ distinct from
$A$ and
$B$. There are at least 19 arcs
with at least one endpoint
$D$ or
$E$ not exceeding
${120}^{\u02c6}$.
Since all arcs emanating form
$A$ and
$B$ have been counted, there
are at least 17 new such arcs, and at most 18 arcs exceeding
${120}^{\u02c6}$.
Continuing this procedure, we find that at most
$20+18+16+\dots +2=110$ arcs exceeding
${120}^{\u02c6}$. So there must be
at least 100 arcs that do not exceed
${120}^{\u02c6}$.
Comment. Here is an example in which the number of
arcs not exceeding
${120}^{\u02c6}$ is exactly 100. Let the
centre of the circle be
$O$, and let
$\mathrm{AB}$ and
$\mathrm{CD}$ be
two diameters with
$\angle \mathrm{AOC}={60}^{\u02c6}$. On the
circumference of the circle, put 10 points on the smaller
arc
$\mathrm{AC}$ and 11 on the smaller arc
$\mathrm{BD}$, all distinct from
$A$,
$B$,
$C$,
$D$. Consider all arcs between a point from
the first set and a point from the second set; there are
$10\times 11=110$ such arcs, all exceeding
${120}^{\u02c6}$.
The remaining arcs do not exceed
${120}^{\u02c6}$.

24.

$\mathrm{ABC}$ is an acute triangle with orthocentre
$H$.
Denote by
$M$ and
$N$ the midpoints of the respective segments
$\mathrm{AB}$ and
$\mathrm{CH}$, and by
$P$ the intersection point of the
bisectors of angles
$\mathrm{CAH}$ and
$\mathrm{CBH}$. Prove that the points
$M$,
$N$ and
$P$ are collinear.
Solution. Let
${h}_{a}$ and
${h}_{b}$ be the altitudes from
$A$ and
$B$ respectively, and let them
$\mathrm{BC}\cap {h}_{a}=\{E\}$ and
$\mathrm{AC}\cap {h}_{b}=\{D\}$. Let
${l}_{1}$ and
${l}_{2}$ be the respective angle bisectors of angles
$\mathrm{CAH}$ and
$\mathrm{CBH}$. Since
$\angle \mathrm{CDH}=\angle \mathrm{CEH}={90}^{\u02c6}$,
the quadrilaterial
$\mathrm{CDHE}$ is inscribed in a circle
${k}_{1}$ with
centre
$N$ and diameter
$\mathrm{CH}$. Hence
$\mathrm{ND}=\mathrm{NE}$, as radii of the
circle
${k}_{1}$. Similarly, since
$\angle \mathrm{ADB}=\angle \mathrm{AEB}={90}^{\u02c6}$, the quadrilateral
$\mathrm{ADEB}$ is inscribed in a
circle
${k}_{2}$ with centre
$M$ and diameter
$\mathrm{AB}$. Hence
$\mathrm{MD}=\mathrm{ME}$ as
radii of the circle
${k}_{2}$. It follows that
$\mathrm{MN}$ is the right
bisector of the segment
$\mathrm{DE}$; denote it by
${S}_{\mathrm{DE}}$. So, to prove
$M$,
$N$ and
$P$ collinear, it suffices to prove that
$P\in {S}_{\mathrm{DE}}$,
or
$\mathrm{PD}=\mathrm{PE}$.
Consider the circle
$\mathrm{ADEB}$. Let
$G$ be the centre of the
arc
$\mathrm{DE}$. Since
$\angle \mathrm{DAG}=\angle \mathrm{GAE}$,
${l}_{1}$ must pass
through
$G$; since
$\angle \mathrm{EBG}=\angle \mathrm{GED}$,
${l}_{2}$ must
pass through
$G$.
But then the point of intersection of
${l}_{1}$ and
${l}_{2}$ is
$P$, so that
$P$ must
coincide with
$G$ and therefore be the midpoint of the arc
$\mathrm{DE}$.
Now it is easy to see that the triangles
$\mathrm{DPM}$ and
$\mathrm{EPM}$ are congruent
(
$\mathrm{DM}=\mathrm{PM}=\mathrm{EM}$ as radii and
$\angle \mathrm{DMP}=\angle \mathrm{PME}$). Hence,
$\mathrm{PD}=\mathrm{PE}$ and so
$M$,
$N$ and
$P$ are collinear.