Six friends were playing a game of indoor soccer together, but got into a fight during their game. Upset with each other, they decided to position themselves in the (square) 300x300 foot gymnasium so as to maximize the distance between the closest pair. Where should they each stand?

(In reply to Better Still by bernie)

Here is a QBASIC program that finds your solution.

DEFLNG H-Q: DEFDBL A-G, R-Z
M = 7: N = M: MN = M * N
LSQTOP = (M - 1) * (M - 1) + (N - 1) * (N - 1): LSQMAXIMIN = 0
MN1 = MN - 1: MN2 = MN - 2: MN3 = MN - 3: MN4 = MN - 4: MN5 = MN - 5
K0 = 0: K1 = 1: K2 = 2: K3 = 3: K4 = 4: K5 = 5
KNT = 0
WHILE K0 < MN5
  WHILE K1 < MN4
    WHILE K2 < MN3
      WHILE K3 < MN2
        WHILE K4 < MN1
          WHILE K5 < MN
          REM PRINT K0; K1; K2; K3; K4; K5
          J0 = K0 \ M: J1 = K1 \ M: J2 = K2 \ M: J3 = K3 \ M: J4 = K4 \ M: J5 = K5 \ M
          I0 = K0 - J0 * M: I1 = K1 - J1 * M: I2 = K2 - J2 * M: I3 = K3 - J3 * M: I4 = K4 - J4 * M: I5 = K5 - J5 * M
          J01 = J1 - J0: J02 = J2 - J0: J03 = J3 - J0: J04 = J4 - J0: J05 = J5 - J0
          J12 = J2 - J1: J13 = J3 - J1: J14 = J4 - J1: J15 = J5 - J1
          J23 = J3 - J2: J24 = J4 - J2: J25 = J5 - J2
          J34 = J4 - J3: J35 = J5 - J3
          J45 = J5 - J4
          I01 = I1 - I0: I02 = I2 - I0: I03 = I3 - I0: I04 = I4 - I0: I05 = I5 - I0
          I12 = I2 - I1: I13 = I3 - I1: I14 = I4 - I1: I15 = I5 - I1
          I23 = I3 - I2: I24 = I4 - I2: I25 = I5 - I2
          I34 = I4 - I3: I35 = I5 - I3
          I45 = I5 - I4
          H01 = I01 * I01 + J01 * J01
          H02 = I02 * I02 + J02 * J02
          H03 = I03 * I03 + J03 * J03
          H04 = I04 * I04 + J04 * J04
          H05 = I05 * I05 + J05 * J05
          H12 = I12 * I12 + J12 * J12
          H13 = I13 * I13 + J13 * J13
          H14 = I14 * I14 + J14 * J14
          H15 = I15 * I15 + J15 * J15
          H23 = I23 * I23 + J23 * J23
          H24 = I24 * I24 + J24 * J24
          H25 = I25 * I25 + J25 * J25
          H34 = I34 * I34 + J34 * J34
          H35 = I35 * I35 + J35 * J35
          H45 = I45 * I45 + J45 * J45
          LSQMIN = LSQTOP
          IF H01 < LSQMIN THEN LSQMIN = H01
          IF H02 < LSQMIN THEN LSQMIN = H02
          IF H03 < LSQMIN THEN LSQMIN = H03
          IF H04 < LSQMIN THEN LSQMIN = H04
          IF H05 < LSQMIN THEN LSQMIN = H05
          IF H12 < LSQMIN THEN LSQMIN = H12
          IF H13 < LSQMIN THEN LSQMIN = H13
          IF H14 < LSQMIN THEN LSQMIN = H14
          IF H15 < LSQMIN THEN LSQMIN = H15
          IF H23 < LSQMIN THEN LSQMIN = H23
          IF H24 < LSQMIN THEN LSQMIN = H24
          IF H25 < LSQMIN THEN LSQMIN = H25
          IF H34 < LSQMIN THEN LSQMIN = H34
          IF H35 < LSQMIN THEN LSQMIN = H35
          IF H45 < LSQMIN THEN LSQMIN = H45
          IF LSQMIN > LSQMAXIMIN THEN
          LSQMAXIMIN = LSQMIN
          PRINT LSQMIN
          PRINT K0; K1; K2; K3; K4; K5
          PRINT I0; J0; I1; J1; I2; J2; I3; J3; I4; J4; I5; J5
          PRINT I01; I02; I03; I04; I05; I12; I13; I14; I15; I23; I24; I25; I34; I35; I45
          PRINT J01; J02; J03; J04; J05; J12; J13; J14; J15; J23; J24; J25; J34; J35; J45
          PRINT H01; H02; H03; H04; H05; H12; H13; H14; H15; H23; H24; H25; H34; H35; H45
          PRINT "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"
          END IF
          K5 = K5 + 1
          KNT = KNT + 1
          WEND
        K4 = K4 + 1: K5 = K4 + 1
        WEND
      K3 = K3 + 1: K4 = K3 + 1: K5 = K4 + 1
      WEND
      K2 = K2 + 1: K3 = K2 + 1: K4 = K3 + 1: K5 = K4 + 1
    WEND
  K1 = K1 + 1: K2 = K1 + 1: K3 = K2 + 1: K4 = K3 + 1: K5 = K4 + 1
  WEND
K0 = K0 + 1: K1 = K0 + 1: K2 = K1 + 1: K3 = K2 + 1: K4 = K3 + 1: K5 = K4 + 1
WEND
PRINT KNT, LSQMAXIMIN, LSQTOP
PRINT "___________________________________________________________________"

The running time is already very long for the 7x7 grid used here, but increasing to 8x8 or 9x9 give really really long running times and a poorer result! 

Posted by Richard on 2004-08-19 13:36:21