Forum de mathématiques - Bibm@th.net

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 505

graphes et Sherlock Holmes

Bonjour,

Un jour, Sherlock Holmes reçoit la visite de son ami Watson que l’on avait chargé d’en-
quêter sur un assassinat mystérieux datant de plus de trois ans.

À l’époque, le Duc de Densmore avait été tué par l’explosion d’une bombe, qui avait en-
tièrement détruit le château de Densmore où il s’était retiré. Les journaux d’alors relataient
que le testament, détruit lui aussi dans l’explosion, avait tout pour déplaire à l’une de ses
sept ex-épouses. Or, avant de mourir, le Duc les avait toutes invitées à passer quelques jours
dans sa retraite écossaise.

Holmes : Je me souviens de cette affaire ; ce qui est étrange, c’est que la bombe avait été
fabriquée spécialement pour être cachée dans l’armure de la chambre à coucher, ce qui
suppose que l’assassin a nécessairement effectué plusieurs visites au château !

Watson : Certes, et pour cette raison, j’ai interrogé chacune des femmes : Ann, Betty,
Charlotte, Edith, Félicia, Georgia et Helen. Elles ont toutes juré qu’elles n’avaient été au
château de Densmore qu’une seule fois dans leur vie.

Holmes : Hum ! Leur avez-vous demandé à quelle période elles ont eu leur séjour respectif ?

Watson : Hélas ! Aucune ne se rappelait les dates exactes, après plus de trois ans ! Néan-
moins, je leur ai demandé qui elles avaient rencontré :
Ann a rencontré Betty, Charlotte, Félicia et Georgia.
Betty a rencontré Ann, Charlotte, Edith, Félicia et Helen.
Charlotte a rencontré Ann, Betty et Edith.
Edith a rencontré Betty, Charlotte et Félicia.
Félicia a rencontré Ann, Betty, Edith et Helen.
Georgia a rencontré Ann et Helen.
Helen a rencontré Betty, Félicia et Georgia.
Vous voyez, mon cher Holmes, les réponses sont concordantes !

C’est alors que Holmes prit un crayon et dessina un étrange petit dessin, avec des points
marqué A, B, C, E, F, G, H et des lignes reliant certains de ces points. Puis, en moins de
trente secondes, Holmes déclara :

– Tiens, tiens ! Ce que vous venez de me dire détermine d’une façon unique l’assassin.

Qui est l’assassin ?

Expliquer la démarche ( réussie ) de Holmes , sachant que personne (dont l'assassin)  n'a menti
sur ses rencontres, mais que l'assassin est par-contre passé plusieurs fois !

Alain

Dernière modification par bridgslam (25-08-2023 15:01:41)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 659

Re : graphes et Sherlock Holmes

Salut,

Un début de réflexion : ce qui est louche c'est que Georgia et Helen se soient rencontrées...

Explication : Ce que je pense pour l'instant c'est qu'un sous-graphe de la forme X---Y---W---Z contenant aussi un lien entre X---Z (mais pas d'autres liens plus directs entre X, Y, Z et W) me semble impossible, sauf si X ou Z est venue deux fois...

On doit donc pouvoir chercher de tels sous-graphes.

Roro.

Dernière modification par Roro (25-08-2023 17:22:29)

Glozi

Invité

Re : graphes et Sherlock Holmes

Bonsoir,
Merci pour l'énigme, j'ai pas mal tâtonné, je propose la réponse suivante

▼réponse

La coupable est Ann.

▼raisonnement

Considérons un graphe avec comme sommets $A,B,C,E,F,G,H$, on relie deux sommets si deux épouses se sont vues (faire un dessin de ce graphe).

Voyons $\mathbb{R}$ comme une frise chronologique, et identifions les sommets à des sous ensembles de $\mathbb{R}$ (correspondant à la période de temps où les épouses étaient dans le château). Selon le ce procédé, il y a une arête dans le graphe si et seulement si les sous ensembles correspondant ont une intersection non vide. Avec cette modélisation, à une épouse qui n'est pas coupable correspond un sous ensemble de $\mathbb{R}$ qui sera un intervalle non vide, alors que la coupable aura certainement un sous ensemble qui sera union de plusieurs intervalles (si ça se trouve la coupable est amie avec de curieux énergumènes comme Cantor, mais en vérité il ne faut pas s'en inquiéter !)

On a les 4 sommets $A,G,H,F$ qui forment un cycle carré dans le graphe, cela signifie que le sous ensemble $A$ chevauche $G$, $G$ chevauche $H$, $H$ chevauche $F$ et $F$ chevauche $A$. En revanche $A$ et $H$ ne se sont pas rencontrés et $G$ et $F$ non plus. Si les quatre disent la vérité alors $A,G,H,F$ sont des intervalles, faisons cette hypothèse et aboutissons à une contradiction :
Puisque $A$ et $H$ ne se sont pas rencontré alors les intervalles $A$ et $H$ sont distincts. Notons $I\neq \emptyset$ l'intervalle entre ces deux intervalles. Puisque $G$ et $F$ ont rencontré $A$ et $H$, et puisqu'on suppose que ce sont des intervalles, alors $I\subset G$ et $I\subset F$. Mais donc $I\subset G\cap F$ et donc $G$ intersecte $F$ ce qui est absurde (faire un dessin)

Finalement, c'est donc que parmi $A,G,H,F$ l'une est un menteuse.

On fait le même raisonnement avec les points $A,G,H,B$ et avec les points, $A,F,E,C$

Finalement la coupable est forcément $A$.
(à vrai dire je n'ai pas vérifié qu'en considérant uniquement les 6 autres alors on obtient bien quelque chose de cohérent mais bon...)

Bonne soirée

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 505

Re : graphes et Sherlock Holmes

Bonsoir,

Oui c'est l'idée essentielle.
A est seule sommet commun à trois 4-cycles sans diagonale.
Deux sommets adjacents représentant un  chevauchement de séjours, un quadrilatère conduit forcément à une répétition de séjours pour l'un des sommets, si ce quadrilatère n'a pas de diagonale.
Comme on n'a pas de repère de chronologie on procède par intersection de plusieurs tels 4-cycles.

Cette énigme est liée aux graphes d'intervalles, aux propriétés particulières.
Deux intervalles sont joints s'ils se coupent.
A cause de l'ordre, leur structure n'est pas quelconque.
Ann est bien là coupable, elle a fait au moins deux séjours.
Bravo

A.

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Glozi

Invité

Re : graphes et Sherlock Holmes

Je dirais même au moins trois séjours car A rencontre C, F et G or les trois intervalles C,F et G sont disjoints.
Sinon je me demande pourquoi il n'y a pas d'épouse avec la lettre D ?
Bonne nuit !

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 505

Re : graphes et Sherlock Holmes

Bonjour,

oui, mais c'était la seule personne de toute façon commune à deux 4-cycles sans diagonales, ça suffisait ;-) pour aller en prison.

Il n'y en a pas avec la lettre D car les personnes citées ont existé vraiment ( écrivains, musicien etc...) et sans doute l'auteur de l'énigme a manqué d'inspiration et ou de connaissances ...

A.

Dernière modification par bridgslam (26-08-2023 09:38:15)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Glozi

Invité

Re : graphes et Sherlock Holmes

Bonjour,
J'ai vu sur internet une autre version de cette énigme (même énoncé avec des témoignages différents),
Cette fois :
A voit B,C,D,F et G
B voit A,D et E
C voit A,D,E,G et H
D voit A,B et C
E voit B et C
F voit A et G
G voit A,C,F et H
H voit C et G

Il faut un argument de plus que précédemment pour conclure.
Bonne journée