note
blokhead
<b>Update 2:</b> The first half of this post was found to be wrong, and lived inside <strike> tags for a long time. Now it's in HTML comments..
<!
<hr>
<blockquote><strike>
<b>It <i>is</i> possible for nonpowers of two</b>, even with everyone playing each round and no duplicate matches.
<p>
Here's one way to think about the problem. It doesn't get you much closer to a programmatic solution, but it might prove useful for analysis. Maybe someone around here will recognize this as an instance of some combinatorial algorithm problem..
<p>
If you have n players, P1 through Pn, make an n*n matrix. Each entry a(i,j) in the matrix should tell in which round Pi plays Pj. We have a few restrictions as well: the main diagonal should be empty since a player doesn't play himself. And the matrix must be symmetric across the main diagonal (in other words, a(i,j) = a(j,i)). We get a "valid" solution when all the rows and columns have no repeats (that means no player has two matches in the same round).
<p>
Here's an example solution for n=6. I did this one on a sheet of paper.
<code>
P1 P2 P3 P4 P5 P6
P1 1 2 3 4 5
P2 1 4 5 3 2
P3 2 4 1 5 3
P4 3 5 1 2 4
P5 4 3 5 2 1
P6 5 2 3 4 1
</code>
From the matrix, we can see that our rounds are:
<code>
Rd 1: (P1,P2), (P3,P4), (P5, P6)
Rd 2: (P1,P3), (P2,P6), (P4, P5)
Rd 3: (P1,P4), (P2,P5), (P3, P6)
Rd 4: (P1,P5), (P2,P3), (P4, P6)
Rd 5: (P1,P6), (P2,P4), (P3, P5)
</code>
There's no strong pattern that jumps out at me, and this feels very much like the Nqueens problem. It's quite possible that this problem is NPcomplete. You may have to use brute force.
<p>
By symmetry, certainly the top row of the matrix can be (1,..,n1) every time. And because of the symmetry of the matrix, you only need to brute force the entries of the upperright triangle.
For small values of n, this might not be an unreasonable approach.
<p>
It would be cooler, though, to write a crazy regex to solve this problem for you, à la [AbigalIIAbigail] <tt>;)</tt>
<p>
<b>Update 1:</b> There are always n/2 matches per round, which means each round number must appear n/2 times in the upperright triangle of the matrix. If you have already distributed (1,..,n1) to the top row, and are trying to fill in the rest of the upperright triangle, you have to place exactly ((n/2)1) more copies of each number. So the number of distinguishable ways to fill in these squares is:
<code>
factorial[ ((n/2)1) * (n1) ] / [ factorial((n/2)1) ]^(n1)
</codE>
It's exponential in n! (And who said that combinatorics class wouldn't pay off?) I can't see any way of avoiding the need to check <i>all</i> of these arrangements. This is a pretty interesting problem. Maybe when I have some free time on my hands I'll try to make the regex engine solve it <tt>;)</tt>
<p>
<font size=1>(also fixed a typo in transcribing my matrix and list of rounds ... and fixed my formula)</font>
</blockquote>
>
<hr>
<b>Update 2:</b> Wouldn't you know it, in combinatorics class today we actually discussed this exact problem. It has an analogous problem in graph theory dealing with edgecolorings of complete graphs. In any case, the solution is certainly not NPcomplete, and the algorithm is very simple with a visual explanation..
<p>
Make a circle out of the competitors, except put one player in the middle. For each round, match up the middle guy with someone, then match up the other ones in a symmetric. It's easier to understand what I mean by "symmetric" with a picture, so here's an example with n=8:
<code>
Round 1:
match 8 with 1, then pair up the rest
symmetric to that line..
1

72
8
63
54
Round 2:
match 8 with 2, then pair up the rest
symmetric to the line..
1
7 \ 2
\ \^
\ 8^ \
6 \ 3
\ \
\ \
5 4
Round X: ... keep rotating around the circle, etc
</codE>
You obviously never get duplicates with the person you put in the middle. But you will also never get duplicates with the other people in the circle, because there are an odd number of them to pair up. You won't get duplicates until you've rotated all the way around.
<p>
Doing this in code is pretty easy:
<code>
my @players = qw/Frodo Sam Merry Pippin Strider Gandalf Legolas Gimli/;
########
my $num = @players;
die "must have even number of players" if $num % 2;
for my $partner (0 .. $num2) {
print "Round #" . ($partner + 1) . ":\n";
print " $players[1] vs $players[$partner]\n";
for my $pair (1 .. ($num2)/2) {
my $p1 = ($partner  $pair) % ($num  1);
my $p2 = ($partner + $pair) % ($num  1);
print " $players[$p1] vs $players[$p2]\n";
}
}
</code>
Yay combinatorics class!
<div class="pmsig"><div class="pmsig137386">
<p>
blokhead
</div></div>
301061
301061