Joute n°69 : Le Gigantic

Posté par godefroy_lehardi godefroy_lehardi

Bonjour à tous,

En cette froide nuit du 14 avril, vous êtes l'officier de quart à bord du Gigantic, un luxueux paquebot transatlantique. Le Commandant vous a chargé de traverser le plus rapidement possible la zone truffée d'icebergs qui se trouve devant vous.
Votre radar vous montre l'image suivante, où on distingue clairement les énormes blocs de glace (vous êtes en A1) :



L'imposant paquebot n'est pas aisé à manoeuvrer.
Les déplacements se font par segments droits entre deux points d'intersection de la grille. Chaque segment est parcouru dans une même unité de temps. Cela signifie que la vitesse du navire sur un segment de longueur L est deux fois moins grande que sur un segment de longueur 2L.
Pour déterminer en quel point de la grille le navire peut arriver au bout de la prochaine unité de temps, on répète le segment précédent puis on choisit soit le point d'arrivée, soit l'un des points immédiatement voisins.
Même si on effectue plusieurs étapes sur des segments alignés, on ne répète que le dernier pour calculer le prochain déplacement.
Il est interdit de passer par un des points du bord de la zone car le radar ne voit pas ce qui s'y trouve. Par ailleurs, les segments ne doivent absolument pas toucher ne serait-ce que l'extrémité d'un iceberg.
Au départ en A1, on peut aller en n'importe quel point (sauf si la trajectoire touche un iceberg évidemment).

Voici un exemple :



A l'étape 1, on est allé de A1 en C2.
L'étape 2 nous mènera donc jusqu'en E3 ou bien sur l'un des points verts (D2, D3, D4, E2, E4, F3, F4). Le point F2 est interdit car l'étape suivante nous conduirait à coup sûr au naufrage ou sur le bord de la zone.
On voit que si on choisit le point F3 (en accélérant), on n'aura plus le choix ensuite qu'entre H4, H5, I4 ou I5 pour l'étape 3. Les points H3 et I3 sont interdits car la trajectoire passerait par le point G3 qui est la pointe d'un iceberg.

Enfin, ne tenez pas compte des petites imperfections du dessin. Les sommets des figures qui représentent les icebergs se trouvent exactement aux intersections des lignes de la grille.

Question : Quel est le trajet le plus rapide pour aller de A1 en K11 tout en évitant les icebergs ?
Donnez la réponse en dessin ou par les coordonnées des points successifs.

Posté par fasa fasa

17 déplacements

Posté par totti1000 totti1000

Salut godefroy,

Voici ma proposition :



Merci.

Posté par Nofutur2 Nofutur2

Je trouve le chemin:
A1-B3-C4-D4-E3-G2-H2-I3-I4-H5-G7-F8-F9-G10-I10-K11.

Posté par sephdar sephdar

bonjour,

j'essaie ceci :

Posté par Kidam Kidam

Je n'ai pas trouvé mieux que 16 segments

Merci pour l'énigme

Posté par masab masab

Trajet le plus rapide pour aller de A1 en K11 tout en évitant les icebergs
A1
B3
C4
D4
F3
G2
H2
I3
I4
H5
G7
F8
F9
G10
I10
K11

Posté par Tof Tof

Bonjour,

Je propose le trajet suivant :
A1
B3
C4
D4
E3
G2
H2
I3
I4
H5
G7
F8
F9
G10
I10
K11

Soit un total de 15 déplacements.
Merci pour l'énigme,

Tof

Posté par dpi dpi

Bonjour,

Si  j'ai bien compris les points possibles je donnerais
le parcours ci-joint

Posté par rschoon rschoon

Bonjour à tous.

Ma réponse ci-dessous

Cordialement

Posté par Skep Skep

Bonsoir, je vous donne ma réponse très tard, j'espère ne pas avoir fait d'erreurs d'inattention

Posté par Bam Bam

Salut Godefroy !

Voici ma réponse :

A1-B3-C4-D4-E3-G2-H2-I3-I4-H5-G7-F8-F9-G10-I10-K11

Posté par dpi dpi

Une colonne de trop !!!!

Mon plan possède la colonne F en trop !!!!

Mon GIGANTIC ne coulera pas gràce à une fauusse carte !

la seule manoeuvre différente est F2/G1 au lieu de F2/H1.
La fin du parcours est superposable.
Bon exemple d'alignement des repères en colonnes/excel

Posté par kotaryu kotaryu

Posté par caylus caylus

Bonjour Godefroy,

J'ai trouvé une solution mais elle n'est peut-être pas le minimum.


Merci pour la joute.

Posté par romeagle96 romeagle96

Chemin plus court : A1;H2;J7;I10;K11.
Distance parcourue si on admet que le quadrillage est constitué de carreaux de 1cm de coté= racine de (49 + 1) + rac(4+25) + rac(1+4) + rac(4+1) = 17,8546 cm.

Posté par plumemeteore plumemeteore

Bonjour Godefroy.
A1 B3 C4 D4 E3 G2 H2 I3 I4 H5 G7 F8 F9 G10 I10 K11
parcours en quinze unités de temps

Posté par geo3 geo3

Bonjour
Sans conviction pour le chemin minimum
A+

Posté par RickyDadj RickyDadj

Salut, Godefroy!
Je vais jouer avec le feu, parce que je suis pas sur d'avoir tout bien compris, mais je propose le trajet aux coordonnees suivant:
A1 ; B3 ; C4 ; D4 ; F3 ; G2 ; H2 ; I3 ; I4 ; H5 ; G7 ; F8 ; F9 ; G10 ; I10 ; K11.
Le tout en 15 segments, donc 15 unites de temps! Pitie, faites que ce soit le (l'un des) plus court(s)!
Merci, et a tres bientot, j'espere...

Posté par ksad ksad

Bonjour
Voici ma proposition de trajet
Les ronds (bleus ou rouges) symbolisent les points de la grille qui ne sont ni au bord de la zone, ni sur un radar.
Il s'agit donc de trouver le trajet le plus rapide passant par ces points et respectant les règles de déplacement. Il a donc quelques petites variantes possibles, mais globalement le trajet optimal devrait ressembler à ceci (voir image).
Merci pour cette gigantesque joute et à bientôt !

Posté par torio torio

A+
Torio

Posté par manpower manpower

Bonjour,

ça me rappelle furieusement les "courses de vecteurs" que je faisais pendant les cours de maths...

Premier jet, sans chercher à optimiser les chemins. Je pense qu'il y a deux variantes:




Merci godefroy_lehardi.

Posté par Belladu44 Belladu44

le rouge signifie les points succèssifs

Posté par Nanou2b Nanou2b

Bonjour,

je trouve plusieurs parcours possibles, pour un temps minimal de 15 segments. Voici un de ces parcours possibles :

Posté par sbarre sbarre

Bonjour a tous et merci a messire Godefroy,
je propose le trajet suivant:
A1-B3-C4-D4-E3-G2-H2-I3-I4-H5-G7-F8-F9-G10-H10-I10-K11
Ce qui fait un total de 16 segments/unites de temps (17points).

Posté par Pierre_D Pierre_D

Bonjour Godefroy,

Je ne trouve pas de trajet en moins de 15 étapes, d'un tas de façons possibles ; une étape peut d'ailleurs être de longueur nulle, ce qui n'autorise pas à la supprimer, et donc à passer à l'as sa durée unité.

Parmi les solutions à 15 étapes, je te donne l'une de celles dont le tracé me semble le plus harmonieux :

Posté par salmoth salmoth


Bonjour

voila ma reponse:
il existe un trajet de 15 etapes (soit 14 points en excluant A1 et K11)
il y a excatement 8 (2³) trajets distincts de 15 etapes :
ces trajets sont de la forme:
A1;B3;{B4;C4};E3;{G2};H2;I3;I4;H5;{G6};F8;F9;G10;I10;K11
          {C4;D4}      {F2}                    {G7}
(j'ai attaché une image pour plus de clareté ...)

il n'existe pas de trajet de moins de 15 etapes ... enfin j'espere !

merci pour cette joute !

Posté par Eric1 Eric1

Bonjour

Pas sur que ce soit optimum, mais j'ai 2 solutions:
Les points:
A1-B3-C4-D4-E3-G2-H2-I3-I4-H5-G7-F8-F9-G10-I10-K11

Posté par Benwat Benwat

Voilà ma solution. 15 étapes. Il y en a plusieurs je crois, mais on peut pas faire moins (ou alors je mange mon chapeau).



Sinon, vous connaissez un bon logiciel gratuit pour traiter des graphs ?

Posté par Chatof Chatof

Bonjour,
Je propose le parcours vert.
Je trouve 14 solutions pour un parcours en 15 unités de temps.
3 variantes au départ puis 2 variantes (plus une pour la verte) puis de nouveau 2 variantes soit (3*2+1)*2 =14 solutions

A1 B3 C4 D4 E3 - G2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11
A1 C3 D4 D4 E3 - G2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11
A1 B3 B4 C4 E3 - G2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11

A1 B3 C4 D4 E3 - F2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11
A1 C3 D4 D4 E3 - F2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11
A1 B3 B4 C4 E3 - F2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11

A1 B3 C4 D4 - F3 - G2 H2 I3 I4 H5 G6 F8 F9 G10 I10 K11

A1 B3 C4 D4 E3 - G2 - H2 I3 I4 H5 G7 F8 F9 G10 I10 K11
A1 C3 D4 D4 E3 - G2 - H2 I3 I4 H5 G7 F8 F9 G10 I10 K11
A1 B3 B4 C4 E3 - G2 - H2 I3 I4 H5 G7 F8 F9 G10 I10 K11

A1 B3 C4 D4 E3 - F2 - H2 I3 I4 H5 G7 F8 F9 G10 I10 K11
A1 C3 D4 D4 E3 - F2 - H2 I3 I4 H5 G7 F8 F9 G10 I10 K11
A1 B3 B4 C4 E3 - F2 - H2 I3 I4 H5 G7 F8 F9 G10 I10 K11

A1 B3 C4 D4 - F3 - G2 H2 I3 I4 H5 G7 F8 F9 G10 I10 K11

Dommage pour :
A1 C3 D4 D4 E3 - G2 - H2 I3 I4 H5 G6 F8 F9 G10 I10 K11
Le segment D4 D4 compte pour une unité de temps, un temps d'arrêt pour un virage serré !
Je n'arrive pas à trouver plus court.
Merci pour cette énigme sympathique.

Posté par -greg- -greg-

Bonjour,
Je propose le chemin suivant :

Posté par dakane dakane

15 segments

Posté par isis974 isis974

Bonjour, c'est ma première énigme.
A1 D4 G2 I3 I4 F9 K11;

Posté par DreamrelS DreamrelS

On passe par les points suivants, dans l'ordre :
A1-H2-J7-I10-K11

Posté par jonjon71 jonjon71

Bonjour,

Sans conviction je propose une solution en 15 déplacements en image.



Merci!

Posté par brubru777 brubru777

Bonjour,

Je trouve un trajet en 15 déplacements

A1 B3 C4 D4 E3 G2 H2 I3 I4 H5 G7 F8 F9 G10 I10 K11

Posté par godefroy_lehardi godefroy_lehardi

Clôture de l'énigme :

Quelques naufrages et pas mal de retards. Il vaut mieux prendre l'avion.
Il y avait en gros une seule route possible, avec des petites variantes.

Posté par RickyDadj RickyDadj

Ouf! J'ai eu bon! Je dois dire que c'est la joute qui m'a le plus terrifie* en ce mois d'Avril (probleme d'incertitude...).
J'etais assez vite parvenu a* la conclusion (peut etre fausse, d'ailleurs) que le trajet devait obligatoirement passer par le sud-est de la grille et qu'a partir du point I3, on ne pouvait arriver en K11 qu'avec minimum 8 deplacements. Y avait plus qu'a minimiser le trajet de A1 a* I3, de facon que l'arrive en I3 permette de continuer...
Bref, ce fut effrayant, mais c'est comme ca qu'on les aime sur l'ile (enfin, je l'espere...).

Posté par RickyDadj RickyDadj

Sinon, j'ai une petite question a* poser a kidam: tu serais pas du genre a* rechercher desesperement du poisson? Je plaisante, mais je dis ca parce que t'as bien poste* le trajet en 15 deplacements et tout, mais t'as ecrit au-dessus... 16! Grace a* la vigilance du correcteur (bravo! bravo!), nous n'aurons pas besoin de faire une requete (qui aurait ete* tout a* fait justifiee, car la reponse est parfaitement juste).
Peut etre que ton corps veut du poisson, mais ton cerveau, un peu trop performant, trouve malgre* lui les reponses...
Bon, a plus!

Posté par Kidam Kidam

Tu as oublié une possibilité RickyDadj : Je suis schizophrène ! Ma première personnalité est un boulet incapable de compter correctement ou de faire une addition tandis que ma seconde extrait les racines cubiques de tête tout en trouvant simultanément le mot le plus long au jeu "Des chiffres et des lettres".

Posté par dpi dpi

Dans le genre poissonier,j'ai une grande expérience.
Regardez ma réponse et cherchez l'erreur....

Sans cela je serais 3 eme ce mois-ci donc premier des
"normaux".

Posté par RickyDadj RickyDadj

Et dire que le trajet se faisait bien en 15 deplacements! Cette colonne ajoutee sur votre carte (ou oubliee par le posteur...) a bien sauver le Gigantic du naufrage, mais son capitaine a ete* remercie* (avec un poisson) pour n'avoir pas respecte* les ordres de l'Etat-Major lehardi...
3eme [...] donc premier des "normaux"! Je suppose que cela sous-entend (auquel cas, je suis bien d'accord) que deux certains individus vivants sur cette ile sont d'une espece superieure et surevoluee! Je crois qu'on n'a pas besoin de les nommer...

Posté par RickyDadj RickyDadj

D'ailleurs, j'ai une theorie (a* ne pas prendre avec serieux) a* ce sujet.
Il me semble tout de meme peu probable qu'il y ait parmi nous deux extraterrestres (ou robots qui reflechissent plus vite que leur ombre) et qu'on ne s'en rende pas compte. Est-il possible que Messieurs Nofutur2 et totti1000 (quels noms bien choisis!) ne soient qu'une seule et meme personne?
Et si, en plus, cette seule et meme personne se trouvait encore n'etre personne d'autre que jamo ou godefroy_lehardi, venu mettre la patee a* tout le peuple de l'ile?
Quel delire!

Posté par Benwat Benwat

Pour être certain d'avoir une réponse optimal, on pouvait considérer un graph orienté où les sommets étaient les déplacements possibles, et où une arrête existe entre deux sommets lorsque l'on peut faire le déplacement du second sommet après celui du premier.
C'est un peu long à construire, mais bon...
On rajoute un sommet-source de départ (parce qu'à priori on ne sait pas quel sera le premier déplacement) relié à tout les déplacements partant de A1 et un sommet-puit d'arrivé (même raison) relié à tout les déplacements allant sur K11.
Et après, il suffit de chercher le chemin le plus court entre le le sommet-source de départ et le sommet-puit d'arrivé.

C'est assez frustrant celà dit, parce que la solution obtenu par ce procédé est finalement celui que j'avais eu par intuition au départ. Mais la crainte de l'incertitude m'a également fait sufisemment douté pour que je cherche une façon d'être sur.

J'avoues c'est con...  :S
Mais du coup, je me demande si, avec ta collone suplémentaire on a pas moyen d'aller plus vite en passant entre les deux icebergs...


En tout cas, superbe énigme, je connaissais pas du tout les courses de vecteurs, c'est vraiment cool.  ^^