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
    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
    May 14, 2013 at 13:24
  • $\begingroup$ Indeed, I had this extra constraint in mind. I've edited the question. Thanks $\endgroup$
    – 5th decile
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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