Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeon Hole Problem Involving Matching Basketball Teams?

  1. Feb 6, 2012 #1
    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.
  2. jcsd
  3. Feb 7, 2012 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook