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
_________
_________
_________ 
_________
_________  
_________ 
_________ 
_________
_________ 
_________ 
_________  
_________
_________ 
_________
_________
Round 1: A vs C, G vs H, B vs D, E vs F
Round 2: A vs H, D vs F
Round 3: A vs F, F wins
Here are some discoveries I made along the way to the proof:
Basic statements:
A : XOR( AC in R1, A in L2)
B : XOR( BD in R1, B = W3)
C : XOR( CE in R1, C in L1)
D : XOR( DG in R1, D in L2)
E : XOR( EF in R1, E in L2)
F : XOR( FH in R1, F = W3)
G : XOR( BG in R1, G in L1)
H : XOR( AH in R1, H in L2)
X : AND( CD not in R1, CD not in R2)
___________
The basic statements combine to:
AC : (A in L2) OR (C in L1)
AH : (A in L2) OR (H in L2)
BD : (B = W3) OR (D in L2)
BG : (B = W3) OR (G in L1)
CE : (C in L1) OR (E in L2)
DG : (D in L2) OR (G in L1)
EF : (E in L2) OR (F = W3)
FH : (H in L2) OR (F = W3)
______________
BD & EF imply that at least one of E,F must be in L2. However, we know from AH that at least one of A,H must be in L2. L2 only has two elements, hence:
L2.1 : XOR(A in L2, H in L2)
L2.2 : XOR(D in L2, E in L2)
Next, suppose G not in L1, then since there is no room for further members in L2, we would have to require that G in R3. Also what
If G not in L1 implies (from G) BG in R1
implies (from B) B = W3
implies (from DG) D in L2
implies (from L2.2) E not in L2
implies (from EF) F = W3
Since at most one of B,F can win the tournament, this gives a contradiction so
GL1 : G in L1
Similarly, what
If C not in L1 implies (from A) A in L2
implies (from CE) E in L2
implies (from D) DG in R1
implies (from B) B = W3
implies (from FH) H in L2
Since A and H cannot simultaneously be in L2, this is a contradiction, so
CL1 : C in L1
___________________
Now what
If B not= W3 implies (from BD) D in L2
implies (from L2.2) E not in L2
implies (from FH) F = W3
so that one of B,F must win the tournament
W3 : XOR(B = W3, F = W3)
___________
Let's summarise what we know about first round matchups:
R1.1 : From B, F: XOR( BD in R1, FH in R1)
R1.2 : From A, H: XOR( AC in R1, AH in R1)
R1.3 : From C, CL1: CE not in R1
R1.4 : From D, E: XOR( DG in R1, EF in R1)
R1.5 : From G, GL1: BG not in R1
R1.6 : From X: CD not in R1
Now consider what happens
If AC not in R1 implies (from R1.2) AH in R1
implies (H committed) not FH in R1
implies (from R1.1) BD in R1
This leaves only C, E, F, G uncommitted. But CF not in R1 (from R1.6) and C cannot be paired with G, since both lose in the first round. This would leave just CE and FG. Summarising, If AC not in R1 then R1 is composed of AH, BD, CE, FG. Consequences of this combination would include (from C) C not in L1. But this is a contradiction. Hence we conclude that AC in R1.
We now work out the consequences of this fact:
AC in R1 implies (from A) A not in L2
implies (from L2.1) H in L2
implies (from FH) F = W3
implies (from B) BD in R1
implies (A not in L2) A = L3
implies (from D) D in L2
implies (from L2.2) E not in L2
implies (from E) EF in R1
implies (only ones remaining) GH in R1
implies (from X) R2 = (A vs H) + (D vs F)
This completes the proof.
Edited on April 7, 2008, 1:03 am

Posted by FrankM
on 20080406 23:54:30 