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

_________
         |_________
_________|         |
                   |_________
_________          |         |
         |_________|         |
_________|                   |
                             |_________
_________                    |
         |_________          |
_________|         |         |
                   |_________|
_________          |
         |_________|
_________|

Others have already presented the answer, but here goes an attempt to show how to derive the solution without a computer.

First, call a knave + if their first statement is true and their second statement is false; call a knave - if the opposite is true. Also, abbreviate all of the knaves by their first initials.

Suppose C is a +. Then C didn't lose in round one and so won round one. But E must then be a - since his first statement is false, and so E lost in round 2. But to do that, E would need to win round one, so the assumption that C is a + leads to a contradiction and C is therefore a -. The same argument about G and B establishes that G too is a -. Also, both C and G lost in round one.

Suppose F is a +. Then F played H in round one,  H is a - and lost in round 2 and E is also a - and also lost in round two. Since H and E lost in round two, they both won their round one games. Also, since there were only two round two games, everyone else who claims to have lost in round 2 is therefore a +. So A and D are +, and A played C and D played G in round one. That means B played E (the only remaining pair) and B is a -. But if this is so, then B won the contest and therefore won his round one game. That means both B and E (who played each other in round one) must have won--a contradiction. So F is a - and won the contest.

F won the contest, so B is a + and played D in round one. D is therefore a - and lost in round two.

Now, H and A are not both + (because their first statements are incompatible). So at least one of them is a - and lost in the second round, as did D (above). But no more than two of A,D,E,H can be - because no more than two games can be lost in the 2nd round so E is a + as is one of A and H. Since E is a +, E played F in round one and lost.

That leaves A and H who played C and G (since G and C couldn't have played each other and both lost.) That makes H the other - and A a +. Which in turn means A played C and one in round one and H played G and won in round one. A didn't lose in round one (he won) and he didn't lose in round two (or both his statements would be true) and he didn't win (F did) so A lost in round three (to F)To summarize at this point:

Round one

A beats C
D beats B
F beats E
H beats G

Round two

A wins
F wins
D loses
H loses

Round three

F beats A

Almost there. We just have to determine who beat whom in round two. To do that, note that the person who beat C and D can't play each other in round two. If they did, then had C won C and D would have met each other as other than the final contestants which is prohibited by the terms of the problem. So A did not defeat D and instead beat H

The final tree:

A
   A
C
      A
H
   H
G
         F

F
   F
E
      F
D
   D
B
     

Posted by Paul on 2008-04-04 01:02:19