Author: José de Jesús García Ruvalcaba
Date: 04:01:00 06/09/04
Go up one level in this thread
On June 09, 2004 at 05:36:44, Peter Berger wrote: >On June 09, 2004 at 03:54:25, Mark Winands wrote: > >>2. The tournament will be an 11-round Swiss-system event, using standard >>(non-accelerated) Swiss pairings. The provisional playing schedule was given on >>page 293 of the December issue. > >In case there were only 13 participants I wonder if it would really be possible >to do legal Swiss pairings for 11 rounds - probably not. > Actually 14 participants is more difficult than 13. In any case, since a player can not get a bye twice, there is no essential difference for this purpose. >Someone sent me an interesting thought experiment some time ago. > >Assume a Swiss event with six players, A-F - A is the highest seed. > >1st round: > >A-D 1-0 >E-B 0-1 >C-F 0-1 > >2nd round: > >A is paired first, F gets downfloat and has already played C, thus: > >B-A 1/2 >F-E 1/2 >D-C 1/2 > >Standings: > >A:1.5 (WB) >B:1.5 (BW) >F:1.5 (BW,d) >C:0.5 (WB) >D:0.5 (BW) >E:0.5 (WB,u) > >F already had downfloat, so it's B's turn. A gets F, B gets C, so: > >3rd round: > >A-F >C-B >E-D > >Whatever the results of the 3 round now, there are no legal pairings for round >4. > >It is possible that there is some mistake in the above, but I don't think the >principal problem can be avoided. > >Peter Let me see, with 14 players and 11 rounds there are two rounds to few to make it a round robin. So, before the last round each player has only three posible opponents. Lets define a graph. Its vertices are the players of the tournament (with bye included as a "player"), and its arcs are between players wich have not played each other in the first 10 rounds. Since each vertex has exactly three neighbours, it is called a 3-regular graph. The problem is to find a pairing (hehehe, this concept is also defined in graph theory, and means exactly what we need here), and you pointed out that there might be no pairing. Let me generalise the problem, we have a 3-regular simple graph (simple means no loops and no parallel arcs, and 3-regular implies also that the number of vertices is even and at least four), lets find a pairing. I have not studied graph theory in a long time, but since the concept of regular graph is quite common and pairing problems are classical, I expect this problem to be already solved. I somewhat suspect that under those conditions there is always a pairing, just give me some time to check a few books. José.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.