Problem of the Week 1081

Who Stole the Book

Six students visited the library on the day a rare book was stolen. Each student entered once, stayed for some time, and left. For any two of them that were in the library at the same time, at least one of them saw the other. The dean questioned the students and learned the following:

Student     Reported seeing
Alice     Bob, Eve
Bob     Alice, Frank
Charlie     Doris, Frank
Doris     Alice, Frank
Eve     Bob, Charlie
Frank     Charlie, Eve

The dean believes that each student reported all the others that he or she saw, with the exception of the thief who, in an attempt to frame another student, reported that other student as being seen when that other student was not in fact in the library. Assume the dean's belief is correct. Can the dean determine the thief?

Suggested by Joan Hutchinson, Macalester College, who found it in Doug West's book, Introduction to Graph Theory, 2nd ed., p. 346, where it is attributed to M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, p. 20.

© Copyright 2007 Stan Wagon. Reproduced with permission.



3 October 2007