Scribd Logo
Upload

Welcome to Scribd!

  • 96 views

    Round-Robin: Tournaments

    Uploaded by

    Abhilash K
    This document discusses round-robin tournaments and algorithms for scheduling such tournaments. It begins with an introduction to round-robin tournaments where every team plays every other team once. It then presents three theorems: 1) Exactly one team gets a bye each round; 2) A team gets a bye in round i if its number is congruent to (p+1)/2 times i modulo p; and 3) The scheduling function g is injective for each round. An algorithm for scheduling the tournaments is then described which uses modular arithmetic. Finally, an example schedule for a 7 team tournament is provided.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Round-Robin: Tournaments

    Uploaded by

    Abhilash K
    96 views13 pages
    This document discusses round-robin tournaments and algorithms for scheduling such tournaments. It begins with an introduction to round-robin tournaments where every team plays every other team once. It then presents three theorems: 1) Exactly one team gets a bye each round; 2) A team gets a bye in round i if its number is congruent to (p+1)/2 times i modulo p; and 3) The scheduling function g is injective for each round. An algorithm for scheduling the tournaments is then described which uses modular arithmetic. Finally, an example schedule for a 7 team tournament is provided.

    Original Title

    Untitled

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses round-robin tournaments and algorithms for scheduling such tournaments. It begins with an introduction to round-robin tournaments where every team plays every other team once. It then presents three theorems: 1) Exactly one team gets a bye each round; 2) A team gets a bye in round i if its number is congruent to (p+1)/2 times i modulo p; and 3) The scheduling function g is injective for each round. An algorithm for scheduling the tournaments is then described which uses modular arithmetic. Finally, an example schedule for a 7 team tournament is provided.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    96 views13 pages

    Round-Robin: Tournaments

    Uploaded by

    Abhilash K
    This document discusses round-robin tournaments and algorithms for scheduling such tournaments. It begins with an introduction to round-robin tournaments where every team plays every other team once. It then presents three theorems: 1) Exactly one team gets a bye each round; 2) A team gets a bye in round i if its number is congruent to (p+1)/2 times i modulo p; and 3) The scheduling function g is injective for each round. An algorithm for scheduling the tournaments is then described which uses modular arithmetic. Finally, an example schedule for a 7 team tournament is provided.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 13

    Number Theory​

    Round-Robin
    Tournaments

    K Abhilash
    22PC01
    A
    Agenda
    Introduction

    Round-Robin

    Theorems

    Algorithm

    Example

    2
    Introduction
    Let m be a positive integer. Then an integer a is congruent to an integer b
    modulo m if m|(a − b). In symbols, we then write a ≡ b (mod m); m is the
    modulus of the congruence relation.

    3
    Round-Robin Tournaments
    In round-robin tournaments, every team plays every other team exactly once. Suppose
    there are n teams, labeled 1 through n. Then the tournament can be represented by a
    polygon with n vertices with every pair of vertices connected; every vertex represents a
    team and every line segment with endpoints i and j represents a game between teams i and j.
    Let gn denote the number of games by n teams in a round-robin tournament. It can be
    defined recursively:
    g1 = 0
    gn = gn−1 + (n − 1), n ≥ 2

    Solving this recurrence relation, we get


    gn = n(n-1)/2 = (n 2)

    4
    Congruences can be applied nicely to schedule round-robin tournaments. If n is
    even, then every team can be paired with another team; but if n is odd, not all
    teams can be paired, so one team gets a bye in that round. So, whenever n is odd,
    we add a dummy team X, so that if a team is paired with X in a certain round, it
    gets a bye in that round. Consequently, we assume n is even.

    Let g(i,j) denote the team played in round i by team j. If g(i,j) = j, team j gets
    a bye in round i. We define g as

    g(i,j) ≡ i − j (mod p)

    where the least residue 0 modulo p is interpreted as p.


    For example, let p = 7. Then g(1, 1) = 0 (mod 7), so g(1, 1) = 7; similarly,
    g(1, 2) ≡ −1 (mod 7), so g(1, 2) = 6, and so on.
    5
    Theorems
    Theorem 1 :
    Exactly one team draws a bye in each round.
    Proof :
    Suppose teams j1 and j2 draw byes in round i. Then
    g(i,j1) ≡ j1 (mod p) and g(i,j2) ≡ j2 (mod p)
    case 1:
    If i = j1, then i = j1 = p. Because g(i,j2) ≡ j2 (mod p), i−j2 ≡ j2 (mod p);that is,
    p − j2 ≡ j2 (mod p)
    2j2 ≡ 0 (mod p)
    j2 ≡ 0 (mod p)
    So j2 = p. Thus, j1 = j2.
    6
    case 2 :

    If i≠j1, then g(i,j1) ≡ i − j1 ≡ j1 (mod p), so i ≡ 2j1 (mod p).


    If i = j2, g(i,j2) ≡ i ≡ p (mod p). Then p ≡ 2j1 (mod p), so 2j1 ≡ 0 (mod p);
    that is, j1 ≡ 0 (mod p) or j1 = p. Then i ≡ 2p ≡ 0 (mod p), so i = p. Thus, i = j1, a
    contradiction.

    So i≠j2. Therefore, g(i,j2) ≡ i − j2 ≡ j2 (mod p). This yields i ≡ 2j2 (mod p), so

    2j1 ≡ 2j2 (mod p)


    j1 ≡ j2 (mod p)

    Therefore, j1 = j2, since they are least residues modulo p.


    Thus, in both cases, j1 = j2, so exactly one team gets a bye in each round.

    The following theorem identifies the team that draws a bye in each round. 7
    Theorem 2 :
    g(i,j) ≡ j (mod p) if and only if j ≡ ((p + 1)/2) i (mod p).
    Proof :
    Assume g(i,j) ≡ j (mod p). If i = j, then g(i,j) ≡ p (mod p), so i ≡ j ≡ p ≡ 0 (mod p). Therefore, j ≡
    (p+1)i/2 (mod p).

    If i ≠ j, then g(i,j) ≡ i − j (mod p). Then


    i − j ≡ j (mod p)
    That is,

    i ≡ 2j (mod p)
    Therefore, (p + 1)i/2 ≡ (p + 1)2j/2 ≡ pj + j ≡ j (mod p).
    Thus, in both cases, team j draws a bye in round i if j ≡ (p + 1)i/2 (mod p).
    Conversely, suppose j ≡ (p + 1)i/2 (mod p). Then

    g(i,j) ≡ i − j (mod p)
    ≡ i − (p + 1)i/2 ≡ (1 − p)i/2 (mod p)
    ≡ (p + 1)i/2 ≡ j (mod p)

    Thus, team j draws a bye in round i.


    8
    The following theorem shows that g schedules every team exactly once in each
    round; that is, g outputs every value 1 through p exactly once.

    Theorem 3 :
    The function g is injective for each i.

    Proof :
    Suppose g(i,j1) = g(i,j2). Then i − j1 ≡ i − j2 (mod p), so j1 ≡ j2 (mod p); thus,
    j1 = j2 and g is injective.

    9
    Algorithm
    • Place the first bye in column (p + 1)/2; in each successive row, cyclically
    advance to the right by (p + 1)/2 cells, and place a bye in the resulting cell;
    continue like this until a bye is placed in every row.
    • Beginning with the first cell in row 1, count down the numbers p through
    1 and enter them in empty cells (i.e., skip over the cell occupied by a bye),
    to obtain the permutation p, p − 1,... , bye, . . . , 2, 1; to obtain each
    remaining row, cyclically permute to the right the numbers in the preceding
    row.

    10
    Example
    Develop a schedule for a round-robin tournament with seven teams.
    Solution :
    First, label the teams 1 through 7. Since the number of teams is odd, we add a dummy team
    X. We now prepare the schedule round by round.
    To develop the schedule for round 1:
    Team 1 plays team j, where 1 + j ≡ 1 (mod 7); then j = 7, so team 1 plays team 7.

    Team 2 plays team j, where 2 + j ≡ 1 (mod 7); this yields j = 6, so team 2 plays
    team 6. Similarly, team 3 plays team 5.

    Because i = 4 is the solution of the congruence 2i ≡ 1 (mod 7), team 4 plays team 8; that is,
    team 4 gets a bye in round 1.
    11
    To develop the schedule for round 2:
    Because 2i ≡ 2 (mod 7) implies i = 1, team 1 plays team 8; that is, team 1 enjoys a
    bye in round 2.
    Team 2 plays team j, where 2 + j ≡ 2 (mod 7), so j = 7; thus, team 2 plays team 7.
    Similarly, team 3 plays team 6 and team 4 plays team 5.
    Continuing like this, we can find the pairings in other rounds. The resulting
    schedule is ,

    12
    Thank You

    You might also like