Unit 2 Notes:
Wasted Games - Determining Number of Entries
There are basically three variables that a sports programmer needs to know in order to schedule a single elimination tournament. They are the number of entries in the tournament (n), the number of days needed to conduct the tournament, and the number of games needed to play each day of the tournament. By knowing any of these two variables, the programmer can figure out the third. The first step for the programmer, therefore, is to figure out which piece of information they need to figure out.
For determining number of entries, the programmer will know how many games are available per day and how many days he/she has to play the tournament. This is a fairly common scenario...most of the time, we receive a facility reservation, and we must determine how many teams we can accommodate in our tournament. In this case, we are assuming that teams will not play more than one game per day....
Here's how it works....
Lets say that the following information is applicable for our tournament:
Number of games that can be played each day = 5
Number of days that are available = 7
Step 1: The first step in solving the problem is to determine the number of total possible games that can be scheduled in a single elimination tournament. Do this by multiplying the number of days that are available (7) by the number of games that can be played each day (5). The answer will be the TOTAL POSSIBLE number of games that can played in the tournament (35).
Remember, in single elimination tournaments, you will never use all of the possible games available to you...you will always end up wasting games. For example, if we have 5 games available to play each day, during our final round, we will only use 1 of these games. That means in the final round, we will be wasting 4 games. We must figure out how many TOTAL games we will waste throughout the tournament, and subtract that number from the TOTAL POSSIBLE number of games that can be played (35).
Step 2: Begin with the last round of the tournament.....how many games will always be played in the last round? Thats right, the answer is 1. We know that if we can play 5 games in a day, and we only are playing 1 game in the last round, we will be wasting 4 games.
How about the other rounds? Work backwards from the last round and determine the number of games that will be played....remember, we use powers of 2 to figure this out. Continue to figure out the number of wasted games by subtracting the number of games in the round from the number of games that can be played each day (5). In the next to last round, you will play 2 games. If you can play 5 games in one day, you will be wasting 3 games. Continue working backwards until you hit a point where you will not be wasting any games....in this case, when you hit 8 games in a round, you won't be wasting any of the games you will play in one day. You will use all 5 games. At this point, you STOP, and add the number of wasted games.
Round R R R R Last
Games 16 8 4 2 1
Wasted 0 0 1 3 4 = 8 wasted games
Step 3: Subtract the total wasted games (8) from the total number of possible games (35). Your answer will be 27. This represents the ACTUAL number of games that can be played in your tournament.
Step 4: The total number of entries that can be accommodated in the tournament is determined using the following formula:
Number of games = N - 1
27 = N - 1
28 = N
Therefore, in your tournament, you could accommodate a MAXIMUM of 28 teams. Once you receive 28 entries, you must close your registration and it would be advisable to start a waiting list!