The Duke of Densmore was killed by an explosion that damaged his castle. His testament, evidentally destroyed, was said to have displeased one of his 7 ex-wives. However, each of these women had come in the castle by invitation shortly before the crime. Each of the 7 ex-wifes swears that the invitation was the only time she went there. All of them could be guilty, but because of the careful preparation of the bomb, which was hidden and adjusted to fit in a knight's armor in the Duke's bedroom, the murderess must have come in the castle more than one time. So the guilty woman lied: she came in the castle several times. The women do not remember exactly the date when they went there, but they remember who they met:
Ann met Betty, Charlotte, Felicia, Georgia.
Betty met Ann, Charlotte, Edith, Felicia, Helen.
Charlotte met Ann, Betty, Edith.
Edith met Betty, Charlotte, Felicia.
Felicia met Ann, Betty, Edith, Helen.
Georgia met Ann, Helen.
Helen met Betty, Felicia, Georgia.
Which one was lying? Who is therefore the murderess?
________________________________________________
The original problem was posed in 1980 by the French mathematician Claude Berge (1926 - 2002) to demonstrate a solution by graph theory.
The puzzle is more a mathematical problem than a logical one. We can also see that every statement of an ex-wife confirms the other ones. (I put the problem in the category of 'logic' only because of its flavor.)
CLAUDE BERGE (1980):
"L'énigme policière", Regards sur la théorie des graphes,
Actes du Colloque de Cérisy, Presses polytechniques romandes, Lausanne.
CLAUDE BERGE (1994): "Qui a tué le duc de Densmore?",
Bibliothèque Oulipienne no. 67.
CLAUDE BERGE (2000): "Qui a tué le duc de Densmore?", Une nouvelle policière où le meurtrier est confondu grâce à l'utilisation d'un théorème de combinatoire.
(= Réédition du 1994 par Ed. Castor Astral)
The version of the problem given above is based on the following source:
http://mathafou.free.fr/pbm_en/pb205.html
When I tried to solve this problem some years ago, I was not able to do it. The following hint may be useful.
For a systematic solution, there is an interesting theorem by György Hajós about interval graphs from 1957.
Let us take four U.S.-Presidents and let us look at Presidents belonging to the same time with another.
A: John ADAMS (1735 - 1826)
B: James BUCHANAN (1791 - 1868)
C: Grover CLEVELAND (1837 - 1908)
J: Andrew JACKSON (1767 - 1845)
If a President was a contemporary of another, that means their intervals intersected (overlapped).
A: --------
B: --------
C: -------
J: ----------
Suppose we didn't know the true names of A,B,C,J (neither their lifetimes), but we were told who of the four was a contemporary of another. Usually we would make a adjacency matrix or a adjacency list (no President is contemporary of himself):
A B C J
A 0 1 0 1
B 1 0 1 1
C 0 1 0 1
J 1 1 1 0
A-[B,J], B-[A,C,J], C-[B,J], J-[A,B,C],
But the fascinating thing is that a graph can reveal facts that can not be revealed by any other means (adjacency matrix, adjacency list or whatever else).
If what is told to us is true, then this graph will be an interval graph. We can take a pencil and draw this intersection graph (G1).
There will be a connecting line (edge) between two persons (vertices) if the lifetimes of the persons overlap.
Square ABCJ with diagonal BJ (graph G1):
A o-----o J
| / |
| / |
| / |
B o-----o C
One important statement in Hajós theorem of 1957 is as follows:
An interval graph can not have a cycle of a length >3
(at least 4) without having any chord.In fact, no matter how we draw that graph exactly, we can see in any case: ABCJ has the chord BJ. The reason for this will become clear, if something is wrong!
This leads to the question: What happens if we are told about four Presidents as follows?
A C E F
A 0 1 0 1
C 1 0 1 0
E 0 1 0 1
F 1 0 1 0
A-[C,F], C-[A,E], E-[C,F], F-[A,E].
Now we draw the graph that will look like this square (graph G2):
A o-----o F
| |
| |
| |
C o-----o E
We can see: A and E were not contemporaries, whereas C was a contemporary of both of them.
From this follows that C has been living in the time interval from the dead of the one to the birth of the other.
C
-----------
A or E A or E
-------- -----------
But the cycle ACEF shows that F was a contemporary of A and E too. So F has also been living in the time interval from the dead of the one to the birth of the other.
Therefore, C and F must have been contemporaries!
And so there must be a chord CF in the cycle ACEF.
The graph G2 as he is drawn now, is not an interval graph! Something is wrong.
Suppose the information about persons meeting each other was nevertheless true (meeting 'in lifetime' as in our case now, or meeting 'in the castle').
Our conflict with ACEF is based on our reasonable assumption that every person lived only once.
Let us suppose now that C was born twice. (This question means for the original problem: "Which woman came in the castle more than once?")
Then, for example, we could have the following situation with two lifes of C:
A: ------
C: ------ -------
E: ------
F: -------
This situation is consistent with the given information about A,C,E,F that was taken to be true.
Even if we do not believe in reincarnation and related stuff, this situation can at least explain the graph G2 with the square ACEF. (However this is not an interval graph anymore.)
So this theorem of Hajós about interval graphs (1957) can help us to discover the one who came more than only once.If we want to discover the murderess among the seven ex-wives, we need a graph from which we can draw conclusions.
This graph will be a little bit more complicated, but it doesn't really matter how we draw the graph exactly.
If our graph represents the given information (who met whom), then it will have all the properties we need.
Finally we need to look at those chordless cycles and verify whether they have a vertex in common that is responsible for these problems. This vertex (wife) prevents the graph from being an interval graph.
Edited on April 12, 2017, 5:29 am
|
|
Posted by ollie
on 2017-04-05 12:06:53 |
little hint
