In a round-robin tournament each team plays every other team exactly once. If the teams

Chapter 5, Problem 36

(choose chapter or problem)

In a round-robin tournament each team plays every other team exactly once. If the teams are labeled \(T_{1}, T_{2}, . . . , T_{n}\) , then the outcome of such a tournament can be represented by a drawing, called a directed graph, in which the teams are represented as dots and an arrow is drawn from one dot to another if, and only if, the team represented by the first dot beats the team represented by the second dot. For example, the directed graph below shows one outcome of a round-robin tournament involving five teams, A, B, C, D, and E.

Use mathematical induction to show that in any roundrobin tournament involving n teams, where n ≥ 2, it is possible to label the teams  \(T_{1}, T_{2}, . . . , T_{n}\) so that \(T_{i}\) beats \(T_{i+1}\) for all i = 1, 2, . . . , n − 1. (For instance, one such labeling in the example above is \(T_{1} = A, T_{2} = B, T_{3} = C, T_{4} = E, T_{5} = D\).) (Hint: Given k + 1 teams, pick one— say T’—and apply the inductive hypothesis to the remaining teams to obtain an ordering \(T_{1}, T_{2}, . . . , T_{k}\) . Consider three cases: T’ beats \(T_{1}\), T’ loses to the first m teams (where 1 ≤ m ≤ k − 1) and beats the (m + 1)st team, and T’ loses to all the other teams.)

Text Transcription:

T_1, T_2, . . . , T_n

T_i

T_i+1

T_1 = A, T_2 = B, T_3 = C, T_4 = E, T_5 = D

T_1, T_2, . . . , T_k

T_1