Le logicien et son chateau

[Mario2015]

Salut,

Un logicien vous propose l`enigme suivante.
ll possede un chateau comprenant 16 pieces agencees sous une forme de grille 4x4 dont les pieces sont numerotees de 1 a 16 comme suit :
1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-16

Il se positionne dans une piece parmi les 16.
Vous ne connaissez pas sa position de depart.
Ensuite, il commence a se deplacer d`une piece a l`autre. Il se deplace horizontalement et verticalement (par rapport a la grille). Pas de deplacement en diagonale.
Il vous communique a chaque deplacement le sens de son mouvement (nord ou sud ou est ou ouest).

Nord

Ouest (grille4x4) Est

Sud
Il ne passse jamais par la meme piece et vous assure qu`il ne sera pas bloque. Son itineraire est etabli de maniere a ne pas mettre les pieds dans la meme piece 2 fois et a ne pas se trouver bloque.

Il vous lance le defi suivant : quel est le nombre de mouvements minimal qui, quelque soit la position de depart, vous donne la certitude de decouvrir le numero de la piece ou il se trouve?
Par deduction logique vous devez etre sur qu`au bout de k mouvements (k etant minimal) vous lui donnez exactement le numero de la piece ou il se trouve.

Exemple de mouvements:

Sud-Sud-Est-Nord-Est-Sud- (6 mouvements)
Chaque deplacement = 1 mouvement.
Le deplacement se fait d`une piece donnee a une piece voisine.

Peut-on generaliser la solution pour 4x4 a nxn (avec n>4)?

[lulu math discovering]

S'il ne doit pas se retrouver bloqué, alors cela veut dire qu'à la fin de l'ensemble de tout ses déplacements il doit lui rester une possibilité de déplacement ?

[Mario2015]

S'il ne doit pas se retrouver bloqué, alors cela veut dire qu'à la fin de l'ensemble de tout ses déplacements il doit lui rester une possibilité de déplacement ?

Oui! bien evidemment sauf que l`on peut trouver la solution bien avant (nombre minimal).
Exemple :
Si le logicien vous donne cette suite de mouvements : sud-sud-sud-est-est-est (soit 6 mouvements) on sait ou il se trouve (piece numero 16) car il n`a pas le choix : une seule case est possible (la piece numero 12). On connait avec precision sa position au 6eme mouvement.

[Mario2015]

A partir d`un certain nombre de mouvements sa liberte de deplacement devient nulle. Comme il ne doit pas repasser par la meme piece, son chemin ulterieur devient unique. A ce moment, on peut deceler la piece ou il se trouve avec certitude.
Quel est ce mysterieux nombre de mouvements a partir duquel sa liberte de deplacement devient nulle? That is the big question!
Je pense qu`avec un peu d`analyse on peut solutionner le probleme pour 16 pieces (4x4).
Au-dela (n=5,6,7....k) cela se complique.
Il y a probablement une loi sous-jacente a ce probleme.
Pour n=2 (2x2) le nombre minimal est 2.
Une relation a decouvrir entre n et m (n etant le cote du carre et m le nombre minimal de mouvements ou la reponse est certaine).

[nodjim]

Pour moi, il faut n(n-1) +1 coups pour être sûr de la position de départ. En effet, on peut remplir au mieux 1 rectangle n(n-1) de 2 façons différentes, grace à la largeur n-1. Seul un coup supplémentaire en dehors de ce rectangle permet de conclure.

[beagle]

Si je termine mon trajet dans un angle, 4 cases d'un angle, si je termine dans une des 3 cases du 2x2restant, j'ai encore deux choix.
donc 4x4 -3 occupées
cela doit se généralisér à n (sauf si impair ne permet pas ce parcours, mais sur le 4x4 ça tourne bien) donc dans un 16x16 on doit pouvoir aller jusqu'à 16x16-3 cases

[beagle]

bah, si on te demande à quel moment du chemin emprunté on n'avait plus qu'un seul choix, beagle t'as répondu n'importe quoi mon pote.

[beagle]

pour le 4x4,
au maximum 9 cases occupées permettent encore deux choix
qu'on dirait...

et 45 pour un 8x8?

c'est encore faux beagle,
qu'il reste deux possibilités ne signifie pas que je ne sais pas où tu es,
exemple:
tu dis
dans le 4x4
sud-sud-est-est-est
ben il te rste deux possibilités pour le prochain coup,
et pourtant je te vois, je sais où tu es beagle ...
tu comprends?

[Doraki]

Tu veux dire quoi quand tu dis que le logicien évite de se retrouver bloqué ?
Au bout du 15ème mouvement il est bloqué puisqu'il est passé par toutes les cases.

A partir d`un certain nombre de mouvements sa liberte de deplacement devient nulle. Comme il ne doit pas repasser par la meme piece, son chemin ulterieur devient unique. A ce moment, on peut deceler la piece ou il se trouve avec certitude.

Non, pas si il fait nord nord est est sud sud ouest nord.

[L.A.]

Bonjour,

l'exemple de Doraki suggère qu'il faut imposer la condition suivante : le type prévoit son itinéraire de façon à visiter les 16 pièces avant d'être bloqué (par cas de force majeure :mur: ).

pour le 4x4 on peut éventuellement étudier tous les trajets possibles : certains sont cycliques (terminent dans une pièce contiguë à la pièce de départ), d'autres non (spirales par exemple), mais il n'y en a pas tant que ça.

une idée peut-être à creuser : distinguer les mouvement NS d'une part et EO d'autre part, par exemple la présence d'une série SSS quelque soient E et O intercallés permet de connaitre l'ordonnée à tout instant ultérieur, et connaître la position c'est connaître l'abscisse et l'ordonnée.

bizarrement, on obtient plus souvent une information quand le type est dans les pièces du bord...

:hein:

[Mario2015]

Tu veux dire quoi quand tu dis que le logicien évite de se retrouver bloqué ?
Au bout du 15ème mouvement il est bloqué puisqu'il est passé par toutes les cases.



Non, pas si il fait nord nord est est sud sud ouest nord.

Salut,

S`il va jusqu`au bout de ses 15 mouvements possible il n`est pas bloque. Le fait que son itineraire soit sans blocage est tres utile pour savoir ou il est et ou il peut aller. J`aurai pu compliquer l`enigme en autorisant le logicien a etre bloque au-dela d`un certain nombre de mouvements (au dela du nombre minimal par exemple ou au dela du 12eme mouvement). Ce qui aurait rendu le probleme bien plus difficile.
Quand je dis sa liberte de mouvement devient nulle cela veut dire qu`il n`a plus qu`un seul choix possible.
L`analyse exhaustive dans le cas de 4x4 est possible sans ordinateur, avec un papier et un crayon.
Chaque mouvement elimine des points de depart possibles.
Exemple :
nord comme premier mouvement va eliminer des cases departs : 1-2-3-4. Quand on se positionne en haut de la grille on ne peut aller direction nord.
Chaque suite de mouvements va donner des indices.
Si on arrive a connaitre le point de depart comme on a la suite des mouvements on peut decouvrir ou le logicien est a la seule condition que le point de depart soit UNIQUE.
nord-est va eliminer 7 pieces comme points de depart : 1-2-3-4-8-12-16 etc...
apres nord-est- on a 3 directions possibles nord-sud-est et chaque triplet va nous eliminer d`autres cases depart etc....

[Doraki]

S`il va jusqu`au bout de ses 15 mouvements possible il n`est pas bloque

????????????
ben si puisqu'il ne peut plus avancer.

Si il fait nord nord nord est, il a combien de positions possibles ?


D'ailleurs il n'y a aucune implication logique entre savoir où est le logicien et le fait que le logicien ait une liberté dans ses déplacements ou non, ni dans un sens, ni dans l'autre.
Je ne comprends pas pourquoi tu attaches tant d'importance à la liberté de déplacement alors que ça n'a aucun rapport avec la connaissance de sa position.

Si il fait nord nord nord est est sud sud sud ouest, il n'a plus aucun choix il est forcé de faire nord nord et de s'arrêter, donc en utilisant tes termes, sa liberté de mouvement est bien nulle, mais on ne sait toujours pas où il est, et on ne le saura jamais.

Si il fait nord nord nord est est est sud, on sait où il est mais il a encore plein de choix possibles pour continuer.

Dans un grand carré, si il fait nord nord est est sud ouest, il est forcé de faire sud au prochain coup mais on ne sait quand même pas où il est.

[Mario2015]

????????????
ben si puisqu'il ne peut plus avancer.

Si il fait nord nord nord est, il a combien de positions possibles ?

Si il fait nord nord nord est est sud sud sud ouest, il n'a plus aucun choix il est forcé de faire nord nord et de s'arrêter, donc en utilisant tes termes, sa liberté de mouvement est bien nulle, mais on ne sait toujours pas où il est, et on ne le saura jamais.

D'ailleurs il n'y a aucune implication logique entre savoir où est le logicien et le fait que le logicien ait une liberté dans ses déplacements ou non, ni dans un sens, ni dans l'autre.
Je ne comprends pas pourquoi tu attaches tant d'importance à la liberté de déplacement alors que ça n'a aucun rapport avec la connaissance de sa position.

L`enonce stipule que le logicien fait un parcours sans blocage. S`il fait les 15 deplacements possibles sur une grille 4x4 sans que l`on decouvre sa position (ce qui est impossible!), dans ce cas le nombre minimal serait de 15. Absurde!
Un parcours avec blocage au dela du ombre minimal aurait complique l`enigme puisque certains itineraires seraient rejoutes.
Le logicien peut tres bien se bloquer en k mouvements. Et alors il ne peut plus communiquer son deplacement. Impossible de savoir ou il est.
D`ou la contrainte d`un parcours clean sans blocage.

[Doraki]

Donc quand tu dis qu'il ne se bloque pas en fait tu veux juste dire qu'il ne se met jamais dans une position où il ne pourrait plus visiter toutes les autres cases ?

[Mario2015]

Donc quand tu dis qu'il ne se bloque pas en fait tu veux juste dire qu'il ne se met jamais dans une position où il ne pourrait plus visiter toutes les autres cases ?

Exact! C`est bien cela

[beagle]

On peut répondre à la fin du sixième déplacement où il doit aller pour le septième déplacement,
ce qui fait 8cases avec départ et arrivée obligatoire.Pour du 4x4.

[Mario2015]

On peut répondre à la fin du sixième déplacement où il doit aller pour le septième déplacement,
ce qui fait 8cases avec départ et arrivée obligatoire.Pour du 4x4.

Ou serait-il apres :

sud sud est nord est sud (6 mouvements).

[beagle]

Ou serait-il apres :

sud sud est nord est sud (6 mouvements).

reste plus que est,
car nnord et ouest sont pris et sud divise en deux zones non couvrantes en continue

[nodjim]

Avec la contrainte "ne se bloque jamais" il suffit qu'il termine une ligne ou une colonne + une case pour déterminer où il se trouve à coup sûr. En effet, quand une ligne est finie, celle ci ne peut contenir des cases vides en même temps en haut et en bas de la ligne, sinon blocage. La case supplémentaire nous indique où sont les cases vides, et par déduction où se trouve la case de départ. Même raisonnement pour une colonne.

[Mario2015]

Avec la contrainte "ne se bloque jamais" il suffit qu'il termine une ligne ou une colonne + une case pour déterminer où il se trouve à coup sûr. En effet, quand une ligne est finie, celle ci ne peut contenir des cases vides en même temps en haut et en bas de la ligne, sinon blocage. La case supplémentaire nous indique où sont les cases vides, et par déduction où se trouve la case de départ. Même raisonnement pour une colonne.

est est est sud

Il termine la ligne et va dans la piece sud

En plus, il n`est pas obliger d`aller en ligne ou en colonne. Il peut zigzaguer, slalomer etc...
Il y a un tres grand nombre d`itineraires possibles sans blocage.

La question fondamentale est :
quel est l`itineraire le plus long que le logicien doit suivre sans etre detecte (par deduction bien sur)?
Si tu dis qu`au plus au bout de 12 mouvements, je saurai avec certitude ou le logicien se trouve quelque soit sa position de depart tu aurais droit a 12 au plus. S`il fait fait 12 mouvements et que tu ne peux pas le detecter tu perds. Il y a des intineraires que tu peux decouvrir apres 6 coups : sud sud sud est est est (cet itineraire n`est possible que si le logicien part de la piece numero 1). Il se trouve a la piece numero 16.