738 Combinatorics and Probability
This is a well-known property, true ind-dimensional space, where “disks’’ becomes
“balls’’ and the number 3 is replaced byd+1. The cased=1 is rather simple. Translating
the problem for the real axis, we have a finite family of intervals[ai,bi],1≤i≤n, such
that any two intersect. Thenai<bjfor anyi, j, and hence
[maxai,minbj]⊂∩i[ai,bi],proving the claim. In general, we proceed by induction ond. Assume that the prop-
erty is not true, and select thed-dimensional balls (disks in the two-dimensional case)
B 1 ,B 2 ,...,Bk− 1 ,Bksuch that
B 1 ∩B 2 ∩···∩Bk− 1 =G =∅ and B 1 ∩B 2 ∩···∩Bk− 1 ∩Bk=∅.LetHbe a hyperplane (line in the two-dimensional case) that separatesGfromBk. Since
Bkintersects each of the ballsB 1 ,B 2 ,...,Bk− 1 , the setsXi=Bi∩H,i= 1 , 2 ,...,k−1,
are nonempty. Moreover, since by hypothesisBkand anydof the otherk−1 balls have
nontrivial intersection, any collection ofdsetsXihas nontrivial intersection. But then,
by the induction hypothesis, allXihave nontrivial intersection. Therefore,
H∩B 1 ∩B 2 ∩···∩Bk− 1 =∅,i.e.,H∩G =∅, a contradiction. Our assumption was false, which proves the inductive
step. So the property is true in general, in particular in the two-dimensional case.
847.The problem is solved once we show that the faces of this polyhedron can be colored
black and white such that neighboring faces have different colors. Indeed, the edges of
the polygonal section will themselves be colored in such a way that consecutive edges
have different colors, and this can be done only if the number of edges is even.
To prove the claim, we will slightly generalize it; namely, we show that if in a planar
graph every vertex belongs to an even number of edges, then the faces of the graph and
its exterior can be colored black and white such that neighboring regions are of different
colors. Once we allow edges to bend, and faces to be bigons, we can induct on the number
of faces.
The base case consists of a face bounded by two edges, for which the property
obviously holds. Assume that the property holds true for all graphs with at mostkfaces
and let us prove it for an arbitrary graph withk+1 faces. Choose a face of the graph,
which may look as in Figure 97. Shrink it to a point. Color the new graph as permitted
by the inductive hypothesis. Blow up the face back into the picture. Because an even
number of edges meet at each vertex, all the faces that share an edge with the chosen one
are colored by the same color (when moving clockwise around the chosen face we get
from one neighboring face to the next in an even number of steps). Hence the face can
be given the opposite color. This completes the argument.
(Kvant(Quantum))