Alex, Bert, Carl, Dave, Eddy, Fred, Gary, and Hank have just finished a single elimination contest. They are all knaves, meaning each one alternates between making true and false statements. Each person makes two statements about the contest as follows:
Alex:
1: I played against Carl in the first round.
2: I lost in round 2.
Bert:
1: I played against Dave in the first round.
2: I won the contest.
Carl:
1: I played against Eddy in the first round.
2: I lost in round 1.
Dave:
1: I played against Gary in the first round.
2: I lost in round 2.
Eddy:
1: I played against Fred in the first round.
2: I lost in round 2.
Fred:
1: I played against Hank in the first round.
2: I won the contest.
Gary:
1: I played against Bert in the first round.
2: I lost in round 1.
Hank:
1: I played against Alex in the first round.
2: I lost in round 2.
The contest was setup in a way so that the only way Carl and Dave would play against each other was if they were the final two contestants.
Determine the pairs of players for all seven games in the contest with the given statements.
Round 1 | Round 2 | Round 3 | Winner
_________
|_________
_________| |
|_________
_________ | |
|_________| |
_________| |
|_________
_________ |
|_________ |
_________| | |
|_________|
_________ |
|_________|
_________|
WLOG, we can assume Carl was in the topmost match in the first round, and Dave was in the bottommost. In line with that, also, statements about playing against either in the first round can be translated into statements about being in the topmost or bottommost match in that round.
In the program, the list of contestants' initials, cont$, is in the sequence: winner of topmost match, loser of topmost match, winner of second match, loser of second match, etc. (within first round).
For each of the 40,320 permutations of the eight initials in which c occurs in the first two and d in the last two (there are 720 of these), the program evaluates the truth values of the 16 statements for each of the 8 possible sets of results in rounds 2 and 3 (the results in round 1 are determined by the odd/even parity of positions within the string), so only 8*720=5,760 sets need to be thoroughly evaluated.
DECLARE SUB permute (a$)
cont$ = "abcdefgh"
true = 1
CLS
h$ = cont$
DO
IF INSTR(cont$, "c") <= 2 AND INSTR(cont$, "d") >= 7 THEN
IF MID$(cont$, 3, 1) < MID$(cont$, 4, 1) THEN
low2$ = MID$(cont$, 3, 1):
ELSE
low2$ = MID$(cont$, 4, 1)
END IF
IF MID$(cont$, 5, 1) < MID$(cont$, 6, 1) THEN
low3$ = MID$(cont$, 5, 1):
ELSE
low3$ = MID$(cont$, 6, 1)
END IF
ct = ct + 1
r2$ = MID$(cont$, 1, 1) + MID$(cont$, 3, 1) + MID$(cont$, 5, 1) + MID$(cont$, 7, 1)
' permutations take care of who is winner of each round 1 contest
FOR r2win1 = 0 TO 1
FOR r2win2 = 0 TO 1
r3$ = MID$(r2$, 1 + r2win1, 1) + MID$(r2$, 3 + r2win2, 1)
FOR r3win = 0 TO 1
winner$ = MID$(r3$, 1 + r3win, 1)
IF INSTR(cont$, "a") <= 2 THEN a1 = true: ELSE a1 = 0
IF INSTR(r2$, "a") > 0 AND INSTR(r3$, "a") = 0 THEN a2 = true: ELSE a2 = 0
IF a1 + a2 = 1 THEN
IF INSTR(cont$, "b") >= 7 THEN b1 = true: ELSE b1 = 0
IF winner$ = "b" THEN b2 = 1: ELSE b2 = 0
IF b1 + b2 = 1 THEN
ix1 = INSTR(cont$, "ce")
ix2 = INSTR(cont$, "ec")
IF ix1 MOD 2 = 1 OR ix2 MOD 2 = 1 THEN c1 = true: ELSE c1 = false
IF INSTR(r2$, "c") = 0 THEN c2 = true: ELSE c2 = false
IF c1 + c2 = 1 THEN
ix1 = INSTR(cont$, "dg")
ix2 = INSTR(cont$, "gd")
IF ix1 MOD 2 = 1 OR ix2 MOD 2 = 1 THEN d1 = true: ELSE d1 = false
IF INSTR(r2$, "d") > 0 AND INSTR(r3$, "d") = 0 THEN d2 = true: ELSE d2 = 0
IF d1 + d2 = 1 THEN
ix1 = INSTR(cont$, "ef")
ix2 = INSTR(cont$, "fe")
IF ix1 MOD 2 = 1 OR ix2 MOD 2 = 1 THEN e1 = true: ELSE e1 = false
IF INSTR(r2$, "e") > 0 AND INSTR(r3$, "e") = 0 THEN e2 = true: ELSE e2 = 0
IF e1 + e2 = 1 THEN
ix1 = INSTR(cont$, "fh")
ix2 = INSTR(cont$, "hf")
IF ix1 MOD 2 = 1 OR ix2 MOD 2 = 1 THEN f1 = true: ELSE f1 = false
IF winner$ = "f" THEN f2 = true: ELSE f2 = false
IF f1 + f2 = 1 THEN
ix1 = INSTR(cont$, "gb")
ix2 = INSTR(cont$, "bg")
IF ix1 MOD 2 = 1 OR ix2 MOD 2 = 1 THEN g1 = true: ELSE g1 = false
IF INSTR(r2$, "g") = 0 THEN g2 = true: ELSE g2 = 0
IF g1 + g2 = 1 THEN
ix1 = INSTR(cont$, "ha")
ix2 = INSTR(cont$, "ah")
IF ix1 MOD 2 = 1 OR ix2 MOD 2 = 1 THEN h1 = true: ELSE h1 = 0
IF INSTR(r2$, "h") > 0 AND INSTR(r3$, "h") = 0 THEN h2 = true: ELSE h2 = 0
IF h1 + h2 = 1 THEN
PRINT cont$: PRINT r2$: PRINT r3$: PRINT winner$
PRINT a1; a2; " ";
PRINT b1; b2; " ";
PRINT c1; c2; " ";
PRINT d1; d2; " ";
PRINT e1; e2; " ";
PRINT f1; f2; " ";
PRINT g1; g2; " ";
PRINT h1; h2; " "
PRINT
END IF
END IF
END IF
END IF
END IF
END IF
END IF
END IF
NEXT
NEXT
NEXT
END IF
permute cont$
LOOP UNTIL cont$ = h$
finds
achgfedb
ahfd
af
f
1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1
where achgfedb is the order of contestants in the first round, from top to bottom on the chart; ahfd is the order of the contestants in the second colum of the chart, again from top to bottom; af are the two players in round 3; and f is the winner.
The 1's and 0's represent true(1) and false(0) statements in the order presented, so the first statements of Alex, Bert and Eddy were their true statements, while the others' second statements were the true ones.
Translated, the above data yields the board filled out as follows:
Alex
Carl Alex
Alex
Hank Hank
Gary
Fred
Fred
Eddy Fred
Fred
Dave Dave
Bert
Of course any of the paired players in the first round could be interchanged, but then we'd have 16 solutions, and even more (64 altogether) if the top two matches in the first round could be switched, and/or the bottom two matches; and that would double, if we switched Dave's pair of matches with Alex's pair of matches.
|
|
Posted by Charlie
on 2008-04-03 14:34:52 |
computer solution
