COMBINATORIAL NUMBER THEORY 9 Theorem 1.3.3F=((A,B)is a(ke)-system then h) Proof.Put X =(A:U B:)and consider a random order r of X.For each i, 1ih,let X be the event that all the elements of A precede all those of B:in this order.Clearly Pr=1/().It is also easy to check that the events are pairwise disjoint.Indeed,assume this is false and let be an order in which all the elements of A;precede those of B;and all the elements of A;precede those of B.Without loss of generality we may assume that the last element of A does not appear after the last element of Aj But in this case,all elements of A precede all those of Bj,contradicting the fact that AB0.Therefore all the events Xi are pairwise disjoint,as claimed.It follows that 1≥Px-∑Px1=M(t) completing the proof. ■ Theorem 1.3.3 is sharp,as shown by the familyF=(A,X\A):AC X,A= k,where=(1,2....,k+eh. 1.4 COMBINATORIAL NUMBER THEORY A subset A of an abelian group G is called sum-free if(A+A)A =0;that is.if there are no a1,a2,a3 E A such that a +a2=a3. Theorem 1.4.1 [Erdos (1965a)]Every set B=(b1:...,bn}of n nonzero integers contains a sum-free subset A of size A>n. group Zp and that ICI k+11 p-1=3k+1>3 Let us choose at random an integer,1<<p,according to a uniform distribution on {1,2....,p-11,and define d1,...,dn by di=xbi (mod p),0<di<p. Trivially,for every fixed i,1 <i<n,as ranges over all numbers 1,2,.. p-L,d ranges over all nonzero elements of Zp and hence Prd,C=Cl/(p-1)> Therefore the expected number of elements b;such that di E C is more than n/3. Consequently,there is an x.1 z<p and a subsequence A of B of cardinality lA>n/3,such that za(modp）∈C for all a∈A.This A is clearly sum-free since if a+a2=a3 for some a1,a2,a3 E A then xa ra2 xa3 (mod p contradicting the fact that C is a sum-free subset of Zp.This completes the proof.COMBINATORIA!. NUMBER THEORY 9 h Theorem ;„„iu o\ „„t„m *u„„ h ^ fk+e\ 1.3.3 IfT = {{Ai, £¿)} i = 1 is a (k, l)-system then h < (fc+*). \h Proof. Put X = \Ji=1(Ai U Bi) and consider a random order ir of X. For each i, 1 < i < h, let Xi be the event that all the elements of Ai precede all those of Bi in this order. Clearly Pr [Xi] = l/( £ )• It is also easy to check that the events Xi are pairwise disjoint. Indeed, assume this is false and let n be an order in which all the elements of A¿ precede those of Bi and all the elements of Aj precede those of Bj. Without loss of generality we may assume that the last element of A, does not appear after the last element of Aj. But in this case, all elements of Ai precede all those of Bj, contradicting the fact that Ai n Bj ^ 0. Therefore all the events X¿ are pairwise disjoint, as claimed. It follows that 1 > Pr V * ¿Pr[*] =*/(*£*), completing the proof. Theorem 1.3.3 is sharp, as shown by the family T = {(A, X \ A) : A c X, [A] — k},v/here X = {1,2,... ,k + ¿}. 1.4 COMBINATORIA!. NUMBER THEORY A subset A of an abelian group G is called sum-free if (A + A) n A = 0; that is, if there are no ai, a^, a-¡, € A such that a,\ + ai = a^. Theorem 1.4.1 [Erdós (1965a)] Every set B = {b\,..., bn} ofn nonzero integers contains a sum-free subset A ofsize \A\ > |n . Proof. Let p = 3fc + 2 be a prime, which satisfies p > 2max{¡6¿|}™=1 and put C = {k+ l,k + 2,... ,2k + 1}. Observe that C is a sum-free subset of the cyclic group Zp and that \C\ _ fc + 1 1 p-1 3k + l 3 Let us choose at random an integer x, 1 < x < p, according to a uniform distribution on {1,2,... ,p — 1}, and define di,... ,dn by di = x6¿ (mod p), 0 < d¿ < p. Trivially, for every fixed i, 1 < i < n, as x ranges over all numbers 1,2,... ,p—l,di ranges over all nonzero elements of Zp and henee Pr [d¿ e C] = \C\/{p — 1) > | . Therefore the expected number of elements 6¿ such that di G C is more than n/3. Consequently, there is an x, 1 < x < p and a subsequence A of B of cardinality \A\ > n/3, such that xa (mod p) £ C for all a e A. This A is clearly sum-free, since if ai + Ü2 = a% for some ai, 02,03 £ A then xa\ + xa^ = xa% (mod p), contradicting the fact that C is a sum-free subset of Zp. This completes the proof. •