Hosted by The Math Forum

Problem of the Week 1067

Tournament Time

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

True or False: Every tournament on 7 teams has a subtournament on 4 teams that is totally ordered.

Background: A classic induction exercise proves that every tournament on 8 teams has a subtournament of size 4 that is fully ordered. This means that if 8 teams have a tournament in which each team plays each other team once (no draws), there are four teams A, B, C, D so that A beat B, C, and D, B beat C and D, and C beat D. So the question is whether the assertion is true if 8 is lowered to 7. A more standard term for "fully ordered" is "transitive."

Of course, one can ask more generally: Given m, what is the least n such that an n-tournament has a fully ordered subtournament of size m? This problem is not solved in general.

© Copyright 2006 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


14 November 2006