Hockey League Tournament Schedule

Date: 03/09/2000 at 13:44:07
From: Tim Gibbons
Subject: Matrix/Permutation of hockey teams for a tournament

I guess you're trying to help school kids, me too. But I'm trying to 
teach them field hockey from age six to twelve over here in England. 
And I don't seem to have the brainpower to sort this out.

I have to run a 7-a-side "Mini's" hockey tournament on Sunday and I 
need to formulate a matrix or timetable to permute the sides, like 
this:

Four fields are available, so I can run 4 games at a time (4 games per 
"time slot.") Each "time slot" should be 10 or 12 minutes and there 
should be about 3 minutes between "time slots" for the kids to clear 
the field and the next teams come on ready to start.

There are two groups of kids (I) Under 8, and (II) Under 10.

There are 6 teams in Under 8 category: A, B, C, D, E and F.

There are 10 teams in Under 10 category: 1, 2, 3, 4, 5, 6a, 6b, 7, 8a 
and 8b. The reason there are a's and b's for teams 6 and 8 is that 
they have two teams competing from their sports club (the others all 
have one team only.)

I need to draft a matrix like this:

     Start     FIELD "W"     FIELD "X"     FIELD "Y"      FIELD "Z" 
     Time      Under 8's     Under 8's     Under 10's     Under 10's
     -----     ---------     ---------     ----------     ----------
     10:00       A v B         C v D         1 v 2          3 v 4
     10:12       E v F         A v C         5 v 6a         6b v 7
     etc.        etc.          etc.          etc.           etc.

I want the teams to play as many games as possible in the time 
available. The tournament starts at 10:00 and should finish at 12:30 
or quite soon after, depending on the best compromise over the 
mathematics.

Each team should play as many of the other teams in their group as 
possible. The Under 8's can play some fixtures twice, whilst the Under 
10's probably cannot play all the other sides. For the Under 10's, 
please don't let 6a play 6b or 8a play 8b.

Teams should "rest" no longer than two "time slots" between games and 
they can play consecutive games.

The difficulty is in reconciling playing 4 games at a time with 
matching each side against as many of the other teams in their group 
without scheduling them to be on two fields in the same time slot.

If you needed, you could restrict the Under 8's to one field and use 
three fields across which to permute the larger Under 10's group.

I realize I am being "cheeky" asking for your help. Thanks anyway!

Tim

Date: 03/09/2000 at 17:40:39
From: Doctor TWE
Subject: Re: Matrix/Permutation of hockey teams for a tournament

Hi Tim - thanks for writing to Dr. Math!

Don't worry about being "cheeky," this is what we're here for.

Let's first calculate the total number of games playable. We have 
12:30-10:00 = 2:30 (or 150 minutes) in which to play the games. Each 
game takes 15 minutes counting "field clearing" time (I'm giving them 
the upper end of your 10-12 minute range - you may find you need to 
cut the game time down and increase the "field clearing" time. Kids 
are never as efficient as you'd like them to be!) Dividing 150/15 = 10 
games per field times 4 fields = 40 total games. Since each game 
involves 2 teams, there are 40*2 = 80 "team slots" available.

There are a total of 6+10 = 16 teams, so the "average" team should be 
able to play 80/16 = 5 games. It came out even, how convenient! The 6 
"Under 8" teams are easy; each team will play every other team once. 
(We'll get back to the scheduling of time slots.) For the "Under 10" 
group, each team will play 5 of the 9 other teams, with the caveat 
that 6a will not play 6b and 8a will not play 8b.

Next, let's make a time/field grid (like the one you started above.) 
Since each of the "Under 8" teams plays 5 games and we want them as 
"evenly spaced" as possible, we can designate every other timeslot on 
fields W, X and Y for the "Under 8" games, and the rest of the 
timeslots for the "Under 10" games, like so:

      Start | Field W | Field X | Field Y | Field Z
     -------+---------+---------+---------+---------
      10:00 | Under 8 | Under 8 | Under 8 | Under10
      10:15 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      10:30 | Under 8 | Under 8 | Under 8 | Under10
      10:45 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      11:00 | Under 8 | Under 8 | Under 8 | Under10
      11:15 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      11:30 | Under 8 | Under 8 | Under 8 | Under10
      11:45 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      12:00 | Under 8 | Under 8 | Under 8 | Under10
      12:15 | Under10 | Under10 | Under10 | Under10

In every pair of timeslots, we have 3 "Under 8" games (in the first 
half) and 5 "Under 10" games (one in the first half and four in the 
second half.) By having each team play in one of these games in each 
timeslot pair, we know that no team will wait more than 30 minutes, 
nor play more than 2 consecutive games. Having some "Under 10" teams 
play back-to-back games or have back-to-back rests is necessary due to 
the "extra" game.

To schedule a round-robin tournament efficiently (minimum number of 
rounds, no "extra" byes), you can use the polygon method. It's too 
complicated to explain here, but if you're interested, you might try 
to find it in a recent Geometry, Graph Theory, or Network Theory 
textbook. I used that method to schedule the "Under 8" games (see 
schedule below.) Of course, you could take any complete line of those 
and swap it with any other complete line (but don't move the "Under 
10" game along with it!)

Using the polygon technique for the "Under 10" games, I came up with 
the following nine "rounds":

     1:  2-3     4-8b    5-8a   6a-7     1-6b
     2:  3-4     2-5    6a-8b   6b-8a    1-7
     3:  4-5     3-6a    2-6b    7-8b    1-8a
     4:  5-6a    4-6b    3-7     2-8a    1-8b
   --5:-6a-6b----5-7-----4-8a----3-8b----1-2---
     6: 6b-7    6a-8a    5-8b    2-4     1-3
     7:  7-8a   6b-8b    2-6a    3-5     1-4
   --8:-8a-8b----2-7-----3-6b----4-6a----1-5---
     9:  2-8b    3-8a    4-7     5-6b    1-6a

Of course, rounds 5 and 8 are not allowed because of the a/b not 
playing each other restriction. This leaves 7 other rounds, of which 
we need to choose 5. I used 1, 2, 3, 4, and 6 in the schedule below, 
but you could select any five you want. If certain teams are 
especially strong or weak, you could choose to "eliminate" the rounds 
where a strong team plays a weak team - to make the schedule more 
competitive. I also rotated the teams around so that they wouldn't be 
playing on the same field too often. Here's what I have come up with, 
after all that:

      Start | Field W | Field X | Field Y | Field Z
     -------+---------+---------+---------+---------
      10:00 |   A-B   |   C-E   |   D-F   |  6a-7
      10:15 |   2-3   |   4-8b  |   5-8a  |   1-6b
     -------+---------+---------+---------+---------
      10:30 |   D-E   |   B-F   |   A-C   |   2-5
      10:45 |  6a-8b  |  6b-8a  |   1-7   |   3-4
     -------+---------+---------+---------+---------
      11:00 |   B-C   |   A-D   |   E-F   |   1-8a
      11:15 |   4-5   |   3-6a  |   2-6b  |   7-8b
     -------+---------+---------+---------+---------
      11:30 |   C-F   |   A-E   |   B-D   |   4-6b
      11:45 |   2-8a  |   3-7   |   1-8b  |   5-6a
     -------+---------+---------+---------+---------
      12:00 |   A-F   |   C-D   |   B-E   |  6b-7
      12:15 |   1-3   |   5-8b  |   2-4   |  6a-8a

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/17/2000 at 12:33:45
From: Tim Gibbons
Subject: Re: Matrix/Permutation of hockey teams for a tournament

Hi there!

This is all rather late in the day to do this but you said if I had 
any further questions about the attached solution of yours... well, 
there are a couple.

First we had 6 teams in the Under 8's, but someone has asked to add 
one more team. Can you redo your matrix for 7 teams, all other details 
as before? Secondly, the way you wrote the matrix for the Under 10's 
they each get 5 games; could you make it 6 each? And lastly, I have 
given you two clubs with an "a" and "b" team, i.e. teams 6 and 8, and 
you kindly avoided pairing their own a and b sides against one 
another. Could you re-permute things so that no team plays both 6a AND 
6b nor 8a AND 8b but instead just one of the a or b teams in each 
case?

Each of these questions is independent. Only the first is a priority; 
the second and third points are just things I'd like to do. See if you 
can answer me before Sunday the 19th local time. If not - that's quite 
okay, I understand... it's just this has been sprung on me at the last 
minute. I can probably re-work the Under 8's matrix you gave me to 
include 7 teams without too much trouble (probably!).

Bye for now,
Tim

Date: 03/17/2000 at 20:22:52
From: Doctor Twe
Subject: Re: Matrix/Permutation of hockey teams for a tournament

Hi again Tim! Thanks for writing back!

There's an old saying that says "if you give a man a fish, you feed 
him for a day, but if you teach a man to fish, he's fed for life." So 
I was going to point you to a FAQ, archive entry, or other website 
that explains the "polygon method" of round-robin tournament 
scheduling. Much to my dismay, after some fairly thorough searching, I 
could find no explanation of the method on the web - either on our 
site or any other! (I did find two questions in a standardized 
Geometry test data bank that asked students to use the method, but it 
did not explain how the method works or how it is applied.) Oh well. 
Someday when I have more time, I'll write an explanation and add it to 
our archives. At any rate, here's the fish...

To accommodate the extra games (adding a team to the Under-8 group and 
adding an extra game per team for the Under-10 group) and stay 
reasonably within our time constraints, we'll have to shorten the 
games to 10 minutes (plus 3 minutes to clear the filed.) This way we 
can add 2 extra "time slots" (8 games) but still only push our 
finishing time back to 12:33. We'll still use the same pattern for 
field/group assignments, but extend it as follows:

      Start | Field W | Field X | Field Y | Field Z
     -------+---------+---------+---------+---------
      10:00 | Under 8 | Under 8 | Under 8 | Under10
      10:13 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      10:26 | Under 8 | Under 8 | Under 8 | Under10
      10:39 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      10:52 | Under 8 | Under 8 | Under 8 | Under10
      11:05 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      11:18 | Under 8 | Under 8 | Under 8 | Under10
      11:31 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      11:44 | Under 8 | Under 8 | Under 8 | Under10
      11:57 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      12:10 | Under 8 | Under 8 | Under 8 | Under10
      12:23 | Under10 | Under10 | Under10 | Under10

Each Under-10 team will play once in each timeslot pair, and 6 of the 
7 Under-8 teams will play in each timeslot pair. (Of course, this 
means that the team with the 'bye' in that round will be sitting idle 
for 3 timeslots instead of 2, but I don't think there's any practical 
way to avoid that.)

Redoing the Under-8 pairings is fairly straight forward using the 
polygon method. Because there are an odd number of teams, and an odd 
number of games per team (5 - trying to push it to 6 would've meant 
finishing MUCH later), one team - G in the schedule below - plays an 
extra game. Teams A through F play 5 games each, but G plays 6.

Fulfilling your request for the Under-10's is a bit trickier. I tried 
several ways to fulfill your request that no team play both 6a and 6b 
nor 8a and 8b, but I could not find a solution. In theory, it should 
be possible (since each team plays only 6 others, and there are seven 
to choose from) - but all the methods I tried didn't produce the 
desired combination. In the schedule below, I incorporated the version 
I found with the fewest violations. I'll investigate this further and 
see if I can come up with a system that works, but I presume you'd 
rather have a "flawed" schedule now than a "perfect" schedule next 
week sometime... 

   [Note: since sending this e-mail, I have proven to my own 
    satisfaction that fulfilling the a/b request is, in fact, 
    impossible. -Dr. TWE]

      Start | Field W | Field X | Field Y | Field Z
     -------+---------+---------+---------+---------
      10:00 |   B-G   |   C-F   |   D-E   |   4-8b
      10:13 |   2-3   |   1-6a  |   5-8a  |   7-6b
     -------+---------+---------+---------+---------
      10:26 |   A-C   |   D-G   |   E-F   |   2-5
      10:39 |   7-8b  |  6a-8a  |   1-6b  |   3-4
     -------+---------+---------+---------+---------
      10:52 |   B-D   |   A-E   |   F-G   |   1-8a
      11:05 |   4-5   |   3-7   |   2-6a  |  6b-8b
     -------+---------+---------+---------+---------
      11:18 |   C-E   |   B-F   |   A-G   |   4-6b
      11:31 |   2-8b  |   3-8a  |   1-7   |   5-6a
     -------+---------+---------+---------+---------
      11:44 |   D-F   |   C-G   |   A-B   |   5-7
      11:57 |   3-6b  |   1-8b  |   2-8a  |   4-6a
     -------+---------+---------+---------+---------
      12:10 |   E-G   |   A-D   |   B-C   |   3-8b
      12:23 |   4-8a  |   7-6a  |   5-6b  |   1-2


Best of luck, and may the best teams win. If you have any more 
questions, write back again.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/18/2000 at 10:38:02
From: Tim Gibbons
Subject: Re: Matrix/Permutation of hockey teams for a tournament

I don't know if you're a man or a woman and right now, I don't really 
care, I want to marry you anyway! ;-)

You are SO, SO kind, I have been telling everyone about Dr. Math over 
here in England.

If you ever want to come to Southern England, you must look my family 
and me up... heck, the whole junior hockey club! Come and have a drink 
or two with us and lend a face to the name.

Thanks SO much. I am SO pleased with your flawed fish, you can't 
imagine. There will be well over a hundred kids there Sunday morning.
(god, I hope your system works!) And you know what'll happen, one team 
will have their bus break down, another will arrive with not enough 
players and then, someone will arrive who I asked but forgot about!

Bye for now - if there's anything [legal!] I can do for you, let me 
know. Forever in your debt!

Tim.

Date: 03/06/2001 at 11:48:41
From: Tim Gibbons
Subject: "Round robin" tournament scheduling

Last year you sent me a solution to a problem. I`m begging again!  
Can you help?

I`m organizing a grass hockey festival this coming Sunday for two groups 
of kids, "Under-8" and "Under-10." My problem is that my brain is small. 
Here's the thing I've got to try to work out:

Grass Hockey Tournament

Two Groups :
Under 8 - SIX TEAMS play each other, so each team to play 5 games;
Under 10 - NINE TEAMS play 5, 6 or 7 games, depending on feasibility.

Start time 10:00 A.M. Latest time for end of last game 1:30 P.M.
Four games are played at a time. Games should last about 10 to 13 minutes, 
with allowance for 2 or 3 minutes between games.

This is how I would approach things :

Under 10's teams #'s: 1,2,3,4,5,6,7,8,9. 
Under 8's ref's: = a,b,c,d,e,f.

10 AM : 1v2,  3v4,  5v6,  7v8, = 20
10.15 : 9v1,   avb,  cvd,  evf,
10.30 : 2v3, 4v5, 6v7, 8v9
10.45 : 1v3,  bvc,  dve,  fvg,

Beyond that, my mind drops out. Can you help me, please?

Thanks for your time.
Tim Gibbons, Southampton, England.

Date: 03/07/2001 at 15:21:58
From: Doctor Twe
Subject: Re: "Round robin" tournament scheduling

Hi Tim - thanks for writing again.

I remember the Southampton Field Hockey Tournament and your wonderful 
thank-you e-mail. It's still my all-time favorite!

Later that month, I also managed to find the time to write an explanation 
of the "polygon method" of round-robin tournament scheduling in response 
to someone else's similar query. It is archived at:

   Round Robin Tournament Schedule
   http://mathforum.org/dr.math/problems/kinley.3.31.00.html   

You might want to check it out for future reference.

As to this year's schedule, a few quick preliminary computations: 

We need 5*6/2 = 15 games for the Under 8's, and 9*8/2 = 36 games for 
the Under 10's. That's 15+36 = 51 games total. We have four fields, so 
we'll need (at least) 51/4 = 13 (rounded up) timeslots. 

13:30 - 10:00 = 3:30 or 210 minutes to work with; 210/13 = 16 minutes 
(rounded down) per timeslot. Great! that lets us use the maximum 13 minutes 
per game plus the maximum 3 minutes between games without a problem.

As I did last year, I'll use three fields every other timeslot for the 
Under 8's. Since there are so few Under 8 games relative to the Under 10's, 
we'll start them in the second timeslot, and they'll finish in 10. Here's 
the Time & Field Assignment chart:

      Start | Field W | Field X | Field Y | Field Z
     -------+---------+---------+---------+---------
      10:00 | Under10 | Under10 | Under10 | Under10
      10:16 | Under 8 | Under 8 | Under 8 | Under10
     -------+---------+---------+---------+---------
      10:32 | Under10 | Under10 | Under10 | Under10
      10:48 | Under 8 | Under 8 | Under10 | Under 8
     -------+---------+---------+---------+---------
      11:04 | Under10 | Under10 | Under10 | Under10
      11:20 | Under 8 | Under10 | Under 8 | Under 8
     -------+---------+---------+---------+---------
      11:36 | Under10 | Under10 | Under10 | Under10
      11:52 | Under10 | Under 8 | Under 8 | Under 8
     -------+---------+---------+---------+---------
      12:08 | Under10 | Under10 | Under10 | Under10
      12:24 | Under 8 | Under 8 | Under 8 | Under10
     -------+---------+---------+---------+---------
      12:40 | Under10 | Under10 | Under10 | Under10
      12:56 | Under10 | Under10 | Under10 | Under10
     -------+---------+---------+---------+---------
      13:12 | Under10 | Under10 | Under10 | <idle>

Note that the last game should finish at 13:25. I've shifted the fields for 
the Under 8's so that the same number of games are played on each field by 
the Under 10's.

Now to fill in the games. For the Under 8's, we can use the same schedule we 
used last year. For the Under 10's, we'll need to construct a new schedule. 
Using the polygon method, here are the match-ups needed:

                Matches         Idle
     1:  2-9   3-8   4-7   5-6   1
     2:  1-3   4-9   5-8   6-7   2
     3:  2-4   1-5   6-9   7-8   3
     4:  3-5   2-6   1-7   8-9   4
     5:  4-6   3-7   2-8   1-9   5
     6:  5-7   4-8   3-9   1-2   6
     7:  6-8   5-9   1-4   2-3   7
     8:  7-9   1-6   2-5   3-4   8
     9:  1-8   2-7   3-6   4-5   9

Now to put these in the Time & Field Assignment chart, we'll start by using 
one of the rows in each odd-numbered timeslot; then we'll plug one of the games 
from the "extra" rows into the lone even numbered timeslot. Since one team was 
idle in the odd-numbered row, we'll be sure that that team plays in the "extra" 
game. A bit of shuffling will allow each team to play two games on each filed. 
Our final schedule: 

      Start | Field W | Field X | Field Y | Field Z
     -------+---------+---------+---------+---------
      10:00 |   5-6   |   2-9   |   4-7   |   3-8
      10:16 |   A-B   |   C-E   |   D-F   |   1-6
     -------+---------+---------+---------+---------
      10:32 |   1-3   |   5-8   |   6-7   |   4-9
      10:48 |   D-E   |   B-F   |   2-5   |   A-C
     -------+---------+---------+---------+---------
      11:04 |   2-4   |   1-5   |   6-9   |   7-8
      11:20 |   B-C   |   3-4   |   A-D   |   E-F
     -------+---------+---------+---------+---------
      11:36 |   8-9   |   1-7   |   3-5   |   2-6
      11:52 |   7-9   |   A-E   |   C-F   |   B-D
     -------+---------+---------+---------+---------
      12:08 |   2-8   |   4-6   |   1-9   |   3-7
      12:24 |   A-F   |   C-D   |   B-E   |   4-5
     -------+---------+---------+---------+---------
      12:40 |   5-7   |   3-9   |   4-8   |   1-2
      12:56 |   1-4   |   6-8   |   2-3   |   5-9
     -------+---------+---------+---------+---------
      13:12 |   3-6   |   2-7   |   1-8   | <idle>

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/   

Date: 03/08/2001 at 07:58:38
From: Tim Gibbons
Subject: Friends across "The Pond"

Thank you for the third year running, from 'across the Pond'. And I am MOST 
gratified to have entered your archives in a roundabout way (or is it 
"roundrobin" way)... I shall look up the site you mention, and next time, 
I'll work out my own solution and send it to you to prove you've managed 
to educate a 41-year-old man who's often foolish enough to think he's nothing 
left to learn!

I really just want to say I can't thank you enough for your time and 
effort and the very speed with which you responded again. It is so, so 
gratifying I'm genuinely moved. You don't know me from Adam, as we say - 
which means you have no reason to be so helpful and so generous, and 
there's nothing in it for you.

These are controversial times when the Internet is creating so much adverse 
feeling. The privacies and sensitivities of people are so often abused by 
mischievous and sometimes evil people, hiding behind the anonymity of the 
computer. To be treated in so friendly a manner and to be given so much 
assistance on what many people would dismiss as a trivial matter, is 
positively uplifting.

If this eulogizing of mine sounds  rather excessive, I don't wish it to - 
you've transformed my mood - the better side of human nature is still out 
there, alive and kicking! And it's smiled on me when I asked it to. That's 
how you've made me feel... and I'm going to be telling everyone about it 
for the next few days, just as I did last year, and the year before that!

MAY THE SUN SHINE THIS SUNDAY -  BOTH SIDES OF THE ATLANTIC !

Cheers!   

Tim