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

Question

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 round-
robin 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.)

Use mathematical induction to show that in any round- robin tournament involving n teams, where n 2, it is possible to label the teams TI, T2, T, so that T beats T for all i 1, 2 n 1. (For instance, one such it-1 labeling in the example above is T A. T B, T3 C, T E, T D.) (Hint: Given k 1 teams, pick one- say T'. and apply the inductive hypothesis to the remain- ing teams to obtain an ordering TI, T2, T. Consider three cases: T beats Ti T loses to the first m teams (where l s m sk 1) and beats the (m 1)st team, and T loses to all the other teams.)

Explanation / Answer

Answer:     Let n = 2. Then there was only single pastime played. tag the victor as T1 and loser as T2 and we be done.

Inductive Step:

Let k>=2. Suppose so as to for all tournament by income of k team present is a labeling as described above. Think a contest on k+1 team. at what time we take away single team, utter team A, we have a contest on k teams.

Thus, by our inductive theory, present is a labeling T1, T2... TM as above.

Also A beat team T1, A loses to the relax m team (where 1<=m<=k-1) plus beat the (m+1) set team, or A loses to everyone the other team.

In the first container A, T1, T2, ...., TM be a desired ordering, so we relabeled our team so that A become T'1, T1 becomes T'2, and so on.

In the following case, T1, T2, ...., Tm, A, Tm+1, ...., TM is a preferred order (since A gone to Tm save for beat Tm+1), and so we relabeling consequently.

In the third case, T1, T2... TM, A is a desired ordering (since A lost to everyone, in particular they lost to TM), and so we relabeling accordingly.

In all cases, we contain found the desired labeling. Thus the result holds through statistical induction.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.