Math problem

[geoschmo]

Ok, I like math but my brain doesn't work well when you get past two dimensions. http://forum.shrapnelgames.com/images/icons/icon10.gif

I am trying to figure something out. Assume a hypothetical tournament which are all 3 player games. In the tournament everybody has to play everybody else once, but only once.

If there are three players it's easy, A,B,C. What's the next number of players that this format will work for? Can it be done with 9 or do you need 27, or is it some other number completely?

Is there an easy way to figure this out including who has to play who?

[geoschmo]

Ok, I figured it out the long way using graph paper. http://forum.shrapnelgames.com/images/icons/blush.gif

So I guess then it's x squared, where x is the number of players per game. Not x to the power of x. So with 4 player games it would take 16 people in the tourney and 5 player games would take 25? Does that sound right? Is there a way to verify that without using graph paper? http://forum.shrapnelgames.com/images/icons/shock.gif

[BBegemott]

Originally posted by Geoschmo:
I am trying to figure something out. Assume a hypothetical tournament which are all 3 player games. In the tournament everybody has to play everybody else once, but only once.
<font size="2" face="Verdana, Helvetica, sans-serif">IMHO it can't be done with 3 player games with any number of players (except 3 of course).

Assume 9 players tournament. Nine players will be marked with numbers 1,2,...,9.
I could make only legal 10 triplets:

1) 123
2) 145
3) 167
4) 189
5) 246
6) 278
7) 259
8) 347
9) 369
10)358
11)48?
12)49?

There is no legal substitution for 11th & 12th triplet, because 4th player has already played 1,5,2,6,3,7. Putting any number instead of '?' contradicts to the rule 'everybody has to play everybody else once, but only once'.

Or have I missed some kind of hidden trick? I am really curious to see your solution http://forum.shrapnelgames.com/images/icons/icon7.gif

[tesco samoa]

hey geo i use that for figuring out how many tickets i need to do in betting on sport games

3 of 3 rotations ( 3 teams to 25) right up to 12 of 12 rotations

3 of 4 is 4
3 of 5 is 10
3 of 6 is 20
3 of 7 is 35
3 of 8 is 56
3 of 9 is 84
3 of 10 is 120
4 of 5 is 5
4 of 6 is 15
4 of 7 is 35
4 of 8 is 70
4 of 9 is 126
4 of 10 is 210
5 of 6 is 6
5 of 7 is 21
5 of 8 is 56
5 of 9 is 126
5 of 10 is 252
6 of 7 is 7
6 of 8 is 28
6 of 9 is 84
6 of 10 is 210
7 of 8 is 8
7 of 9 is 36
7 of 10 is 120
8 of 9 is 9
8 of 10 is 45

many different rotations...

[Z.e.r.o]

The number of matches you need is n!
where n! = 1*2*3*4*...*(n-1)*(n)
and is called factorial and can be used to determine the numbers of permutations of n tokens.

In a 3 players match where anyone is playing a role only once is 3! (1*2*3 = 6)

Empirical solution:
123
213
312
321
132
231

If I'm not right you can spank me with a crowbar

[tesco samoa]

umm mine was total games that would be needed to play each other in every combination...

ignore

[Z.e.r.o]

Spank me.

Is not right, every player plays two times in the same role.

But I'm sure that the number will be a subset of n!, but I also believe that you need an even number of players to not have conflicts.

[tesco samoa]

i have a question along this line

say you have 24 numbers and you want to sort them in combinations of 4 where each number only appears once with each other how many combinations would that be ???

now if some one wanted to whip up a little program that does that ( but i can select the numbers (say up to 50), combinations ( 2 to 12 ) and uniqueness ( say once to 6 times ) and can produce a text file output i would be forever thankful

[Erax]

It will work for nine players. Here's how :

1-2-3 | 1-4-7 | 1-5-9 | 1-8-6
4-5-6 | 2-5-8 | 2-6-7 | 4-2-9
7-8-9 | 3-6-9 | 3-4-8 | 7-5-3

Nope, used no math, did it empirically.

[ August 06, 2003, 18:41: Message edited by: Erax ]

[geoschmo]

Originally posted by BBegemott:
IMHO it can't be done with 3 player games with any number of players (except 3 of course).

Assume 9 players tournament. Nine players will be marked with numbers 1,2,...,9.
I could make only legal 10 triplets:

1) 123
2) 145
3) 167
4) 189
5) 246
6) 278
7) 259
8) 347
9) 369
10)358
11)48?
12)49?

There is no legal substitution for 11th & 12th triplet, because 4th player has already played 1,5,2,6,3,7. Putting any number instead of '?' contradicts to the rule 'everybody has to play everybody else once, but only once'.

Or have I missed some kind of hidden trick? I am really curious to see your solution http://forum.shrapnelgames.com/images/icons/icon7.gif <font size="2" face="Verdana, Helvetica, sans-serif">The problem is not every legal combination will work. For example, by using
1) 123
2) 145
3) 167
4) 189
you prevent the option of trying 146. This is fine for 1, 4, and 6 as long as they all play each other once, but might prevent others from being able to play each other, as you found out.

Instead if you do something like...
1) 123
2) 456
3) 789
4) 147
5) 158
6) 169
7) 249
8) 275
9) 268
10) 348
11) 359
12) 367

then it works.

[spoon]

When in doubt, ask a programmer (if you have one handy...) Here's the reply I got:
-----
If you want to do all x*x sized games, then any power of x will support your goal. However, be warned that in a 27-man tournament of 3x3 matchings, you are talking about 9 games apiece (3^n-1).

Scheduling is a bit of a pain but manageable. The way I would do it is to schedule x^n-1 guys for the first round, and then everything sort of falls out of that just by pairing that guy off with the next guy down the list, then 2 down the list, etc.. For 27 guys (a-z and 1) at x=3. You essentially match up randomly in the first round, and then down diagonals for each subsequent round based on the first round.

ABC
DEF
GHI
JKL
MNO
PQR
STU
VWX
YZ1

AEI
DHL
GKO
JNR
MQU
PTX
SW1
VZC
YBF

AHO
DKR
GNU
JQX
MT1
PWC
SZF
VBI
YEL

etc.

[LGM]

I used a program. Here are two solutions:

N=7
3,5,6
3,4,7
2,5,7
2,4,6
1,6,7
1,4,5
1,2,3

N=15
7,11,12
7,10,13
7,9,14
7,8,15
6,11,13
6,10,12
6,9,15
6,8,14
5,11,14
5,10,15
5,9,12
5,8,13
4,11,15
4,10,14
4,9,13
4,8,12
3,13,14
3,12,15
3,9,10
3,8,11
3,5,6
3,4,7
2,13,15
2,12,14
2,9,11
2,8,10
2,5,7
2,4,6
1,14,15
1,12,13
1,10,11
1,8,9
1,6,7
1,4,5
1,2,3

[geoschmo]

Originally posted by LGM:
I used a program. Here are two solutions:

N=7
3,5,6
3,4,7
2,5,7
2,4,6
1,6,7
1,4,5
1,2,3

<font size="2" face="Verdana, Helvetica, sans-serif">This isn't what I was looking for. This is everybody playing 3 three man games. I wanted everybody to play EVERYBODY else once and only once in a three man game. 7 players won't work for that. You need a power of 3 as Spoon says so 9, or 27, etc.

[ August 06, 2003, 19:48: Message edited by: geoschmo ]

[LGM]

Here is another solution. The patern appears to be 2^x-1. I would suspect that the next solution is at 63, but 31 took long enough to prove and my algorythm uses prime numbers with the mod function to find matches, so I don't want to look up another 32 prime numbers to make it that far.

N=31
15,23,24
15,22,25
15,21,26
15,20,27
15,19,28
15,18,29
15,17,30
15,16,31
14,23,25
14,22,24
14,21,27
14,20,26
14,19,29
14,18,28
14,17,31
14,16,30
13,23,26
13,22,27
13,21,24
13,20,25
13,19,30
13,18,31
13,17,28
13,16,29
12,23,27
12,22,26
12,21,25
12,20,24
12,19,31
12,18,30
12,17,29
12,16,28
11,23,28
11,22,29
11,21,30
11,20,31
11,19,24
11,18,25
11,17,26
11,16,27
10,23,29
10,22,28
10,21,31
10,20,30
10,19,25
10,18,24
10,17,27
10,16,26
9,23,30
9,22,31
9,21,28
9,20,29
9,19,26
9,18,27
9,17,24
9,16,25
8,23,31
8,22,30
8,21,29
8,20,28
8,19,27
8,18,26
8,17,25
8,16,24
7,27,28
7,26,29
7,25,30
7,24,31
7,19,20
7,18,21
7,17,22
7,16,23
7,11,12
7,10,13
7,9,14
7,8,15
6,27,29
6,26,28
6,25,31
6,24,30
6,19,21
6,18,20
6,17,23
6,16,22
6,11,13
6,10,12
6,9,15
6,8,14
5,27,30
5,26,31
5,25,28
5,24,29
5,19,22
5,18,23
5,17,20
5,16,21
5,11,14
5,10,15
5,9,12
5,8,13
4,27,31
4,26,30
4,25,29
4,24,28
4,19,23
4,18,22
4,17,21
4,16,20
4,11,15
4,10,14
4,9,13
4,8,12
3,29,30
3,28,31
3,25,26
3,24,27
3,21,22
3,20,23
3,17,18
3,16,19
3,13,14
3,12,15
3,9,10
3,8,11
3,5,6
3,4,7
2,29,31
2,28,30
2,25,27
2,24,26
2,21,23
2,20,22
2,17,19
2,16,18
2,13,15
2,12,14
2,9,11
2,8,10
2,5,7
2,4,6
1,30,31
1,28,29
1,26,27
1,24,25
1,22,23
1,20,21
1,18,19
1,16,17
1,14,15
1,12,13
1,10,11
1,8,9
1,6,7
1,4,5
1,2,3

[geoschmo]

Originally posted by spoon:
When in doubt, ask a programmer (if you have one handy...) Here's the reply I got:
-----
If you want to do all x*x sized games, then any power of x will support your goal. However, be warned that in a 27-man tournament of 3x3 matchings, you are talking about 9 games apiece (3^n-1).
<font size="2" face="Verdana, Helvetica, sans-serif">Ok, I see how I need a power of x, so for 4 man games I'd need at least 16 players, and for 5 man I'd need 25 players. How did you calculate nine games each for 27 players in a 3 on 3 tourney though? With 27 player field if you play everybody once and only once and do it with 3 man games that would be (27-1)/2=13 games. With a nine player player field it would be (9-1)/2=4 games each.

Geoschmo

[LGM]

Originally posted by geoschmo:
</font><blockquote><font size="1" face="Verdana, Helvetica, sans-serif">quote:</font><hr /><font size="2" face="Verdana, Helvetica, sans-serif">Originally posted by LGM:
I used a program. Here are two solutions:

N=7
3,5,6
3,4,7
2,5,7
2,4,6
1,6,7
1,4,5
1,2,3

<font size="2" face="Verdana, Helvetica, sans-serif">This isn't what I was looking for. This is everybody playing 3 three man games. I wanted everybody to play EVERYBODY else once and only once in a three man game. 7 players won't work for that. You need a power of 3 as Spoon says so 9, or 27, etc.</font><hr /></blockquote><font size="2" face="Verdana, Helvetica, sans-serif">I am not sure I follow. Player 1 places all 3 player games and plays every player once and only once. The same applies for player 2, 3, etc.

[spoon]

Originally posted by geoschmo:
How did you calculate nine games each for 27 players in a 3 on 3 tourney though? With 27 player field if you play everybody once and only once and do it with 3 man games that would be (27-1)/2=13 games. With a nine player player field it would be (9-1)/2=4 games each.

Geoschmo<font size="2" face="Verdana, Helvetica, sans-serif">Oh that? Must be programmer error... heh. That's why you should never listen to them... http://forum.shrapnelgames.com/images/icons/icon12.gif

[LGM]

Originally posted by geoschmo:
Assume a hypothetical tournament which are all 3 player games. In the tournament everybody has to play everybody else once, but only once.<font size="2" face="Verdana, Helvetica, sans-serif">What part of the requirement did I neglect?

[geoschmo]

Oh wait LGM, I think I see what you are saying now. Did your program find solutions for anything between 7 and 15. The way I am looking at this now it should be possible to do for many numbers, not just powers of x.

Approaching the problem from the other end was the key if I am correct. For example, in a tournament of three man games the minimum number of players would be 3, and the number of games would be 1. The forumula should be:

x, game size
y, number of tourney games
n, total tourney field

EDIT: IGNORE EVERYTHING IN THIS POST AFTER THIS POINT. I haven't figured out what I did wrong, but this isn't right at all.

(y(x-1))+1=n

plugging in the ones we know already
(1(3-1))+1=3
(3(3-1))+1=7
(7(3-1))+1=15
(13(3-1))+1=27

We should be able to work out an n for any positive real integer X and Y fairly easy.
If x=3
y=1, n=3
y=2, n=5
y=3, n=7
y=4, n=9
.
.
y=15, n=31

So for x=3 n can be any odd number except 1.

The hard part would be actually coming up with the y number of combinations so that each player doesn't play anyone else more then once.

[ August 06, 2003, 20:44: Message edited by: geoschmo ]

[geoschmo]

No, that's not right.

LGM, I didn't mean any offense. I looked at your initial post and didn't think it solved teh problme, but after looking at it again I see it does. Can you explain the math your program is doing to find the solutions? That is what I am trying to figure out.

Geoschmo

[Slick]

I didn't read all the replies, so pardon this if already stated, but aren't you talking about the statistical formula for combinations? Mathematically, it means: how many ways can I group n things in groupings of r where the order of grouping is not important. (There is a separate formula for permutations where order is important)

The general formula for C(n,r) = n!/[r!(n-r)!]

Where the number of combinations C(n,r) is a function of the total number of people n taken r at a time.

You don't need any particular number of players to start with. If n = 10 and r = 3 then the required number of games is 10!/[3!x7!] = 120

Exactly how to arrange the people in each game is most easily worked out by hand although I suppose it could be done with a program.

Slick.

[LGM]

Only solutions are 3, 7, 15, 31,...

Other numbers of players leave a three some with two players and no one to match them with. Someone demonstrated this earlier with 9 players.

[geoschmo]

Sorry slick, this is way over my head.

"The general formula for C(n,r) = n!/[r!(n-r)!]"

What do n and r represent in the formula, and what are the exclamation points for?

And is C(n,r) the total numebr of players needed in the tourney, or the number of games played by each person in the tourney, or something else alltogether? http://forum.shrapnelgames.com/images/icons/confused.gif

[geoschmo]

Originally posted by LGM:
Only solutions are 3, 7, 15, 31,...

Other numbers of players leave a three some with two players and no one to match them with. Someone demonstrated this earlier with 9 players.<font size="2" face="Verdana, Helvetica, sans-serif">Right, but other then working them out by hand, or having you plug it into yoru black box and give me the result, can you explain how you know this? What I am trying to learn is not the answer, but how the answer is derived.

Geoschmo

[LGM]

Here is the code. Crudely done by brute force in a rather esoteric flavor of basic:

PRIMES = '2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61 ,67,71,73,79,83,89,97,101,103,109,113,127,131,137'
SWAP ',' WITH @AM IN PRIMES
ILIMIT = DCOUNT(PRIMES,@AM)
PRINT ILIMIT
FOR I = 4 TO ILIMIT
NBR = I
COMBOS = ''
COMBOX = ''
IDX = 1
FOR J = 1 TO I
FOR K = J+1 TO I
FOR L = K+1 TO I
GOSUB FIND.DUPLICATE
IF NOT(FOUND.DUPLICATE) THEN
COMBOS<-1> = PRIMES<J>*PRIMES<K>*PRIMES<L>
COMBOX<-1> = J:',':K:',':L
END
NEXT L
NEXT K
NEXT J
GOSUB CHECK.SOLUTION
NEXT I
PRINT 'DONE'
STOP
*
SOLVED:*
PRINT '---------------------'
PRINT 'SOLVED'
PRINT NBR
FOR M = DCOUNT(COMBOX,@AM) TO 1 STEP -1
PRINT COMBOX<M>
NEXT M
INPUT CH,1_
RETURN
*
CHECK.SOLUTION: *
FOR J = 1 TO I
FOR K = J + 1 TO I
NBR.MATCHES = 0
FOR M = DCOUNT(COMBOS,@AM) TO 1 STEP -1
A.COMBO = COMBOS<M>
IF MOD(A.COMBO,PRIMES<J>)=0 AND MOD(A.COMBO,PRIMES<K>)=0 THEN
NBR.MATCHES = NBR.MATCHES + 1
IF NBR.MATCHES > 1 THEN RETURN
END
NEXT M
IF NBR.MATCHES = 0 THEN RETURN
NEXT K
NEXT J
GOSUB SOLVED
RETURN
*
FIND.DUPLICATE: *
FOUND.DUPLICATE = 0
FOR M = DCOUNT(COMBOS,@AM) TO 1 STEP -1
A.COMBO = COMBOS<M>
J.MOD = MOD(A.COMBO,PRIMES<J>)
K.MOD = MOD(A.COMBO,PRIMES<K>)
L.MOD = MOD(A.COMBO,PRIMES<L>)
IF J.MOD = 0 THEN
IF K.MOD=0 OR L.MOD=0 THEN
FOUND.DUPLICATE = 1
END
END ELSE IF K.MOD=0 AND L.MOD=0 THEN
FOUND.DUPLICATE = 1
END
NEXT M
RETURN

[geoschmo]

Ok, so bascially you are having the couputer run through all the possible options fast and see if a number works. Ok, that does the job but isn't really what I was looking for. Mayeb there is no simple mathematical formula for what I am looking for.

Basically I can take x players and group them into games of three players each and see fairly quickly that 7 players will work, but 5 will not. What I was hoping to find was a formula that I could plug the numbers in and be able to tell if a combination of x and y would work without having to go through all teh grouping by hand.

Geoschmo

[geoschmo]

By the way LGM, what is the reason for using the prime numbers in the program? I'm not a programmer so I can't really make heads or tails of your code there, not that it wasn't apprecieated. http://forum.shrapnelgames.com/images/icons/icon10.gif

[LGM]

Try X raised to the Yth power and subtract one. Just a theory. I am not sure if that works for 4 or 5 man games yet. X is Number of players per game minus 1. Incidentally, that does not work for 2 players games as any number works for 'round robin' leagues.

[LGM]

Prime numbers are a nice way to test if something is a member of a set. Products of prime numbers is a common way of encoding sets because you can divide by a given prime. If the remainder is zero, it is an element of the set.

[LGM]

You could use 21 players (3 sets of 7) with a championship game from the winners of each set.

Or you could use 49 players (7 sets of 7) and have a championship round of the top 7 playing each of the top 7.

[ August 06, 2003, 21:13: Message edited by: LGM ]

[Slick]

Originally posted by geoschmo:
Sorry slick, this is way over my head.

"The general formula for C(n,r) = n!/[r!(n-r)!]"

What do n and r represent in the formula, and what are the exclamation points for?

And is C(n,r) the total numebr of players needed in the tourney, or the number of games played by each person in the tourney, or something else alltogether? http://forum.shrapnelgames.com/images/icons/confused.gif <font size="2" face="Verdana, Helvetica, sans-serif">Sorry, no offense intended...

n are the total number of players in the tourney
r are the number of players in the group (i.e. 3 for your case)

x! (spoken "x factorial") is defined as x! = x(x-1)(x-2)(x-3)...(3)(2)(1)

So 10! = 10x9x8x7x6x5x4x3x2x1

C(n,r) means C is a function of the variables n & r.

Bottom line:

The number of ways to group n people in Groups of r (i.e. the total number of games required to have everyone play everyone else in one and only one game) is C(n,r) = n!/[r!(n-r)!]

I seriously recommend you think up a better tourney. For 10 people, you need 120 games.

Slick.

[Slick]

Nevermind. Forget everything I said. C(n,r) is the wrong formula for this. Sorry for the confusion. http://forum.shrapnelgames.com/images/smilies/rolleyes.gif

Slick.

[Ack]

Outside of being an interesting mathematical series problem, the general question is void. It would be incredibly difficult to get 27 players in a round-robin style game. It would take months if not years for every combination to be played out. I'd recommend a bracket style where only the top one or two players advance to the next round. Which is how the NCAA tournament decides a winner in just 6 rounds out of a pool of 64 teams.

[geoschmo]

Originally posted by Ack:
Outside of being an interesting mathematical series problem, the general question is void. It would be incredibly difficult to get 27 players in a round-robin style game. It would take months if not years for every combination to be played out.<font size="2" face="Verdana, Helvetica, sans-serif">Not really. I suppose it depends on the players in the tourney though. Months I can see, but it should not take years.

27 players in games of three, where each player must play every other player once and only once. Each player only has to play 13 games total. That's a lot, but you can play them simultaneously, or at least 3 or 4 at a time. And 3 man games of SE4 go pretty quick.

But that would be a lot of games nonetheless. It would be hard to find 27 people willing to do that many probably.

Geoschmo

[Slynky]

One of the good things about chess and its rating system (see my remark about one possible way to have a rating system in SE4 in the "New League" thread) is the wonderful way tournements can be run. Using the rating of the player, you just use Swiss-System pairing and get a tourney done in 4-5 rounds...considering anywhere from 15-30 people.

[geoschmo]

Originally posted by Slick:
Nevermind. Forget everything I said. C(n,r) is the wrong formula for this. Sorry for the confusion. http://forum.shrapnelgames.com/images/smilies/rolleyes.gif

Slick.<font size="2" face="Verdana, Helvetica, sans-serif">That's allright. I got Fyron to explain to me offline how that formula worked and it is interesting. It's close, but as you say not exactly right. It looks like it's counting all possible combinations, instead of each player facing every other player once and only once.

Maybe there is no forumla and LGM's way is the solution. Or maybe there is one and we'll all get the Nobel prize for mathematics for working it out. http://forum.shrapnelgames.com/images/icons/icon7.gif

[Fyron]

There is certainly a formula for it, we just do not know it. Any professional mathematicians out there? http://forum.shrapnelgames.com/images/icons/icon10.gif

[Suicide Junkie]

Choose 2 from N, since order is unimportant.
On my calculator, that's the "nCr" button
For N=27, that's 351 games to be played round-robin.

27 players in games of three, where each player must play every other player once and only once. Each player only has to play 13 games total. <font size="2" face="Verdana, Helvetica, sans-serif">No; Player 1 goes up against all 26 other players. Similarily for the others, so that's 26 games total for each player. http://forum.shrapnelgames.com/images/icons/icon12.gif

26games*27people = 702 plays
That makes for 351 two-player games.

[ August 06, 2003, 22:11: Message edited by: Suicide Junkie ]

[Fyron]

But, each player only plays the others once each, so it does not work for larger games than 2 player ones.

[Suicide Junkie]

More than two players would get you problems with teaming up, I imagine.

[Gryphin]

Has something to do with "Pigeon Holing
Geo I don't know if these help. I did a search at google on the formula:

http://www.cs.mtu.edu/~shene/COURSES/cs201/NOTES/chap06/fact-2.html

This is a word doc:
http://www.cecs.csulb.edu/~lam/cecs228/ch4.doc

I think this is a powerpoint presentation:
file:///D:/Temporary%20Internet%20Files/Temporary%20Internet%20Files/Content.IE5/I56W66T4/275,10,r-permutations

This one seemed the simplest:
http://fclass.vaniercollege.qc.ca/web/mathematics/real/Calculators/PermsCombs_Intro.htm

[Gryphin]

This site has
"Real Life Mathmatics" and includes calculators.
http://fclass.vaniercollege.qc.ca/web/mathematics/real/2real.htm

Edit:
Oh well, too little too late but I did learn a lot and the above link has some interesting math described in laymens terms. It also has some math word puzzles under the "Teasers"

[ August 06, 2003, 22:51: Message edited by: Gryphin ]

[Fyron]

Originally posted by Suicide Junkie:
More than two players would get you problems with teaming up, I imagine.<font size="2" face="Verdana, Helvetica, sans-serif">Yes, and it is not meant for 2-player games. http://forum.shrapnelgames.com/images/icons/icon12.gif

[Captain Kwok]

You need to change the format!

What about setting it up like a sports league?

For example, 12 players and 2-player games.

Make 2 divisions of 6 players. Each player plays two matches against their division mates and 1 game against the opposite division. This makes 16 games. The top 2 players from each division play a best-of-3 series to determine a 'pennant' winner, and then the pennant winners from each division play for the grand championship in a best-of-3 series.

The games can be played concurrently:

Day 1 to 75 > 1st games against own division
Day 76 to 150 > games against other division
Day 151-225 > 2nd games against own division
Day 225-? > Playoffs

If this is too long, you can set up this style for any amount of players. You could set up a smaller league that runs faster, say like 8-player leagues. You could even run several small leagues at different intervals, giving opportunities for new players to join etc...

[cybersol]

Originally posted by LGM:
Only solutions are 3, 7, 15, 31,...

Other numbers of players leave a three some with two players and no one to match them with. Someone demonstrated this earlier with 9 players.<font size="2" face="Verdana, Helvetica, sans-serif">I have verified the following solution by Erax for 9 players. LGM, why do you think it does not work and why does your program fail to find it?

Originally posted by Erax:
It will work for nine players. Here's how :

1-2-3 | 1-4-7 | 1-5-9 | 1-8-6
4-5-6 | 2-5-8 | 2-6-7 | 4-2-9
7-8-9 | 3-6-9 | 3-4-8 | 7-5-3

Nope, used no math, did it empirically.<font size="2" face="Verdana, Helvetica, sans-serif"> Originally posted by geoschmo:
Is there an easy way to figure this out including who has to play who?<font size="2" face="Verdana, Helvetica, sans-serif">Here is what I know so far:
n = total number of players in tournament
x = number of player in each game

(n-1)/(x-1) = number of games played in the torunament by each player (#gpp)
This must be an integer for the tournament to work, so for x=3 player games there must be an odd number of players.

(#gpp*n)/x = total number of games in tournament
This must be an integer to work also, so for x=3 that leaves valid n=3,7,9,13,15,19,21,25,etc. This is really two series n=3,9,15,21,etc. and n=7,13,19,25,etc. deriving from whether n or #gpp is divisible by 3 respectively.

We have seen solutions for 3,7,9, and 15. If anyone wants to look for another empirical solution, I suggest seeing if 13 works.

Hope this helps,
cybersol

[ August 07, 2003, 00:17: Message edited by: cybersol ]

[geoschmo]

Kwok and SJ, the idea isn't to use 2 player games. I am trying to figure out a way to mathematically derive the total number of players needed for a round robin tourney of larger then two player games. And I want to be able to figure it out for any possible number, not jsut three.

Coming up with alternate formats isn't the idea. I am not really trying to make a tourney. I am just trying to figure out the math side of it.

It's a tanget. http://forum.shrapnelgames.com/images/icons/icon7.gif

Gryphin, those sites are interesting, but they are have the same problem as Slicks formula. They are calculating all possible combinations. That's not what I am trying to do.

Geoschmo

[geoschmo]

Originally posted by cybersol:
I have verified the following solution by Erax for 9 players. LGM, why do you think it does not work and why does your program fail to find it?
<font size="2" face="Verdana, Helvetica, sans-serif">I suspect his program is hitting a point where it can't find a valid remaining set and is then deciding that number n has no solution. Whil ein fact as we showed earlier sometimes you can get stuck down a "blind-alley" where there is a solution for n, but not for every possible set of 3. Like what happened to Bbgemont. To completely rule out a possible solution it would have to back track when it reaches these end points and change an earlier set and rework from that point. Sounds complicated. http://forum.shrapnelgames.com/images/icons/icon7.gif

Geoschmo

[Gryphin]

(I don't really know anything about the math involved)
I did another google search:
"round robin tournament"
Then I tried:
"round robin tournament" +software

Quite a few hits that might help including calcuators.
Here is one link:
http://www.devenezia.com/downloads/round-robin/

I guess what I'm driving at here is others must have wanted this and their answer must be on the web. http://forum.shrapnelgames.com/images/icons/icon12.gif
Good luck

[ August 07, 2003, 00:58: Message edited by: Gryphin ]

[Captain Kwok]

Geo:

You have a difficult problem. Most programs used to set up match schedules like this are based on 2 players/teams.

What you are proposing is not a very common format to schedule and will be very difficult to organize. Other than finding the total number of games required (i.e. number of all the different combinations of players as calculated by others), you'll have to manually arrange the games or find someone to make a program for you that can do this automatically. On a more positive note, I'm sure there is some sort of combinations calculator out there on the net that lists each of the combinations...

[ August 07, 2003, 01:07: Message edited by: Captain Kwok ]

[Jack Simth]

Let's see: Floor function for the numbers:

Pp = players per game
Np = Number of players (total)
Gp = Games per player
Tg = Total games

Gp = (Np - 1) / (Pp - 1)
Tg = (Np * Gp) / Pp
= (Np*((Np - 1) / (Pp - 1)))/Pp
= (Np * (Np - 1)) / (Pp * (Pp - 1))

Gp = (Np - 1) / (Pp - 1)
Tg = (Np * (Np - 1)) / (Pp * (Pp - 1))

If Gp and Tg come out as positive integers, it should be doable - I'm not sure about the arrangement, however.

Edit: Arrangement method:

1) List players
2) Variables
Pp = players per game
Np = Number of players (total)
Gp = Games per player
Tg = Total games
Sk = Skip (counting variable; internal use only)
3) Gp = (Np - 1) / (Pp - 1)
4) Tg = (Np * (Np - 1)) / (Pp * (Pp - 1))
5) Sk = 0
6) Group, skipping Sk
7) Sk = Sk + Pp
8) If Sk < Np, Goto 6

[ August 07, 2003, 01:44: Message edited by: Jack Simth ]

[tesco samoa]

geo you should grab one of those wheel systems for lotteries.

you need a 3 of n wheeler with a filter

[cybersol]

Originally posted by Jack Simth:
Let's see: Floor function for the numbers:

Pp = players per game
Np = Number of players (total)
Gp = Games per player
Tg = Total games

Gp = (Np - 1) / (Pp - 1)
Tg = (Np * Gp) / Pp
...
If Gp and Tg come out as positive integers, it should be doable - I'm not sure about the arrangement, however.<font size="2" face="Verdana, Helvetica, sans-serif">I think this is the same as what I had a few Posts back, or am I missing something?

Edit: Oh sure add more http://forum.shrapnelgames.com/images/icons/icon7.gif

Originally posted by Jack Simth:
Edit: Arrangement method:
Edit: Arrangement method:

1) List players
2) Variables
Pp = players per game
Np = Number of players (total)
Gp = Games per player
Tg = Total games
Sk = Skip (counting variable; internal use only)
3) Gp = (Np - 1) / (Pp - 1)
4) Tg = (Np * (Np - 1)) / (Pp * (Pp - 1))
5) Sk = 0
6) Group, skipping Sk
7) Sk = Sk + Pp
8) If Sk < Np, Goto 6<font size="2" face="Verdana, Helvetica, sans-serif">Looks promising, but I don't understand exactly what you mean by group, skipping sk. Could you show the Np=13 and Pp=3 case I mentioned earlier as an example (since no one has shown it yet)?

[ August 07, 2003, 01:56: Message edited by: cybersol ]

[Captain Kwok]

Originally posted by tesco samoa:
geo you should grab one of those wheel systems for lotteries.

you need a 3 of n wheeler with a filter<font size="2" face="Verdana, Helvetica, sans-serif">This is exactly what he needs! Some sort of calculator that will list all the possible combinations of numbers (i.e. players) for n number of players, and r number of players per game!

[Jack Simth]

A few people posted while I was editing, so I'll put it back up:

Arrangement method:

1) List players
2) Variables
Pp = players per game
Np = Number of players (total)
Gp = Games per player
Tg = Total games
Sk = Skip (counting variable; internal use only)
3) Gp = (Np - 1) / (Pp - 1)
4) Tg = (Np * (Np - 1)) / (Pp * (Pp - 1))
5) Sk = 0
6) Group, skipping Sk
7) Sk = Sk + Pp
8) If Sk < Np, Goto 6
<font size="2" face="Verdana, Helvetica, sans-serif">I might have an off by one error in line 7.

[ August 07, 2003, 09:16: Message edited by: Jack Simth ]

[Ack]

Geoschmo is correct that you cannot use a combination equation for a round robin. This is from some website:

Example:

How many ways can we select three letters from the letters of RSTUV?

n = 5 r = 3

These are: RST, RSU, RSV, RTU, RTV, RUV, STU, STV, SUV and TUV.

From this you can see that, if RSTUV represented players, players would meet more than once (RS for example).

Permutation equations do not work for exactly the same reason.

Geoschmo,

I believe the only way you can avoid having players meet more than once is if the number of players is the square of the number of players per game. Actually another case is if the number of players is equal to the number of players per game (or 1 game). Anything other than this and you'll either having players facing each other multiple times or rounds where players do not play.

Next, the most possible games occurs if the number of players per game is equal to one. In this case the number of games is the summation of A (from A=1 to A= n-1). Where n is the total number of players. This is an important event.

So adjusting for the number of players, which should be a simple division, gives this:

Pg = players per game
n = total number of players

# games = (1/Pg) Summation (A=1 to A=n-1)

Solving a few cases:

Pg = 1, n = 1: # games = 1
Pg = 4, n = 2: # games = 3 (wrong, should be 6)
Pg = 9, n = 3: # games = 12

In summations, having variation between the odd and even entries is fairly common. So you need another equation for the even values, which I'm not going to work out tonight.

I suspect there is a more graceful solution by using some series expansions. Try looking at Taylor, Binomial, Geometric, etc. Series Expansions to find a better solution. To help you along, try determining the number of games required for 25-5 and 36-6.

One more quick thing. The number of games per round is simply n/Pg. So another option would be to use this and find a series that describes the number of rounds.

[tesco samoa]

i posted this earlier

i have a question along this line

say you have 24 numbers and you want to sort them in combinations of 4 where each number only appears once with each other how many combinations would that be ???

now if some one wanted to whip up a little program that does that ( but i can select the numbers (say up to 50), combinations ( 2 to 12 ) and uniqueness ( say once to 6 times ) and can produce a text file output i would be forever thankful

And in VB and send me the source http://forum.shrapnelgames.com/images/icons/icon7.gif

[tesco samoa]

i posted this earlier

i have a question along this line

say you have 24 numbers and you want to sort them in combinations of 4 where each number only appears once with each other how many combinations would that be ???

now if some one wanted to whip up a little program that does that ( but i can select the numbers (say up to 50), combinations ( 2 to 12 ) and uniqueness ( say once to 6 times ) and can produce a text file output i would be forever thankful

And in VB and send me the source http://forum.shrapnelgames.com/images/icons/icon7.gif

[Ack]

The only hard part about that would be using VB. I switched to Perl and haven't used anything else in about 2 years.

Oh yeah. I believe the even equation is simply:

Pg = players per game
n = total number of players

# games = [(1/Pg) Summation (A=1 to A=n)] + 1

[Ack]

Duh! Algorithm.

1. Drop each combination into an array of n elements. Where n is the number of players per game.
2. Sort each array numerically.
3. Compare each array to the next and discard in duplications.
4. Output the remaining arrays into a text file.

Ugly and inefficient, but a P4 should make short work of it.

[LGM]

I guess I missed Erax's solution for 9 players. To appears that how you pick your combinations matters. My alogorythm finds combinations in a certain manner so it only works for certain numbers. A different method might find other solutions.

An exhaustive method would build all combinations and start eliminating redundant combaintions and each iteration it would pick a different combination of redundants to eliminate. This makes the problem even messier.

I tried doing 9 on paper myself and I couldn't do it. Probably because I did it much the same way I programmed it.

Good news for Geosmo is we have known solutions now for 7,9,15, and 31. Maybe someone else can figure out solutions for 11, 13, 17, 19, ...

I know the even numbers will not work because player 1 must play every other player in three player games. Therefore the number of players opposing player one must be a multiple of 2. Adding in player 1 makes the total number of players an Odd number.

[ August 07, 2003, 15:41: Message edited by: LGM ]

[LGM]

I had an SEIV turn to do Last night (my gracious host is running turns manually while PBW is down). Maybe tonight I can tackle writting a program to find combinations for Geo.

It is an interesting problem. This time I will probably write it in Delphi and make it a Windows executible. I'll need to arrange my data a bit better to back track when I get stuck down a blind alley looking for a solution.

I'll publish the code. Delphi code should be fairly easy for C++ or Java programmers to understand as the language is somewhat similiar.

[Erax]

I tried doing 9 on paper myself and I couldn't do it. Probably because I did it much the same way I programmed it. <font size="2" face="Verdana, Helvetica, sans-serif">I did it graphically. I set the players up like this :

1 2 3
4 5 6
7 8 9

Then connected them first horizontally, then vertically, then along the diagonals (you have to imagine that the numbers 'wrap around' for the diagonals). To my surprise, this solved it for nine players.

[tesco samoa]

http://www.singlix.com/download/combinator.html

has the source code for the routine that determines pairing of numbers

It is in turkish but stepping though it will be ok

[Hakuen Kage]

(Loser showed me this thread this morning, I hope I'm not imposing.)

If you were doing it standard elimination style, then it would just be powers of 3. Since each contest would require three participants, you would need three games to fuel each contest. So it would work with 3, 9, 27, 81, 243, 729...

If you want each person to actually play each other person only once, then it's a bit tougher.

In order to determine the number of games it will take for everyone to play everyone, do the following (exactly as Cybersol suggested):

n = Number of players
x = number of games each player must play
z = number of players per game

x = (n-1)/(z-1)

In each game, each player removes two (or the number of people in each game minus one) people from the pool of people that they must play. They obviously don't have to play themselves, so you have to remove from from the total.

From this, we can see that the set with a solution is an odd integer (since x has to be an integer). It is of the form 2x + 1, which in fact means, it is a positive odd integer. Positive because the number of games played must be positive.

Let's try 5. Find x and write down the first player x number of times like so:

1
1

Now go to player two. Since you can't have them playing each other more than once, you need to record it as follows:

1,2
1
2

Proceed to 3

1,2,3
1,
2
3

4:

1,2,3
1,4
2,4
3

5:

1,2,3
1,4,5
2,5
3,4

Here we come to an additional limitation on the number of players required. In this case, we have 10 elements which are not going to fit evenly into games where only three people play at a time. The number of elements must also be divisible by 3 (z).

e = number of elements

e = x * n
or
e = x * [x*(z-1)+1)]

Since e has to be divisible by z

e mod(z) = 0

We can simplify for our particular case

e = 2x^2 + x

So, for all values of x where:

(2x^2 + x) mod(3) = 0

Should be the solutions to your problem. Some of you programmers should be able to write a program to solve that in a heartbeat.

I believe the solutions you will come up with (based on intuition) are that the numbers will be of of the form 3r + 1 and 3r. So all numbers divisible by 3 should work (duh) and all those numbers plus one should work.

Okay, I just verified the 3r + 1 solution set and it works. If someone wants that proof, I'll more than happily post it.

This solves the problem for the number of games that each player must play. So the number of players it works for can be easily backtracked.

2x + 1 = n

So the solution sets for the number of players will be 6r + 1 and 6r + 3. This can actually be seen quite easily by looking at Cybersol's Last post.

With that in mind, someone should be able to easily write a program that uses the method in my example above to arrange the matches. Randomizing it would be tricky, but is still quite doable. Sadly, I can only code in Pascal and I don't have a compiler handy.

Edit: I got my friend's handle wrong. Oops.

[ August 07, 2003, 20:58: Message edited by: Hakuen Kage ]

[Loser]

Somebody asked for a mathematician?
Is he great or what?
Somebody give the teacher an apple.

[SamuraiProgrammer]

Originally posted by Slynky:
One of the good things about chess and its rating system (see my remark about one possible way to have a rating system in SE4 in the "New League" thread) is the wonderful way tournements can be run. Using the rating of the player, you just use Swiss-System pairing and get a tourney done in 4-5 rounds...considering anywhere from 15-30 people.<font size="2" face="Verdana, Helvetica, sans-serif">I play in bridge tournaments where there are 'Swiss' events. It works pretty well in that as you win, you play against people that are winners (and more apt to be at your level). As you lose, you play against others who did not win (and more apt to be at your level).

It ends up being an event that, after the first few rounds, you end up playing against your own level of competition. This makes the matches more enjoyable. Everyone wants to feel competitive.