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:
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.