Solutions and Comments

Is it possible to divide the natural numbers 1,2,,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 i1,4,6,7 (mod 8), put i in set A;
- if i2,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

(8k+1)2 +(8k+4)2 +(8k+6)2 +(8k+7)2 =4×(8k)2 +16×(1+4+6+7)+(1+16+36+49) =4×(8k)2 +16×(2+3+5+8)+(4+9+25+64) =(8k+2)2 +(8k+3)2 +(8k+5)2 +(8k+8)2

for 0k4999. 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,

12 + 22 ++ n2 = 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.

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.

The natural numbers x1 , x2 , , x100 are such that

1 x1 + 1 x2 ++ 1 x100 =20.

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 x1 , 2 x2 , 3 x3 , , 100 x100 , so that

1 x1 + 2 x2 ++ 1 x100 1 1 + 1 2 ++ 1 100 .

On the other hand, for each natural number n,

2n>n+n-1= 1 n-n-1


1 n <2(n-n-1).

It follows that

20 = 1 x1 + 1 x2 ++ 1 x100 1 1 + 1 2 ++ 1 100 <2[(1-0)+(2-1)++(100-99)]=20

or 20<20, which is palpably false. Therefore, the assumption that the numbers x1 , x2 , , x100 is false, and the desired result holds.

Let R be a rectangle with dimensions 11×12. Find the least natural number n for which it is possible to cover R with n rectangles, each of size 1×6 or 1×7, with no two of these having a common interior point.
Comment. Clearly, we can use 22 rectangles of size 1×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×6 or 1×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×7 and 8 of size 1×6, as indicated in Figure 2.

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 AB, BC, 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) n2 /4.
(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 n2 /4 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 B1 , B2 , , Bk are the vertices connected to A by an edge, and that G' 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'). Obviously, there is no edge Bi Bj because, otherwise, the vertices A, Bi , Bj will form a triangle. So, in G' are counted only all edges emanating from the n-k-1 vertices of G other than A, B1 , B2 , , Bk . Since d(A)=k is the maximum number of edges emanating from any vertex, l(G')(n-k-1)k. Therefore


Applying the arithmetic-geometric means inequality, we get k(n-k)[k+(n-k)]2 /4= n2 /4, so that l(G) n2 /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 p2 = n2 /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)= n2 /4 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) n2 /3. 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)= n2 /3. 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=( 21 2 ) 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 212 /4=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 AB exceeding 120ˆ . For any third point C, among the three arcs AB, AC, BC, at least one must not exceed 120ˆ ; since it is not 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×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 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++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 AB and CD be two diameters with AOC= 60ˆ . On the circumference of the circle, put 10 points on the smaller arc AC and 11 on the smaller arc 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×11=110 such arcs, all exceeding 120ˆ . The remaining arcs do not exceed 120ˆ .

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