Advanced book on Mathematics Olympiad

6.1 Combinatorial Arguments in Set Theory and Geometry 283

824.LetMbe a subset of{ 1 , 2 , 3 ,..., 15 }such that the product of any three distinct

elements ofMis not a square. Determine the maximum number of elements inM.

825.LetSbe a nonempty set andFa family ofm≥2 subsets ofS. Show that among

the sets of the formA   BwithA, B∈Fthere are at leastmthat are distinct. (Here

A   B=(A\B)∪(B\A).)

826.Consider the sequence of functions and sets

··· →An

fn− 1

→An− 1

fn− 2

→An− 2

fn− 3

→ ···

f 3

→A 3

f 2

→A 2

f 1

→A 1.

Prove that if the setsAnare nonempty and finite for alln, then there exists a sequence

of elementsxn∈An,n= 1 , 2 , 3 ,...,with the property thatfn(xn+ 1 )=xnfor all

n≥1.

827.In a society ofnpeople, any two persons who do not know each other have exactly

two common acquaintances, and any two persons who know each other don’t have

other common acquaintances. Prove that in this society every person has the same

number of acquaintances.

828.LetAbe a finite set and letf:A→Abe a function. Prove that there exist the

pairwise disjoint setsA 0 ,A 1 ,A 2 ,A 3 such thatA=A 0 ∪A 1 ∪A 2 ∪A 3 ,f(x)=x

for anyx∈A 0 andf(Ai)∩Ai=∅,i= 1 , 2 ,3. What if the setAis infinite?

6.1.2 Permutations............................................

A permutation of a setSis a bijectionσ : S → S. Composition induces a group
structure on the set of all permutations. We are concerned only with the finite case
S={ 1 , 2 ,...,n}. The standard notation for a permutation is

σ=

(

123 ···n

a 1 a 2 a 3 ···an

)

,

withai=σ(i),i= 1 , 2 ,...,n.
A permutation is a cycle(i 1 i 2 ...in)ifσ(i 1 )=i 2 ,σ(i 2 )=i 3 ,..., σ(in)=i 1 ,
andσ(j)=jforj =i 1 ,i 2 ,...,in. Any permutation is a product of disjoint cycles.
A cycle of length two(i 1 i 2 )is called a transposition. Any permutation is a product of
transpositions. For a given permutationσ, the parity of the number of transpositions
in this product is always the same; the signature ofσ, denoted by sign(σ ), is 1 if this
number is even and−1 if this number is odd. An inversion is a pair(i, j )withi<jand
σ(i)>σ(j).
Let us look at a problem from the 1979 Romanian Mathematical Olympiad, proposed
by I. Ra ̧sa.