Given the final points of all teams in a sports league, counting the number of possibilities that would lead to it

87 Views Asked by At

Does this problem have a name:

"Given the final points table of a sports league having $n$ teams, enumerate the possible results leading up to it, or at least provide the number of possible results".

So suppose there were 3 teams X, Y, Z which played each other twice (once at home and once away). A win meant 2 points, a draw/tie meant 1 and a loss meant 0 points.

At the end the points table was as follows:

X had 3 points

Y had 3 points

Z had 6 points

Given this info what are all the possible results?

One possibility is that X defeated Y at home but drew away. Z defeated X both times, & Y and Z drew both their games. In this way, one can enumerate all the possibilities. How many possibilities will be there in total?

I wish to know whether this problem can be solved easily, or not (for $n$ teams where winning yields $p$ points, drawing $q$ points and losing $r$ points). In the latter case, is it equivalent to some other problem that has a name?

1

There are 1 best solutions below

0
On

You can use binary decision variables and constraint programming (or integer linear programming) to find all feasible solutions. Here is how to do it in SAS:

data indata;
   input team $ points;
   datalines;
X 3
Y 3
Z 6
;

proc optmodel;
   /* declare parameters and read data */
   num p = 2, q = 1, r = 0; /* win, draw, lose */
   set <str> TEAMS;
   num points {TEAMS};
   read data indata into TEAMS=[team] points;
   set GAMES = {i in TEAMS, j in TEAMS diff {i}}; /* <away, home> */
   set OUTCOMES = /away draw home/;

   /* declare binary decision variable IsOutcome[i,j,o] = 1 if game <i,j> has outcome o */
   var IsOutcome {GAMES, OUTCOMES} binary;

   /* declare linear constraint that each game has exactly one outcome */
   con OneOutcomePerGame {<i,j> in GAMES}:
      sum {o in OUTCOMES} IsOutcome[i,j,o] = 1;

   /* declare linear constraint that each team earns the specified total number of points */
   con PointsCon {t in TEAMS}:
      sum {<i,(t)> in GAMES} (p * IsOutcome[i,t,'home'] + q * IsOutcome[i,t,'draw'] + r * IsOutcome[i,t,'away'])
    + sum {<(t),j> in GAMES} (p * IsOutcome[t,j,'away'] + q * IsOutcome[t,j,'draw'] + r * IsOutcome[t,j,'home'])
    = points[t];

   /* call constraint programming solver */
   solve with clp / findallsolns;

   /* report solutions */
   for {s in 1.._NSOL_} do;
      put s=;
      for {<i,j> in GAMES} for {o in OUTCOMES: IsOutcome[i,j,o].sol[s] > 0.5} put i j o;
      put;
   end;
quit;

For your example, here are the resulting 24 feasible solutions (solution s=7 is the one you mentioned), where the three columns are away team, home team, and outcome:

s=1
X Y home
X Z home
Y X home
Y Z home
Z X draw
Z Y draw

s=2
X Y draw
X Z home
Y X draw
Y Z home
Z X draw
Z Y draw

s=3
X Y home
X Z home
Y X home
Y Z draw
Z X draw
Z Y away

s=4
X Y home
X Z home
Y X draw
Y Z home
Z X home
Z Y away

s=5
X Y draw
X Z home
Y X draw
Y Z draw
Z X draw
Z Y away

s=6
X Y home
X Z draw
Y X draw
Y Z home
Z X draw
Z Y away

s=7
X Y draw
X Z home
Y X home
Y Z draw
Z X away
Z Y draw

s=8
X Y home
X Z draw
Y X home
Y Z home
Z X away
Z Y draw

s=9
X Y home
X Z draw
Y X home
Y Z draw
Z X away
Z Y away

s=10
X Y draw
X Z draw
Y X draw
Y Z home
Z X away
Z Y draw

s=11
X Y draw
X Z draw
Y X draw
Y Z draw
Z X away
Z Y away

s=12
X Y draw
X Z home
Y X home
Y Z home
Z X away
Z Y home

s=13
X Y draw
X Z home
Y X home
Y Z away
Z X away
Z Y away

s=14
X Y draw
X Z home
Y X away
Y Z home
Z X home
Z Y away

s=15
X Y draw
X Z draw
Y X away
Y Z home
Z X draw
Z Y away

s=16
X Y home
X Z away
Y X draw
Y Z home
Z X away
Z Y away

s=17
X Y draw
X Z away
Y X away
Y Z home
Z X away
Z Y away

s=18
X Y away
X Z home
Y X draw
Y Z home
Z X away
Z Y home

s=19
X Y away
X Z home
Y X draw
Y Z away
Z X away
Z Y away

s=20
X Y away
X Z home
Y X draw
Y Z draw
Z X away
Z Y draw

s=21
X Y away
X Z home
Y X away
Y Z draw
Z X draw
Z Y away

s=22
X Y away
X Z home
Y X away
Y Z home
Z X draw
Z Y draw

s=23
X Y away
X Z draw
Y X away
Y Z draw
Z X away
Z Y away

s=24
X Y away
X Z draw
Y X away
Y Z home
Z X away
Z Y draw