From: "Eric and Rachael Farmer" Subject: Re: combinatorical problem --- team competitions Date: Mon, 15 Mar 1999 21:02:25 -0500 Newsgroups: sci.math Keywords: scheduling tournaments Christophe Lermytte wrote in message ... > >I thought one of my friends who studies math would know this >in a nanosecond, but he couldn't really help me on the spot >so I'll try it here. > >Given are 2n teams. Every week they form pairs to play >a game. > >n=3 : week 1 1 vs 2 3 vs 4 5 vs 6 > week 2 3 vs 6 4 vs 2 1 vs 5 > ... > week 5 4 vs 2 1 vs 6 3 vs 5 > >Can anyone give me a nice symmetrical way >(as symmetrical as possible) of constructing the games every week ? This should be in any introductory number theory or (maybe) combinatorics text. In each round r (r ranges from 1 to 2n-1), schedule team i (where i ranges from 1 to 2n-1; note that team 2n is left out) to play team j such that i+j is congruent to r (mod 2n-1). But for each round r, there will be exactly one i such that i+i = 2i is congruent to r (mod 2n-1), since 2 and 2n-1 are relatively prime. Schedule this team to play team 2n. Eric Farmer ============================================================================== From: Robin Chapman Subject: Re: Rotating players through a card tournament Date: Tue, 16 Mar 1999 23:44:37 GMT Newsgroups: sci.math To: tivol@mit.edu 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: robjohn9@idt.net (Rob Johnson) Subject: Re: Block Scheduling Algorithm Date: 15 Dec 1999 22:02:39 GMT Newsgroups: sci.math In article <836480$gmo$1@nnrp1.deja.com>, alawisious@my-deja.com wrote: >I am looking for a block scheduling algorithm that schedules a certain >number of teams (in this case), where a team does not play each other >twice... > >eg. 4 teams > > 1 2 >==== ==== >1vs2 1vs4 >3vs4 2vs3 > >it is easy to do with 4 teams but when you try do do it for 6, 8, 10, >12...etc... it gets pretty tough... If anyone knows of a formula for >this i would much appreciate it. Some compensation may be in order for >anyone who can figure it out. To match things up properly, you need to have an even number of teams, say 2n. If you have an odd number of teams, just assign a bye as team 2n. To have each team play each other team, you need 2n-1 rounds. In round r match teams x and y where x + y = r mod 2n-1 [1] Since 2n = 1 mod 2n-1, we will handle 2n separately. There will always be a team scheduled to play itself by this algorithm (2x = r always has a solution in an odd modulus); assign that team to play team 2n. n=1 (2n-1 = 1): round 1: 1-2 n=2 (2n-1 = 3): round 1: 1-3 2-4 round 2: 1-4 2-3 round 3: 1-2 3-4 n=3 (2n-1 = 5): round 1: 1-5 2-4 3-6 round 2: 1-6 2-5 3-4 round 3: 1-2 3-5 4-6 round 4: 1-3 2-6 4-5 round 5: 1-4 2-3 5-6 n=4 (2n-1 = 7): round 1: 1-7 2-6 3-5 4-8 round 2: 1-8 2-7 3-6 4-5 round 3: 1-2 3-7 4-6 5-8 round 4: 1-3 2-8 4-7 5-6 round 5: 1-4 2-3 5-7 6-8 round 6: 1-5 2-4 3-8 6-7 round 7: 1-6 2-5 3-4 7-8 Rob Johnson robjohn9@idt.net