Bonjour à tous,
Pour débarrasser la contrée de la sorcière Maléfica, Godefroy le Hardi doit impérativement traverser le marais maudit de Sainte Putride, vaste étendue rectangulaire tapissée de souches d'arbres morts affleurant à la surface et régulièrement réparties tous les 5 mètres selon un quadrillage 20 x 11 (voir le dessin).
Par ailleurs, le marais est entouré d'une végétation si touffue qu'on ne peut y pénétrer que par la souche A1 et qu'on ne peut en sortir autrement qu'en arrivant sur la souche T1.
La seule possibilité de déplacement consiste à sauter de souche en souche. Mais il est impossible pour un homme de sauter une telle distance sans élan et quiconque tombe dans les eaux empoisonnées n'en réchappe pas.
Heureusement, le mage Eusébius a prêté à Godefroy des bottes magiques permettant de franchir de grandes distances. Hélas, comme Eusébius ne fait jamais les choses simplement, elles ne permettent d'effectuer que des bonds en ligne droite sur une distance de 1825 mètres, ni plus, ni moins.
Question : Existe-t-il un chemin pour passer de A1 jusqu'à T1 ? Si vous pensez que non, répondez « aucun chemin possible »
Vous donnerez votre réponse en indiquant dans l'ordre les coordonnées des souches utilisées (le dessin n'est pas obligatoire).
Relisez bien votre réponse avant de poster !
Bonjour Godefroy,
En considérant une petite déformation de l'espace, on peut voir cela comme un labyrinthe. Dans un labyrinthe, on peut à partir d'une case aller sur une case adjacente. Ici la case adjacente se situe à 8 cases selon une coordonnée et 3 selon l'autre (pythagore donne (3*5)²+(8*5)²=1825 et c'est la seule décomposition en élément divisible par 5). Ce serait un peu comme un cavalier aux échecs, mais qui se déplace d'un plus grand nombre de case.
Et la encore une fois l'option info intervient : on avait fait un TP sur le labyrinthe, on donne un labyrinthe sous forme de matrice (ici ce serait un labyrinthe sans mur de taille 11x20), un départ et une arrivée et le programme nous trouve le chemin le plus court pour aller du départ à l'arrivée. Je n'ai eu dans l'algorithme qu'à modifier la façon de se déplacer : d'une case (i,j) on ne peut pas aller à (i-1,j) ; (i+1,j) ; (i,j-1) et (i,j+1) mais à (i-8,j+3) ; (i-8,j-3) ; (i+8,j+3) ... etc.
L'algorithme me trouve la liste de coordonnées suivante : [19, 9; 11, 12; 14, 20; 17, 28; 9, 25; 12, 17; 15, 25; 18, 17; 10, 20; 13, 28; 16, 20; 19, 28]
Seulement pour éviter les effets de bords j'ai en plus du marais représenter les 8 cases adjacentes de forêt, comme des murs (cela évite de traiter différemment les cas où notre preux chevalier se trouve sur le bord du marais) et donc il faut enlever 8 aux coordonnées comme ceci :
Une petite fonction de conversion plus tard :
[A,1 ; D,9 ; L,6 ; T,3 ; Q,11 ; I,8 ; Q,5 ; I,2 ; L,10 ; T,7 ; L,4 ; T,1]
et une petite représentation image parce qu'on avait fait ça aussi pour le labyrinthe alors puisque c'est déjà codé (j'ai juste rajouter le quadrillage et les traites entre les points rouge )
Merci pour l'énigme
J'ai trouvé un chemin :
A1 - I4 - Q7 - I10 - L2 - T5 - L8 - T11 - Q3 - I6 - Q9 - T1.
Il faut caser 8 fois le couple (+ou-8,+3) et 3 fois le couple (+ou-3,-8) pour obtenir (19,0) et ne pas dépasser les limites du marais.
La seule combinaison qui permet d'atteindre (avec des coefficients positifs)19 est 2*8 + 1*3
Bonjour godefroy_lehardi,
Je propose la solution suivante :
A1-D9-L6-T3-Q11-I8-A5-I2-L10-T7-L4-T1.
Encore merci pour cette énigme très intéressante...
Bonjour...
Bon, on n'a droit qu'à des trajets de 3 cases sur 8 cases si j'ai bien compris !
Je propose cela.
MM
Bonsoir godefroy,
Ce fut très dur de prendre son pied avec cette joute.
En texte:
A1-I4-A7-I10-L2
O10-G7-O4-G1-J9
R6-J3-M11-P3-S11
K8-S5-K2-N10-F7
N4-F1-I9-L1-N9
R1-J4-B1-E9-H1
K9-N1-Q9-T1
Et en image:
Merci pour la recherche.
Bonjour Godefroy.
Le chemin est A1 I2 M9 N1 J8 R9 Q1 P9 L2 T1 et comprend neuf pas.
Les vecteurs de déplacements possibles sont (8;1), (7;4), (4;7), (8;1), chaque coordonnée pouvant prendre l'un ou l'autre signe.
Du côté des ordonnées, on remarque que 8-7-1 = 0. Les trios de déplacements verticaux 1, 7 et 8 permettent donc de retrouver la rangée du bas tous les trois déplacements.
Les déplacements horizontaux respectivement correspondants sont 8, 4 et 1. Or 8+4+1 = 13; 8-4-1 = 3; et 13+3+3 = 19. Les trios de déplacements horizontaux seront donc {8;4;1} {8;-4;-1} et {8;-4;-1}. Chaque trio doit encore être rangés dans le bon ordre pour éviter de sortir de la grille.
Les déplacements verticaux seront {1;7;-8} pour les deux premiers trios et, par nécessité, {8;-7;-1} pour le troisième trio.
Les vecteurs de déplacement sont donc successivement :
(+8;+1) (+4;+7) (+1;-8)
(-4;+7) (+8;+1) (-1;-8)
(-1;+8) (-4;+7) (+8;-1)
La lieue dont il s'agit mesurait 3248 futurs mètres et était utilisée par Paris avant 1674.
Bonjour,
comme il faut progresser de souche en souche en ligne droite avec les bottes magiques qui permettent de faire un bond de 1825m; on applique le théorème de Pythagore. La somme x2+y2= 1825 donne comme seule solution possible x=40m ou 15m et y= 15m ou 40m. En clair on doit progresser suivant des droites qui franchissent 3 intervalles entre souches horizontalement et 8 intervalles entre souches verticalement ou l'inverse.
Il y a entre A1 et T1 19 intervalles horizontaux soit 8+8+3. Comme on doit tenir compte des intervalles verticaux, on ne peut directement relier A1 et T1.
Le trajet finalement est celui de la figure ci-dessous:
Bien à vous
Bonjour,
Je pense qu'il faut 11 sauts pour trouver la sortie.
Voir plus bas en image ma proposition de parcours...
Explication :
Un bond de (1825) n'est possible que par un déplacement de 8 et 3 exprimé en coordonnées.
Pour passer de A1 à T1, il faut un déplacement global de +19 horizontalement et 0 verticalement.
Il faut donc décomposer 19 et 0 comme sommes de termes choisis parmi : -8, -3, 3 et 8.
Puis équilibrer la répartition de 8 et 3.
Pour 19, la somme 8 + 8 + 3 = 19 convient.
Elle peut être complétée de paires -3 +3 et -8 +8 autant que nécessaire.
Dans ce cas le nombre de sauts est toujours impair.
Pour obtenir 0, toute somme de paires -3 +3 et -8 +8 convient.
Mais le nombre de sauts serait pair dans ce cas.
Il faut donc une décomposition impaire.
Le PGCD de 8 et 3 (premiers entre eux) est de 24.
La décomposition possible est donc de 3x8 - 8x3,
soit une somme de 0 = +8 +8 +8 -3 -3 -3 -3 -3 -3 -3 -3.
En conclusion, il faut trouver un parcours comprenant :
Verticalement : 3 fois +8 et 8 fois -3.
Horizontalement : 1 fois +3 et 2 fois +8, complété par 1 paire -3 + 3 et 3 paires -8 +8.
Le chemin proposé respecte cet équilibre, sans sortir des limites du cadre.
Merci pour cette énigme stimulante .
Désolé, une erreur de codification s'est produite:
l'image est bonne mais le texte est fautif:
au lieu de
A1-I4-A7-I10-L2
O10-G7-O4-G1-J9
R6-J3-M11-P3-S11
K8-S5-K2-N10-F7
N4-F1-I9-L1-N9
R1-J4-B1-E9-H1
K9-N1-Q9-T1
il faut lire
A1-I4-A7-I10-L2
O10-G7-O4-G1-J9
R6-J3-M11-P3-S11
K8-S5-K2-N10-F7
N4-F1-I9-L1-O9 <------------------------------ ici
R1-J4-B1-E9-H1
K9-N1-Q9-T1
Bonsoir godefroy_lehardi
décidément, tes énigmes me donnent du fil à retordre et me font cogiter (20 minutes bien concentré pour celle-ci pour d'abord montrer que c'était possible avec Bezout et ensuite trouver le bon chemin)
Dans l'ordre : A1 ; D9 ; L6 ; T3 ; Q11 ; I8 ; A11 ; D3 ; G11 ; O8 ; G5 ; O2 ; L10 ; D7 ; L4 et enfin T1
Je ne sais si c'est le chemin optimal, j'en ai trouvé plusieurs mais plus longs.
Bonjour,
d'abord j'ai trouve que les seules solutions de 1825=(5a)2+(5b)2 sont (a,b)=(3,8) ou (a,b)=(8,3) (ou a et b representent des cases, plutot que des metres).
Il faut donc pouvoir passer de A1 a T1 (translation de (19,0) par des translations successives de vecteurs (3,8) et (8,3). Pour savoir si le probleme admet une solution, j'ai donc pose :
(3,8)+(8,3)=(19,0)
Je pense qu'une condition necessaire pour que le probleme admette une solution, est que les solutions et de l'equation ci-dessus soient entieres (ce qui n'est pas le cas).
Je reponds donc PROBLEME IMPOSSIBLE!
Merci pour l'enigme !
Bonjour Godefroy,
Voici un chemin possible, en 11 mouvements, pas si facile (pour moi) à trouver :
A1 - I4 - Q7 - I10 - F2 - N5 - F8 - N11 - Q3 - I6 - Q9 - T1
Merci pour cette jolie énigme.
Bonjour et bravo pour le énigmes (phosphore assuré)
Habitué aux poissons je risque le raisonnement suivant:
Comme le cheval aux échecs le parcours est effectué selon une diagonale de 3 plots sur 8 plots
Aux échecs chacun sait qu'il peut aller partout en quelques coups astucieux ,mais ici :
* dans le sens de la longueur (axe des x )20 plots ne peuvent être atteints qu'avec une somme algébrique
de sauts de 4 pour le coté 3 et d' une somme algébrique de 1 pour le coté 8 pour l'axe des x
soit 4+4+4+4+8 =20
* ce qui implique pour l'axe des y (inclus dans 11 plots) les mêmes paramètres pour l'autre coté
du rectangle des pas (8 ) mais cette fois en sachant que l'on ne peut faire qu'un seul pas de 8
ou -8 à chaque fois et il faudra un multiple de 3 pour atteindre 20 ce qui est impossible
Bonsoir,
je répond aucun chemin possible.
Je m'explique,comme les trajectoires possibles sont suivant des côtés de longueurs 5m ou des hypoténuses de triangles dont les côtés sont des multiples de 5 alors pour faire exactement 1825 m il faut soit que ce soit un multiple de 5 ce qui n'est pas le cas, soit par le théorème de pythagore qu'on trouve des entiers a et b tels que (5a)²+(5b)²=1825 soit 25(a²+b²)=1825 soit a²+b²=73 les seuls couples d'entiers (a,b) vérifiant ceci sont (3,8).
En remarquant que le trajet suivant les abscisses de A1 à T1 a une longueur total de 19 fois 5 et que quelque soit les trajectoires qui permettraient d'aller de A1 à T1 en le trajet en projetant sur l'axe des abscisses serait de la forme un multiple de 3 + un multiple de 8 donc 3k+8k', il faudrait donc qu'il existe 2 entiers positifs u et v tels que 19=3u+8v.
Ensuite la longueur totale de A1 à A11 est de 10 fois 5 , par le même raisonnement en projetant la trajectoire suivant l'axe des ordonnées on fait donc autant de multiple de 3 que de 8 suivant les abscisses donc v et autant de multiple de 8 que de 3 suivant les abscisses donc u , donc u et v doivent aussi vérifier 10=3v+8u.
On vérifie facilement que pour 19=3u+8v seuls u=1 et v=2 conviennent , mais ils ne conviennent pas pour la 2e égalité où on trouve 14 au lieu de 10 avec ces valeurs de u et v.
Merci pour l'énigme.
Bonjour.
je pense que c'est possible, sauf erreur, en passant par :
A1, I4, Q7, I10, L2, T5, L8, T11, Q3, I6, Q9, T1
En tout cas, même si cela est faux, félicitation pour l'énigme.
joël
Bonjour,
Un chemin possible entre A1 et T1, en 13 pas et 14 souches:
Soit A1 - I4 - Q1 - T9 - L6 - T3 - Q11 - I8 - Q5 - I2 - L10 - T7 - L4 - T1
Merci pour cette intéressante énigme.
Encore moi
Ce n'était pas demandé, mais il y avait plus court, avec 11 pas et 12 souches,
les pas A1 - I4 et T9 - L6 de mon schéma précédent s'annulant.
Alors tout d'abord mon calcul marche si l'on peut faire des trajets en diagonales (mais en ligne droite) et qu'on ne tient pas compte des ",07" qu'il peut y avoir...
Voici mon calcul : 1825 = 42.7
La diagonale d'un carré vaut c2 donc ici 5*2 = 7 (réelment 7.07)
Je divise ensuite 1825 par 5*2 et je trouve 6 (réelment 6.04)
Je peux donc me déplacer de 6 souches par 6 souches. Voici ce que ça donne :
CF Image.
Toutefois je précise qu'avec les bottes nous dépassons T1 donc je ne sais pas si ça marche...
[En tout cas si ça ne marche pas je ne vois pas comment on peut faire alors...peut-être qu'alors il n'y a aucun chemin possible ?!]
Mais Racine(1825) = 42,72... Comment faire pour sauter un nombre entier avec une distance à virgule ? o_O
Chaqu'un de mes sauts va me permettre d'avancer de 3 souches v/h et 8 souches h/v soit pour mon premier saut me retrouver sur la souche D9 ou I4 et ainsi de suite, mon avant dernier saut devant se trouver sur Q9 ou L4. Les sauts intermédiaire sont multiples, je présente ici deux des solutions.
Voici pour ma réponse :
A1 - D9 - L6 - T3 - Q11 - I8 - A5 - I2 - L10 - D7 - L4 - T1
OU
A1 - I4 - A7 - I10 - F2 - N5 - F8 - M11 - K3 - S6 - K9 - N1 - Q9 - T1
Que voici en image :
merci @+
Bonjour,
c'est possible et je pense (après une recherche exhaustive avec papier et crayon) qu'on ne peut faire moins de 11 sauts (j'aurais donc dit 0.011 lieues pour les bottes).
Voici une solution (mais il y a plusieurs variantes à 11 sauts):
D9-L6-T3-Q11-I8-A5-I2-L10-D7-L4-T1
Une variante: I4-A7-I10-L2-D5-L8-T11-Q3-I6-Q9-T11
(au passage T11 en un minimum de 7 coups)
Merci godefroy_lehardi pour cette belle énigme, comme je les aime !
(merci également d'en proposer...)
PS: L'énigme peut encore être rendue plus difficile avec un nombre (1825) ayant deux décompositions différentes en somme de carrés...
Franchement si trouver comment avancer de sqrt(1825) n'était pas trop dur,...,trouver un chemin était autrement plus prise de tete!
je suis tombé sur celui-la un peu par hasard en faisant des deplacements symetriques entre le départ et l'arrivé et en priant pour que mes chemins se rencontrent!
Merci pour cette belle enigme
Clôture de l'énigme :[u][/u]
Il existait de multiples chemins possibles, les plus courts comportant 11 sauts.
Bravo à tous ceux qui ont trouvé !
Au fait, c'était la dernière énigme du mois !
J'ai juste oublié de féliciter totti1000 pour sa quatrième victoire !
Je me disais aussi ...
Bravo totti1000. C'est une victoire précieuse, acquise sur une série vraiment difficile. Je devine que tu dois en tirer une satisfaction particulière...
Bravo aussi à gloubi, l'autre "sans-faute" du mois.
Bonjour,
visiblement je me suis planté
Je n'étais pas sûr de mon raisonnement en le postant, mais je n'arrive toujours pas à trouver l'erreur : si quelqu'un a une idée et pourrait m'expliquer...
Merci
Bonjour cohlar ,
Il me semble que tu considères une combinaison linéaire avec seulement les vecteurs (3;8) et (8;3), tu oublies donc les vecteurs (-3;8), (-3;-8), (3;-8), (-8;3), (-8;-3) et (8;-3)...
LeDino>> Bonjour, et merci! Nofutur2 était encore devant au temps (comme en août), mais cette fois-ci il a commis l'erreur... C'est vrai que la première énigme du mois m'a pris un temps fou...
Le mois d'octobre lui aussi, est loin d'être facile, je pense...
Enfin merci à godefroy-lehardy pour ses énigmes (et je n'oublie pas jamo)...
Mais ouiiiiiiiiii, merci totti!
Et bravo pour le mois (j'sais pas comment tu fais/vous faites pour répondre aussi vite aux énigmes !) ^^
Bonjour,
Bravo totti1000 !
Et merci, LeDino ! C'est vrai, ce n'est pas la première fois que je suis dans le peloton de tête ...
Mais avec plus de 100 heures de temps moyen par énigme, ce n'est pas évident.
Bravo totti1000, belle performance !
Il m'est avis que cette quatrième victoire (en si peu de temps) ne sera pas la dernière ... Impressionnant de rigueur et de rapidité !!.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :