Déduction et logique

[Aracoco]

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)?
-----

[invite52487760]

Salut :

Si je ne m'abuse, ton énigme relève de la théorie des graphes avec des matrices adjacentes etc. Je ne suis pas très familier avec ça, sinon, pour le cas : , le nombre de mouvements ne dépassera pas le nombre il me semble.
Si tu rédiges ça sous forme d'un algorithme que tu peux le traduire en programme informatique, peut être que tu auras une réponse assez rapide de la part d'un ordi.

Cordialement.

[Aracoco]

Le nombre de mouvements ne depassera pas 15 = 16 - la position de depart.

[invite52487760]

Est ce que tu peux jeter un œil ici : https://fr.wikipedia.org/wiki/Algori...e_Bellman-Ford , ça peut susciter plus ton intérêt.

[A voir en vidéo sur Futura]

[Aracoco]

Est ce que tu peux jeter un œil ici : https://fr.wikipedia.org/wiki/Algori...e_Bellman-Ford , ça peut susciter plus ton intérêt.

Merci. Sauf que c`est totalement inutile pour mon probleme.

Ps : je sais utiliser Google et d`autres outils de recherche.

[Aracoco]

Un itineraire du genre :
sud-sud-sud-est-est-est-nord
soit 7 mouvements donne directement la reponse : piece numero 12.
La question a se poser est : combien de mouvements peut-on faire sans que l`on soit certain de decouvrir l`emplacement du logicien?
On n`a pas besoin de la theorie des graphes.
On n`utilise pas un marteau pour tuer un moustique.
xxxx
Ce n`est pas un devoir d`ecole.
C`est un probleme pointu qui demande un peu d`imagination creative.

[Dynamix]

Je dirais :

 Cliquez pour afficher

Après 8 déplacements dans un carré de 3x3 , il sort de ce carré et dévoile sa position en colonne ou en rangée .
Après 3 autres déplacements il dévoile sa position dans l' autre sens .

PS
Cette énigme aurait du être placée dans science amusantes .

[Médiat]

Bonjour,

Il faut, au moins (n-1)² mouvements, mais je n'ai pas démontré que c'est suffisant (dans le cas n = 2, il faut 2 mouvements et non 1)

[mh34]

Aracoco merci de changer de ton s'il vous plait, rien ne vous oblige à être aussi désagréable. Et j'ajoute que vous n'avez pas la propriété de cette discussion, même si c'est vous qui l'avez initiée.

[ansset]

première déduction peut être trop rapide.
d'une case qcq à une autre qcq il existe un chemin qui passe par les n cases.
pour être sur de tomber sur la bonne , il n'y que n-1 cases d'arrivée.
d'ou n(n-1)

[Médiat]

Bonjour,

d'ou n(n-1)

Sauf erreur de ma part, pour n = 3, on peut trouver après 4 mouvements et non 6 (peut-être, faut-il distinguer les cas pairs et les cas impairs ???).

[Dynamix]

Il faut, au moins (n-1)² mouvements, mais je n'ai pas démontré que c'est suffisant (dans le cas n = 2, il faut 2 mouvements et non 1)

Pas tout à fait ...

 Cliquez pour afficher

Minimum = 2n-2
Exemple : N,N,N,E,E,E
Maximum = n²-n

[Dynamix]

première déduction peut être trop rapide.
d'une case qcq à une autre qcq il existe un chemin qui passe par les n cases.
pour être sur de tomber sur la bonne , il n'y que n-1 cases d'arrivée.
d'ou n(n-1)

Bonne remarque .
Le minimum serait 4

 Cliquez pour afficher

Exemple :
N,N,N,E

[Médiat]

Pas tout à fait ...

 Cliquez pour afficher

Minimum = 2n-2
Exemple : N,N,N,E,E,E
Maximum = n²-n

 Cliquez pour afficher

Ce que je voulais dire en parlant de minimum, c'est qu'il existe des chemins de longueur (n - 1)² - 1 pour lesquels on ne peut pas trouver le point de départ, j'ai l'impression que pour vous minimum veut dire qu'existe des chemins de longueur 2n -2 pour lesquels on peut trouver ; si c'est cela, pour n = 4 , N, N, N, E est suffisant pour trouver la case de départ.

[Dynamix]

L' énoncé prête à confusion .
Le minimum étant le nombre maximum de déplacement sans être détecte
C' est pour ça que je parle de minimum et de maximum .

Suite à la remarque de ansset , je trouves bien (n-1)²
Raison :

 Cliquez pour afficher

On ne peut pas effectuer plus de 3 (n-1) déplacements sur une même ligne ou colonne sans dévoiler sa position .

[ansset]

L' énoncé prête à confusion .

effectivement,
attendons le retour d' Aracoco pour savoir si nos dires correspondent à son énigme.
ps : pour moi c'est n(n-1) car il y a n cases d'arrivée possibles ( qui correspond d'ailleurs au cas n=2 )
mais c'est encore une fois "mon" interprétation de la question.
Cdt

[ansset]

Il vous communique a chaque deplacement le sens de son mouvement (nord ou sud ou est ou ouest).

à la relecture , j'ai forcement tord car j'avais zappé cette phrase.
qui a forcement un sens pour le résultat final.
retour à la case départ pour moi.
sorry

[Dynamix]

il y a n cases d'arrivée possibles

Pour un carré 3x3 j' en trouves 5
Et autant de case de départ , bien entendu .

[Médiat]

C'est pourquoi je me demandais s'il n'étais pas nécessaire de distinguer le cas PAIR (n² cases de départ possibles) et IMPAIR ((n²+1)/2 cases de départ possibles), peut-être est-il possible de trouver sans cette distinction

[Dynamix]

le cas PAIR (n² cases de départ possibles)

Es tu certain qu' on peut partir de n' importe ou ?
Même si c' est le cas , le logicien choisis son point de départ pour maximiser le nombre de déplacements non révélateurs de sa position .

[Aracoco]

Es tu certain qu' on peut partir de n' importe ou ?
Même si c' est le cas , le logicien choisis son point de départ pour maximiser le nombre de déplacements non révélateurs de sa position .

Exact! C`est la la cle du probleme.
Le logicien se doit choisir l`itineraire qui maximise "le nombre de deplacements non revelateurs de sa position".
Eureka boom boom!

[Médiat]

Es tu certain qu' on peut partir de n' importe ou ?

Je crois oui, par récurrence, on peut démontrer que si de n'importe quelle case d'un carré de côté 2n on peut trouver un chemin qui se termine sur son bord, alors c'est vrai pour un carré de taille 2n + 2 (c'est évidemment vrai pour n = 1).

[ansset]

Pour un carré 3x3 j' en trouves 5
Et autant de case de départ , bien entendu .

oui bien sur: boulette, désolé.
reste que je ne sais pas si oui ou non doit intégrer l'information que j'ai rappelé ds mon mess #17
et si oui, comment la faire intervenir.
Cdt

[Dynamix]

reste que je ne sais pas si oui ou non doit intégrer l'information que j'ai rappelé ds mon mess #17
et si oui, comment la faire intervenir.

Tu dessines les déplacement sur une feuille quadrillé .
A un moment ça doit faire tilt .

On peut aussi le noter en E,O,S,N
exemple :
Parcours = S+O+N+O+S+S+E+E
Avec la regle : S+N = E+O = 0
On obtient le parcours réduit (point départ/point d' arrivée) = S+S
Quand le parcours réduit comporte 3 termes identique , tu lèves un sourcil

[Médiat]

Bonjour,

Au moment où on est sûr d'avoir fait un chemin d'un bord au bord opposé, éventuellement + 1 mouvement, on peut recomposer le chemin à l'envers, ceci est obligatoire après au plus (n - 1)² mouvements, mais si ce nombre est atteint le mouvement supplémentaire est inutile : la bonne réponse (si je ne me suis pas planté) est donc (n - 1)² mouvements, sauf dans le cas n = 2, où il faut 2 mouvements.

[Dynamix]

Oui , il faut 2 conditions pour dévoiler sa position .
La première c' est d' aller d' un bord à l' opposé , ce que l' on évite en évoluant dans un carré 3x3
La deuxième , je pense que c' est d' effectuer au moins 4 mouvements

[Médiat]

En fait, avec n > 1, car sinon le problème n'est pas passionnant, il faut au moins aller d'un bord à l'autre et avoir fait un mouvement dans la direction perpendiculaire (pour savoir dans quel angle on est), c'est à dire au moins (n-1)² et au moins n mouvements, 2 est le seul cas ou n > (n-1)²

[Aracoco]

Qui peut me donner 8 mouvements sur une grille 4x4?
Je veux juste voir si je peux trouver votre position.

Merci.

[Dynamix]

Qui peut me donner 8 mouvements sur une grille 4x4?
Je veux juste voir si je peux trouver votre position.

On peut t' en donner 8 , mais tu ne trouveras pas
S+O+N+O+S+S+E+E
(2 solutions)

[Dynamix]

La prochaine chambre visitée est la 13
Dit nous si cet indice t' a aidé .