Create a special Playing Schedule - Logical/Mathematical Solution

Question

Last Week in Training (I'm a Cycleball player) a logial problem/puzzle tricked us. And I'm wondering if there exists a logical solution for the next time.

Cycleball is played in pairs (2 Players vs. 2 Players) and last week we were 5 People who joined the training - let's call us Player A,B,C,D,E.

Our Goal was to play a bunch of matches with the condition that every player had played in a team with each other. So we started and thought that we don't need to plan that. But we run into a conflict because in the last game (each player must play 4 matches) A and B would have to play with E at the same time.

I started by listing the possible Teams (AB,AC,AD,AE,BC,BD,BE,CD,CE,DE) , arranged them in a circle and connect the possible meetings. Each Team in the Circle is connected to 3 others. But here starts the puzzle for me. What's the solution? and are there general view on that problem?

Sorry for my bad english - corrections are always welcome!!!

Answer 1

As others have said

Yes it is possible

Furthermore

Each game $1$ person sits out and each person needs to play with $4$ others at some point so you need at least $4+1=5$ games.

During the play of $5$ games you will make $5*2=10$ teams, and the number of unique teams you must form is $\binom{5}{2}=10$, so this works out nicely.

Since there are $3$ ways to choose $2$ teams of $2$ from $4$ players, there are $3^5=243$ possible sets of $5$ games we could consider including many obviously invalid ones such as:

{BCvDE; ACvDE; ABvDE; ABvCE; ABvCD}

Of these $243$ sets $6$ are valid:

{BCvDE; ADvCE; AEvBD; ACvBE; ABvCD}
{BCvDE; AEvCD; ADvBE; ABvCE; ACvBD}
{BDvCE; ACvDE; ADvBE; AEvBC; ABvCD}
{BDvCE; AEvCD; ABvDE; ACvBE; ADvBC}
{BEvCD; ACvDE; AEvBD; ABvCE; ADvBC}
{BEvCD; ADvCE; ABvDE; AEvBC; ACvBD}

In each of the $6$ cases each player will play $2$ games against each other player.
Since each set may be permuted in $6!=120$ ways there are $6*120=720$ possible schedules.

Also note that

If $6$ of you turn up you will need to play exactly $2$ games with each other person, since there are $15$ combinations of sitters, which is an odd number.
Of the $3^{15}=14348907$ sets of $15$ games, $2124$ are valid.
One example would be:

{CDvEF; BDvEF; BEvCF; BCvDF; BCvDE;
 AEvDF; AEvCF; AFvCD; ADvCE; AFvBE;
 ADvBF; ABvDE; ACvBF; ABvCE; ACvBD}

In all $2124$ cases each player will play $4$ games against each other player.

---

This type of problem is similar to one often referred to as a social golfer problem which is in general unsolved. The first commonly known problem of that kind is Kirkman's schoolgirl problem (1850).

This paper discusses some solving techniques for the social golfer problem itself and shows that the completion-problem (of deciding if a so-far valid, but incomplete, schedule may be validly completed) is NP-complete.

Answer 2

Here is the example of everyone played once and with each other.

ab+cd, ac+ed, ad+be, ae+bc, ce+bd

You just want not to have a player, who played 2+ less games, than others at any stage.

Answer 3

If I understand your question correctly:

Yes it is possible.
A possible solution is:
AB - CD (E)
AC - BE (D)
AD - CE (B)
AE - BD (C)
BC - DE (A)


Another possible solution is:
AB - CD (E)
AE - BC (D)
AC - DE (B)
AD - BE (C)
BD - CE (A)

It is easy to understand that the order of the matches is arbitrary. However the second solution to your example is important since they both have the same first match, but different formations during the second match with the same guy sitting out and is thus a different solution (instead of just a mix up of the order).
This proves that there is no unique solution, not even after the first match has been played. All that I can add are the following characteristics of any such system:
- The total number of matches played for $n$ players $= (n-1 + n-2 + ... + 2 + 1)/j$ or $(\frac{n(n+1)}{2})/j$ (with j being the number of teams playing per matching, in this case 2)
- The order of matches does not matter

For an example with 5 players the team formations are quite straight forward since for every player who sits out only 3 possible combinations of teams can be made. However with a larger player set either multiple players sit out or multiple matches are played per round making it more complex and increasing the number of solutions.

Answer 4

If we generalise from 5 players to $n=8$ or more players, but keep the number of players in a team 2, then, for some values of $n$, there are tournaments where

• each player plays in the same team as each other player once
• each player plays against each other player twice
• there are $n-1$ rounds, where no player plays in two or more games in the same round

The proviso is that $n=0$ or $1$, modulo 4. So this works for 8 or 9 players, but not 6 or 7, for example.

There are examples here at the text links that follow the word "pure".