Pigeon Hole Problem Involving Matching Basketball Teams?

  • Thread starter Thread starter bigi247
  • Start date Start date
  • Tags Tags
    Basketball Hole
Click For Summary
SUMMARY

The discussion centers on the Pigeon Hole Problem as it applies to basketball teams, specifically determining the largest integer n such that |S| ≥ n, where S is a set of teams that have not played each other. It is established that for any group of three teams, at least two teams have not played each other, leading to the conclusion that the problem can be modeled as a triangle-free graph. The participants highlight the complexity of proving the lower bound for n, suggesting that while there are 120 possible combinations of teams, a significant number of these combinations do not involve any games played.

PREREQUISITES
  • Understanding of combinatorial mathematics
  • Familiarity with graph theory, specifically triangle-free graphs
  • Knowledge of the Pigeonhole Principle
  • Basic skills in mathematical proof techniques
NEXT STEPS
  • Research the properties of triangle-free graphs in combinatorial contexts
  • Study the Pigeonhole Principle and its applications in graph theory
  • Explore methods for proving lower bounds in combinatorial problems
  • Investigate the implications of matchings in bipartite graphs
USEFUL FOR

Mathematicians, combinatorial theorists, and students studying graph theory or discrete mathematics will benefit from this discussion, particularly those interested in the applications of the Pigeonhole Principle in complex problem-solving scenarios.

bigi247
Messages
1
Reaction score
0
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.
 
Physics news on Phys.org
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.
 

Similar threads

For a round-robin of n teams find the number of different outcomes
  • · Replies 21 ·
Replies
21
Views
16K
Statistics and Maple: Constructing a Team of 4 from 3 Groups"
  • · Replies 1 ·
Replies
1
Views
2K
High School Validating Darts Tournament Skill Levels: A Non-Intrusive Approach
  • · Replies 4 ·
Replies
4
Views
2K
High School Round-Robin Matching Teams (Darts)
  • · Replies 15 ·
Replies
15
Views
2K
Permutations matches in basketball league
  • · Replies 1 ·
Replies
1
Views
5K
Combinatorics: tennis game with 8 people
  • · Replies 8 ·
Replies
8
Views
4K
Probability of girls on a team getting shirts with pair numbers
  • · Replies 3 ·
Replies
3
Views
2K
Need help on working out of a probability problem
  • · Replies 3 ·
Replies
3
Views
2K
A somewhat simple Probabilty problem
  • · Replies 11 ·
Replies
11
Views
4K
1968 NY Jets vs. 2018 Clemson Tigers football team---Who would win?
  • · Replies 19 ·
Replies
19
Views
3K