Math problem

Ack · #1 August 7th, 2003, 02:46 AM

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 · #2 August 7th, 2003, 02:48 AM

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

tesco samoa · #3 August 7th, 2003, 02:49 AM

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

Ack · #4 August 7th, 2003, 02:56 AM

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 · #5 August 7th, 2003, 03:01 AM

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

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 · #7 August 7th, 2003, 04:57 PM

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.