Combinatorics and Probability 729person inMBhas exactly one acquaintance inMA. This allows us to establish a bijection
betweenMAandMB, and conclude thatmA=mB.
Finally, ifAandBdo not know each other, then they have a common acquaintance
C. The above argument shows thatmA=mC=mB, and we are done.
(Kvant(Quantum))828.We setf^0 = (^1) A,fn+^1 =fn◦f,n≥ 0. Define onAthe relationx ∼yif
there existmandnsuch thatfn(x)=fm(y). One verifies immediately that∼is an
equivalence relation, and that equivalence classes are invariant underf. An equivalence
class resembles a spiral galaxy, with a cycle into which several branches enter. Such an
equivalence class is illustrated in Figure 94, where the dots are elements ofEand the
arrows describe the action off.
Figure 94
Thusfdefines a directed graph whose connected components are the equivalence
classes. We color the vertices of this graph by 0, 1 , 2 ,3 according to the following rule.
All fixed points are colored by 0. Each cycle is colored alternately 1, 2 , 1 , 2 ,...with its
last vertex colored by 3. Finally, each branch is colored alternately so that no consecutive
vertices have the same color. The coloring has the property that adjacent vertices have
different colors. If we letAiconsist of those elements ofAcolored byi,i= 0 , 1 , 2 ,3,
then these sets have the required property. The construction works also in the case that
the cycle has length one, that is, when it is a fixed points off. Note that in general the
partition is not unique.
This argument can be easily adapted to the case in whichAis infinite. All cycles are
finite and they are taken care of as in the case of a finite set. The coloring can be done
provided that we can choose one element from each cycle to start with, thus we have to
assume the axiom of choice. This axiom states that given a family of sets one can choose
one element from each of them. Now let us consider an equivalence class as defined
above, and look at the dynamic process of repeated applications off. It either ends in
A 0 or in a cycle, or it continues forever. In the equivalence class we pick a reference
pointx 0 , which is either the point where the equivalence class entersA 0 or a cycle, or
otherwise is an arbitrary point. Eitherx 0 has been colored, by 0 or as part of a cycle, or if
not, we color it by the color of our choice. Say the color ofx 0 isi, and letjandkbe two