Math problem

[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*PRIMES*PRIMES
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
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
IF MOD(A.COMBO,PRIMES)=0 AND MOD(A.COMBO,PRIMES)=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
J.MOD = MOD(A.COMBO,PRIMES)
K.MOD = MOD(A.COMBO,PRIMES)
L.MOD = MOD(A.COMBO,PRIMES)
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.

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

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.