Monday, May 05, 2008

Who Killed the Duke of Densmore?

The idea of using interval graphs in detective stories was exploited in depth by Claude Berge in his novelette Que a tuZ le Duc de Densmore? (Who killed the Duke of Densmore?, Bibliotheque Oulipienne No.67). The story presented ideas of using Graph Theories to help solve realistic problems. However, getting this as an assignment can be far from realistic of getting a good grade. So anybody knows who killed Duke of Densmore, please tell me. I know the answer, but i can't solve it using Interval graphs or the academician style of explaining it in interval graphs. The question is as below:

The Duke of Densmore is found dead in the explosion of its castle on the Isle of White. The murder was committed with a bomb placed carefully in the labyrinth of the castle, which would require a long preparation in hiding in the mazes of the labyrinth. During his last years, the Duke had received eight visitors at his castle; each of them was brought first to the island and then back to the mainland by a motor boat. None of them recalls the precise dates or duration of her stay on the island, but each remembers with certainty whom else she had met on the Isle of White:

-- Ann saw Betty, Cynthia, Emily, Felicia and Georgia
-- Betty saw Ann, Cynthia and Helen
-- Cynthia saw Ann, Betty, Diana, Emily and Helen
-- Diana saw Cynthia and Emily
-- Emily saw Ann, Cynthia, Diana and Felicia
-- Felicia saw Ann and Emily
-- Georgia saw Ann and Helen
-- Helen saw Betty, Cynthia and Georgia

The testimony of each woman is comfirmed by the others and collusion between any two is out of question.

If you are a detective like Sherlock Holmes, and also happens to be a Graph Theory enthusiast, how do you find the killer. The killer must have stayed in the labyrinth once, or perhaps several times in order to prepare for her evil plan. Also, none of the suspects are giving false testimony, cause the Sailor who transported the suspects confirmed their testimony. However, the possibility of two people were at the same place and at the same time, but not see each other is highly probable. Any ideas?

There are a couple of ways to answer this question, you either need to be good at graph theory or have exceptional googling skills. I tried Googling, but can't find the exact solution I wanted.


  1. I know who Killed the Duke - JR , and he lives in "Dallas".

  2. Is this one of those game-theory thingy?

    I am INTRIGUE.I'm a professional at Googling, but lemme figure this out the surirumahtanggaway.After all, ONLY a woman can tell who is lying [insert lagu suspen cite P.Ramlee here]

    Will get back at you later...

  3. fariz: That one in the 80s lah bro....already not playing on the TV

    Mrs. C: Well, good luck then. I'm not sure if you can use game theory to solve the problem, but you might just be on the way of getting your PhD kalau you solve using game theory...

  4. Aku terlupa la nak buat 2nd quiz tu. Nanti aku update. This one kinda ok la.

  5. Encik, I give up.My husband thinks I'm mental(especially when he saw me doodling on the notepad ABCD with arrows flying out).I had to explain that when one has so much time in their hands, one tries to solve world problems.So husband suggested that I stick to saving the planet, and leave the Duke of Densmore whodunnit murder to that fictional-math bloke on NUMBERS.

    Oh, and he also added that,"One Duke with 8 chickybabes?That sure is trouble.Hell hath no fury like a woman scorned".


  6. Mrs. Curmudgeon: Yea, I suppose the Duke was a sure looker and a player to have 8 women wrap around his Island. I have a theoretical answer for the problem, but I am still trying to get verification of its veracity. Once a clear answer has been verified, and that I have time, I'll put up an answer.

  7. This comment has been removed by the author.

  8. Today, July 1st, I received a comment from anonymous about the answer to this riddle.

    Though I have already solved the mystery behind this murder case, with much detail, i just wanted to acknowledge that anonymous posted a correct answer. Though his explaination did not include graphs to help explain his answer, it was definitely a valid answer.

    I felt it was necessary for me to acknowledge his effort, and thank you for making math fun.

    I, however, feel that I should not post my answers or anonymous answers, since a lot of academicians are using this problems in class to teach graph theory. Displaying the answer would just spoil the process of learning.

    Unfortunately, anonymous did not leave an email. But you can post your email here if you want a few pointers to help you solve this mystery.

    Also, I hope anonymous would put his email here so that people can contact anonymous for tips on how to answer the mystery.

  9. pela teoria dos grafos foi Ann


I don't really wish to moderate any comments, but its necessary to avoid spammers.