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 well-known 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

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{n-1}=\frac{1}{\sqrt{n}-\sqrt{n-1}}$
whence

$\frac{1}{\sqrt{n}}<2(\sqrt{n}-\sqrt{n-1})\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}^{ˆ}$ 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 $n-k-1$ 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 (n-k-1)k$. Therefore

$l(G)\le k+(n-k-1)k=k(n-k)\hspace{1em}.$
Applying the arithmetic-geometric means inequality, we get $k(n-k)\le [k+(n-k)]{}^2/4=n^2/4$, so that $l(G)\le n^2/4$. Since $l(G)$ is a natural number, the desired result follows. $♠$

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}^{ˆ}$ 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}^{ˆ}$; 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}^{ˆ}$ giving an angle sum in excess of ${180}^{ˆ}$. According to Turan's theorem, there are no more than $\lfloor {21}^2/4\rfloor =110$ such segments, so there must be at least $210-110=100$ arcs that do not exceed ${120}^{ˆ}$.

Solution 2. [M. Tancer, O. Bormashenko] There are 210 arcs not exceeding ${180}^{ˆ}$ 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}^{ˆ}$. If all of the 210 arcs do not exceed ${120}^{ˆ}$, then the problem is solved.

Suppose that there is an arc $\mathrm{AB}$ exceeding ${120}^{ˆ}$. For any third point $C$, among the three arcs $\mathrm{AB}$, $\mathrm{AC}$, $\mathrm{BC}$, at least one must not exceed ${120}^{ˆ}$; 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}^{ˆ}$. Thus, there are at least 19 arcs one of whose endpoints is either $A$ or $B$ exceeding ${120}^{ˆ}$. 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}^{ˆ}$ is 20. If there are no further arcs exceeding ${120}^{ˆ}$, the problem is solved.

Otherwise, let $\mathrm{DE}$ be a second arc exceeding ${120}^{ˆ}$, 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}^{ˆ}$. 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}^{ˆ}$. Continuing this procedure, we find that at most $20+18+16+\dots +2=110$ arcs exceeding ${120}^{ˆ}$. So there must be at least 100 arcs that do not exceed ${120}^{ˆ}$.

Comment. Here is an example in which the number of arcs not exceeding ${120}^{ˆ}$ 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}^{ˆ}$. 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}^{ˆ}$. The remaining arcs do not exceed ${120}^{ˆ}$.

---

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}^{ˆ}$, 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}^{ˆ}$, 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.