Ceci est le plan du quartier d’une prison assez spéciale, dont les 16 cellules contiennent chacune un prisonnier.
|A||||
|||||
|||||
|||_|B|
Le prisonnier de la cellule A veut tuer celui de la cellule B.
Après avoir longuement fulminé dans son coin, la rage le prend, et il démolit le mur de la cellule voisine et massacre le prisonnier qui s’y trouve.
De plus en plus furieux, il casse d’autres murs pour cheminer à travers toutes les cellules et tuer à chaque fois l’occupant de la cellule en abandonnant son cadavre sur le sol.
Il ne retourne jamais dans une cellule où se trouve un cadavre et ne traverse jamais une cellule sans tuer son occupant !
Il lui est impossible de franchir les murs extérieurs, ou de passer d’une cellule à l’autre en diagonale.
Il termine son parcours sanglant dans la cellule B et y tue le prisonnier qui s’y trouve.
Pouvez-vous reconstituer son itinéraire ?
impossible
il rate une cellule 
Diamant dit:Pouvez-vous reconstituer son itinéraire ?
S'il ne déplace aucun cadavre, moi non.
Oui je me souviens plus exactemnt pour quoi mais il y a une histoire de coté impair, je crois.
En tous cas, si le carré fait 2x2 ou 2x4, ça ne marche pas. S’il fait 2x3, ça marche.
c bien la peine que je poste en invisible 
Tu sais quoi ?
J’ai du perdre la main, je le trouve pas l’invisible 
Moi je trouve pas il me manque toujours une cellule…
C’est démontrable par les graphes si je ne m’abuse mais bon se sont des lointains souvenirs et là j’ai plus les détails en tête … cycle et chemin de je-ne-sais-plus-qui …
Avis aux informaticiens … 
Il ne retourne jamais dans une cellule où se trouve un cadavre, mais il peut donc passer deux fois par sa propre cellule!
Cependant, la solution n’est pas unique encore…
La solution n’est pas unique.
Modifier le problème original pour rendre la solution unique m’a semblé être une complication inutile.
Si la solution n’est pas unique, il est donc impossible de reconstituer son itinéraire…
Ca me fait penser au problème de l’enveloppe croisée à dessiner “sans lever le stylo” :
/<br /> —
IXI
—
Problème classique (mais intéressant) en théorie des graphes : il faut, si mes souvenirs sont bons, 0 ou 2 noeuds uniquement avec un nombre impair de liaisons.
C’est possible avec de la chance.
Rody dit:Ca me fait penser au problème de l'enveloppe croisée à dessiner "sans lever le stylo" :
/\
—
IXI
—
Problème classique (mais intéressant) en théorie des graphes : il faut, si mes souvenirs sont bons, 0 ou 2 noeuds uniquement avec un nombre impair de liaisons.
C'est vrai pour les chemins eulériens (1 fois par chaque arête), mais on cherche ici un chemein hamiltonien (une fois par chaque face)
Ici : Si le prisonnier peut repasser par sa cellule, il y a par exemple la solution EOSEENESSOOOSEEE
En revanche il ne peut pas atteindre B en passant une seule fois par toutes les cases y compris la sienne, et l'argument est le suivant : supposons que les cases soient de couleur noire et blanche comme pour un échiquer, et supposons A blanc. Alors à chaque tour le prisonier change de couleur de case. Après un nombre impair de mouvements, il doit ariver dans une cases noire. Or, il veut arriver en B (blanc) après 15 mouvements. C'est impossible.
Yep…
Mais la regle ne dit pas qu il lui est pas possible de repasser par sa cellule ! Donc il suffit juste qu’il fasse un aller retour dans sa cellule pour combler un leger déficit d’une case. Disons qu’apres avoir massacré son premier voisin, il revient dans sa cellul et se dit… Hum et si je repartais par là !
Mister Forest
A priori, cela semble impossible :
En prenant un exemple facilement visualisable :
Imaginons que ce carré soit un échiquier. Les couleurs des cases A et B sont identiques. Disons, qu’elles sont blanches.
Sur un échiquier, lorsqu’on se déplace uniquement vers une des 4 cases adjacentes, on alterne exactement case blanche / case noire/ case blanche / case noire / etc…
Quand A commence sa tuerie il tue quelqu’un dans une case noire, puis quelqu’un dans une case blanche, puis noire, etc… Donc, si quand il fait sa n-ième victime, n est impair, alors il est dans une case noire et si n est pair, alors il est dans une case blanche.
Pour tuer B en dernier (c’est à dire en 15ème), il faudrait donc que B soit sur une case noire. Or B est sur une case blanche.
ça a donc l’air donc impossible…
MAIS
Il a le droit de revenir dans sa cellule de départ puisqu’il n’y a pas de cadavre à l’intérieur ! Donc, il peut tuer dans une case noire le premier, et revenir en A pour ne tuer personne puis retuer quelqu’un dans l’autre case noire adjacente. Là, l’impossibilité ne tient plus puisque les pairs/impairs sont inversés.
En résumé, il tue son voisin, revient dans sa cellule et là peut repartir tuer tout le monde.
Un itinéraire : droite, gauche, bas, droite, droite, haut, droite, bas, bas, gauche, gauche, gauche, bas, droite, droite, droite
j’aime bien réfléchir “tout haut”, ça se voit non ? 
Désolé pour le message un peu long pour pas grand chose…
Ceci dit, il y a bien un “toutes les cellules” mais s’il veut tuer B, ça irait plus vite, en 2 lignes droites, sans s’occuper des autres, sauf les malheureux sur sa route 
grilwick2 dit:Ceci dit, il y a bien un "toutes les cellules" mais s'il veut tuer B, ça irait plus vite, en 2 lignes droites, sans s'occuper des autres, sauf les malheureux sur sa route
C'est exactement ce que je me suis dit à la première lecture !!!
Le prisonnier de la cellule A veut tuer un prisonnier X.
Si l’énoncé vous inidque que X occupe la cellule B, il ne l’apprend pas nécessairement au fou meurtrier ; et de toute façon, il ne faut pas attendre de sa part un comportement vraiment rationnel.