bonjour, 

je viens de finir l'épreuve d'informatique de Centrale, où j'ai été bloquée à une question de logique. 

6 personnes sont entrée dans une bibliotheque, y sont restés un certains temps avant de repartir.  Quand deux personnes sont dans la blibliotheque en même temps, au moins l'une voit l'autre . 

Donc A dit avoir vu B et E 

B dit A et I; C dit D et I, D dit A et I, E dit B et C, enfin I dit C et E . 

Seul une personne ment; le voleur . Qui est -il ? 

Je pense que c'est didier mais je n'arrive pas  a le prouver

Connais-tu la notion de graphe d'intervalle ? Je te laisse la regarder sous Wikipédia sinon.

Il est facile d'écrire le graphe d'intervalle associé à ce problème. Une propriété facile de ces graphes est qu'ils sont triangulés, c'est à dire que tout cycle de longueur >= 4 admet une corde. Lorsqu'on dessine le graphe d'intervalle, on remarque qu'il existe 2 cycles de longueur 4 sans corde, les cycles A-D-I-B et A-D-I-E. Le triplet A-D-I intervient dans les deux cycles et c'est D qui dit avoir vu A et I mais aucun des deux ne confirment ses dires. Donc c'est bien D qui a menti.

Je ne crois pas que ces graphes soient au programme, cependant. La question était au début ou à la fin du sujet ?

-
Edité par edouard22 28 avril 2015 à 20:42:01

Une vidéo de vulgarisation qui présente un problème similaire. Ça devrait aider a comprendre la méthode:

https://m.youtube.com/watch?v=ZGhSyVvOelg