Math problem

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

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*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 ]