Combinatorics and Probability
821.The relation from the statement implies(A∩X)∪(B∩X)=A∩B.Applying de Morgan’s law, we obtain
(A∪B)∩X=A∩B.But the left-hand side is equal to(A∪B∪X)∩X, and this is obviously equal toX.
HenceX=A∩B.
(Russian Mathematics Competition, 1977)
822.This is an easy application of the pigeonhole principle. Letnbe the number of
vertices. Associate to each vertex the set of vertices connected to it by edges. There are
nsuch sets, and each of them has at mostn−1 elements. Hence there are two sets with
the same number of elements. Their corresponding vertices are endpoints of the same
number of edges.
823.We prove the property by induction on the number of elements of the set. For a
set with one element the property clearly holds. Let us assume that we could find the
required listA 1 ,A 2 ,...,A 2 nof the subsets of the set withnelements,n≥1. Add the
elementxto obtain a set withn+1 elements. The list for this new set isA 1 ,A 2 ,...,A 2 n,A 2 n∪{x},...,A 2 ∪{x},A 1 ∪{x},and the induction is complete.
824.Note that the product of the three elements in each of the sets{ 1 , 4 , 9 },{ 2 , 6 , 12 },
{ 3 , 5 , 15 }, and{ 7 , 8 , 14 }is a square. Hence none of these sets is a subset ofM. Because
they are disjoint, it follows thatMhas at most 15− 4 =11 elements.
Since 10 is not an element of the aforementioned sets, if 10∈/M, thenMhas at most
10 elements. Suppose 10∈M. Then none of{ 2 , 5 },{ 6 , 15 },{ 1 , 4 , 9 }, and{ 7 , 8 , 14 }