A Software Solution to the Unsolved Problem of

Scheduling Bowling Tournaments

Kumud Bhandari

**Abstract**

In this paper, we explore the mathematical problem behind creating a proper schedule for a bowling tournament. Then, we discuss the implementation of a system with a graphical user interface that uses a brute force method to generate the schedule.

**1. Introduction**

In a bowling tournament, several teams participate and compete against each other in groups of two or more. In such a tournament, we want to make sure that each team bowls against as many teams as possible without repeat, and more importantly, each team bowls in every round of the tournament. We can accomplish this by reshuffling the group in each round in such a way that no two teams will belong to the same group more than once and each team belongs to at least one group in each round. Table 1 shows a tentative schedule for 16 teams, labeled T1 through T16. In this schedule, for example, T1 is grouped with T2, T3, and T4 in round 0. Hence, in the subsequent four rounds, T1 is never grouped again with T2, T3, or T4. This approach applies to every team.

Some mathematics reveals that it is easy to create such a schedule when teams are grouped in two! However, an attempt to create such a schedule by hand when teams are to be grouped by more than two reveals that it is not an easy task! In this paper, we present this problem in mathematical terms, explore the related mathematical field, and discuss the design of the Graphical User Interface (GUI) enabled software that uses a brute force method to create such schedules.

Table SEQ Table \* ARABIC 1: A schedule for 16 teams

Games |
Group 0 |
Group 1 |
Group 2 |
Group 3 |

Round 0 |
T1,T2,T3,T4 |
T5,T6,T7,T8 |
T9,T10,T11,T12 |
T13,T14,T15,T16 |

Round 1 |
T1,T5,T9,T13 |
T2,T6,T10,T14 |
T3,T7,T11,T15 |
T4,T8,T12,T16 |

Round 2 |
T1,T6,T11,T16 |
T2,T5,T12,T15 |
T3,T8,T9,T14 |
T4,T7,T10,T13 |

Round 3 |
T1,T7,T12,T14 |
T2,T8,T11,T13 |
T3,T5,T10,T16 |
T4,T6,T9,T15 |

Round 4 |
T1,T8,T10,T15 |
T2,T7,T9,T16 |
T3,T6,T12,T13 |
T4,T5,T11,T14 |

**2. Mathematical Problem**

Suppose we partition set *A* of *n* objects into subsets of size *k >*2, where . Let us denote the partition by and the subset within the partition by . Then,

,

where

.

First, we are interested in the maximum number of partitions that can be obtained such that

, where .

Secondly, we are interested in how such partitions can be obtained for large *n* and . Example 1 shows the computation of such partitions for and .

**Example 1:** Suppose we have and we partition into subsets of size 3. Then, partition 0,

,

where

, , and .

Similarly, partition 1,

,

where

, , and .

Similarly, partition 2,

,

where

, , and .

Lastly, partition 3,

,

where

, , and .

We depict the results from example 1 using a graph in Figure 1. We represent *n *objects as vertices of the graph. An edge exists between two vertices if and only if they belong to the same subset. Furthermore, two edges have the same color if and only if the edges belong to the same partition. The edges belonging to partitions , , , and are colored in green, blue, red, and purple respectively.

Figure SEQ Figure \* ARABIC 1: A graph theoretic representation of the partitions of a set containing 9 elements.

**3. The Combinatorial Design Approach**

Although graph theory provides excellent method of visualizing the solution for smaller *n*, the visualization becomes increasing complex with larger values of *m *and *n. *Moreover, graph theory does not provide us with tools to generate such a solution. Thus, we explore the area of ** combinatorial design theory** which concerns questions about whether it is possible to arrange elements of a finite set into subsets so that certain 'balance' properties are satisfied [1].

**Definition 1:** A ** design** is a pair such that the following properties are satisfied:

1. is a set of elements called points, and

2. is a collection (i.e. multiset) of non-empty subsets of called blocks[1].

The word design is used due to the origin of the problem in the experimental design. One of the most important types of design is called balanced incomplete block design which we define below.

**Definition 2: **Let *v, k*, and be positive integers such that . A ** -balanced incomplete block design **(BIBD) is a design such that the following properties are satisfied:

1.

2. each block contains exactly k points, and

3. every pair of distinct points is contained in exactly blocks [1].

The constraint as described in line 3 of the definition is called the 'balance' property. For all the cases that we consider in this paper, because any pair of teams belong to a group (block) only once throughout the tournament. As teams are grouped by four in a bowling tournament, we are primarily concerned with cases where . Although BIBD captures most of the conditions of our problem, it fails to capture one vital condition, i.e., there should be at least one set of blocks whose union should contain all the teams participating in the tournament. This condition, which allows us to construct round(s) of games from blocks, is captured by a resolvable BIBD which we define below.

**Definition 3:** Suppose is a *-BIBD*. A parallel class in is a subset of disjoint blocks from whose union is X. A partition of into r parallel classes is called a ** resolution, **and is said to be a

**Example 2: **The design shown in table 1 is a . Moreover, this *BIBD* is resolvable because we are able to obtain five different resolutions, i.e. five different rounds of games.

**Remark 1:** Assuming , cases where is equal to 4, 8 and 12 are trivial cases since the maximum number of blocks that can be constructed is 1,2, and 3 respectively. Hence, only one resolution is possible in each case.

**Remark 2:** Assuming , be cautioned that our problem is a resolvable BIBD for only certain values of . For instance, when or when *n=*28, every possible pair of teams appear in the block and hence is a case of BIBD (by definition 3). However, when or , every possible pair of teams does not appear in the block and hence is not the case of BIBD.

In some 'nice' cases of BIBD, where each team appears for equal number of times, we calculate the number of blocks (*r*) in which each team appears as follows:

[1].

For a resolvable BIBD, each team appears in a resolution at most once. Hence the number of resolutions (*e*) possible to construct is smaller or equal to the number of blocks in which each team appears. Mathematically,

.

Next, the total number of blocks (*b*) that can be constructed is given by the following relation:

.

**Example 3:** For the *BIBD* in table 1, and . Therefore,

Hence, each team appears in the schedule five times. From the above calculation, we also conclude that

Next, we calculate the number of blocks (*b*) that can be constructed as follows:

Hence, the number of blocks possible to construct is 20. In this case, every block can be used to construct resolution. Therefore, it is possible to construct five resolutions (i.e. five rounds of games).

The problem presented here is popularly known as ** Social Golfer Problem**. In general, it is an unsolved problem in mathematics. No analytic method exists for computing the maximum number of blocks and resolutions for any

**4. Schedule Generation**

Due to the nature of the mathematical problem, no algorithm exists to generate a schedule for *n *teams grouped by *k *teams [2]. However, the solution to the problem entails a high degree of symmetry, the exploitation of which makes it easier to generate the solutions. In all the subsequent discussions, we assume and . In this section, we show how one can generate the schedule for the tournament with 16 teams using example 4. We use the variations of the techniques used in this example to generate schedules when *n* equals 20, 24, 28, 32, 36, 40, 44, and 48.

**Example 4:** Consider a set of 16 teams ( ),

.

Round 0: We obtain round 0 of the tournament by simple partition,

where

, , , and .

Round 1: We obtain group (subset) 0 by taking the team in position 0 from each group in round (partition) 0. Likewise, we obtain group 1 by taking the team in position 1 of each group in the round 0 and so on. In general, the group of round 1 is generated by taking the team from each group of round 0. Thus, round 1 of the tournament is given by the partition,

where

, , , and .

Round 2: We create each group for round 2 by taking elements in positions and of subsets , , , and respectively. To construct group 0 and group 2, we compute the position, , as follows:

where

for group 0, for group 2, and .

Similarly, to construct group 1 and group 3, we compute the position, , as follows:

where

for group 1, for the group 3, and .

Thus, round 2 of the tournament is given by the partition,

where

, , , and .

Round 3: We obtain each group of round 3 by taking elements in positions , , , and of subsets , , , and respectively. To construct group 0 and group 2, we compute the position, , as follows:

where

,

for group 0, for group 2, and .

Similarly, to construct group 1 and group 3, we compute the position, , as follows:

where

,

for group 1, for group 3, and .

Thus, round 3 of the tournament is given by the partition,

where

, , , and .

Round 4: We obtain each group of round 4 by taking elements in positions , , , and of subsets , , , and respectively. To construct group 0 and group 2, we compute the position, , as follows:

where

for group 0, for group 2, and .

Similarly, to construct group 1 and group 3, we compute the position, , as follows:

where

for group 1, for group 3, and .

Thus, the round 4 of the game is given by the following partition,

where

, , , and .

We present the results obtained for all the rounds in table 2.

Table SEQ Table \* ARABIC 2: Schedule for 16 teams obtained in example 4

Games |
Group 0 |
Group 1 |
Group 2 |
Group 3 |

Round 0 |
1, 2, 3, 4 |
5, 6, 7, 8 |
9, 10, 11, 12 |
13, 14, 15, 16 |

Round 1 |
1, 5, 9, 13 |
2, 6, 10, 14 |
3, 7, 11, 15 |
4, 8, 12, 16 |

Round 2 |
1, 6, 11, 16 |
2, 5, 12, 15 |
3, 8, 9, 14 |
4, 7, 10, 13 |

Round 3 |
1, 7, 12, 14 |
2, 8, 11, 13 |
3, 5, 10, 16 |
4, 6, 9, 15 |

Round 4 |
1, 8, 10, 15 |
2, 7, 9, 16 |
3, 6, 12, 13 |
4, 5, 11, 14 |

Table 3 shows the number of rounds we obtained for the different numbers of teams. The highest number of rounds possible is 9, and it occurs when . We computed schedule for each *n* in table 3 and hard coded the solution in the software.

**Table SEQ Table \* ARABIC 3: Number of rounds obtained for different values of n**

No of Teams ( |
No of rounds ( |

4 |
1 |

8 |
1 |

12 |
1 |

16 |
5 |

20 |
5 |

24 |
6 |

28 |
7 |

32 |
9 |

36 |
6 |

40 |
5 |

44 |
5 |

48 |
5 |

**5. Design and Implementation of the Software**

We designed and implemented the software application titled *'McKendree Schedule Maker'* using the object-oriented paradigm. The design contains the following main classes, whose purposes we describe below in the context of their functionality and interaction:

* MainForm

* NewScheduleDialog

* ScheduleDisplayInternalFrame

* ManipulateSchedule

* ManipulateTeam

* NewSheduleInputData

* FileActivity

* OpenInternetBrowser

The *MainForm* is the main class. It is responsible for orchestrating other classes. The N*ewScheduleDialog* class collects information necessary to generate a new schedule from the user. Inside the *NewScheduleDialog *class, an instance of the class *NewScheduleInputData* is instantiated with the user provided information and passed to class *MainForm* by reference. The *NewScheduleInputData* class provides necessary data structure to hold all the information required to create a new schedule. The user provided information is then passed by reference from *MainForm* to *ScheduleDisplayInternalForm*, which is responsible for formatting and displaying the schedule in a table inside the internal frame. *ScheduleDisplayInternalForm* first uses *ManipulateSchedule* class to obtain the schedule for the given number of teams and rounds of games. The class *ManipulateSchedule* contains pre-computed schedule for those cases where number of teams is a positive multiple of four less than 48. We first compute the lowest multiple of four that is greater than or equal to the user-specified number of teams and consider the schedule corresponding to that multiple of four as a base schedule. If the number of rounds required is more than the rounds available in the base schedule then, we generate additional rounds while minimizing the number of times a pair of teams are grouped together. Next, if the user-specified number of teams is not a multiple of four, then we get rid of the extra teams from the base schedule. We also randomly reshuffle teams within the group so that they are not always on the same side of other teams in a bowling alley. Moreover, we reshuffle groups within each round of the tournament so that a group does not belong to the same bowling alley each time. The final schedule is passed to the *ScheduleDisplayInternalForm* which converts the schedule into formatted string and displays it in a table along with the index table.

The class *FileActivity* provides with facility to browse the filesystem so that the user can choose the location and filename to save or load a schedule. Once the user chooses the filename and location to open the file, The *FileActivity* class returns the name and location of the file to the class *ScheuduleDisplayInternalFrame* which then formats and displays the schedule. Similarly, once the user chooses the filename and location to save the schedule, the *FileActivity* class returns this information to *ScheduleDisplayInternalFrame*,* *which then writes the schedule to the specific file in the specific location. Additionally, *ScheduleDisplayInternalFrame* also generates the HTML code for the schedule being displayed and allows the user to save the HTML file in one�s chosen location. Furthermore, it provides the HTML file location to the class *OpenInternetBrowser* which then launches a default web browser with the HTML file displayed in it. The application also maintains the database of all the team names in a league. The class *ManipulateTeam* enables the user to add or remove a team permanently from the database. We summarize the functionality described in this section using a data flow diagram in figure 2. We present the Unified Modeling Language (UML) class diagram for these main classes in figure 3.

**Figure SEQ Figure \* ARABIC 2: Data Flow Diagram for the McKendree Schedule Maker**

**Figure SEQ Figure \* ARABIC 3: UML class diagram of the main classes**

**6. Graphical User Interface**

A user-friendly graphical interface is an integral part of this software. The main display frame consists of a menu, a toolbar and a display pane where the user opens one or more schedule for display; however, only one of them is in focus or activated at any given time. The menu bar contains drop-down menus, namely *File*, *Action*, and *Help*. *File* consists of menu items that enable the user to create a new schedule, open a saved schedule, save a schedule, save schedule with a new filename, close a schedule and exit the application. Likewise, *Action* consists of facilities to add a team to the database of teams or remove a team from it, generate a web page, print the schedule, and also e-mail it. Note that the printing and e-mailing facilities are disabled in the first release of the software. Finally, the *Help* menu consists of menu items to access information about the software, its creator and to look up help topics. The user can also access most of these functionalities by using the buttons on the toolbar situated below the menu bar. Figure 4 shows the screen shot of the application.

Figure SEQ Figure \* ARABIC 4: Snap shot of the application

The user can either create a completely new schedule by using a form shown in figure 5 or load a saved schedule from a file. This form also makes sure that the user selects the exact number of teams that one wishes to select.

Figure SEQ Figure \* ARABIC 5: Snapshot of the form to create a new schedule

The application displays each schedule in an internal window on the display pane of the main window as shown in figure 4. The user can close or minimize these internal windows individually. Inside the internal window, it displays the schedule in a table using numerical indices for participating teams. In the next table below the schedule, it displays names of the participating teams alongside their corresponding indices. The user can change the team that has been assigned to specific numerical index by double clicking on the team name and selecting different name from the list of teams participating in the tournament. Moreover, for portability and printing, one can generate the HTML code for the schedule with a single click. The application also prompts the user to save the webpage in a desired location and automatically displays it in a default browser. Figure 6 shows the webpage generated by the application.

Figure SEQ Figure \* ARABIC 6: Web page generated for a schedule

The user can also add or remove team(s) from the database which contains names of more than 260 teams belonging to a league by using the form shown in figure 7.

Figure SEQ Figure \* ARABIC 7: A form to add or remove teams from the database

To guide the new users through the application, it contains hyperlinked help pages which can be launched in a web browser using a single click. Figure 8 shows the help main topic page.

Figure SEQ Figure \* ARABIC 8: Help main page

**7. Conclusion**

In this paper, we presented the unsolved mathematics behind bowling tournament scheduling. We showed how the maximum number of rounds for a tournament can be calculated for some cases, and how symmetry of the problem can be exploited to generate the solution by brute force. Finally, we presented the software implementation of the solution. We expect the resulting software to ease the burden of creating an efficient bowling schedule for the bowling tournament organizers.

**References**

[1]** Stinson, Douglas R.** *Combinatorial Designs Construction and Analysis. *New York : Springer- Verlag,

2004.

[2] **Colbourn, C.J and J, Colbourn M.** *Algorithms in Combinatorial Design Theory. *Amsterdam : Elsevier

Science, 1985.

[3] **Pless, Vera.** *Introduction to the Theory of Error-Correcting Codes. *New York : John Wiley & Sons,

1998.

[4] **Pressman, Roger S.** *Software Engineering: A Practitioner's Approach. *New York : McGraw-Hill, 2005.

[5] **Buckley, Fred and Lewinter, Marty.** *A Friendly Introduction to Graph Theory. *New York : Prentice

Hall, 2002.

©