1
$\begingroup$

I'm looking for a format for a 4 vs. 4 tournament where the green team and blue team each has 6 players but two different people sit out each competition. How many match ups must occur before everyone has sat out at least once or everybody has played everybody once?

Thank you.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It is clear that at least 3 matches must occur to satisfy either condition. Perhaps I am missing something, because it seems 3 also suffices to establish both. Perhaps this is too localized? Gerhard "Ask Me About System Design" Paseman, 2010.03.02 $\endgroup$
    – Gerhard Paseman
    Commented Mar 2, 2010 at 22:13
  • 6
    $\begingroup$ The question is not too localized; it is just poorly written and maybe looks like homework to some people. $\endgroup$
    – Qiaochu Yuan
    Commented Mar 2, 2010 at 22:52
  • 1
    $\begingroup$ Decompositing K_{6,6} into 4K_2+4K_1 (four complete graphs on two vertices and four isolated vertices) requires at least 6^2/4=9 rounds. I found, by a randomised computer search, a solution with exactly 9 rounds satisfying (a) every player has sat out at least once and (b) every player has played every member of the other team exactly once. [omitted, just in case this is a homework question] $\endgroup$
    – Douglas S. Stones
    Commented Mar 3, 2010 at 5:03
  • $\begingroup$ To DSS: So a match is between 4 pairs, rather than a pair of teams of four? Gerhard "Ask Me About System Design" Paseman, 2010.03.03 $\endgroup$
    – Gerhard Paseman
    Commented Mar 3, 2010 at 18:18
  • $\begingroup$ Yes, eg. two teams of six playing in a chess tournament with four boards. I admit there can be other interpretations of this question -- this one made the most sense to me. $\endgroup$
    – Douglas S. Stones
    Commented Mar 3, 2010 at 21:42

1 Answer 1

Reset to default
2
$\begingroup$

In light of the comments, I'll post an answer. It's probably not a homework question, but it's not exactly a research-level mathematics question either. The question was:

How many match ups must occur before everyone has sat out at least once or everybody has played everybody once?

Define the two teams {1,2,3,4,5,6} and {a,b,c,d,e,f}. In a volleyball context finding a solution is easy (as Gerhard "Ask Me About System Design" Paseman pointed out) -- mathematically, it is a collection of K4,4 subgraphs whose edges cover K6,6 such as

{1,2,3,4} x {a,b,c,d}
{1,2,5,6} x {a,b,e,f}
{3,4,5,6} x {c,d,e,f}.

If we interpret the original question in a strict sense (taking the word "or" literally), then two rounds would suffice.

I had a different interpretation of the question (which is slightly less trivial) which could be of interest to a chess tournament organiser, for example (often chess teams consist of 4 players with 2 reserves). That is, finding a decomposition of K6,6 into G≅4K1,1+4K1 such that each vertex is an isolated vertex in at least one G. Since G has 4 edges and K6,6 has 62=36 edges. We deduce that we need 36/4=9 rounds (i.e. components). Here's the solution I found (via a randomised algorithm using GAP)

match-up      byes
1a 3c 4e 6b   2 5 d f
1b 2e 4c 5d   3 6 a f
1c 3e 5a 6f   2 4 b d
1d 2c 3b 6e   4 5 a f
1e 2d 5f 6a   3 4 b c
1f 2a 4b 5e   3 6 c d
2b 3f 4a 6d   1 5 c e
2f 3a 4d 5c   1 6 b e
3d 4f 5b 6c   1 2 a e

I just noticed that the byes are balanced, that is each player has a bye in three rounds.

Neither of the above interpretations uses the graph-theoretic interpretation of tournament.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .