Math problem

spoon · #1 August 6th, 2003, 08:19 PM

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 · #2 August 6th, 2003, 08:42 PM

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 · #3 August 6th, 2003, 08:48 PM

Quote:

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

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 · #4 August 6th, 2003, 08:50 PM

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 · #5 August 6th, 2003, 08:55 PM

Quote:

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).

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 · #6 August 6th, 2003, 08:55 PM

Quote:

Originally posted by geoschmo:

quote:
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

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.

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 · #7 August 6th, 2003, 09:03 PM

Quote:

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

Oh that? Must be programmer error... heh. That's why you should never listen to them...