Once a week I get to play ping-pong over at my neighbor's house. Often there are five of us, which means someone has to sit out each game.
Even though we're all college graduates, we had a tough time remembering whose turn it was to sit out and who hadn't been on the same team for a while. Even keeping track of the score is a test of our mental abilities at times.
It doesn't work to just rotate people in a circular fashion. It doesn't mix up the teams sufficiently. I kept thinking, "this shouldn't be so hard." It should be possible to make list of five games, such that:
- Each person sits out once.
- Each player teams up once with every other player.
- Each player plays twice on each side of the table.
- A player never serves to another player more than once.
About a month ago, while it was my turn to sit out, I jotted down some diagrams showing where each player stands (or sits out) for each of five games. The others were quite happy to have the diagrams. However, I only managed to satisfy the first two rules. Even though we knew something was wrong, the consensus was that the diagrams were good enough and we shouldn't try to mess with it.
After last week's game I thought I could write a program to find a perfect round. It turned out to be harder than I thought. My lame brute-force approaches didn't work very well.
There are 5!, or 120, ways for 5 people to play one game of doubles ping-pong. Its the same as how many ways to arrange the numbers 1 through 5. For example:
12345 12354 12435 12453 12534 12543 and so on...
Thats just combinations for a single game. The trick is to find 5 games, which makes up a round, that meets the above rules. There are "120 choose 5" possible rounds. This is a pretty big number. It is, in fact:
120! ----------- = 119 * 118 * 117 * 116 = 190,578,024 5! (120-5)!
Of course, most of these potential rounds are invalid because they have the same person sitting out, or the same players teamed up. A more realistic way to enumerate the possibilities is to fix the first digit in every game (representing the person sitting out) and then count permutations of the other spots. It should be:
4!^5 = 7,962,624
Even with this more manageable number, I didn't accomplish my goal of writing a program that spat out a solution before the heat death of the universe.
During tonight's game the imperfections bugged me. I took another stab at doing it manually, with the help of a spreadsheet, and I believe this is a perfect round of doubles ping-pong for five people. Note, the person sitting out is shown below the table:
| 2 | 4 |
| 3 | 5 |
| 1 | |
| 5 | 3 |
| 1 | 4 |
| 2 | |
| 1 | 5 |
| 4 | 2 |
| 3 | |
| 3 | 2 |
| 5 | 1 |
| 4 | |
| 4 | 1 |
| 2 | 3 |
| 5 | |
I think I'm becoming a better ping-pong player, but worse at math and programming.
