728 Combinatorics and Probability
is a subset ofM.If{ 3 , 12 } ⊂M, it follows again thatMhas at most 10 elements. If
{ 3 , 12 }⊂M, then none of{ 1 },{ 4 },{ 9 },{ 2 , 6 },{ 5 , 15 }, and{ 7 , 8 , 14 }is a subset ofM,
and thenMhas at most 9 elements. We conclude thatMhas at most 10 elements in
any case.
Finally, it is easy to verify that the subset
M={ 1 , 4 , 5 , 6 , 7 , 10 , 11 , 12 , 13 , 14 }has the desired property. Hence the maximum number of elements inMis 10.
(short list of the 35th International Mathematical Olympiad, 1994, proposed by Bul-
garia)
825.FixA∈Fand consider the functionf : P(S)→P(S) onthe subsets ofS,
f(X)=X A. Because
f(f(X))=(X A) A=((X A)\A)∪(A\(X A))
=(X\A)∪(X∩A)=X,fis one-to-one. Therefore,f(F)has at leastmelements. The conclusion follows.
(I. Tomescu,Problems in Combinatorics, Wiley, 1985)
826.If all functionsfn,n= 1 , 2 , 3 ,...,are onto, then the property is obvious. We will
reduce the general situation to this particular one. For somekandn, define
Bn,k=(fn◦fn+ 1 ◦···◦fn+k− 1 )(An+k).We have the descending sequence of sets
An⊃Bn, 1 ⊃Bn, 2 ⊃ ···.Because all these sets are finite, the sequence is stationary, so there existsk 0 such that
Bn,k=Bn,k+ 1 , fork≥k 0. LetBn=Bn,k 0. It is not hard to see thatfn(Bn+ 1 )=Bn,
and in this way we obtain a sequence of sets and surjective maps. For these the property
holds; hence it holds for the original sets as well.
(C. Nast ̆ ̆asescu, C. Ni ̧ta, M. Brandiburu, D. Joi ̧ta, ̆ Exerci ̧tii ̧si Probleme de Algebra ̆
(Exercises and Problems in Algebra), Editura Didactica ̧ ̆si Pedagogica, Bucharest, 1983) ̆
827.For a personXwe will denote bymXthe number of people he knows. LetAandB
be two people who know each other. We denote byMAandMBthe set of acquaintances
ofA, respectively,B. By hypothesisMAandMBare disjoint. IfX∈MA, thenXhas
exactly one acquaintance inMB. Indeed, eitherX=A, in which case he only knowsB
inMB,orX =A, in which case he does not knowB, so he has exactly one common
acquaintance withB. This latter person is the only one he knows inMB. Similarly, any