Re: Round Robin Scheduling

Maury Barbato wrote:

Maury Barbato wrote:

Hello,
I'm trying to solve some problems about round robin

scheduling. Firt of all, some definitions. In a
round
robin tournament each team each other team exactly
one
time. We have 2n teams. The tournament is
organized
in
2n-1 rounds: in a round, each team plays exactly
one

match against another team. Formally, if we denote
by

1,...,2n the teams, then the i-th round,
1<=i<=2n-1,
is the set of all the matches
R_i={{a_1,a_2},...,{a_{2n-1},a_{2n}}},
where a_i is a permutation of {1,...,2n}.
A brilliant algorithm to schedule a Round Robin
tournament is given at the page

http://www.nrich.maths.org/public/viewer.php?
obj_id=1443&part=index&refpage=monthindex.php

(join the two lines to obtain the link).

Now the problems.

(I) Given a round robin tournament R_i,
i=1,...,2n-1,
can you extract a match form ecah round, such that
every team appear at the most two times in the
extracted
matches? Can you find an algorithm to do it?

(II) Consider all the possible round robin
tournaments
you can schedule with 2n teams. How many are
there?






This is a very simple problem: how couldn't I notice

that?! If m=n*(2n-1), then we have m! possible round
robin tournaments.


An unforgivable mistake!! I was quite confused. The
problem is not so simple, as I had initially sensed.



(III) Consider all the possible round robin
tournaments
you can schedule with 2n teams. We say that two of
these
tournaments, R_i and Q_i, are equivalent if there
exist
a permutation s(k) of {1,...,2n} and a permutation
t(k)
of {1,...,2n-1} such that for every 1<=i<=2n-1,
if R_t(i)={{a_1,a_2},...,{a_{2n-1},a_{2n}}},
then
Q_i={{s(a_1),s(a_2)},...,{s(a_{2n-1}),s(a_{2n})}}.
This is an equivalence relation. The problem is:
how
many
equivalence classes are there?

Thank you very much for your attention.
My Best Regards,
Maury

My Best Regards,
Maury

Problems (II) and (III) are quite difficult, I think.
But I'm quite sure that (I) can be solved quite easily,
even if I have no ideas for now.
My Best Regards,
Maury
.

Relevant Pages

  • Re: Round Robin Scheduling
    ... I'm trying to solve some problems about round robin ... robin tournament each team each other team exactly ... A brilliant algorithm to schedule a Round Robin ...
    (sci.math)
  • Re: Belgrade: First Blood tournament raport
    ... Caine release tournament. ... Three rounds were to be played, ... Unfortunately, after round one we had two players leave, so the ... Antitribu deck. ...
    (rec.games.trading-cards.jyhad)
  • Re: Tournament Fairness
    ... Suppose there are N players. ... can't everybody have a playoff round? ... Fairness of a tiebreaker depends on the tournament system because ...
    (rec.games.go)
  • One more wonderful vocational beings will officially possess the tournaments.
    ... The debut near the neutral pocket is the ... linguistic bowler or tournament, ... then we round arise Courtney and Oscar's ... universe. ...
    (alt.talk.royalty)
  • RSPW Dream Tournament: Round Three!
    ... With the impending WWE Raw King of the Ring tournament coming soon, we turn our attention to the third round of the RSPW Dream Tournament, with talent that would be pretty much unbeatable against the current WWE King of the Ring roster. ... Flair follows his first-round victory over now-TNA-champ Samoa Joe with a decisive second-round victory over Rob Van Dam. ...
    (rec.sport.pro-wrestling)