[net.puzzle] Who is the thief?

thill@ssc-bee.UUCP (Tom Hill) (03/14/85)

Get out your graph paper and try this one:

One of the six students A, B, C, D, E, F stole a book from the library
last Monday night.  Each student is questioned about whom they saw
at the library, and all tell the truth except the thief (it is possible
one student saw another without in turn being observed, but we assume
that one must have seen the other if both were there at the same time).
A saw B and E; B saw A and F; C saw D and F; D saw A and F; 
E saw B and C; and F saw C and E.  Who is the thief?


This is taken from APPLIED COMBINATORICS by Alan Tucker (page 215).
I highly recommend this text for anyone interested in combinatorics.


Have Fun,

Tom Hill

lhl@lanl.ARPA (03/29/85)

> 
> 
> Get out your graph paper and try this one:
> 
> One of the six students A, B, C, D, E, F stole a book from the library
> last Monday night.  Each student is questioned about whom they saw
> at the library, and all tell the truth except the thief (it is possible
> one student saw another without in turn being observed, but we assume
> that one must have seen the other if both were there at the same time).
> A saw B and E; B saw A and F; C saw D and F; D saw A and F; 
> E saw B and C; and F saw C and E.  Who is the thief?
> 
> 
> This is taken from APPLIED COMBINATORICS by Alan Tucker (page 215).
> I highly recommend this text for anyone interested in combinatorics.
> 
> 
> Have Fun,
> 
> Tom Hill

  Since our mailer doesn't recognize the return address, and there
has been no answer posted, I'll broadcast mine.

  Suppose A and F were not in the library at the same time.  Then
a) if B and D are truthful, they were both there in the interval;
but neither saw the other.
b) if B only lied, then D and E were there in the interval.
c) if D only lied, then B and E were there in the interval.

  By contradiction, A and F were there at the same time, and one of
them is lying.
If it is F, then A and C were both present in the interval between
D and E, but neither saw the other.

  Therefore A is the liar.

  The sequence could have been as follows:

A, B, E, and F arrive in any order (A sees F).

B leaves.

C arrives (A sees C).

E leaves.

D arrives.

A, C, D, and F leave in any order but perhaps A last, with book.

holmes@dalcs.UUCP (Ray Holmes) (04/06/85)

>  The sequence could have been as follows:

>A, B, E, and F arrive in any order (A sees F).

>B leaves.

>C arrives (A sees C).

>E leaves.

>D arrives.

>A, C, D, and F leave in any order but perhaps A last, with book.

My sequence is as follows:
1) A and D arrive (D sees A).
2) D leaves.
3) B and E arrive (A sees B & E, E sees B).
4) A leaves.
5) F arrives (B sees F, F sees E).
6) B leaves.
7) C arrives (C sees F, F sees C, E sees C).
8) E leaves.
9) D arrives (D sees F, C sees F & D).
10) Everyone leaves.

and everyone is telling the truth!!

					Ray