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)
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 |
solution--computer used
