4 team Round Robin where top two advance, how many possible ties

[sciencewhiz]

If you have a 4 team round robin with the top two advancing (like the first round of the world cup), how many possible ways are there for there to be a tie for the top two positions.

For example, if ties are not allowed in individual games, I can think of two, are there others?
Team A: 2-1
Team B: 2-1
Team C: 2-1
Team D: 0-3

Team A: 3-0
Team B: 1-2
Team C: 1-2
Team D: 1-2

If ties are allowed in individual games, how many possibilities are there?

Can a generalized equation be derived to find the number of ties when there are N teams with K advancing?

 

[CycloWizard]

There are surely generalizable formulations for this sort of problem. If we let p_ij=1 for a win and 0 for a loss, then the total points for team i are given by P_i=sum(p_ij), j=1:n, j!=i, where n is the number of teams. The tie condition is then given by P_i=P_j. Also note that p_ij=1-p_ji. You should be able to derive the general form for the number of ties without too much trouble. Let me know if you get stuck and I'll come back to it.

 

[TuxDave]

Originally posted by: CycloWizard
There are surely generalizable formulations for this sort of problem. If we let p_ij=1 for a win and 0 for a loss, then the total points for team i are given by P_i=sum(p_ij), j=1:n, j!=i, where n is the number of teams. The tie condition is then given by P_i=P_j. Also note that p_ij=1-p_ji. You should be able to derive the general form for the number of ties without too much trouble. Let me know if you get stuck and I'll come back to it.

You know I've been pondering this problem in the back of my head since he posted this question and I still don't have a good way to do it.

 

[CycloWizard]

Originally posted by: TuxDave
You know I've been pondering this problem in the back of my head since he posted this question and I still don't have a good way to do it.

Maybe it's not as easy as I think then. I'll take a closer look in a while after I'm done writing for the day.

edit: It gets complicated fairly quickly as you increase the number of teams in the group. The number of results is equal to 1/2*(n^2-n), where n is the number of teams. Still working on a solution. I can probably generate the solution faster using brute force simulations than solving it by hand, especially since now I'm not even 100% sure that a closed form solution is possible.

 

[KIAman]

Interesting, I found the total number of results equal N!-N where N is the number of teams but it turns out it is the same as 1/2*(n^2-n).

As to the rest of the problem, if ties were allowed, I found 3 more examples...

T1:0-0-3
T2:0-0-3
T3:0-0-3
T4:0-0-3

T1:1-0-2
T2:1-0-2
T3:0-1-2
T4:0-1-2

T1:2-1-0
T2:2-1-0
T3:0-2-1
T4:0-2-1

As to the question "the number of ties when there are N teams with K advancing" I am confused as to what the criteria for the Tie is. Are you looking for how many situations do ALL teams advanced based on N teams and K advancing?

 

[sciencewhiz]

Originally posted by: KIAman
As to the question "the number of ties when there are N teams with K advancing" I am confused as to what the criteria for the Tie is. Are you looking for how many situations do ALL teams advanced based on N teams and K advancing?

I'm really looking for ambiguity of which teams should advance, ie there would be more then K teams with a record better or equal to the Kth team (when teams are sorted by record).

Originally posted by: CycloWizard

edit: It gets complicated fairly quickly as you increase the number of teams in the group. The number of results is equal to 1/2*(n^2-n), where n is the number of teams. Still working on a solution. I can probably generate the solution faster using brute force simulations than solving it by hand, especially since now I'm not even 100% sure that a closed form solution is possible.

Don't worry about brute forcing it, I can do that. The last part was more of an intellectual curiosity.