3
$\begingroup$

As a member of boy scouts I was considering the following problem:
suppose you're organising some kind of olympic games...
*You divide the boys in $2n$ teams (subsets of equal size)
*There are $2n-1$ types of sports which all involve two-team matches
*There will be $2n-1$ time slots: during every time slot every team will play one of the sports in a match against one other team.
*Constraint 1: Every sport can be played by only two teams simultaneously.
*Constraint 2: At the end, every team must have played each type of sport.
*Constraint 3: At the end, every team must have faced all other teams in one match.

The problem is trivially solved for $n=1$, but one can easily check that it cannot be solved for $n=2$ and I have some confidence that neither it can be solved for $n=3$.

Is this problem only solvable for $n=1$?

Is, however, the variant of...

*$2n$ teams, $2n$ sports and $2n$ time slots.
*constraint 1 unchanged
*constraint 2 unchanged
*constraint 3 being relaxed to: "At the end, every team must have faced all other teams in at least one match"

...solvable for all $n \neq 2$ (I have found a solution for $n=1, 3, 4, 5$ but since writing them down is a lengthy business, I'll not give them here unless someone's really interested)?
If so, can you give details of a constructive method to find a solution for a particular $n$?

Improve this question
$\endgroup$
3
  • $\begingroup$ Keyphrases: combinatorial designs, graeco-latin square. $\endgroup$
    – Gerry Myerson
    Commented May 14, 2013 at 13:16
  • $\begingroup$ Your original problem does sound solvable to me (essentially, you need a $(2n-1)$-edge coloring of $K_{2n}$). Is there an additional constraint (e.g. only one match of each sport per round)? $\endgroup$
    – Klaus Draeger
    Commented May 14, 2013 at 13:24
  • $\begingroup$ Indeed, I had this extra constraint in mind. I've edited the question. Thanks $\endgroup$
    – 5th decile
    Commented May 14, 2013 at 13:41

1 Answer 1

Reset to default
5
$\begingroup$

Problem 1 is just asking for a Room square of size 2n-1. On the Wikipedia page for Room squares or in Anderson's book "Combinatorial designs and tournaments", for example, you'll find that the cases n=2,3 are the only ones for which construction is impossible.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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