6.2 Binomial Coefficients and Counting Methods 307888.A numbernof tennis players take part in a tournament in which each of them plays
exactly one game with each of the others. Ifxiandyidenote the number of victories,
respectively, losses, of theith player,i= 1 , 2 ,...,n, show that
x 12 +x^22 +···+xn^2 =y 12 +y 22 +···+yn^2.889.LetAbe a finite set andfandgtwo functions onA. Letmbe the number of
pairs(x, y)∈A×Afor whichf(x)=g(y),nthe number of pairs for which
f(x)=f(y), andkthe number of pairs for whichg(x)=g(y). Prove that
2 m≤n+k.890.A setScontaining four positive integers is calledconnectedif for everyx∈Sat
least one of the numbersx−1 andx+1 belongs toS. LetCnbe the number of
connected subsets of the set{ 1 , 2 ,...,n}.
(a) EvaluateC 7.
(b) Find a general formula forCn.
891.Prove that the set of numbers{ 1 , 2 ,..., 2005 }can be colored with two colors such
that any of its 18-term arithmetic sequences contains both colors.
892.ForA={ 1 , 2 ,..., 100 }letA 1 ,A 2 ,...,Ambe subsets ofAwith four elements
with the property that any two have at most two elements in common. Prove that if
m≥40425 then among these subsets there exist 49 whose union is equal toAbut
with the union of any 48 of them not equal toA.
893.LetSbe a finite set of points in the plane. A linear partition ofSis an unordered
pair{A, B}of subsets ofSsuch thatA∪B=S,A∩B=∅, andAandBlie on
opposite sides of some straight line disjoint fromS(AorBmay be empty). Let
LSbe the number of linear partitions ofS. For each positive integern, find the
maximum ofLSover all setsSofnpoints.
894.LetAbe a 101-element subset of the setS={ 1 , 2 ,..., 1000000 }. Prove that there
exist numberst 1 ,t 2 ,...,t 100 inSsuch that the sets
Aj={x+tj|x∈A},j= 1 , 2 ,..., 100 ,are pairwise disjoint.895.Given a setAwithn^2 elements,n≥2, andFa family of subsets ofAeach of
which hasnelements, suppose that any two sets ofFhave at most one element in
common.
(a) Prove that there are at mostn^2 +nsets inF.
(b) In the casen=3, show with an example that this bound can be reached.