1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

For a round-robin of n teams find the number of different outcomes

  1. Sep 12, 2017 #1
    1. The problem statement, all variables and given/known data
    In a round-robin tournament each team plays every other team once, find the number of different outcomes possible for ##n## teams.

    e.g. for 4 teams the possible outcomes are:
    |3-0 | 3-0 | 2-1 | 2-1
    | 2-1 | 1-2 | 2-1 | 2-1
    | 1-2 | 1-2 | 1-2 | 2-1
    | 0-3 | 1-2 | 1-2 | 0-3

    so there are 4 possible outcomes.

    2. Relevant equations
    Combinations: ##\frac{n!}{r!(n-r)!}##

    3. The attempt at a solution

    I don't know much about how to solve this question so I will just list what I do know. ##n(n-1)/2## games will take place, this gives ##2^{n(n-1)/2}## possible outcomes for the games. The total number of wins must always be equal to ##(n-1)(n-2)/2## so if it's useful the question can be turned into how many unique ways can you create ##(n-1)(n-2)/2## from ##n## digits using the digit ##(n-1)## at most once since only one team could theoretically go flawless and digits ranging from ##0\leq d < n##. Unfortunately I'm terrible at combinatorics so I really have no clue how to approach solving this.

    For 2 teams:
    1-0 |
    0-1 |
    For 3 teams:
    2-0 | 1-1
    1-1 | 1-1
    0-2 | 1-1

    If someone could point me in the right direction that would help a lot!
     
  2. jcsd
  3. Sep 13, 2017 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It depends what you consider to be different outcomes. Do we care about exactly which team beat which, or only how many games each won?
    I assume there are no draws.
     
  4. Sep 13, 2017 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Please explain your notation: what does |3-0 | 3-0 | 2-1 | 2-1 mean in the first line of your first table?
     
  5. Sep 13, 2017 #4

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member
    2017 Award

    I believe they are intended to be grouped in columns rather than rows and each entry representing the number of wins and losses for a team. The first column would be the possibility with one team winning all three games (3-0), the second team winning two games (2-1), the third team winning one game (1-2), and the last team losing all games (0-3).
     
  6. Sep 13, 2017 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    OK, so would the first column be listing the wins for Team A? Would the second column list the wins for Team B? If so, what could be meant by the fact that its three entries are |3-0|, |1-2|, |1-2|, |1-2| ?
     
  7. Sep 13, 2017 #6

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member
    2017 Award

    No, the first row seems to be listing the wins for the team with the most wins, not necessarily a specific team. Every column is a different realisation.

    Consider the outcome table (team names made up):
    Physicists 3W-0L
    Chemists 1W-2L
    Biologists 1W-2L
    Geologists 1W-2L
    which is a possible outcome. This would be represented as the column
    3-0
    1-2
    1-2
    1-2
    and is one of the listed outcomes - the second one (the OP seems to suggest that the team order does not matter, although in the case of those team names it obviously does as the 3-0 in the first entry is obvious and excludes two outcomes!)
     
    Last edited: Sep 13, 2017
  8. Sep 13, 2017 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Thanks: that clarifies it. I wish the OP had gotten back here with the explanation.
     
  9. Sep 13, 2017 #8
    Yep there are no draws.

    We only care about the overall result and not which team beat which.
    E.g. Team A:(1-0) and Team B:(0-1) is the same as Team A:(0-1) and Team B:(1-0).

    Yes the way Orodruin explained it is correct. Hopefully my reply to Haruspex clarifies any confusion about order.
     
  10. Sep 13, 2017 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This does seem to be a hard problem, perhaps on a par with finding the partition numbers.
    Let the number of outcomes for n teams be Nn. I can show that the number in which either one team beats all the others or one team loses to all the others is 2Nn-1-Nn-2.
    For n=5, that leaves just three other patterns: 3 3 2 1 1, 3 2 2 2 1, 2 2 2 2 2. N5=2.4-2+3=9.
    Likewise, for n=6, if all scores are from 1 to 4 then all 9 partitions of 15 into the 6 scores within that constraint appear to be valid. This gives 2.9-4+9=23.
    At n=7 further constraints arise since, e.g., no subset of four teams can have a score line 2 1 1 1.
     
  11. Sep 14, 2017 #10
    Yikes.
    Just to make sure I'm understanding this correctly, we are solving for the cases in which one team beats all the others or one team loses to all the others in order to remove sums involving a 0 as one of the digits which then allows us to sum that with the partitions of n(n-1)/2 that have n scores in order to get the total number of outcomes? It appears as though the mathematical solution to this problem is quite over my head so I will try to come up with a somewhat brute-force algorithm tomorrow after I wake up.
     
  12. Sep 14, 2017 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    and those involving n-1.
    Those partitions in which all lie in the range 1 to n-2. But as I posted, that counts too many for n>6.
     
  13. Sep 14, 2017 #12
    Whoops forgot about that.
    For some reason I thought I would be able to avoid the constraints when coding an algorithm, clearly this is not the case. I took this code for the unique partitions of an integer and implemented some basic checks to see if the current partition could be a potential outcome however I am struggling to identify the last outcome in which one team beats all the others or one team loses to all the others for n = 5 (probably more problems arising with larger n). Here is my code so far.

    Output for n = 5 :
    10
    9 1
    8 2
    8 1 1
    7 3
    7 2 1
    7 1 1 1
    6 4
    6 3 1
    6 2 2
    6 2 1 1
    6 1 1 1 1
    5 5
    5 4 1
    5 3 2
    5 3 1 1
    5 2 2 1
    5 2 1 1 1
    4 4 2
    4 4 1 1
    4 3 3 <- Added outcome
    4 3 2 1 <- Added outcome
    4 2 2 2 <- Added outcome
    3 3 3 1 <- Added outcome
    3 3 2 2 <- Added outcome
    3 3 2 1 1 <- Added outcome
    3 2 2 2 1 <- Added outcome
    2 2 2 2 2 <- Added outcome
    Number of unique outcomes:8

    I suppose I could bypass this problem by using your recurrence relation however I haven't been able to successfully derive it yet so I opted out of using it for now. Another thing I don't understand is how you got the constraint that for n=7 that the subset 2 2 2 1 is invalid, I understand why it's invalid since it leads to the outcome 5 5 4 2 2 2 1 which after drawing a picture I was unable to create a valid diagram for. However, I have no clue how you noticed this subset leads to problems.
     
  14. Sep 15, 2017 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Neither do I. I think I must have meant 2 1 1 1.

    For an algorithm to generate solutions, I suggest building it up from just two teams. When you add the n+1th team, there are 2n possibilities for that team. Eliminate duplicates and continue to n+2.
     
  15. Sep 18, 2017 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Consider a sequence A=(a1, a2, ... , an), 0<=a1<a2<...<an.
    Say A supports a tournament if the sequence represents a feasible outcome of an all-play-all tournament.
    Theorem: A suports a tournament if and only if these two conditions are met:
    1. ##\Sigma_{i=1}^na_i=\frac 12n(n-1)##
    2. For every r, ##\Sigma_{i=1}^ra_i>=\frac 12r(r-1)##
    That the conditions are necessary is trivial. It remains to prove they suffice.
    Suppose A satisfies the conditions.
    Result is trivially true for n=2.

    Lemma
    an<n
    Proof, exercise.

    Define B=(b1, ... bn-1) by
    bi=ai for i <= an
    bi=ai-1 otherwise.

    Lemma
    B satisfies the conditions.
    Proof: exercise.

    By induction, B supports a tournament.

    Lemma
    If a tournament between n-1 teams produces the outcome B, adding an nth team which beats the first an and loses to the rest results in the outcome A.

    Proof, exercise.
     
  16. Sep 19, 2017 #15
    Im a bit confused as to why we've defined ##a_i < a_{i+1}## instead of ##a_i \leq a_{i+1}## since this doesn't have to hold for tournaments in general.

    Proof: Consider the series ##A=a_1+a_2+\cdots +a_n## with ##0\leq a_1<a_2<\cdots < a_n## then ##\sum a_i=\frac12n(n-1)=0+1+\cdots+(n-1)## then one cannot redistribute a 1 to ##a_n## from an ##a_i, 0\leq i \leq n - 1## without setting ##a_1 \leq 0## or removing the property of ##a_i < a_{i+1}## for ##0\leq i \leq n - 1##.

    I got a C+ in introductory analysis and never took more proof-related classes after that so this proof is probably pretty bad lol.
     
  17. Sep 19, 2017 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Typo on my part. They should all have been <=.
     
  18. Sep 19, 2017 #17
    Ok that makes more sense
     
  19. Sep 19, 2017 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't nderstand why you are summing them. I wrote that A is the sequence (a1,...,an), these being the score totals (1 for a win, 0 for a loss) of the n teams, from lowest to highest.
     
  20. Sep 19, 2017 #19
    Yes I suppose that doesn't make sense after how you've defined it.
     
  21. Sep 19, 2017 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Oh, sorry, I see you are checking off the first criterion. You confused me by calling the series A.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: For a round-robin of n teams find the number of different outcomes
  1. Find number n,m (Replies: 26)

Loading...