All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic > Liars and Knights
Knave Contest (Posted on 2008-04-03) Difficulty: 4 of 5
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

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

See The Solution Submitted by Brian Smith    
Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 3 of 8 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information