Math problem

[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

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

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:

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]

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

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

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 ]

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