Solutions and Comments

Solutions and Comments

19.: 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 i º 1, 4, 6, 7 (mod 8), put i in set A;

- if i º 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

(8k+1)² + (8k + 4)² + (8k + 6)² + (8k + 7)²

= 4 ×(8k)² + 16 ×(1 + 4 + 6 + 7)+ (1 + 16 + 36 + 49)

= 4 ×(8k)² + 16 ×(2 + 3 + 5 + 8)+ (4 + 9 + 25 + 64)

= (8k+2)² + (8k+3)² + (8k+5)² + (8k+8)²

for 0 £ k £ 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² + ¼+ n² =

n(n+1)(2n+1)

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₁, x₂, ¼, x₁₀₀ are such that

__
Öx₁

__
Öx₂

+ ¼+

x₁₀₀

= 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 £ x₁, 2 £ x₂, 3 £ x₃, ¼, 100 £ x₁₀₀, so that

__
Öx₁

__
Öx₂

+¼+

x₁₀₀

Ö1

Ö2

+ ¼+

___
Ö100

On the other hand, for each natural number n,

2 Ön > Ön +

___
Ön-1

Ön -

___
Ön-1

whence

Ön

< 2(Ön -

___
Ön-1

) .

It follows that

__
Öx₁

__
Öx₂

+ ¼+

x₁₀₀

Ö1

Ö2

+ ¼+

___
Ö100

< 2[(Ö1 - Ö0) + (Ö2 - Ö1) + ¼+ (

___
Ö100

__
Ö99

)] = 20

or 20 < 20, which is palpably false. Therefore, the assumption that the numbers x₁, x₂, ¼, x₁₀₀ is false, and the desired result holds.

22.: 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.

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 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) £ ën²/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 ën²/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 B₁, B₂, ¼, B_k 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 B_iB_j because, otherwise, the vertices A, B_i, B_j will form a triangle. So, in G¢ are counted only all edges emanating from the n-k-1 vertices of G other than A, B₁, B₂, ¼, B_k. Since d(A) = k is the maximum number of edges emanating from any vertex, l(G¢) £ (n-k-1)k. Therefore

l(G) £ k + (n-k-1)k = k(n-k) .

Applying the arithmetic-geometric means inequality, we get k(n-k) £ [k + (n-k)]²/4 = n²/4, so that l(G) £ n²/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² = n²/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) = ën² /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) £ ën²/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) = ën²/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 ë21²/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^°.

24.: 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 h_a and h_b be the altitudes from A and B respectively, and let them BC Çh_a = { E } and AC Çh_b = { D }. Let l₁ and l₂ be the respective angle bisectors of angles CAH and CBH. Since ÐCDH = ÐCEH = 90^°, the quadrilaterial CDHE is inscribed in a circle k₁ with centre N and diameter CH. Hence ND = NE, as radii of the circle k₁. Similarly, since ÐADB = ÐAEB = 90^°, the quadrilateral ADEB is inscribed in a circle k₂ with centre M and diameter AB. Hence MD = ME as radii of the circle k₂. It follows that MN is the right bisector of the segment DE; denote it by S_DE. So, to prove M, N and P collinear, it suffices to prove that P Î S_DE, or PD = PE.

Consider the circle ADEB. Let G be the centre of the arc DE. Since ÐDAG = ÐGAE, l₁ must pass through G; since ÐEBG = ÐGED, l₂ must pass through G. But then the point of intersection of l₁ and l₂ 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.