Pigeon Hole Problem Involving Matching Basketball Teams?

[bigi247]

Suppose we have ten basketball teams, for any group of three teams we know at least two teams have not played each other. Let S be the largest set of teams such that none have played each other. Provide, with proof, the largest integer n satisfying |S| ≥ n.

Can't choose a particular matching of basketball teams. We have to determine the lower bound 'n' for ALL possible matchings that satisfies: Picking any three teams, at least two teams have not played each other.

We do not know the matching so saying 'assume none have played each other - then we obtain n=10' would not be correct

I'm really not sure what the question is asking for. Obviously there are 10C3 = 120 Different groupings of which 80 or more groups play no games. I really don't know where to go from here.

 

[Joffan]

What we are looking at is a triangle-free graph. A little research will help you somewhat, although proofs are tricky in this field. Certainly I can get a much lower upper bound on n than 10, but proving it is a requirement on |S| is not easy.

I'm trying to think how the pigeonhole principle comes in here but I can't see it.