2
$\begingroup$

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!!!

| improve this question | |
$\endgroup$
  • $\begingroup$ what's the question? $\endgroup$ – JMP Jun 2 '16 at 10:07
  • $\begingroup$ I'm interested in a general solution for this kind of problem - Let all possible Teams (A,B,C,....) play together. With the restriction that each pair plays only for one Time together. Additionally the amount of matches has to be fewest. $\endgroup$ – QAdratur Jun 2 '16 at 10:16
  • 3
    $\begingroup$ @QAdratur Hi, this looks more like a math question than a puzzle. I think it might be more appropriate on the mathematics stack exchange. $\endgroup$ – Fabich Jun 2 '16 at 10:28
  • $\begingroup$ A relevant key word for is that you are looking for a perfect matching on the graph that you drew. (Though this is more general than is really necessary) $\endgroup$ – Milo Brandt Jun 2 '16 at 19:20
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In social-golfer-type problems there's an extra constraint that, if I'm understanding right, is not present in the question here: the matches need to be grouped into equal-size blocks that can be played simultaneously. I would not be surprised to find a reasonably generalizable solution to this problem. $\endgroup$ – Gareth McCaughan♦ Jun 2 '16 at 15:44
  • $\begingroup$ This is a problem of the same type. $\endgroup$ – f'' Jun 2 '16 at 15:52
  • $\begingroup$ @GarethMcCaughan yes that is true, for this problem we will have $2$ teams of $2$ and one "team" of $n-4$ sitters. I am not sure if this makes it easier in general. $\endgroup$ – Jonathan Allan Jun 2 '16 at 15:52
  • $\begingroup$ ...also if we had $n\geq 8$ we may want to schedule across more than one court too. $\endgroup$ – Jonathan Allan Jun 2 '16 at 16:00
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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".

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.