Minimum number of players

Date: 26 Apr 2006 09:16:31
From: Zero
Subject: Minimum number of players

Hi

Is there a chart that I can get which tells me the number of minimum
players required in a tournament that would prevent any pairing
conflicts. If I am running a 4 round tournament, how many players do i
need at least to stop any possible pairing conflicts in rounds 3 & 4 ?

thanks

Date: 27 Apr 2006 14:11:42
From: Grant Perks
Subject: Re: Minimum number of players

Whenever the number of players comes close to the number of rounds in a
section there might be pairing issues. For a 4 round swiss event you
need at least 7 players to ensure that pairings aren't repeated.

There are two fairly easy ways to pair a 4 round event with 5 or 6
players and avoid the possibility of duplicate pairings. The first
method is the 1vs2, 3 vs4 system. The second method is to use 4 rounds
from the table of a 5 round Round Robin.

At a recent event I showed a fellow TD how to pair a 6 player Swiss
using the Round Robin method. Apparently he had run into duplicate
pairing the month before. In the first round we paired the players as
normal then assigned Round Robin pairing numbers. For the second and
subsequent rounds the Round Robin pairings that came the closes to what
we would have done under Swiss pairings were used.

Date: 27 Apr 2006 06:21:31
From: David J Bush
Subject: Re: Minimum number of players

On 26 Apr 2006 09:16:31 -0700, "Zero" <[email protected] > wrote:

Date: 26 Apr 2006 19:42:16
From: Zero
Subject: Re: Minimum number of players

Also assume the worst case scenario where the player with pairing#1
wins all his games. Similary the lowest rated player could be bad and
could lose all of his games. So is there a formula which can be used
to prevent this from happening again ?

Date: 26 Apr 2006 19:39:19
From: Zero
Subject: Re: Minimum number of players

CLARIFICATION:

I am asking for a Swiss system paired tournament, how many players are
necessary so that the computer will not say in the last round that it
is having "pair trouble" I have played in tournaments where the
director said that there were too many rounds for the number of
participants in the tournament. As a result, two players were paired
again by the computer.

Thanks.

Date: 27 Apr 2006 06:30:43
From: David J Bush
Subject: Re: Minimum number of players

On 26 Apr 2006 19:39:19 -0700, "Zero" <[email protected] > wrote:

Date: 27 Apr 2006 07:02:22
From: David J Bush
Subject: Re: Minimum number of players

Date: 26 Apr 2006 16:12:46
From: Tom Martinak
Subject: Re: Minimum number of players

>> I think that you have answered:
>> "What is the minimum number of players in a N-round tournament such
>> that there exists a way to pair all the rounds legally?"
>> (where by legally I mean without being forced to have two players play
>> a second time)

>> In my post, I was trying to answer the question:
>> "What is the minimum number of players in a N-round tournament such
>> that no matter which legal pairings were made in the first N-1 rounds,
>> the Nth round can still be paired legally."

>Those two questions are fully equivalent.

I don't think so. For example consider a 4-round tournament with 6
players. Since 6 >4+1, this should be OK by the 1st question and your
proof. And there is a possible tournament which is legal, i.e.:

Player Rd1 Rd2 Rd3 Rd4
1 4 2 3 5
2 5 1 6 3
3 6 4 1 2
4 1 3 5 6
5 2 6 4 1
6 3 5 2 4

Now consider this alternative legal pairings for the first 3 rounds:

Player Rd1 Rd2 Rd3
1 4 2 6
2 5 1 3
3 6 4 2
4 1 3 5
5 2 6 4
6 3 5 1

But now there is no legal pairing for the 4th round. So 6 isn't enough
for the second question.

- Tom tinak

Date: 27 Apr 2006 10:03:40
From: Ralf Callenberg
Subject: Re: Minimum number of players

27.04.2006 01:12, Tom tinak:

>> Those two questions are fully equivalent.
>
> I don't think so.

You are right. My "proof" had a hole as big as Lake Michigan.

Greetings,
Ralf

Date: 26 Apr 2006 15:14:42
From: Tom Martinak
Subject: Re: Minimum number of players

>> Is there a chart that I can get which tells me the number of minimum
>> players required in a tournament that would prevent any pairing
>> conflicts.

>Well, i would say, if you have got an uneven number of rounds, the
>minimum number of players is equal to the number of rounds. If you have
>got an even number of rounds, the minimum number of players is equal to
>the number of rounds plus one.

The correct answer is going to depend upon exactly what question he was
asking. I think that you have answered:
"What is the minimum number of players in a N-round tournament such
that there exists a way to pair all the rounds legally?"
(where by legally I mean without being forced to have two players play
a second time)

In my post, I was trying to answer the question:
"What is the minimum number of players in a N-round tournament such
that no matter which legal pairings were made in the first N-1 rounds,
the Nth round can still be paired legally."

- Tom tinak

Date: 27 Apr 2006 00:24:40
From: Ralf Callenberg
Subject: Re: Minimum number of players

27.04.2006 00:14, Tom tinak:
>> I think that you have answered:
> "What is the minimum number of players in a N-round tournament such
> that there exists a way to pair all the rounds legally?"
> (where by legally I mean without being forced to have two players play
> a second time)
>
> In my post, I was trying to answer the question:
> "What is the minimum number of players in a N-round tournament such
> that no matter which legal pairings were made in the first N-1 rounds,
> the Nth round can still be paired legally."
>

Those two claims are fully equivalent.

Greetings,
Ralf

Date: 27 Apr 2006 01:07:44
From: Ed Seedhouse
Subject: Re: Minimum number of players

On Thu, 27 Apr 2006 00:24:40 +0200, Ralf Callenberg
<[email protected] > wrote:

>27.04.2006 00:14, Tom tinak:
>>> I think that you have answered:
>> "What is the minimum number of players in a N-round tournament such
>> that there exists a way to pair all the rounds legally?"
>> (where by legally I mean without being forced to have two players play
>> a second time)

>> In my post, I was trying to answer the question:
>> "What is the minimum number of players in a N-round tournament such
>> that no matter which legal pairings were made in the first N-1 rounds,
>> the Nth round can still be paired legally."

>Those two claims are fully equivalent.

Ralph is fully correct.

Date: 27 Apr 2006 10:04:27
From: Ralf Callenberg
Subject: Re: Minimum number of players

27.04.2006 03:07, Ed Seedhouse:

> Ralph is fully correct.

No, I am completely false.

Greetings,
Ralf

Date: 27 Apr 2006 00:27:31
From: Ralf Callenberg
Subject: Re: Minimum number of players

27.04.2006 00:24, Ralf Callenberg:
> 27.04.2006 00:14, Tom tinak:
>>> I think that you have answered:
>> "What is the minimum number of players in a N-round tournament such
>> that there exists a way to pair all the rounds legally?"
>> (where by legally I mean without being forced to have two players play
>> a second time)
>>
>> In my post, I was trying to answer the question:
>> "What is the minimum number of players in a N-round tournament such
>> that no matter which legal pairings were made in the first N-1 rounds,
>> the Nth round can still be paired legally."
>>
>
> Those two claims are fully equivalent.

Correction:

Those two questions are fully equivalent.

Greetings,
Ralf

Date: 26 Apr 2006 23:59:57
From: Ralf Callenberg
Subject: Re: Minimum number of players

26.04.2006 18:16, Zero:

> Is there a chart that I can get which tells me the number of minimum
> players required in a tournament that would prevent any pairing
> conflicts.

Well, i would say, if you have got an uneven number of rounds, the
minimum number of players is equal to the number of rounds. If you have
got an even number of rounds, the minimum number of players is equal to
the number of rounds plus one.

This proof I can provide:

First I assume an even number of participants p, one of them could be
the "bye".

It is clear, that p must be at least one more than the number of rounds
r, otherwise you are guaranteed to get problems at the last round. So
this is the lower limit of the minimum.

Let's take the case of an uneven r and p=r+1. In the last round
everybody has had r-1 opponents. Which means, one possible opponent is
left over for each participant. A conflict can only arise, if this one
possible opponent is the same for two participants. This would mean,
that both did not play against this opponent, but this is not possible,
as this opponent also can have only one participant left over, he didn't
play before. So, the assumption, that there is a pairing conflict leads
to a contradiction. Which leads to the result, that there is no pairing
conflict. So, for an odd r, the minimum p is r+1. As one of the
participants can be the "bye", this proves the first half of the claim
for uneven number of rounds.

The case of even r is easy now. As p is even and must be higher than the
r, we have to look at the p = r+2. r+1 is uneven and with the result
from above we know, that for r+1 rounds the minimum p is r+2. But if we
can play r+1 rounds without pairing conflict, we can play r as well. So
the minimum p is r+2. As one can be the "bye", this proves the second
half of the claim for even number of rounds.

q.e.d.

Of course, if you are playing Swiss system, the pairings can become very
ugly, with unfortunate distribution of colors. And there is no
guarantee, that the pairing program you are using actually will find the
solution (this would be a bug of the program, but one I would expect).
As a rule of thumbs the optimum number of players for swiss pairing is
about thrice the number of rounds.

Greetings,
Ralf

Date: 26 Apr 2006 17:52:19
From: Mike Nolan
Subject: Re: Minimum number of players

"Zero" <[email protected] > writes:

>Is there a chart that I can get which tells me the number of minimum
>players required in a tournament that would prevent any pairing
>conflicts. If I am running a 4 round tournament, how many players do i
>need at least to stop any possible pairing conflicts in rounds 3 & 4 ?

What do you define as a 'pairing conflict'?

2^N, where N is the number of rounds, will tell you how many rounds it
takes to ensure that no more than one player can go undefeated. For
example, if there are 16 players then you need four rounds, but if there
are 17 players you need five rounds.

However, it is still possible for two players to tie for first place (if
both of them have at least one draw) or for there to be other pairing issues
that will cause you to use something other than the 'natural' pairing, such
as an odd number of players in a score group or a score group consisting
of just two players who have already faced each other.

With careful planning, as long as the number of rounds is at least one
less than the total number of players (eg, a quad is three rounds long),
it is possible to ensure that no two players face each other more than
once, but it takes some forethought in pairing the middle rounds and
some players will wind up being paired outside of their score group,
sometimes WAY outside of it.
--
Mike Nolan

Date: 27 Apr 2006 01:06:14
From: Ed Seedhouse
Subject: Re: Minimum number of players

On 26 Apr 2006 17:52:19 GMT, [email protected] (Mike Nolan) wrote:

>"Zero" <[email protected]> writes:

>>Is there a chart that I can get which tells me the number of minimum
>>players required in a tournament that would prevent any pairing
>>conflicts. If I am running a 4 round tournament, how many players do i
>>need at least to stop any possible pairing conflicts in rounds 3 & 4 ?

>What do you define as a 'pairing conflict'?

>2^N, where N is the number of rounds, will tell you how many rounds it
>takes to ensure that no more than one player can go undefeated. For
>example, if there are 16 players then you need four rounds, but if there
>are 17 players you need five rounds.

>However, it is still possible for two players to tie for first place

You are adding a condition. The original question (above) said nothing
about being sure of a unique winner.

Date: 26 Apr 2006 10:21:03
From: Tom Martinak
Subject: Re: Minimum number of players

> Is there a chart that I can get which tells me the number of minimum
> players required in a tournament that would prevent any pairing
> conflicts. If I am running a 4 round tournament, how many players do i
> need at least to stop any possible pairing conflicts in rounds 3 & 4 ?

The worst case occurs when the field gets divided into two groups -
each member of which played all the members of the opposing groups.
When these groups have an odd number of players, then the next round
cannot be paired without having someone play an opponent that they have
already played..

For example:

4 rounds - 6 players
In the first 3 rounds A1, A2, and A3 have played B1, B2 and B3. Now you
can take a pair from group A and group B, but you'll have one left
player from each group - and they have already played.

If you watch the 3rd round pairings you can prevent this problem in the
4th round, but I don't think that the computer pairing programs check
for it.

For any odd N, this problem occurs, when there are 2N players and N+1
rounds.

Rounds # of players
2 2
4 6
6 10
...

Having more players than this will leave you OK. So for your 4 round
event, 8 players will leave you safe (or even 7, though then all the
byes cause other problems).

I've never looked at the issue for tournaments with odd numbers of
rounds.

- Tom tinak

Date: 26 Apr 2006 09:43:46
From:
Subject: Re: Minimum number of players

Raise 2 to the power of the number of rounds. For example, in a four
round tournament, 16 players are required.

Regards,
Mike Petersen

Date: 26 Apr 2006 17:14:17
From: bruno de baenst
Subject: Re: Minimum number of players

<[email protected] > schreef in bericht
news:[email protected]...
> Raise 2 to the power of the number of rounds. For example, in a four
> round tournament, 16 players are required.
>
> Regards,
> Mike Petersen

2 to the power of the number of rounds doesn't give the minimum number of
players but the maximum.
16 players is the maximum number of players for which you can be sure that a
player with a 100% score will be the sole winner of a 4 round tourney.

Date: 27 Apr 2006 01:04:28
From: Ed Seedhouse
Subject: Re: Minimum number of players

On Wed, 26 Apr 2006 17:14:17 GMT, "bruno de baenst"
<[email protected] > wrote:

>2 to the power of the number of rounds doesn't give the minimum number of
>players but the maximum.
>16 players is the maximum number of players for which you can be sure that a
>player with a 100% score will be the sole winner of a 4 round tourney.

No, it is the minimum, given a knockout tournament format.

Date: 27 Apr 2006 10:43:52
From: bruno de baenst
Subject: Re: Minimum number of players

"Ed Seedhouse" <[email protected] > schreef in bericht
news:[email protected]...
> On Wed, 26 Apr 2006 17:14:17 GMT, "bruno de baenst"
> <[email protected]> wrote:
>
>>2 to the power of the number of rounds doesn't give the minimum number of
>>players but the maximum.
>>16 players is the maximum number of players for which you can be sure that
>>a
>>player with a 100% score will be the sole winner of a 4 round tourney.
>
> No, it is the minimum, given a knockout tournament format.

Wrong, it's also the maximum for a knockout tournament. But it's not the
minimum as you can easily have less players, then you'll just have to seed
some players immediately in round 2.