Unfortunately the Conversing Club has lost members so now they are down to 12 members. Many of the members felt talking with 3 members about things ended up with 2-against-1 situations. To address this pain, the members decided to have only 2 people sit at a table each day. They also decided that with the decline in members, they only needed 6 tables and didn't need "move every time" rule. (In other words, there aren't any extra tables once two people are placed at each of 6 tables and a person can sit at a particular table more than once each "cycle") The first day they sit as following:
AB CD EF GH IJ KL
(So the second day A could sit with C or D (and others too), but not B. C could sit with A, B or E (and others too) but not D)
After 11 days, they wouldn't have anyone left to talk with, so would repeat their schedule. Their schedule was still constructed such that everyone would talk to everyone else exactly once. How was it constructed?
This problem is solved similarly to the original Conversing Club problem, where three people met each day. In that one, the sets could be found by imagining one person's name in the center of a circle and the other names surrounding it along that circle. Triangles would be formed, most connecting three points (names) on the circle, but one connecting two points on the circle with the center. The edges that form chords would have to all span different lengths. Then each day, the set of triangles was rotated one position relative to the names, or the names relative to the triangles--same thing.
This is similar, except that instead of triangles we just have lines connecting two names. Again, one name is in the center and 11 names are on the circumference, and one line connects the center to a point (call it point 1) on the circle. The chords are among the remaining 10 positions and must each be a different length. One such way is to connect points 2 and 3 for length 1; 4 and 7 for length 3; 5 and 9 for length 5; 6 and 11 for length 5; and 8 and 10 for length 2, summarized as
2 3 ( 1); 4 7 ( 3); 5 9 ( 4); 6 11 ( 5); 8 10 ( 2)
Note that spans, n, larger than 5 are just formed by the same chord as 11 - n.
All the ways of doing this are:
2 3 ( 1); 4 7 ( 3); 5 9 ( 4); 6 11 ( 5); 8 10 ( 2)
2 3 ( 1); 4 9 ( 5); 5 7 ( 2); 6 10 ( 4); 8 11 ( 3)
2 4 ( 2); 3 6 ( 3); 5 10 ( 5); 7 11 ( 4); 8 9 ( 1)
2 4 ( 2); 3 7 ( 4); 5 8 ( 3); 6 11 ( 5); 9 10 ( 1)
2 4 ( 2); 3 10 ( 7); 5 11 ( 6); 6 9 ( 3); 7 8 ( 1)
2 5 ( 3); 3 7 ( 4); 4 9 ( 5); 6 8 ( 2); 10 11 ( 1)
2 5 ( 3); 3 8 ( 5); 4 6 ( 2); 7 11 ( 4); 9 10 ( 1)
2 5 ( 3); 3 9 ( 6); 4 11 ( 7); 6 7 ( 1); 8 10 ( 2)
2 6 ( 4); 3 4 ( 1); 5 10 ( 5); 7 9 ( 2); 8 11 ( 3)
2 6 ( 4); 3 8 ( 5); 4 5 ( 1); 7 10 ( 3); 9 11 ( 2)
2 6 ( 4); 3 11 ( 8); 4 10 ( 6); 5 7 ( 2); 8 9 ( 1)
2 7 ( 5); 3 4 ( 1); 5 8 ( 3); 6 10 ( 4); 9 11 ( 2)
2 7 ( 5); 3 5 ( 2); 4 8 ( 4); 6 9 ( 3); 10 11 ( 1)
2 8 ( 6); 3 6 ( 3); 4 11 ( 7); 5 7 ( 2); 9 10 ( 1)
2 8 ( 6); 3 10 ( 7); 4 7 ( 3); 5 6 ( 1); 9 11 ( 2)
2 8 ( 6); 3 11 ( 8); 4 5 ( 1); 6 10 ( 4); 7 9 ( 2)
2 9 ( 7); 3 4 ( 1); 5 11 ( 6); 6 8 ( 2); 7 10 ( 3)
2 9 ( 7); 3 5 ( 2); 4 10 ( 6); 6 7 ( 1); 8 11 ( 3)
2 9 ( 7); 3 11 ( 8); 4 6 ( 2); 5 10 ( 5); 7 8 ( 1)
2 10 ( 8); 3 7 ( 4); 4 6 ( 2); 5 11 ( 6); 8 9 ( 1)
2 10 ( 8); 3 8 ( 5); 4 11 ( 7); 5 6 ( 1); 7 9 ( 2)
2 10 ( 8); 3 9 ( 6); 4 5 ( 1); 6 8 ( 2); 7 11 ( 4)
2 11 ( 9); 3 6 ( 3); 4 10 ( 6); 5 9 ( 4); 7 8 ( 1)
2 11 ( 9); 3 9 ( 6); 4 8 ( 4); 5 6 ( 1); 7 10 ( 3)
2 11 ( 9); 3 10 ( 7); 4 9 ( 5); 5 8 ( 3); 6 7 ( 1)
------
Then we need to assign names to positions and then start rotating them. We have to assign the positions so that we start out with AB, CD, EF, GH, IJ and KL as the matchups. Here's a way:
2 3 ( 1); 4 7 ( 3); 5 9 ( 4); 6 11 ( 5); 8 10 ( 2);
A BCDEGIFKHLJ AB CD EF GH IJ KL
A JBCDEGIFKHL AJ BC DI EK FH GL
A LJBCDEGIFKH AL BJ CG DF EH IK
A HLJBCDEGIFK AH BE CI DK FG JL
A KHLJBCDEGIF AK BG CF DJ EI HL
A FKHLJBCDEGI AF BI CL DG EJ HK
A IFKHLJBCDEG AI BH CE DL FK GJ
A GIFKHLJBCDE AG BD CH EL FI JK
A EGIFKHLJBCD AE BK CJ DH FL GI
A DEGIFKHLJBC AD BL CK EG FJ HI
A CDEGIFKHLJB AC BF DE GK HJ IL
----
where A is placed at the center, where he remains. B starts off at position 1 so in the first set he is paired with A. C and D are in positions 2 and 3 of the circumference as they are connected, while E and F are at positions 4 and 7, as that is the next connected pair, etc.
So each line above shows the center person, the order of names around that center, and then the pairings, shown alphabetically, based upon the positions listed at the top.
Other sets that work come from the other sets of chords, such as:
2 3 ( 1); 4 9 ( 5); 5 7 ( 2); 6 10 ( 4); 8 11 ( 3);
A BCDEGIHKFJL AB CD EF GH IJ KL
A LBCDEGIHKFJ AL BC DK EI FG HJ
A JLBCDEGIHKF AJ BL CH DG EK FI
A FJLBCDEGIHK AF BI CE DH GK JL
A KFJLBCDEGIH AK BD CI EH FJ GL
A HKFJLBCDEGI AH BG CL DI EJ FK
A IHKFJLBCDEG AI BJ CG DF EL HK
A GIHKFJLBCDE AG BE CK DJ FL HI
A EGIHKFJLBCD AE BH CF DL GI JK
A DEGIHKFJLBC AD BK CJ EG FH IL
A CDEGIHKFJLB AC BF DE GJ HL IK
2 4 ( 2); 3 6 ( 3); 5 10 ( 5); 7 11 ( 4); 8 9 ( 1);
A BCEDGFIKLHJ AB CD EF GH IJ KL
A JBCEDGFIKLH AJ BE CG DL FH IK
A HJBCEDGFIKL AH BD CJ EK FI GL
A LHJBCEDGFIK AL BH CI DK EJ FG
A KLHJBCEDGFI AK BF CH DG EI JL
A IKLHJBCEDGF AI BL CF DE GJ HK
A FIKLHJBCEDG AF BG CE DH IL JK
A GFIKLHJBCED AG BC DJ EL FK HI
A DGFIKLHJBCE AD BJ CK EH FL GI
A EDGFIKLHJBC AE BI CL DF GK HJ
A CEDGFIKLHJB AC BK DI EG FJ HL
2 4 ( 2); 3 7 ( 4); 5 8 ( 3); 6 11 ( 5); 9 10 ( 1);
A BCEDGIFHKLJ AB CD EF GH IJ KL
A JBCEDGIFHKL AJ BE CI DF GL HK
A LJBCEDGIFHK AL BG CJ DK EI FH
A KLJBCEDGIFH AK BL CG DJ EH FI
A HKLJBCEDGIF AH BD CF EL GI JK
A FHKLJBCEDGI AF BI CK DG EJ HL
A IFHKLJBCEDG AI BH CL DE FK GJ
A GIFHKLJBCED AG BK CE DL FJ HI
A DGIFHKLJBCE AD BC EK FG HJ IL
A EDGIFHKLJBC AE BJ CH DI FL GK
A CEDGIFHKLJB AC BF DH EG IK JL
or by putting others than A in the center:
2 3 ( 1); 4 7 ( 3); 5 9 ( 4); 6 11 ( 5); 8 10 ( 2);
B ACDEGIFKHLJ AB CD EF GH IJ KL
B JACDEGIFKHL AC BJ DI EK FH GL
B LJACDEGIFKH AJ BL CG DF EH IK
B HLJACDEGIFK AE BH CI DK FG JL
B KHLJACDEGIF AG BK CF DJ EI HL
B FKHLJACDEGI AI BF CL DG EJ HK
B IFKHLJACDEG AH BI CE DL FK GJ
B GIFKHLJACDE AD BG CH EL FI JK
B EGIFKHLJACD AK BE CJ DH FL GI
B DEGIFKHLJAC AL BD CK EG FJ HI
B CDEGIFKHLJA AF BC DE GK HJ IL
or
2 3 ( 1); 4 7 ( 3); 5 9 ( 4); 6 11 ( 5); 8 10 ( 2);
C DABEGIFKHLJ AB CD EF GH IJ KL
C JDABEGIFKHL AD BI CJ EK FH GL
C LJDABEGIFKH AG BF CL DJ EH IK
C HLJDABEGIFK AI BK CH DE FG JL
C KHLJDABEGIF AF BJ CK DG EI HL
C FKHLJDABEGI AL BG CF DI EJ HK
C IFKHLJDABEG AE BL CI DH FK GJ
C GIFKHLJDABE AH BD CG EL FI JK
C EGIFKHLJDAB AJ BH CE DK FL GI
C BEGIFKHLJDA AK BC DL EG FJ HI
C ABEGIFKHLJD AC BE DF GK HJ IL
---
Each choice of set of chords and identity of the center person seems to produce a unique set.
The program, that finds the appropriate set of chords and then assigns letters is:
DECLARE SUB matchup ()
DIM SHARED cnct(11), dist(5), mcount
CLS
OPEN "conclub2.txt" FOR OUTPUT AS #2
matchup
CLOSE
SUB matchup
DIM ans$(6)
FOR i = 2 TO 10
IF cnct(i) = 0 THEN
FOR j = i + 1 TO 11
d = j - i: IF d > 5 THEN d = 11 - d
IF dist(d) = 0 AND cnct(j) = 0 THEN
cnct(i) = j: cnct(j) = i
dist(d) = 1
mcount = mcount + 1
IF mcount = 5 THEN
'****** Report the Result
FOR p = 2 TO 11
IF p < cnct(p) THEN
PRINT USING "### ## (##);"; p; cnct(p); cnct(p) - p;
PRINT #2, USING "### ## (##);"; p; cnct(p); cnct(p) - p;
END IF
NEXT
PRINT
PRINT #2,
' Assign names A - L
c$ = "A"
round$ = "B" + SPACE$(10)
strPsn = 1
FOR p = 2 TO 11
IF p < cnct(p) THEN
MID$(round$, p, 1) = MID$("CDEFGHIJKL", strPsn, 1)
MID$(round$, cnct(p), 1) = MID$("CDEFGHIJKL", strPsn + 1, 1)
strPsn = strPsn + 2
END IF
NEXT
FOR day = 1 TO 11
ans$(1) = c$ + LEFT$(round$, 1)
a = 2
FOR p = 2 TO 11
IF p < cnct(p) THEN
ans$(a) = MID$(round$, p, 1) + MID$(round$, cnct(p), 1)
a = a + 1
END IF
NEXT
' sort answers within pairs:
FOR a = 1 TO 6
IF RIGHT$(ans$(a), 1) < LEFT$(ans$(a), 1) THEN
ans$(a) = RIGHT$(ans$(a), 1) + LEFT$(ans$(a), 1)
END IF
NEXT
' sort the pairs:
DO
fl = 0
FOR a = 2 TO 6
IF ans$(a) < ans$(a - 1) THEN
SWAP ans$(a), ans$(a - 1): fl = 1
END IF
NEXT
LOOP UNTIL fl = 0
PRINT c$; " "; round$; " ";
PRINT #2, c$; " "; round$; " ";
FOR a = 1 TO 6
PRINT ans$(a); " ";
PRINT #2, ans$(a); " ";
NEXT
PRINT
PRINT #2,
' rotate the people:
round$ = RIGHT$(round$, 1) + LEFT$(round$, LEN(round$) - 1)
NEXT
'*************************
ELSE
matchup
END IF
cnct(i) = 0: cnct(j) = 0
dist(d) = 0
mcount = mcount - 1
END IF
NEXT
EXIT FOR
END IF
NEXT
END SUB
|
|
Posted by Charlie
on 2004-02-06 13:09:23 |
solution
