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 match-ups:

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 2008-04-06 23:54:30