Combinatorics and Probability 735then^2 −n+2 spherical regions divides some spatial region into two parts. This allows
us to write the recursive formula
F(n+ 1 )=F (n)+n^2 −n+ 2 ,F( 1 )= 2.Iterating, we obtain
F (n)= 2 + 4 + 8 +···+[(n− 1 )^2 −(n− 1 )+ 2 ]=∑n−^1k= 1(k^2 −k+ 2 )=
n^3 − 3 n^2 + 8 n
3.
839.Choose three pointsA, B, Cof the given set that lie on the boundary of its convex
hull. There are
(n− 3
2)
ways to select two more points from the set. The lineDEcuts
two of the sides of the triangleABC, say,ABandAC. ThenB, C, D, Eform a convex
quadrilateral. Making all possible choices of the pointsDandE, we obtain
(n− 3
2)
convex
quadrilaterals.
(11th International Mathematical Olympiad, 1969)
840.The grid is made up ofn(n 2 +^1 )small equilateral triangles of side length 1. In each of
these triangles, at most 2 segments can be marked, so we can mark at most^23 ·^3 n(n 2 +^1 )=
n(n+ 1 )segments in all. Every segment points in one of three directions, so we can
achieve the maximumn(n+ 1 )by marking all the segments pointing in two of the three
directions.
(Russian Mathematical Olympiad, 1999)
841.Assume by way of contradiction that the distance between any two points is greater
than or equal to 1. Then the spheres of radius^12 with centers at these 1981 points have
disjoint interiors, and are included in the cube of side length 10 determined by the six
parallel planes to the given cube’s faces and situated in the exterior at distance^12 .It
follows that the sum of the volumes of the 1981 spheres is less than the volume of the
cube of side 10, meaning that
1981 ·
4 π·( 1
2) 3
3
= 1981 ·
π
6> 1000 ,
a contradiction. This completes the proof.
Remark.If we naively divide each side of the cube into^3
√
1981 =12 congruent
segments, we obtain 12^3 =1728 small cubes of side 129 =^34. The pigeonhole principle
guarantees that some small cube contains two of the points, but unfortunately the upper
bound that we get for the distance between the two points is^343
√
3, which is greater than 1.
(Revista Matematica din Timi ̧soara ̆ (Timi ̧soara Mathematics Gazette), proposed by
T. Andreescu)