Home > Logic > Liars and Knights
| Knave Contest (Posted on 2008-04-03) |
 |
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
_________
|_________
_________| |
|_________
_________ | |
|_________| |
_________| |
|_________
_________ |
|_________ |
_________| | |
|_________|
_________ |
|_________|
_________|
|
|
Submitted by Brian Smith
|
|
Rating: 4.0000 (3 votes)
|
|
|
Solution:
|
(Hide)
|
My solution is below. Other solutions are given in the comments, but FrankM's solution is very interesting for its use of boolean logic.
Each knave has one of two possible truth patterns, either true then false (TF) or false then true (FT).
Consider Bert, Dave, and Gary's first statements. At most one of those can be true. Consider the first statements of the other five. At most two of those can be true. Then there must be at most three TF knaves.
Consider Bert and Fred's second statements. At least one of those must be false. Consider Alex, Dave, Eddy, and Hank's second statements. At least two of those must be false. Then there must be at least three TF knaves.
Since there are at least three and at most three TF knaves, there must be exactly three TF knaves. From each person's first statements, exactly one TF knave is in the set {Bert, Dave, Gary} and exactly two are in the set {Alex, Carl, Eddy, Fred, Hank}. From each person's second statements, exactly one TF knave is in the set {Bert, Fred} and exactly two are in the set {Alex, Dave, Eddy, Hank}.
From the sets described above, there are six sets of three TF knaves possible:
1: Dave, Fred, Hank
2: Dave, Eddy, Fred
3: Bert, Eddy, Hank
4: Alex, Dave, Fred
5: Alex, Bert, Hank
6: Alex, Bert, Eddy
Case 1: Dave, Fred, Hank are TF knaves
According to Fred's first statement, his first game was against Hank. According to Hank's first statement, his first game was against Alex. This is a contradiction, so this case is not the solution.
Case 2: Dave, Eddy, Fred are TF knaves
According to Eddy's first statement, his first game was against Fred. According to Fred's first statement, his first game was against Hank. This is a contradiction, so this case is not the solution.
Case 3: Bert, Eddy, Hank are TF knaves
The first round pairings according to each person's first statements are Bert vs Dave, Eddy vs Fred, Alex vs Hank, and Carl vs Gary. Carl and Gary are both FT knaves, so their second statements must both be true. However, both claim to lose in the first round, which is a contradiction since one must win in the first round. Then this case is not the solution.
Case 4: Alex, Dave, Fred are TF knaves
The first round pairings according to each person's first statements are Alex vs Carl, Dave vs Gary, Fred vs Hank, and Bert vs Eddy. Bert and Eddy are both FT knaves, so their second statements must both be true. However, both claim to make it past the first round, which is a contradiction since one must lose in the first round. Then this case is not the solution.
Case 5: Alex, Bert, Hank are TF knaves
According to Alex's first statement, his first game was against Carl. According to Hank's first statement, his first game was against Alex. This is a contradiction, so this case is not the solution.
Case 6: Alex, Bert, Eddy are TF knaves
The first round pairings according to each person's first statements are Alex vs Carl, Bert vs Dave, Eddy vs Fred, and Gary vs Hank. Using each person's second statements and the given fact that Carl and Dave could potentially play against each other only if they were the final two contestants, the complete tournament grid can be filled in as follows:
Round 1 | Round 2 | Round 3 | Winner
__Alex___
|__Alex___
__Carl___| |
|__Alex___
__Gary___ | |
|__Hank___| |
__Hank___| |
|__Fred___
__Bert___ |
|__Dave___ |
__Dave___| | |
|__Fred___|
__Eddy___ |
|__Fred___|
__Fred___|
|
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (1)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (23)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
