All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
The Conversing Club (Posted on 2003-12-29) Difficulty: 4 of 5
There are 10 tables in the Conversing Club and 15 members. Each day, 3 people sit together around each of 5 of 10 possible tables in the club talking to each other.

Every week (7 days) everyone is at the same table with everyone else exactly once. Also, nobody is at the same table twice in the course of a week to provide a change of scenery each time. The first day is as following:

ABC DEF GHI JKL MNO

(The second day A couldn't sit with B, or C; B couldn't sit with C; D couldn't sit with E or F, but could sit with A, B, or C.)

How could their schedule be configured?

(Based on Fifteen Schoolgirls)

See The Solution Submitted by Gamer    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution--computer used | Comment 3 of 6 |
If the members are arranged in a circle, if each member were one vertex of a triangle, they'd be arranged in 5 triangles. The problem is to get all triangles to differ each day.

From looking at Internet treatments of the 15-schoolgirl problem, we see the idea is to arrange 14 members around the outside of the circle, with one at the center. That way, each of the seven days, the entire structure of triangles can be advanced by two units.

So that each person is paired with a given other person only once in the week, each of the sides (chords of the circle, so to speak) that a given person will see in a given direction (say clockwise) must be a different length (different number of persons over). As the motion of the whole set of triangles is by 2 units each day, the vertices are odd and even parity. A chord of even length will connect points of the same parity; a chord of odd length will connect points of opposite parity. The chords of even length will connect to a given point twice: once as length 2n and once as length 14-2n, coming from the other side. The chords of odd length will cover both even and odd parity points.

That means we need two sets of even-length chords--to cover the even and odd parity points. The following program accomplishes this by switching from even to odd beginning points past a chord length of 7. (The chord length is not the strict geometric consideration, but only a counting in the clockwise direction of how many over the chord shifts, even up to 13, which is really 1 counterclockwise). There are 13 chords placed, all of different "size". That's 26 endpoints--enough for each point except for 2 to be at the ends of two chords, as it should be in a triangle. The two vertices that remain with one chord each connecting them are then tied to the center point.

Checks are made to assure that no quadrilaterals, etc. are formed, just triangles. When a set is found, letters are assigned, making the first triangle ABC, etc. The triangle set is then rotated by adding 2*day to each position, mod 4, and the results presented. There are 84 sets that are found. I haven't checked yet whether any are trivially related (just a difference in the order of the days, or people within groups).

In assigning the tables, I just assign the next one that's not used that day and that none of the people in the group have used that week. I don't know if this is optimal, but it finds some of the 84 solutions to the first part of the problem are capable of being done with only 9 tables; some require 10 and others 11. Perhaps with some optimization, all could be done in at most 10; I don't know.

Here are the first four results out of the 84:


0 1 2 4 7 12 6 10 3 11 5 9 8 13 14
ABC 1 DEF 2 GHI 3 JKL 4 MNO 5
CID 2 GLA 1 MFK 3 NEJ 4 HBO 6
DKG 1 MJC 2 HAE 3 BLN 5 FIO 4
GEM 2 HND 1 FCL 3 IJB 5 AKO 7
MLH 1 FBG 3 ADJ 5 KNI 2 CEO 8
HJF 3 AIM 4 CGN 6 EBK 1 DLO 9
FNA 2 CKH 4 DMB 3 LIE 1 GJO 10

0 1 2 4 7 10 8 12 3 11 5 9 6 13 14
ABC 1 DEF 2 GHI 3 JKL 4 MNO 5
CID 2 MLH 1 FAK 3 NEJ 4 GBO 6
DKM 1 GJA 2 HCE 3 BLN 5 FIO 4
MEG 2 FNC 3 ADL 1 IJB 5 HKO 7
GLF 3 HBD 4 CMJ 2 KNI 1 AEO 8
FJH 2 AIM 4 DGN 1 EBK 6 CLO 9
HNA 3 CKG 4 MFB 6 LIE 2 DJO 1

0 1 2 6 9 12 4 8 13 11 5 7 3 10 14
ABC 1 DEF 2 GHI 3 JKL 4 MNO 5
CMG 2 HJA 1 DNB 3 ILE 5 KFO 4
GKD 1 NIC 2 HFM 3 BEJ 4 LAO 6
DLH 2 FBG 1 NAK 3 MJI 5 ECO 7
HEN 1 AMD 2 FCL 3 KIB 4 JGO 8
NJF 3 CKH 4 AGE 6 LBM 1 IDO 9
FIA 2 GLN 5 CDJ 3 EMK 4 BHO 1

0 1 2 8 11 4 12 3 6 13 7 9 5 10 14
ABC 1 DEF 2 GHI 3 JKL 4 MNO 5
CHF 3 NJI 1 AMD 2 BLE 5 KGO 4
FMI 2 GBD 1 CKN 3 HEJ 4 LAO 6
IKD 4 AHN 1 FLG 5 MJB 2 ECO 3
DLN 4 CMG 2 IEA 6 KBH 1 JFO 7
NEG 3 FKA 1 DJC 5 LHM 2 BIO 8
GJA 2 ILC 6 NBF 5 EMK 1 HDO 9

---------
The row of numbers at the top represent the position numbers for the vertices of the triangle, 0 through 13 on the outside; 14 in the center of the circle.

Here's the program. Note that I did not check to make sure that the two points left to team up with the center point were of opposite parity, a necessity so that everyone gets to eat with the center person, but it seems to work out that way anyway.

DEFINT A-Z
DECLARE SUB place (size)
CLEAR , , 4000

DIM SHARED ct(13), hist(14, 2), solCt


ct(0) = 1: ct(1) = 1
hist(1, 1) = 0: hist(1, 2) = 1
CLS
place 2
PRINT solCt

END

SUB place (size)
  FOR ev = 0 TO 12 STEP 2
    IF size <= 7 OR size MOD 2 = 1 THEN i = ev: ELSE i = ev + 1
    j = (i + size) MOD 14
    IF ct(i) < 2 AND ct(j) < 2 THEN
      good = 1
      IF ct(i) AND ct(j) THEN
        FOR sb = 1 TO size - 1
          IF hist(sb, 1) = i THEN other1 = hist(sb, 2)
          IF hist(sb, 2) = i THEN other1 = hist(sb, 1)
          IF hist(sb, 1) = j THEN other2 = hist(sb, 2)
          IF hist(sb, 2) = j THEN other2 = hist(sb, 1)
        NEXT

        IF other1 <> other2 THEN
          good = 0
        ELSE
          '
        END IF
      ELSEIF ct(i) OR ct(j) THEN
        FOR sb = 1 TO size - 1
          IF hist(sb, 1) = i AND ct(hist(sb, 2)) > 1 THEN
           good = 0
          END IF
          IF hist(sb, 2) = i AND ct(hist(sb, 1)) > 1 THEN
            good = 0
          END IF
          IF hist(sb, 1) = j AND ct(hist(sb, 2)) > 1 THEN
            good = 0
          END IF
          IF hist(sb, 2) = j AND ct(hist(sb, 1)) > 1 THEN
            good = 0
          END IF
        NEXT
      END IF
      IF good THEN
        ct(i) = ct(i) + 1: ct(j) = ct(j) + 1
        hist(size, 1) = i: hist(size, 2) = j
        IF size = 13 THEN
          oneCt = 0
          FOR sb = 0 TO 13
           IF ct(sb) = 1 THEN oneCt = oneCt + 1
          NEXT
          IF oneCt = 2 THEN
            REDIM marker(13), soln(5, 3)
            solUpto = 0
            FOR sb = 1 TO 12
              u1 = hist(sb, 1): u2 = hist(sb, 2)
              IF ct(u1) > 1 AND ct(u2) > 1 AND marker(u1) = 0 THEN
                marker(u1) = 1: marker(u2) = 1
                FOR sb2 = sb + 1 TO 13
                  IF hist(sb2, 1) = u1 OR hist(sb2, 2) = u1 OR hist(sb2, 1) = u2 OR hist(sb2, 2) = u2 THEN
                    IF hist(sb2, 1) <> u1 AND hist(sb2, 1) <> u2 THEN
                     u3 = hist(sb2, 1): marker(u3) = 1
                    ELSE
                     u3 = hist(sb2, 2): marker(u3) = 1
                    END IF
                  END IF
                NEXT
                solUpto = solUpto + 1
                soln(solUpto, 1) = u1: soln(solUpto, 2) = u2: soln(solUpto, 3) = u3
                PRINT u1; u2; u3; " ";
              END IF
            NEXT
            pcUpto = 0
            FOR sb = 0 TO 13
             IF ct(sb) = 1 THEN
              pcUpto = pcUpto + 1
              soln(5, pcUpto) = sb
              PRINT sb;
             END IF
            NEXT
            soln(5, 3) = 14
            PRINT 14
            solCt = solCt + 1
            GOSUB show1
            'IF solCt / 40 = INT(solCt / 40) THEN DO: LOOP UNTIL INKEY$ > ""
          END IF
        ELSE
          place size + 1
        END IF
        ct(i) = ct(i) - 1: ct(j) = ct(j) - 1
      END IF
    END IF
  NEXT

EXIT SUB

show1:
  REDIM lets$(14), tbl(14, 20)
  assnCt = 0
  FOR grp = 1 TO 5
   FOR memb = 1 TO 3
    lets$(soln(grp, memb)) = CHR$(65 + assnCt)
    assnCt = assnCt + 1
   NEXT
  NEXT
  FOR day = 0 TO 6
    REDIM tblDay(20)
    FOR grp = 1 TO 5
      tblTry = 1
      FOR memb = 1 TO 3
       IF grp = 5 AND memb = 3 THEN
        PRINT lets$(soln(5, 3));
        sb = soln(5, 3)
       ELSE
        sb = (soln(grp, memb) + 2 * day) MOD 14
        PRINT lets$((soln(grp, memb) + 2 * day) MOD 14);
       END IF
       DO WHILE tbl(sb, tblTry) > 0 OR tblDay(tblTry) > 0
         tblTry = tblTry + 1
       LOOP
      NEXT
      DO WHILE tbl(sb, tblTry) > 0 OR tblDay(tblTry) > 0
        tblTry = tblTry + 1
      LOOP
      tblDay(tblTry) = 1
      tbl(sb, tblTry) = 1
      PRINT tblTry; " ";
    NEXT
    PRINT
  NEXT
  PRINT
  DO: LOOP UNTIL INKEY$ > ""
RETURN

END SUB


  Posted by Charlie on 2003-12-30 10:56:46
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information