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

Consider 2×N politicians and N TV channels. We would like to compute a schedule for N time 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 N slots, 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×N choose 2 couples of politicians and only N×N debates (one debate on each of the N channels for every of the N time 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".