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

Homework Help: 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