Thursday, January 6, 2011

Amazing Solution Behind the 8-Ball

My good neighbor Warren came over last evening with a problem. He schedules 8-Ball and has a dandy scheme for twelve teams over eleven weeks. For each session, pairs of teams are assigned to each of the six tables in the Billiard parlor. His schedule is constructed such that, over the eleven week period, each team plays each other team exactly once.

Well, someone decided to add a thirteenth team! OY!

Warren figured out that the schedule would have to be expanded to thirteen weeks and that, each week, a different team would take a "bye" - not play. Of course, he wanted to retain his system where, over the course of the thirteen weeks, each team plays each other team exactly once.

So, he asked me, how to schedule it?

I thought about it for a while and then, fairly rapidly, came up with a methodology that amazed both of us! (If I have to say so myself :^)

What is the solution? What is the method I came up with?

Think about it before you scroll down.







SOLUTION (Image is below the text)

I made use of a spreadsheet, but it could just as well have been done on graph paper.

1) I marked out a 13 by 13 grid. That way the intersection of any row and any column designated a specific match-up. For example, the intersection of the fourth row and the third column would match team #4 with team #3.

2) I immediately realized that a team could not be matched against itself, so the entire middle diagonal was not applicable. I yellowed that out.

3) Then, I realized that the match-up of #4 with #3 was the same as the match-up of #3 with # 4 (DUH!), so the entire upper right hand triangle of cells would duplicate the lower left triangle. So I yellowed out the upper right cells.

4) That left the lower left triangle of cells. OK, what to do now?

5) Well, the six Billiard tables for any given week could include each team a maximum of one time, so the six cells corresponding to that week had to be on separate rows and columns. In other words, they had to be on a diagonal. (WOW! That was the breakthrough!)

6) So, I noticed that the diagonal that started with cell 13-1 had exactly six cells in it. So, I colored them a deep yellow.

7) The diagonal starting with cell 13-2 also had six cells, so I colored them green.

8) Then I went up the diagonal starting with cell 13-3, coloring them red. Uh, oh! There were only five cells and I needed six. Where to find a nice single cell needing company? I noticed that cell 2-1 was a candidate, so I colored it red as well.

9) Moving on to cell 13-4, I did the same, with the color blue, and so on and on until all the cells in the lower left triangle were colored.

10) It took thirteen colors, a good sign from the math gods! Each color represented one of the thirteen weeks of the schedule. The first diagonal I colored, in deep yellow, gives team #7 a bye. The second, in red, gives team #8 a bye, and so on, for each color. (The byes are listed in the far right column, corresponding to the color in column 1. Team #1 gets a bye for the light green diagonal.)

Neat, ain' it? Ira Glickstein

1 comment:

Anonymous said...

Thank you Ira for solving this diffucult connundrum. Its was interesting watching your brain go through the process, as the solution evolved and manifested itself. One additional small problem; I had to covert colors back to (team)numbers, and being somewhat color blind this became a challenge. However, the final matrix of teams and byes became evident. thanks again...Warren