# Looking for a problem...

I'm trying to find out if the following problem is already well-known in computer science...

Consider 2×Npoliticians andNTV channels. We would like to compute a schedule forNtime slots such that:

- During each time slot, each TV channel broadcasts a live debate featuring exactly two politicians. This means that for each time slot, each politician appears on exactly one channel.
- At the end of the
Nslots, each politician has appeared on all channels. This means that for each politician, each channel is scheduled to exactly one time slot.- No couple of politicians debated more than once. In other words, over all the debates which took place, each featured a different couple of politicians. [Notice that, since there are 2×
Nchoose 2 couples of politicians and onlyN×Ndebates (one debate on each of theNchannels for every of theNtime slots), some couples of politicians will never debate.]

This problem is quite simple and has occurred at least once in
practice (thanks Yannick!), so I'm wondering if it has already been
studied. Maybe it *is* well-known, but under some weird name
("Martian elimination problem"? "Yannick's mother's problem"?), or maybe
it is just a special case of some well-known generic problem. (I tried
to find a simple graph-theoretic formulation, for instance, but
failed.)

Actually, it seems that this is very similar to Kirkman's
schoolgirl problem and the Social Golfer problem: to be
more precise, I think that my problem is the social golfer problem for
*g* = *N*, *s* = 2 and *w* = *N*.

In the meantime, since I wanted to find out if some solutions exist
(and, if yes, what do they look like), I wrote a crappy C program to
find solutions using backtracking. It turns out that this simple
strategy finds solutions for *N* < 11 (apart from the special
case with *N* = 2). For larger values of *N*, no solutions
are found in a reasonable amount of time (though one would expect
solutions to exist).

Here is one possible solution for *N* = 8. Each line is a time
slot, each column is a politician, and the values in the cells are the
channel on which each politician appears at each time slot. There may be
a simple pattern, but I can't see it.

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 2 0 2 0 1 4 5 3 5 6 7 3 7 4 6 2 1 2 0 1 0 5 4 5 7 3 6 7 3 6 4 3 4 4 5 5 6 0 1 7 6 7 0 1 2 3 2 4 3 5 6 7 3 1 7 6 0 0 2 2 4 5 1 5 6 7 3 4 7 2 6 0 1 2 3 4 1 0 5 6 7 3 4 6 5 7 0 1 2 4 1 5 0 2 3 7 5 6 7 3 4 6 2 2 3 1 4 0 5 1 0

It would be quite funny to generate incomplete solutions to the problem (that is, grids with some cells left empty, for which we know that they can be legally completed in only one way). You would probably get something akin to sudoku...

A similar problem is discussed here (in French); search for "Quelqu'un qui assistait à cette réunion".