A challenging Tenpin Bowling round robin problem

[Aielyn]

Hi,

I'm in a tenpin bowling league that's different from typical leagues. In this league, bowlers are put into groups of six each week, and all six in a group are against each other (all six bowl on the same pair of lanes together). There are 48 bowlers in the league.

The way that the league is set up, I require an 11 week draw that ensures that each bowler bowls against every other bowler at least once within those eleven weeks, and preferably no more than twice. It's quite trivial to see that there should be exactly 8 repeats for each bowler - that is, each bowler should bowl against exactly 8 other bowlers twice.

Anyway, I'm having a lot of trouble figuring out how to create such a draw. The best draw I've been able to make has seven weeks, for which no bowler plays any other bowler twice.

To do this, I've modified the 7x7 social square provided on this page. How did I modify it? I started by eliminating all instances of "team" 49. Then, I took the draws from "round 6", and distributed them amongst the other seven rounds, one group per round (for my own reasons, I chose the group with the 49 to go to round 7). For the round that got the group that had 49 in it, I simply deleted the other entries from that group from amongst the other groups for that week, bringing each group's count to six rather than seven.

For the other six rounds (rounds 0-5), I identified which number was scheduled to play against number 49 - that number was then deleted from the added group. The other six members of that group were then deleted as per round 7.

This produces a 7 week schedule for a 6x8 system.

My instinct tells me that there should at least be an 8 week schedule without repeats, based on an 8x8 system with the last two columns removed, but I cannot yet find an 8x8 social square, let alone one with the required column-grouping pattern (where members of the nth group of one specific round show up in column n of each group for each of the other rounds). The theoretical maximum is a 9 week schedule. If I could get a 9 week schedule, it would make things much easier, as each bowler would then only need to be paired with one of their remaining two competitors for each of the final two weeks.

So I suppose there are two variations of the problem:

1. Create a 9 week schedule without repeats.
2. Create an 11 week schedule with no missed pairings.

Can anyone help?

(EDIT: Just as a side note, in previous years, I attempted to create a schedule for 6x9 (9 groups of 6) for a full 44 weeks - this year is running a little different, with 4 sets of 11 weeks- with the requirements that no two play against each other twice within a certain number of weeks (maximised as much as possible) and no three all bowl together twice - so if 1, 2, and 3 all play each other in one week, then any other week in which 1 and 2 play each other, 3 must be on another pair of lanes. Suffice it to say, it was never going to happen, it's just too hard a problem, at that scale)

[Aielyn]

OK, I've made a little progress on the problem, in that I can now produce an 8 week schedule without repeats. In fact, I've figured out how to generalise the social squares solution somewhat - for an MxM system, you can produce M+1 weeks so that every person plays every other person once within that time... so long as M is a prime power. That is, M = p^n, where p is a prime number and n is a positive integer.

In order to do this, one needs to essentially produce a set of mutually orthogonal latin squares. As it turns out, this can be done for any prime power through the use of Galois Fields (I only know a bit of how they work, but enough to understand why it works for this problem), so that you have exactly n-1 orthogonal latin squares. For instance, for n=4, you have the latin square:

0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

This is the latin square produced by the galois field for n=4. This is the starting arrangement that we need. To produce the other orthogonal squares, you simply rotate through the rows other than the first one, like this:

0 1 2 3
2 3 0 1
3 2 1 0
1 0 3 2 (move 1 0 3 2 to the bottom)

0 1 2 3
3 2 1 0
1 0 3 2
2 3 0 1 (now move 2 3 0 1 to the bottom)

So, what are these latin squares in relation to the problem? Well, they're the second, third, and fourth columns of each group for the rounds that aren't in numerical order. So what we do is we increase each of the three latin squares by a multiple of four (assuming the first member is 0, not 1), and then group them together. For instance, the first latin square above ends up looking like this:

4 5 6 7
5 4 7 6
6 7 4 5
7 6 5 4

The second one should be increased by 8, and the third one by 12. This then produces our schedule in the following way.

In the first column of each group, put the first set of numbers, as so:
00          01          02          03
00          01          02          03
00          01          02          03
00          01          02          03

In the second column, we insert the columns from the first latin square, like this:

00 04        01 05        02 06        03 07
00 05        01 04        02 07        03 06
00 06        01 07        02 04        03 05
00 07        01 06        02 05        03 04

You will note that, if you remove the 0, 1, 2, and 3, you are now left with that latin square once again. Now, in the third column, we insert the columns from the second latin square, like this:

00 04 08       01 05 09       02 06 10       03 07 11
00 05 10       01 04 11       02 07 08       03 06 09
00 06 11       01 07 10       02 04 09       03 05 08
00 07 09       01 06 08       02 05 11       03 04 10

Again, if you remove the other columns, you regain the latin square. In the final column... you guessed it, the third latin square:

00 04 08 12      01 05 09 13      02 06 10 14      03 07 11 15
00 05 10 15      01 04 11 14      02 07 08 13      03 06 09 12
00 06 11 13      01 07 10 12      02 04 09 15      03 05 08 14
00 07 09 14      01 06 08 15      02 05 11 12      03 04 10 13

With this done, all that is left is to add the column sets, like this:

00 04 08 12      01 05 09 13      02 06 10 14      03 07 11 15
00 05 10 15      01 04 11 14      02 07 08 13      03 06 09 12
00 06 11 13      01 07 10 12      02 04 09 15      03 05 08 14
00 07 09 14      01 06 08 15      02 05 11 12      03 04 10 13
00 01 02 03      04 05 06 07      08 09 10 11      12 13 14 15

The exact same process works for any prime power n. For instance, for n=8=2^3, the latin square coming from the Galois Field is:

0 1 2 3 4 5 6 7
1 0 4 7 2 6 5 3
2 4 0 5 1 3 7 6
3 7 5 0 6 2 4 1
4 2 1 6 0 7 3 5
5 6 3 2 7 0 1 4
6 5 7 4 3 1 0 2
7 3 6 1 5 4 2 0

And, as with above, you can then create six more orthogonal ones by rotating the bottom seven rows, then use them to create an 8x8 social square schedule over nine weeks.

Now, in the case of my problem, 6x8, you simply leave off two of the latin squares, and thus do not do the last two columns of each group. However, this also invalidates the final round (0 1 2 3 4 5 6 7)(8 9 10 11 12 13 14 15)..., as they don't quite line up correctly. This is why I only have 8 weeks for the 6x8 case, rather than 9 weeks.

For the case of prime M, you get a fairly straight-forward solution. For instance, for M=5,

0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

This can then be rotated as per above. I'm not certain as to whether this produces the same social square solution as those provided here, but it should produce an appropriate solution.

[Ian Wakeling]

I think I have followed your construction for 7 rounds, but I am not sure that I see how to get the 8 round construction from the 8x8 social square (don't I get a 63 player schedule?). Richard's terminology 'social square' is non-standard, and the constructions for prime powers that you have been finding are well known, for more information search for finite geometry or resolvable balanced incomplete block design (BIBD), or resolvable 2-design.  I don't think that it will be easy to find extra rounds to add to your constructions to fill in the missing pairings and take it up to 11 rounds/weeks, have you tried this yet?

The bad news is that I don't believe I can do any better than you have done already. I have looked at a few computer search options and I can make a 15 week schedule where all pairs play one or twice, also I believe it might be possible to make an 11 round schedule for 44 players where there are 4 groups of 6 and 4 groups of 5 in each week.  Are either of those options any good?

Ian.

[Aielyn]

The construction for the 8 round schedule basically constructs the 8x8 = 64 member system, which would result in a 9 round schedule. But for all bar one of the rounds, the first six members of each group are one of the first 48 members of the system. So all you have to do is remove the last two members, and you have eight weeks with six per group, with no two playing each other, and all members in the schedule are one of the first 48. Also note that this should mean that any AxB system where A is no greater than one more than the maximum number of mutually orthogonal graeco-latin squares that can be created of size B, should be possible for a total of B weeks. Apparently the current lower bound on the maximum for a 12x12 graeco-latin square is currently 5, so you could construct a 6x12, 12 week schedule with no repeats (but some pairings missed).

I was using the "social squares" terminology only because I hadn't seen any "official" term in the context of round robin game scheduling.

In terms of using the 8 round schedule I created to bring it up to 11, I was able to logically deduce that you can't complete the schedule using only 3 more weeks. However, I suspect that, if I remove one of the rounds, leaving seven of that set of 8, I may be able to produce four rounds with some repeats (two repeats per member per round) - I'm still testing the idea. There are some complications that come with the approach I'm taking, but I'm hoping that they're resolvable. Using seven rounds from the 8 round schedule should be easier than trying to use the 7 round schedule as the starting point, because the missed pairings are far more ordered and easy to work with.

Anyway, a 15 week schedule or a 44 player system aren't suitable. The league has 48 bowlers with six per pair already, and there are exactly four sets of 11 rounds. The first of these, we're using a random schedule that suffers from major imbalance issues (I know of one case where three people were against each other in both of the first two weeks, at least). The other three sets of rounds, I'm hoping to have a reasonably balanced schedule as described in my first post.

Thanks for at least confirming that this isn't a trivial problem that I was overcomplicating. As you may or may not have guessed, I'm a mathematician, but with expertise in calculus and related fields, not in combinatorics, etc, so I was worried that I might have been taking an overly complicated approach to a relatively simple problem. Difficulty in finding appropriate terminology also contributed.

If I do manage to find a solution, I'll be sure to post how I did it. I'm also open to ideas from others, still, of course.

EDIT: If you'd like a better explanation of either of the two construction methods I mentioned, let me know, and I'll describe it for the actual 6x8 system with proper visual steps.

[Aielyn]

So, as it happens, I've managed to solve the problem. Ironically, though, I did so after discovering that what I thought was a "positional round" wasn't one, and so it needs to be a 12 week draw - and it's not quite trivial to extend the 11 week draw to the 12th week (I'm working on it).

It's a little complicated, so I'm sorry if people get a bit lost. So here's how you construct it (maybe others in a similar situation might get inspiration from it):

1. Construct 7 rounds using the orthogonal latin squares technique on an 8x6 grouping. That is, if you arrange the list like this:

_1 _2 _3 _4 _5 _6 <-- column numbers, for convenience
01 09 17 25 33 41
02 10 18 26 34 42
03 11 19 27 35 43
04 12 20 28 36 44
05 13 21 29 37 45
06 14 22 30 38 46
07 15 23 31 39 47
08 16 24 32 40 48

Then you can use the additive group within the Galois Field of order 8 (see below) to get 8 distinct "weeks"... but we drop the week with the basic layout - that is, the one you see above, with each row being a grouping.

Why drop that grouping? Because we're going to be using the last four weeks to cover its components.

2. Now, look at the rows and the columns. For instance, member 31 has the fourth column and the seventh row. Other members in each member's row and column are the ones that the member hasn't played yet. Now, consider the following groupings:

123456 | 78
127 | 368 | 4 | 5   /  367 | 128 | 4 | 5
347 | 258 | 1 | 6   /  257 | 348 | 1 | 6
567 | 148 | 2 | 3   /  147 | 568 | 2 | 3

What do these mean? Well, the (123456) grouping says that, in the first of the four weeks, members 1-6 of each column are put into a group. So in addition to (01, 02, 03, 04, 05, 06), you also have, for instance, (33, 34, 35, 36, 37, 38) as a group. For the (78), it means "pair together members 7 and 8 of each column"... you then group those pairs - the easiest way to do this is to group the first three pairs (07, 08, 15, 16, 23, 24) and the second three pairs similarly.

For the remaining three weeks, it works a little differently. For the first three columns, you group according to the groupings on the left (such as 127 | 368 | 4 | 5), and for the last three columns, you group according to the groupings on the right. The single values (such as 4 and 5 in the first of the three lines) indicate that the corresponding row gets grouped. So in that week, you get (04, 12, 20, 28, 36, 44), while in the next week, you get (01, 09, 17, 25, 33, 41).

For the triplets (like 127), you pair up the three from that column with the appropriate counterpoint by taking the opposing triplet from one of the opposing three columns (for 127 in column 1, the counterpoint triplet is 367 in column 4 - the 367 is in the same position on the other "side" of that week's groupings). For the first of the three grouping sets, you take columns 1 and 4, 2 and 5, and 3 and 6. For the second one, you go 1-5, 2-6, 3-4, and then for the third you go 1-6, 2-4, 3-5. For a visual idea of what this means, look here:

01 09 17 25 33 41
02 10 18 26 34 42
03 11 19 27 35 43
..
06 14 22 30 38 46
07 15 23 31 39 47
..

Above is the relevant rows for the example being given. Now, you take rows 1, 2, and 7, and grab the first member of each, and group them with the fourth member of rows 3, 6, and 7. These entries are bolded.

I know that this sounds complicated. It might help if you understand what is happening. The provided groupings are designed so that, within a column, every member plays every other member at least once, and no more than twice. So, if you look at member 01, then the first grouping says that member 01 plays against 02, 03, 04, 05, and 06 in the first of the weeks. The second one says that it plays against members 02 (for a second time) and 07. The third one says that it doesn't play against any other members in its column. The fourth one says that it plays against members 04 (for a second time) and 08. So it plays against each of 02-08 either once or twice. For 07, it plays against 08 in the first, 03 and 06 in the second, 02 and 05 in the third, and 01 and 04 in the fourth, so it plays against each other member of its column once.

Where there are singles (such as 4 and 5 in the second grouping), that row is playing against all others in its row. So rows 1, 2, 3, 4, 5, and 6 all play against others in their rows. Rows 7 and 8 are a little more complex - in the first grouping, you have them separated like this:

07 15 23 | 31 39 47
08 16 24 | 32 40 48

So 07, 08, 15, 16, 23, and 24 all play each other. So, for instance, 07 plays 15 and 23, being the first two other members in its row. Similarly, 31 plays 39 and 47 in its row. Then, in the other groupings, you have 127 of the first column against 367 of the fourth column - so while members 01 and 02 play against relatively random members (from their perspective) 27 and 30, member 07 manages to play against member 31 from its own row. The next grouping, it plays against 39, then against 47 in the final grouping. Meanwhile, because of the way that it's constructed, none of the off-row, off-column members in a group (such as 08 and 15, or 02 and 30) duplicate more than once, so you never get any instance of anybody playing anybody else three times.

3. For the sake of best spacing of matches, place the first of the four groupings in the first week, then have the seven "regular" weeks, then the last three of the four groupings in the last three weeks. So here's the resulting draw:

01 02 03 04 05 06 | 07 15 23 08 16 24 | 09 10 11 12 13 14 | 17 18 19 20 21 22 | 25 26 27 28 29 30 | 31 39 47 32 40 48 | 33 34 35 36 37 38 | 41 42 43 44 45 46
01 10 19 28 38 47 | 02 09 21 32 39 46 | 03 13 17 30 36 48 | 04 16 22 25 35 45 | 05 11 18 31 40 44 | 06 15 20 27 33 42 | 07 14 24 29 34 41 | 08 12 23 26 37 43
01 11 20 29 39 48 | 02 13 24 27 38 44 | 03 09 22 26 40 47 | 04 14 17 31 37 42 | 05 10 23 25 36 46 | 06 12 19 32 34 45 | 07 16 21 28 33 43 | 08 15 18 30 35 41
01 12 21 30 40 42 | 02 16 19 31 36 41 | 03 14 18 28 39 45 | 04 09 23 27 34 48 | 05 15 17 32 38 43 | 06 11 24 25 37 47 | 07 13 20 26 35 46 | 08 10 22 29 33 44
01 13 22 31 34 43 | 02 11 23 30 33 45 | 03 10 20 32 37 41 | 04 15 19 29 40 46 | 05 09 24 28 35 42 | 06 16 17 26 39 44 | 07 12 18 25 38 48 | 08 14 21 27 36 47
01 14 23 32 35 44 | 02 15 22 28 37 48 | 03 12 24 31 33 46 | 04 11 21 26 38 41 | 05 16 20 30 34 47 | 06 09 18 29 36 43 | 07 10 17 27 40 45 | 08 13 19 25 39 42
01 15 24 26 36 45 | 02 14 20 25 40 43 | 03 16 23 29 38 42 | 04 13 18 32 33 47 | 05 12 22 27 39 41 | 06 10 21 31 35 48 | 07 09 19 30 37 44 | 08 11 17 28 34 46
01 16 18 27 37 46 | 02 12 17 29 35 47 | 03 15 21 25 34 44 | 04 10 24 30 39 43 | 05 14 19 26 33 48 | 06 13 23 28 40 41 | 07 11 22 32 36 42 | 08 09 20 31 38 45
01 02 07 27 30 31 | 03 06 08 25 26 32 | 04 12 20 28 36 44 | 05 13 21 29 37 45 | 09 10 15 35 38 39 | 11 14 16 33 34 40 | 17 18 23 43 46 47 | 19 22 24 41 42 48
01 09 17 25 33 41 | 02 05 08 35 36 40 | 03 04 07 34 37 39 | 06 14 22 30 38 46 | 10 13 16 43 44 48 | 11 12 15 42 45 47 | 18 21 24 27 28 32 | 19 20 23 26 29 31
01 04 08 45 46 48 | 02 10 18 26 34 42 | 03 11 19 27 35 43 | 05 06 07 41 44 47 | 09 12 16 29 30 32 | 13 14 15 25 28 31 | 17 20 24 37 38 40 | 21 22 23 33 36 39

To make it easier to follow, I've bolded a few key groups. The bolded group in the first week is exactly the "rows 7 and 8, columns 1-3" set from the "first grouping". The third-last week's bolded group is the bolded group visualised half way through the description of step 2. The second-last week's bolded group is the result of taking row 6 as a whole.

I realise that it's still really complicated, and probably quite poorly-explained. I apologise for that.

[Ian Wakeling]

Thanks so much for taking the time to explain how you finally solved this problem - it is a method that I will likely use in the future.