4
$\begingroup$

I need to solve the following problem for actual use.

  • 10 people will be playing a game.
  • They play the game 4 people at a time.
  • Each time they play they garner points within the game.
  • Each person needs to play against each other person at some time.
  • Each person needs to play the same number of times.
  • The winner is the person who has accumulated the most points at the end.

10 choose 4 is 210, so one solution is to have 210 rounds where every combination of 4 players plays the game. But this is an impractical number of rounds!

Is there a solution to this problem in less than 20 rounds? I suppose it would be okay if some rounds were played with only 3 people. How would I figure this out in the fairest way?

EDIT: An additional useful constraint would be that no player plays twice in a row, if that's possible.

$\endgroup$
  • $\begingroup$ Interesting problem. Too bad there aren't only eight players; then it would be trivial! $\endgroup$ – Brian Tung Aug 27 '15 at 16:40
  • $\begingroup$ There is also a solution in which each of the ten players plays three rounds of five players each, but unless that's admissible, that's not of much use. $\endgroup$ – Brian Tung Aug 27 '15 at 16:43
  • $\begingroup$ This may be relevant: en.wikipedia.org/wiki/Block_design $\endgroup$ – Austin Mohr Aug 27 '15 at 17:21
  • $\begingroup$ @AustinMohr Thanks for the link. Although it looks like it might apply, it's a little too deep for me! $\endgroup$ – CrazyApe84 Aug 27 '15 at 20:23
1
$\begingroup$

As there are $10$ players, and each round involves $4$ players, and each player must play an equal number of times, the number of rounds must be a multiple of $5$, so $10$ rounds is the simplest solution.

Here is a solution in which $ABCD$ occurs twice:

roundrobin

Chart of number of meetups:

   A  B  C  D  E  F  G  H  I  J
A  x  2  2  2  1  1  1  1  1  1
B  2  x  2  2  1  1  1  1  1  1
C  2  2  x  2  1  1  1  1  1  1
D  2  2  2  x  1  1  1  1  1  1
E  1  1  1  1  x  1  1  2  2  2
F  1  1  1  1  1  x  4  1  1  1
G  1  1  1  1  1  4  x  1  1  1
H  1  1  1  1  2  1  1  x  2  2
I  1  1  1  1  2  1  1  2  x  2
J  1  1  1  1  2  1  1  2  2  x

Number of number of meetups:

 0:   0
 1:  64
 2:  24
 3:   0
 4:   2
$\endgroup$
  • $\begingroup$ Thanks for you help. I added a chart of the number of meetups between players (awaiting peer review). It would be nice to get rid of the 4's in the meetups chart (between F and G). I wonder if that's a necessary fact in a 10 round solution (paw88789's solution also has two 4's). $\endgroup$ – CrazyApe84 Aug 27 '15 at 20:28
2
$\begingroup$

Here is an ad hoc solution that I believe satisfies your requirements using 10 games, with each player being in four games. A drawback is that some people play each other more than twice (the max is I and J who meet four times. This could possibly be improved with more tinkering).

Game 1: ABCD
Game 2: AEFG
Game 3: AHIJ
Game 4: BEGH
Game 5: BFIJ
Game 6: DEIJ
Game 7: CDFH
Game 8: CGIJ
Game 9: CDEG
Game 10: ABFH

A B C D E F G H I J
* * * *
*       * * *
*             * * *
  *     *   * *
  *       *     * *
      * *       * *
    * *   *   *
    *       *   * *
    * * *   *
* *       *   *

Chart of number of meetups:

   A  B  C  D  E  F  G  H  I  J
A  x  2  1  1  1  2  1  2  1  1
B  2  x  1  1  1  2  1  2  1  1
C  1  1  x  3  1  1  2  1  1  1
D  1  1  3  x  2  1  1  1  1  1
E  1  1  1  2  x  1  3  1  1  1
F  2  2  1  1  1  x  1  2  1  1
G  1  1  2  1  3  1  x  1  1  1
H  2  2  1  1  1  2  1  x  1  1
I  1  1  1  1  1  1  1  1  x  4
J  1  1  1  1  1  1  1  1  4  x

Number of number of meetups:

 0:   0
 1:  68
 2:  16
 3:   4
 4:   2
$\endgroup$
  • $\begingroup$ Thanks for your answer. I've added some charts of your solution (they won't show up until they're reviewed). Both yours and Jon's answers together demonstrate that it pretty much needs to be an ad hoc solution, and as you say, more tinkering could possibly improve it. I'd give you some points but am unable due to my lowly status. $\endgroup$ – CrazyApe84 Aug 27 '15 at 20:24
1
$\begingroup$

Generally if we have $m$ players and $n$ players per game. Let total number of games must be at least $N$.Everyone plays everyone, which means, everyone need to participate in $k_1 = ceil(\frac {m-1}{n-1})$ games.

Let &Player 1& participate in $k_1$ first games and each one plays with him. Now we can not count him anymore. Now we have $m-1$ players each of who need to play $k_2=ceil(\frac {m-1-(n-1)}{n-1})= ceil(\frac {m-n}{n-1})$. After $k_2$ games we have one player less, and rest need to play $k_3=ceil(\frac {m-n-(n-1)}{n-1})= ceil(\frac {m-2n-1}{n-1})$ and so on until $k_s=0$. As you can see, numerator if fraction is a member of arithmetic progression: $a_1=m-1 a_p=a_1-(p-1)\cdot (n-1)$. $a_s<0$, so

$m-1-s \cdot n +s+n-1<0$

$s \cdot (n-1) = m+n-2$

$s = \frac {m+n-2}{n-1}$

So $N=\sum \limits_{p=0}^{p \leqslant s} k_p = \frac { \sum \limits_{p=0}^{p \leqslant s} a_p }{n-1}+s$ ($s$ added because of $ceil$, which adds 1 game per round) which is

$N=\frac {\frac {a_1+a_s}{2} \cdot s}{n-1} + s = \frac {m-1}{2 \cdot (n-1)} \cdot \frac {m+n-2}{n-1} + \frac {m+n-2}{n-1} = \frac {m+n-2}{n-1} \cdot \frac {m-1+2n-2}{2 \cdot (n-1)} = \frac {(m+2 \cdot n-3) \cdot (m+n-2)}{2 \cdot (n-1)^2} $, if I got everything right of course. Then for $m=10, n=4, N=\frac {15 \cdot 12}{18}=10$

$\endgroup$
  • $\begingroup$ Nice analysis showing the minimum number of rounds. Thank you. I'd give you points but am unable due to my meager status. :-) I'll try to remember to come back later. Thanks again. $\endgroup$ – CrazyApe84 Aug 27 '15 at 20:23
  • $\begingroup$ @CrazyApe84 not that I'm mad about rating, just want to teach you something new ;) You can upvote now, and it will count automatically when you get opportunity to vote. $\endgroup$ – EvgeniyZh Aug 27 '15 at 20:27
  • $\begingroup$ Great. I already hit the button but didn't realize that would do it. Thanks again buddy. $\endgroup$ – CrazyApe84 Aug 27 '15 at 20:29

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.