MathDB

round-robin tournament with $2n+1$ teams

Source: Canadian Mathematical Olympiad 2006, problem 4

January 28, 2007

searchcombinatorics unsolvedcombinatoricsgraph theory

Problem Statement

Consider a round-robin tournament with

2n+1

teams, where each team plays each other team exactly one. We say that three teams

X,Y

and

Z

, form a cycle triplet if

X

beats

Y

Y

beats

Z

and

Z

beats

X

. There are no ties. a)Determine the minimum number of cycle triplets possible. b)Determine the maximum number of cycle triplets possible.