From: philmac@dip.eecs.umich.edu (Philip MacKenzie) Subject: Tennis Tournament Problem - Solutions for 12 and 4(2^k) players Date: Tue, 2 Jun 1992 18:06:35 GMT Newsgroups: comp.theory,sci.math Summary: [missing] Keywords: Tournament design algorithms (round-robin, multi-person teams) Thanks to those who responded to my tennis tournament problem! Jaroslaw Tomasz Wroblewski has come up with a solution to the 12 players problem which might be useful for more players. Gene Ressler seems to have a method which can be used to solve the problem for 4(2^k) players. Also thanks to Jim Roche for his posting which lists some references which solve some related problems, and might be useful for solving this problem. I've appended here the original problem and the two partial solutions which were mailed to me: ----------- TENNIS TOURNAMENT PROBLEM: 4n tennis players want to design a doubles tournament as follows: 1. Each round of the tournament has n games. Thus every player plays in every round. 2. Each player must have each other player as a partner exactly once. 3. Each player must play against each other player exactly twice. It is obvious that there must be 4n-1 rounds to the tournament. The solution for 4 players is trivial, and a backtracking algorithm will solve the problem for 8 players in a reasonable amount of time. 4 players [Format: (ab cd) == (a,b) versus (c,d)] (12 34) (13 24) (14 23) 8 players (12 34) (56 78) (13 57) (24 68) (14 58) (23 67) (15 26) (37 48) (16 38) (25 47) (17 46) (28 35) (18 27) (36 45) What I'm looking for is a general solution, or at least a solution for 12 players, if one exists. I would appreciate any help on this problem, or pointers to references. Thanks, Phil ---------- From: "Jaroslaw Tomasz Wroblewski" Date: Mon, 1 Jun 92 15:02:05 EDT To: philmac@dip.eecs.umich.edu Subject: Re: Tennis Tournament Problem By trial and error I seem to have found a solution to 12 players problem. Please check it if you can, feel free to post it if you want to. 1 2 4 9 6 10 8 11 7 YOU 3 5 During the first round you are playing with player #7 against the pair 4,9. You will keep your spot through all the tournament, other players will change place cyclicly each round (#n goes to place left by #n+1, with #11 following #1). How did I do it? Number players 1 through 11 (you are special, you do not need a number) 1. Try to form pairs in such a way that in 5 pairs except your each number 1 through 5 is exactly once a difference of numbers of players - think of a difference as being the distance of numbers mod 11 : eg 9-11=2 , 10-2=3 etc. This can be done in a few ways, not all of them will allow step 2. 2. Couple pairs in such a way that each number 1 through 5 appears twice as the difference of players facing each other from the opposite sides ( again - you do not count, but your partner does). I see no clever way to satisfy 1 and 2 at the moment except for checking all possibilities 1 by 1. However I believe finding a solution for 16 players should be long but a finite job. Going further this way may be tricky. Best regards, Jarek PS. As this method gives you automaticaly schedule of the whole tournament once you set up the first round correctly, you may find solution for 8 players without using computer. -------- ************************************************ The first rounds that work for 4 and 8 are: 1 2 3 You -and- 1 2 4 7 3 5 6 You -Phil ************************************************ ---------------- From ressler@cs.cornell.edu Tue Jun 2 13:48:07 1992 Date: Mon, 1 Jun 92 15:36:01 -0400 From: ressler@cs.cornell.edu (Gene Ressler) To: philmac@zip.eecs.umich.edu Subject: Re: [ressler@cs.cornell.edu: Re: Tennis Tournament Problem] for n=1, consider the court during the first game 1 2 --- <- net :-) 3 4 Now get the other rounds by rotating 2,3,4 to the left. This has to work because 1 is adjacent to each player exacly once and opposite each player exactly twice. Similar reasoning applies to each other planer. Ok, now consider n=2 1 2 5 6 --- --- 3 4 7 8 To get each successive rounds now, first rotate _both_ games as we did above (in the permutations I sent you, I forgot to do the small rotation on the rhs), then do the ``inductive rotation'' of positions (3 4) to (5 6), (5 6) to (7 8), (7 8) to (3 4). This is using the diagram above, not the new locations of the players after the `small' rotations. Note this goes in the direction opposite to the one above, and this is necessary. Don't ask me why. Finally, for n=4, we have 1 2 5 6 9 10 13 14 --- --- ----- ----- 3 4 7 8 11 12 15 16 To get successive rounds, first rotate all 4 games as for n=1, then both the lhs 2 games and rhs 2 games as we did above, and finally positions (3 4 7 8) to (9 10 13 14), (9 10 13 14) to (11 12 15 16), and (11 12 15 16) to (3 4 7 8). Note this is the same rotation direction as above. I have a very hazy intuitive feel for why these work, but no real understanding. I'm speculating that if you go to 32 games and inductively rotate in groups of 8 (to the right?) in the final step, this will also give a solution. < time out > Ok, I did it. I got a solution for 32 games by rotating right-left-right-left at the four levels. Wierd, because only right-left-left or left-right-right works for 16 games, not right-left-right. Time to step back and think in the abstract. The reason I turned to permutation groups was that it seemed if you could express each constraint somehow (or perhaps all the constrains for given n) using them, then you might be able to `solve' for a single permutation that meets all the constraints by taking products. This seems to be roughly what's going on. We're concatenating groups wherein 3/4's of the elements are in 3-orbits and 1/4 is are in 1-orbits. I believe the geometry of the orbits encodes the constraints somehow. Again, this is a huge intuitive leap. A real group theory whiz (which I am not) would probably love this. Gene ============================================================================== From: roche@isl.Stanford.EDU (james r. roche) Subject: Re: Tennis Tournament Problem Date: Tue, 2 Jun 92 15:08:38 GMT Newsgroups: comp.theory,sci.math In article <1992May31.014754.27929@zip.eecs.umich.edu> philmac@dip.eecs.umich.edu (Philip MacKenzie) writes: >I have been quite frustrated trying to solve the following problem. >It is an easily stated problem, so I would assume someone has >already studied it. Unfortunately, I can't seem to find any references. > >TENNIS TOURNAMENT PROBLEM: [quote of original message trimmed --djr] I don't know whether this exact problem problem has been addressed, but you might try the following reference: R. D. Baker, "Whist Tournaments," _Congressus Num._ (1975), 89-100. If that paper doesn't address the problem, you can probably still get an answer for n = 12 by finding a known construction for an RBIBD(12,33,11,4,3) (I'll define this in a moment) and then doing a computer search for the (much simpler) problem that remains. Now for the definition: The RBIBD mentioned above is a Resolvable Balanced Incomplete Block Design with 12 points. (The 12 points represent the 12 players.) These 12 points are to be taken 4 at a time to form blocks. (Each block of 4 points represents the 4 players on a given court at any given time.) There should be 33 blocks in all, and each pair of points should occur together in exactly 3 blocks. (This is because any given pair of players should appear on the same court together exactly 3 times, once as partners and twice as opponents. This condition is necessary, but not sufficient, for your problem. It will turn out, then, that your problem is at least as hard as constructing the RBIBD currently being described, but then you'll also have to split each block of 4 points into 2 blocks of 2 points each such that your conditions hold.) Finishing up the definition, we need to have each point occur in exactly 11 different blocks (of 4). (This corresponds to the number of rounds in the tournament.) Finally, the blocks must partition the 12 points in such a way that groups of 12/4 blocks can be formed with each group containing each point exactly once. (This last condition is the condition that the BIBD be _resolvable_. In your case, it corresponds to the condition that the tournament can be formed such that there are no byes. Incidentally, if it turns out that you can't find a solution to your problem, you might want to allow byes. In this case, you just need a BIBD with the 5 parameters above, and there are more known BIBDs than RBIBDs.) Assuming for the moment that you can find an explicit construction for an RBIBD with the parameters above, then you have a candidate for computer search. You just have to split each of the 33 blocks of 4 into 2 blocks of 2 players each so that each pair of points occurs together exactly once. (Once you've fulfilled this condition, it will automatically follow that each player also faces every other player exactly twice.) An absolutely knuckleheaded search would require trying 3^33 ~ 5x10^15 possibilities, but I'm sure that with a little cleverness you can reduce the number of possibilities to something feasible. Now the question is, where can you find an RBIBD(12,33,11,4,3). In the book _Algorithms in Combinatorial Design Theory_ (Vol. 26 of the Annals of Discrete Mathematics), edited by C.J. Colbourn and M.J. Colbourn, there's a huge table of BIBDs on pp. 275-308 in the article written by Mathon and Rosa. According to the table, there are at least 32 essentially different known BIBDs with your parameters and at least 1 RBIBD. You might be able to find an explicit construction either in one of the references cited in that article or in the following paper: R.L. Constable, "Some nonisomorphic solutions for the BIBD(12,33,11,4,3)," _Utilitas Math._ 15 (1979). 323-333. You might also look at the book _Combinatorial Designs and Applications_, edited by Wallis, Shen, Wei, and Zhu. There's an article in there on pp. 109-118 by SHEN Hao and WU Minzhen [family names capitalized] titled "Existence of Simple Resolvable Block Designs with Block Size 4." They discuss the existence of an "RS_{3}(2,4,v)" for various values of v. This problem is the same as the RBIBD problem above in which there are v players in all, not necessarily 12. According to these authors, a "simple" RS_{3}(2,4,v) exists whenever v is a multiple of 4, except possibly when v = 44 or 284. A _simple_ RS(...) is one in which no block of 4 is repeated. (In your problem, this means that any given set of 4 players appears together on the same court at most once.) However, even if you can find an explicit construction for the simple RS(...), you'll still have to do a computer search to figure out how to split each block of 4 into 2 blocks of 2. There's no guarantee that you'll be able to find a solution to your problem using the ideas above, because it may be that the handful of known BIBDs with the right parameters don't yield solutions to your problem when the blocks of 4 are split into blocks of 2. However, it seems to me that the above approach is the only one that gives you any realistic chance of finding a solution. If none of the known BIBDs works, this means that any solution to your problem would automatically generate a new BIBD not already found by someone who's devoted his life to finding such things. Finally, I'll note that it might be possible to prove that a solution exists for your problem for a given n even though it might be hard to find an explicit construction. My impression, though, is that you actually want to construct a tournament. Good luck! -- Jim Roche roche@isl.stanford.edu roche@research.att.com ============================================================================== From: rex@cq-pan.cqu.edu.au (Rex Boggs) Subject: Summary: Tennis Tournament Problem Date: 11 Feb 1995 23:02:50 GMT Newsgroups: sci.math,rec.puzzles Summary of Doubles Tennis Tournament Problem I recently posted the problem below about setting up a doubles tennis tournament. The original post, and the answers that I have received are included in this message. I have found the discussion to be very informative. Thanks to those who have responded. ******** [Original Post] This is a fair-dinkum question - ie a real-life problem. A friend teaching at the International School in Jakarta, Indonesia sent it a few days ago. I have solved it by trial and error, but with two blemishes. Any help here? Cheers Rex (rex@cq-pan.cqu.edu.au) ****** G'day Rex, Got a math problem for ya. The tennis coach approached me and wanted to know if it was possible to set up a doubles tournament with 8 people, such that each person played 7 games, partnering with each other person only once and meeting every person twice as opponents. eg: AB plays CD. Therefore A will play against C once and only once more when C is somebody else's partner. Over to you... Dave Tarcy ~~~~~ [Solutions] From: "Don Coppersmith (914-945-2288)" Name your players 0,1,2,3,4,5,6,X 0 1 vs 3 X 4 6 vs 2 5 on day 1 1 2 vs 4 X 5 0 vs 3 6 on day 2 2 3 vs 5 X 6 1 vs 4 0 3 4 vs 6 X 0 2 vs 5 1 4 5 vs 0 X 1 3 vs 6 2 5 6 vs 1 X 2 4 vs 0 3 6 0 vs 2 X 3 5 vs 1 4 on day 7 The literature to look for is called "combinatorial designs". Don Coppersmith ~~~~~ From: "Douglas Zare (NC)" The motivation for the following construction is the Fano plane, or the projective plane over Z2. Let the players be labelled 0,1,2,3,4,5,6, and oo. Arithmetic, as used below, is mod 7. Let the games in round 0 be (oo,0) vs (1,3) and (4,5) vs (2,6). Let the games in round 1 be (oo,1) vs (2,4) and (5,6) vs (3,0). Let the games in round i be (oo,i) vs (1+i,3+i) and (4+i,5+i) vs (2+i,6+i). Then it is not difficult to verify that the conditions are met. This is clearly a special case of an algebraic solution to a design problem. I do not know what that is, but I will ask Wilson tomorrow. Douglas Zare zare@cco.caltech.edu ~~~~~ From: wolk@ccm.UManitoba.CA (Barry Wolk) Write AB-CD to mean partners A and B play against partners C and D. Here is a schedule for N=8 players. Round number: 1 2 3 4 5 6 7 First court: 87-32 81-43 82-54 83-65 84-76 85-17 86-21 Second court: 64-51 75-62 16-73 27-14 31-25 42-36 53-47 For N=12 players, call them 1 2 3 4 5 6 7 8 9 A B C. A similar schedule is 1 2 3 4 5 6 7 8 9 10 11 CB-75 C1-86 C2-97 C3-A8 C4-B9 C5-1A C6-2B C7-31 C8-42 C9-53 CA-64 23-A4 34-B5 45-16 56-27 67-38 78-49 89-5A 9A-6B AB-71 B1-82 12-93 69-81 7A-92 8B-A3 91-B4 A2-15 B3-26 14-37 25-48 36-59 47-6A 58-7B A mathematical note: the numbers in the first round are given in this particular order for a reason. For 8 players, look at consecutive powers of 3 (mod 7). For 12 players, look at consecutive powers of 7 (mod 11). This idea does not generalise to 20 players. For small values of N, this is a puzzle. For larger values, this is a serious problem in combinatorial mathematics. I'm sure some work has been done on it, but I do not know of any general results. Barry Wolk Dept of Mathematics University of Manitoba, Winnipeg Manitoba Canada ~~~~ [I had trouble understanding how the powers of 3 (mod 7) fit in. Frank Bernhart has set me well along the path] From: frb6006@cs.rit.edu (Frank R Bernhart) Subject: Doubles in tennis I have looked at the answers provided by Zare, Coppersmith, and Wolk. The Zare scheme is virtually the same as Copp. except that he uses oo (meant to be infinity) where Z. uses X. Ironically, overprint oo with X would actually look right! Modulo 7 means to replace natural numbers 0 1 2 3 4 5 6 7 8 9 ... 20 21 22 23 .. with 0 1 2 3 4 5 6 0 1 2 ... 6 0 1 2 .. so that any multiple of seven counts as zero. (Think of a clock for a seven hour day) The FANO block (or plane, or design) is a set of seven points organised into seven lines of three points each, three lines through each point. It is the smallest non-trivial (= interesting) finite projective plane: (a) Two pts. determine a line (b) two lines determine a point. To picture the Fano block, draw a roughly equilateral triangle. Mark the three corners, and a point inside in the middle. Join the inner point to each triangle corner, and extend the line to meet the opposite side in a point. This gives you seven points, and six of the lines. The seventh line cannot be drawn straight, but the three points lie on a circle which can be sketched. Can you find them?? Taking the Fano block as a design, which is more general than a finite proj. plane, it can be used in certain block design constructions, hence the plans provided by Copp. and Z. Finite projective planes can often be turned into finite fields. The use of 3^m mod seven is related to this kind of arithmetic. Multiply 1 by three repeatedly: 1, 3, 9 == (congruent to) 9-7 = 2, 6, 18 == 18-7-7 = 4, 12 == 12-7 = 5, 15 == 15-7-7 = 1 (and we repeat all over) In other words, the powers 3^m mod 7 are 1,3,2,6,4,5, 1,3,2,... Take the sequence of four out of this: 6,4,5,1. Now increment, mod 7 by one: 0,5,6,2 And again 1,6,0,3 continuing 1,6,0,3; 2,0,1,4; 3,1,2,5; 4,2,3,6 5,3,4,0; bringing us back to 6,4,5,1. The point is, that since 0,..,6 mod seven is a field, a bit of field linear algebra applied to 3^m+i, 3^(m+1)+i,.. can be used to show that if we take 6,4,5,1 as a doubles pairing 64 vs 51, and so on with the rest, that no one meets an opponent more than once, or has a partner more than once. Now we bring in the last player 8. Take our first day grouping 64 vs 51. This leaves the other four 8237. Since partnerships 72, 73 have been scheduled already, we must pair 78, and thus 23 for the other court. The rest of the schedule is similarly set up. Does this help? Frank R. Bernhart ============================================================================== From: pkstoc@cs.wm.edu (Paul Stockmeyer) Subject: A Tournament Problem Date: 1995/05/24 Newsgroups: sci.math About a month ago, someone posted a request for a tournament schedule for bridge, doubles tennis, or whatever, for 12 people, where each pair of participants would compete as partners exactly once, and as opponents exactly twice. Several people posted fallacious proofs that no such schedule was possible, but I never saw a correct posting. The following schedule satisfies the requirements. It consists of 11 rounds, with each round containing 3 matches and involving all 12 participants. [ab | ce] [hi | kd] [jg | lf] [ac | df] [ij | le] [kh | bg] [ad | eg] [jk | bf] [li | ch] [ae | fh] [kl | cg] [bj | di] [af | gi] [lb | dh] [ck | ej] [ag | hj] [bc | ei] [dl | fk] [ah | ik] [cd | fj] [eb | gl] [ai | jl] [de | gk] [fc | hb] [aj | kb] [ef | hl] [gd | ic] [ak | lc] [fg | ib] [he | jd] [al | bd] [gh | jc] [if | ke] This schedule is based on a balanced incomplete block design with v = 12, b = 33, r = 11, k = 4, and lambda = 3. Similar block designs exit for v = 4n, b = 4n^2-n, r = 4n-1, k = 4, and lambda = 3, for all positive n. See, for example, Marshall Hall's book "Combinatorial Theory". PKS ============================================================================== From: ppang@cris.com Subject: Combinatorial Problem, Round Robin Pairings involving Competitive Team Events Date: 1996/02/11 Newsgroups: sci.stat.math,sci.stat.edu,sci.stat.consult I am trying to develop round robin pairing schedules for team type competitions that is fair for all participants. The schedule must be such that every player is paired with every other player once and ompete against every other player twice. For example, in the simplest case we have four players called 1, 2, 3, & 4. The pairings are as follows: Round 1 -- 1 and 2 plays against 3 and 4; Round 2 -- 1 and 3 plays against 2 and 4; Round 3 -- 1 and 4 plays against 2 and 3. In a 8 players situation, we have: Round 1 -- 1 and 2 vs 3 and 4 5 and 6 vs 7 and 8 Round 2 -- 1 and 3 vs 5 and 7 2 and 4 vs 6 and 8 Round 3 -- 1 and 4 vs 5 and 8 2 and 3 vs 6 and 7 Round 4 -- 1 and 5 vs 2 and 6 3 and 7 vs 4 and 8 Round 5 -- 1 and 6 vs 3 and 8 2 and 5 vs 4 and 7 Round 6 -- 1 and 7 vs 4 and 6 2 and 8 vs 3 and 5 Round 7 -- 1 and 8 vs 2 and 7 3 and 6 vs 4 and 5 This type of scheduling is ideal for just about any social competition involving foursomes whether it's in sports or card games. It ensures that everybody experience the same levels of competition, balances the playing field, and requires true teamwork to get the desired results. Doubles tennis and Bridge are good examples where this format can enhance the enjoyment of the competitive spirit in a social environment. In my research on the subject, I have learned that a category called "balanced incomplete block design" under the field of Statistics deals with these types of problems. I, however, have not been able to translate the materials found in books to the real-life problem discribed above. I used brute force trial and error methods to develop schedules for 4, 8, & 16 players. Each schedule calls for n - 1 rounds of competition where n is the number of players. This allows for every player to be teamed up with every other player once and compete against every other player twice. I would like schedules for 12, 20, 24, 28, and 32. Better yet, I would like to know of a systematic way to generate schedules for any multiple of four players. Any help anybody can provide would be much appreciated. Thanks. Please email at ppang@cris.com if you have any ideas or can help. ============================================================================== From: Dave Jones Subject: Re: Combinatorial Problem, Round Robin Pairings involving Competitive Team Events Date: 1996/02/14 Newsgroups: sci.stat.math,sci.stat.edu,sci.stat.consult For practical solutions, try contacting the national bridge league -- ACBL or something like that. What you describe is called an "individual" tournament, as opposed to a "pairs" tournament. Back when I played bridge a couple of decades ago, such contests were relative rarities, but I think the "movements" were all worked out. Some movements were named after tournament directors. I remember "Spider's web" was one of them. The league can probably supply you with a director's kit of some kind, for a price of course. Dave ============================================================================== From: wevrick@qucis.queensu.ca (Dan Wevrick) Subject: Re: Tournament Tables Date: 1996/08/04 Newsgroups: sci.math In article <4tt8ei$7bk@nps.navy.mil>, Laura Lamar wrote: > I have an interesting problem that I have been presented with. > > Twenty golfers are participating in a tournament. They are split into > five foursomes for each round. No golfer can golf with another player > with whom he has already golfed in a previous round. > > How many rounds must be played before the above rule is violated? Suppose you have r rounds. In each round there are 5 groups of 4 contributing 5 * "4 choose 2" = 30 pairs. Thus in the r rounds, there are 30*r pairings. There are a total of "20 choose 2" = 190 pairing of the 20 players. Hence, if you want all the pairings to be distinct, you need 30*r <= 190, or r <= 6. So, the largest number of rounds is 6. > What is one possible grouping of all the golfers in each round played > before the above rule is violated? These are called resolvable (20,4,1)-packings. See if you can find a journal called Journal of Combinatorial Theory or Discrete Math and look in the index for packings. A packing with 6 rounds should exist. You could also write a backtrack routine to find this. > If possible, please respond directly to me at lklamar@nps.navy.mil. Posted and e-mailed. Dan ============================================================================== From: ksbrown@seanet.com (Kevin Brown) Subject: Re: Need help with golf tournament schedule Date: 1997/04/18 Newsgroups: sci.math On 14 Apr 1997 19:13:41 Michael Masalin (mikem@mich.com) wrote: > I am trying to set up a golf outing for 24 people over 5 days and > want to arrange the foursomes such that each of the (6) foursomes > every day is a new foursome of players, that is, people who have > not played with each other previously in another foursome. I will > appreciate any help you can give me... This sounds like a standard problem in combinatorial design. One simple approach would be to start with four pair-wise orthogonal latin squares of size 5x5. (For any prime power N there exist N-1 pairwise orthogonal Latin squares of size NxN.) 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1 4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0 Here we've used the integers (mod 5), and the values of the kth array for k=1,2,3,4 are given by A_k(i,j) = k (i-1) + (j-1) (mod 5) for i,j = 1,2,3,4,5. These arrays are called "latin squares" because each element appears exacly once in each row and column. They are said to be "pairwise orthogonal" because if you super- impose one on top of the other you get all 25 distinct combinations (i,j) with i,j = 0,1,2,3,4. In other words, each element of one array matches up with each element of the other array exactly once. So, if we let the elements of the first array represent the first five players, and the elements of the second array represent the next five players, and so on, we can create 25 foursomes from the 20 players by superimposing the four arrays. Since the arrays are pairwise orthogonal, we are assured that no one plays in a foursome with the same person twice. But you wanted 30 foursomes involving 24 players. This can be done by mixing in four more players, taking advantage of the fact that none of the five players in a given array have yet played with each other. Thus, numbering the players 1 through 24, we have the following five days worth of foursomes. Each of the 24 players plays once per day, and no one plays with the same person twice. Day 1 Day 2 Day 3 Day 4 Day 5 1, 6,11,16 22, 8,14,20 3,10,12,19 4, 7,15,18 5, 9,13,17 2, 7,12,17 23, 9,15,16 4,24,13,20 5, 8,24,19 1,10,14,23 3, 8,13,18 24,10,11,17 5,21,14,16 1, 9,21,20 2, 6,15,24 4, 9,14,19 5, 6,12,18 1,22,15,17 2,10,22,16 3, 7,11,22 5,10,15,20 21, 7,13,19 2,23,11,18 3, 6,23,17 4, 8,12,21 21,22,23,24 1, 2, 3, 4 6, 7, 8, 9 11,12,13,14 16,18,19,20 ______________________________________________________________ | /*\ | | MathPages / \ http://www.seanet.com/~ksbrown/ | |________...And free'd his soul the nearest way._______________| ============================================================================== From: James MacDougall Subject: Card Game Tournament Date: 1998/02/14 Newsgroups: alt.sci.math.probability,sci.math.stat,sci.stat.consult,sci.stat,sci.stat.edu,sci.stat.math I was hoping someone could give me advice on the following problem. Consider a 4-player, partner based card game (e.g. Players#1,2,3, and 4 are playing the game with #1 and #2 partners against #3 and #4). A tournament for this game is trying to be created under the following criteria: (1) 16 players in the tournament (2) 15 rounds with each round consisting of 4-games (4-people in a game) (3) Each player has a different partner each round(15 rounds, 15 other players). (4) Each player faces every other player in a game as a non-partner twice. (5) Based on (3) and (4) each player meets (in a game) every other player exactly 3 times, one time as a partner and twice as an opponent. My primary interest is getting an algorithm, plan, idea, or generally some systematic way to create the player/Table-seating assignment for the 15 rounds. For further clarification the chart below illustrates what I'm trying to fill in with players # 1-16. Tables in Romans (I,II,III,IV), and the Seating Position at a table letters (A,B,C,D): Table_Seat I_A I_B I_C I_D ........IV_A IV_B IV_C IV_D Round 1 1 2 3 4 ........ 13 14 15 16 Round 2 1 3 5 7 ........ 12 11 8 2 ... Round 15 1 12 15 4 ......... 5 6 9 14 I spent a little bit of time on it but didn't get what I needed. I am hoping that there's a way to do this that I haven't thought of. Anyways I found the problem interesting in it's own right, thank you for your time. JimMac p.s. Feel free to reply to me directly or post thanks again. ============================================================================== From: "Andrzej Kolinski" Subject: Re: Card Game Tournament Date: 1998/02/16 Newsgroups: alt.sci.math.probability,sci.math.stat,sci.stat.consult,sci.stat,sci.stat.edu,sci.stat.math This is a typical arrangement for 16 players individual bridge game. Please refer to "Duplicate Bridge Direction" by Alex Groner, p. 192, for example available from the ACBL bookstore. Andrzej James MacDougall wrote in article ... > I was hoping someone could give me advice on the following problem. > Consider a 4-player, partner based card game (e.g. Players#1,2,3, > and 4 are playing the game with #1 and #2 partners against #3 and #4). .... ============================================================================== From: warwick@cs.mu.oz.au (Warwick HARVEY) Subject: Re: Maximum socializing on the golf course Date: 1998/06/05 Newsgroups: sci.op-research,comp.constraints Mark Perkins writes: >As a first cut, there are only certain combinations of weeks and players >which have a chance. Looking at it from my point of view, I will play >with three new golfers each week, so the number of golfers in the group >has to be: > 1 + 3*weeks Yes, but as another poster has already pointed out, there was no requirement that every player play with every other player: only that they don't play more than once. >However, the number of golfers must be a multiple of 4 in order to make >foursomes. The pairs which satisfy these two constraints are: >weeks golfers >------ ------ > 1 4 (I know the solution to this one) > 5 16 ... and I've written a program which yields a solution to this one (golfers are labelled 1-9, A-G): Week 1: 1234 5678 9ABC DEFG Week 2: 159D 26AE 37BF 48CG Week 3: 16BG 25CF 389E 47AD Week 4: 17CE 28BD 35AG 469F Week 5: 18AF 279G 36CD 45BE This immediately yields a 5-week solution for 32 golfers, where you replicate the above pattern for the other 16 golfers. This results in no socialisation between the two groups of 16 (this isn't necessarily a problem, just an observation). One would guess that by mixing all 8 groups in together, one could obtain a solution for more than 5 weeks. Note that you cannot just extend the 5-week solution I just described: you cannot form a group of 4 in the 6th week where none of the golfers have played with another from that group. This is because any group will have at least two golfers from one half or the other, and all golfers in a given half have already played with every other golfer in that half. Anyway, I have my program chewing on a 6-week solution for 32 golfers. It has already said "no" to an 8-week solution (after 9 hours of thinking :-), but that could just be a bug (I intend to play with the problem by hand to try to justify why there can be no 8-week solution, but if this seems obvious to anybody out there, feel free to jump in and answer it for me!). For anybody who is interested, I will present a discussion of my approach to the problem and explain why I did things the way I did sometime in the next few days (right now, I have to go home :-). Warwick ============================================================================== From: Robin Chapman Subject: Re: Rotating players through a card tournament Date: 1999/03/16 Newsgroups: sci.math In article , brian tivol wrote: > > Let's say there's a card-playing tournament with twenty-four entries. > This particular card game takes four players and has no partnerships. > Our organizer wants to have everybody playing at once, so he has six > card tables set up. When every table has completed one game, the > organizer wants to scramble all the players so that each player will > be playing against someone he hasn't faced before in the tournament. > (The method of scrambling does not have to be the same from round to > round.) How many different rounds of play can the tournament have > before the organizer is forced to pair up two players who've > previously faced each other? > > The most rounds I could work out was five. (I'll include my answer > below.) I couldn't find a method to get six rounds, nor could I prove > that six was impossible. Can anyone find the maximum number of rounds > that can be played, along with an example? > Seven (eight is obviously impossible). The following 7 diagrams assign each player (represented as a point in a 3 by 8 grid) one of six tables to play at. 1 1 3 4 2 4 4 5 2 2 1 5 3 5 5 6 3 3 2 6 1 6 6 4 1 5 1 3 4 2 4 4 2 6 2 1 5 3 5 5 3 4 3 2 6 1 6 6 1 4 5 1 3 4 2 4 2 5 6 2 1 5 3 5 3 6 4 3 2 6 1 6 1 4 4 5 1 3 4 2 2 5 5 6 2 1 5 3 3 6 6 4 3 2 6 1 1 2 4 4 5 1 3 4 2 3 5 5 6 2 1 5 3 1 6 6 4 3 2 6 1 4 2 4 4 5 1 3 2 5 3 5 5 6 2 1 3 6 1 6 6 4 3 2 1 3 4 2 4 4 5 1 2 1 5 3 5 5 6 2 3 2 6 1 6 6 4 3 Robin Chapman + "Going to the chemist in Department of Mathematics, DICS - Australia can be more Macquarie University + exciting than going to NSW 2109, Australia - a nightclub in Wales." rchapman@mpce.mq.edu.au + Howard Jacobson, http://www.maths.ex.ac.uk/~rjc/rjc.html - In the Land of Oz -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ============================================================================== From: cmyokota@aol.com (CMYokota) Subject: Re: Scheduling golfers in a tournament Date: 1999/06/05 Newsgroups: sci.math >Can you schedule the golfers such that each golfer over the four rounds >plays with just one other golfer twice, and the rest of the golfers >once? >If so what's the schedule? I don't have the information at hand, but the rotation of players in individual duplicate bridge tournaments is the same problem, and tables for these have been published. You might look in _The Encyclopedia of Bridge_, available at many public libraries. Chuck ============================================================================== Selected Matches for: whist (c) 2002, American Mathematical Society 54 #2513 05C20 Baker, Ronald Whist tournaments. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 89--100. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. Let $X$ be a set of $v$ objects, called players. A whist table, denoted $(x\sb 1,x\sb 2;x\sb 3,x\sb 4)$ is a set of four players with the pairs $\{x\sb 1,x\sb 2\}$ and $\{x\sb 3,x\sb 4\}$ known as partners and the remaining four pairs known as opponents. A whist round is a set of whist tables such that each player occurs at exactly one whist table. A whist tournament denoted $\text{Wh}[v]$, is a set of whist rounds such that any two players are partners at exactly one whist table and opponents at exactly two whist tables. It is shown that $\text{Wh}[v]$ exists for all such $v$ except possibly $v=132,152$ or $264$. Reviewed by A. Gewirtz _________________________________________________________________ 96j:01021 01A55 (01A60 05-03 05B30) Anderson, I.(4-GLAS) A hundred years of whist tournaments. (English. English summary) J. Combin. Math. Combin. Comput. 19 (1995), 129--150. A whist tournament ${\rm Wh}(4n)$ is a collection of $4n - 1$ partitions (known as rounds) of $4n$ players into $n$ games of $4$ players such that each player partners every other player once and opposes every other player twice. A whist tournament ${\rm Wh}(4n + 1)$ is similar except that there are $4n + 1$ players, $4n + 1$ rounds, and each player sits out of just one round. This paper begins with a brief historical introduction in which the author traces constructions of tournaments ${\rm Wh}(4n)$ back to books and articles published in the 1890s and constructions of tournaments ${\rm Wh}(4n + 1)$ back to a paper by G. Watson [Math. Gazette 38 (1954), 129--130; per bibl.], and sketches how tournaments ${\rm Wh}(4n)$ and ${\rm Wh}(4n + 1)$ were constructed for all $n \geq 1$ by R. M. Wilson, R. D. Baker and H. Hanani in the 1970s. The rest of the work is a survey of constructions, some very recent, for tournaments ${\rm Wh}(4n)$ and ${\rm Wh}(4n + 1)$ of various special kinds. Some admit cyclic groups of automorphisms, some satisfy stringent conditions relating to the disposition of the players. Connections are made with other combinatorial structures, and the paper concludes with an extensive bibliography. Reviewed by Peter M. Neumann _________________________________________________________________ 2000m:05054 05B30 Lu, Y.; Shengyuan, Zhang(PRC-FUJN) Existence of whist tournaments with the three-person property $3{\rm PWh}(v)$. (English. English summary) Discrete Appl. Math. 101 (2000), no. 1-3, 207--219. [ORIGINAL ARTICLE] A whist tournament is said to have the 3-person property if no two games have three common players. Such tournaments were discussed by N. J. Finizio [Discrete Appl. Math. 45 (1993), no. 2, 125--137; MR 94h:05009]. It is shown that such tournaments exist for $v$ players, $v\equiv 0$ or $1\pmod 4$, $v>472$. Below this bound, there are at most 38 exceptions. Reviewed by Ian Anderson _________________________________________________________________ 98i:05040 05B30 Finizio, Norman J.(1-RI); Lewis, James T.(1-RI) A criterion for cyclic whist tournaments with the three person property. (English. English summary) Util. Math. 52 (1997), 129--140. Summary: "A whist tournament is said to have the three-person property if the intersection of any two tables in the tournament is at most two. If $a$ is a player at a table in a cyclic whist tournament we introduce the concept of $a$-centered differences and use this concept to develop a necessary and sufficient condition for the three-person property. The well-known whist constructions of Baker, Bose and Cameron, Moore, and Watson are analyzed using this condition. The condition is also generalized to resolvable cyclic block designs of block size $k$." _________________________________________________________________ 94h:05009 05B05 Finizio, Norman J.(1-RI) Whist tournaments---three person property. (English. English summary) Discrete Appl. Math. 45 (1993), no. 2, 125--137. A whist tournament is said to have the three-person property if no three people play together in more than one game. Designs with this property have been constructed by N. S. Mendelsohn [in Recent progress in combinatorics (Waterloo, 1968), 123--132, Academic Press, New York, 1969; MR 41 #85]. The author constructs several infinite families of whist tournaments with this property, and gives explicit cyclic examples for $4k+1$ players for 18 values of $k\leq 30$. Reviewed by Ian Anderson Site providing lots of things like this: ("social golfer" problem) http://www.cs.brown.edu/~sello/golf.html