
 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

(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,

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.

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_{1}, 2 £ x_{2}, 3 £ x_{3}, ¼, 100 £ x_{100}, so that




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.
Turan's Theorem. Let G be a graph with n vertices. If t(G) = 0, then l(G) £ ën^{2}/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^{2}/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_{1}, B_{2}, ¼, 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_{i}B_{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 nk1 vertices of G other than A, B_{1}, B_{2}, ¼, B_{k}. Since d(A) = k is the maximum number of edges emanating from any vertex, l(G¢) £ (nk1)k. Therefore

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) = ën^{2} /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^{2}/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^{2}/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^{2}/4 û = 110 such segments, so there must be at least 210110 = 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^{°}.
Consider the circle ADEB. Let G be the centre of the arc DE. Since ÐDAG = ÐGAE, l_{1} must pass through G; since ÐEBG = Ð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 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.