Inscription / Connexion Nouveau Sujet
Niveau 2 *
Partager :

Enigmo 288 : Saute-mouton le plus long, la suite

Posté par
jamo Moderateur
04-01-13 à 12:19

Bonjour tout le monde,

et voici la suite de l'énigme précédente, passons à la dimension 2 !

Cette fois-ci, les enclos sont organisés en rectangle comme le montre la figure ci-dessous. La longueur de chaque côté d'un petit carré est toujours égale à 1.

Le mouton est initialement dans l'enclos 1, et veut toujours visiter tous les autres enclos une seule fois chacun, puis retourner à l'enclos 1, de telle sorte que le trajet soit le plus long possible.

Attention, cette fois-ci on rajoute une contrainte sur les déplacements : les sauts ne peuvent s'effectuer qu'entre deux cases situées sur une même ligne ou une même colonne (pas de saut diagonale donc, uniquement des horizontaux et verticaux).

Par exemple, pour le cas des 6 enclos (2*3), le trajet le plus long est le suivant : 1-3-2-5-6-4-1, ce qui fait une longueur maximale de : 2+1+1+1+2+1=8.

Question : Quel est le trajet le plus long dans le cas des 10 enclos (2*5) ?

Pour la réponse, vous me donnerez :
- la longueur totale du trajet
- la liste des cases visitées (donc une liste de 11 nombres commençant et finissant par 1).

S'il existe plusieurs trajets pour la longueur maximale, un seul trajet suffira.

Bonne recherche et bonne année à tous !

Enigmo 288 : Saute-mouton le plus long, la suite

Posté par
lo5707
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 12:33

perdubonjour

le mieux que je trouve pour celui-ci est 20, avec cette solution :

1-5-10-6-9-4-2-7-8-3-1

merci pour cette énigme

Posté par
sbarre
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 12:37

perduBonjour,
de facon intuitive, je propose:
1-5-2-4-3-8-9-7-10-6-1   ce qui nous fait 22  
sans plus chercher....

Posté par
panda_adnap
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 13:11

gagné24 unites
1 5 3 8 10 6 9 7 2 4 1

Posté par
masab
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 13:48

gagnéBonjour,

- la longueur totale du trajet : 24
- la liste des cases visitées :  1-5-2-4-9-6-10-7-8-3-1

Merci pour cette énigme double !

Posté par
Alishisap
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 14:28

perduBonjour et merci pour l'énigme

Ma proposition et mon raisonnement sera beaucoup plus intuitif que l'autre énigme. Je prends le risque.

Je propose donc le trajet 1 3 4 2 5 10 7 8 9 6 1 qui donne une longueur de 18, qui est la plus grande longueur possible (comme l'autre énigme, comme par hasard ).

J'ai d'abord considérer simplement la première ligne. Le mouton part du 1 pour arriver au 5, le trajet étant bien sûr le plus long possible. La plus grande longueur possible dans ce cas est de 8 (toujours avec une probabilité proche de 1), que donne par exemple le trajet 1 3 4 2 5.
Ensuite le mouton descend en case 10. La longueur est de 9.
Partant de la case 10, le mouton doit arriver en case 6 (la longueur étant toujours la plus grande possible). Celle-ci est encore de 8 (logique) que donne par exemple le trajet 10 7 8 9 6. La longueur du trajet est alors de 17.
Et pour finir, le mouton retourne en case 1, pour donner une longueur totale de 18.
Encore une fois, je ne suis pas certain de la pertinence de ce raisonnement.

À bientôt.

Posté par
frenicle
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 14:34

gagnéBonjour jamo

Je trouve une longueur maximale de 24

L'un des 16 trajets possibles est :

1, 3, 8, 6, 10, 7, 9, 4, 2, 5, 1.

Posté par
carlou
Enigmo 288 04-01-13 à 15:32

perduBonjour voici la réponse que j'ai obtenue

La distance que le mouton à parcouru est : 2+1+3+1+1+1+3+1+2+1 = 16


La liste des cases visées est : 1 3 2 5 4 9 10 7 8 6 1

Posté par
totti1000
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 16:02

gagnéRe,

Je propose ici 1-3-8-6-10-7-9-4-2-5-1 pour une longueur de 24.

Merci.

Posté par
rijks
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 16:03

gagnéLa meilleur solution que je trouve c'est une longueur de 24
1;3;8;6;10;7;9;4;2;5;1

Posté par
Alishisap
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 16:26

perduRebonjour,
Dans le doute j'ai voulu vérifier ma réponse à l'aide d'un programme. Je pensais qu'il serait relativement long et complexe à réaliser et c'est pourquoi j'ai privilégié la rapidité et donc fait confiance à mon intuition plutôt que de passer 3 jours à faire un programme. En vérité, celui-ci fut bien moins long et complexe à réaliser que je ne le pensais.

Le verdict ? Un gros pour Alishisap et largement mérité

Il s'avère que la longueur du trajet la plus grande possible n'est pas 18 mais 24 (avec une proba de quasiment 100%).

Voici quelques trajets donnant 24 pour longueur, tirés à l'aide de mon programme :

1 4 2 7 9 6 10 8 3 5 1
1 3 8 6 10 7 9 4 2 5 1
1 5 2 3 8 6 10 7 9 4 1
1 4 2 7 10 6 9 8 3 5 1
1 4 3 8 9 6 10 7 2 5 1
1 4 3 8 10 6 9 7 2 5 1
1 5 2 3 8 7 10 6 9 4 1
1 4 3 8 10 6 9 7 2 5 1
1 3 8 7 10 6 9 4 2 5 1
1 4 9 6 10 7 8 3 2 5 1

Quant à la plus petite longueur possible dans la même configuration, il s'agit de 10 (même proba). Et pour le coup, il semble qu'il n'y aie que deux trajets qui donnent cette longueur :

1 2 3 4 5 10 9 8 7 6 1
1 6 7 8 9 10 5 4 3 2 1

Bien, ça m'apprendra à vouloir être trop pressé.

À bientôt

Posté par
fontaine6140
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 17:50

gagnéBonjour Jamo,
24 est la longueur totale du trajet.
[1,5,2,3,8,6,10,7,9,4,1] est la liste des cases visitées.
Merci

Posté par
castoriginal
Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 18:13

perduPour suivre,

voici ma réponse: 1 5 2 4 3 8 10 7 9 6 1  total 22



il y certainement pas mal de solutions qui donnent le même résultat, entre autres les deux solutions suivantes

1 4 2 5 10 7 9 6 8 3 1  total 22
1 4 2 5 10 6 9 7 8 3 1  total 22

Bonne Année

Posté par
geo3
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 18:29

gagnéBonjour
Je dirais :

24 comme longueur du trajet
en passant par  1->4->9->7->10->6->8->3->2->5->1

A+

Posté par
Nofutur2
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 20:05

gagnéJe trouve un trajet de 24....avec 1-5-2-4-9-6-10-7-8-3-1.

Posté par
elidrissi
re : Enigmo 288 : Saute-mouton le plus long, la suite 04-01-13 à 23:44

perdubonjour
la reponse est 22

Posté par
rogerd
Moutons 04-01-13 à 23:45

gagnéBonjour à tous et merci encore à Jamo!

Je propose le trajet

1-3-8-6-10-7-9-4-2-5-1

qui est de longueur 24.

Je pense pouvoir maintenant m'endormir sans compter les moutons!

Posté par
jugo
re : Enigmo 288 : Saute-mouton le plus long, la suite 05-01-13 à 04:14

gagnéBonjour,

Je propose un trajet max de longueur 24, par exemple :

     1     3     8     6     10     7     9     4     2     5     1

Posté par
dpi
re : Enigmo 288 : Saute-mouton le plus long, la suite 05-01-13 à 09:57

perduBonjour (suite)

pas  facile d'explorer,mais une piste:
1 5 10 6 9 4 2 7 8 3 1
soit 4+5+4+3+5+2+5+1+5+3=37

Posté par
dpi
re : Enigmo 288 : Saute-mouton le plus long, la suite 05-01-13 à 12:33

perdusuite
bien sûr 3-1=2 donc ce parcours fait 36 et non 37 (demi-poisson ?)

Posté par
ALGO
re : Enigmo 288 : Saute-mouton le plus long, la suite 06-01-13 à 12:17

perdusalut
longueur du trajet=21
1-4-2-5-3-8-10-7-9-6-1

Posté par
RickyDadj
re : Enigmo 288 : Saute-mouton le plus long, la suite 06-01-13 à 16:54

perduSalut, Jamo! Salut, tous!
Je propose une longueur de 22.
Un trajet:1-4-2-3-8-6-9-7-10-5-1.
Merci!

Posté par
torio
re : Enigmo 288 : Saute-mouton le plus long, la suite 06-01-13 à 22:45

gagnétrajet  1, 5, 3, 8, 10, 6, 9, 7, 2, 4, 1
Longueur : 24

Posté par
pdiophante
énigme 288 07-01-13 à 00:33

gagnéBonjour
Parcours 1-4-2-7-9-6-10-8-3-5-1 de longueur 3+2+1+2+3+4+2+1+2+4 = 24

Posté par
Kidam
re : Enigmo 288 : Saute-mouton le plus long, la suite 07-01-13 à 14:56

gagnéSalut (encore)

Je trouve cette fois un maximum de 24 avec, par exemple, le trajet suivant :

1-3-8-6-10-7-9-4-2-5-1

Merci

Posté par
Pierre_D
re : Enigmo 288 : Saute-mouton le plus long, la suite 07-01-13 à 16:01

gagnéSalut Jamo,

Ce coup-ci, je trouve que les trajets les plus longs sont de longueur  24  ; l'un des plus jolis, symétrique, est :  1 - 5 - 2 - 3 - 8 - 7 - 10 - 6 - 9 - 4 - 1

Posté par
mimimath
re : Enigmo 288 : Saute-mouton le plus long, la suite 08-01-13 à 10:15

perdule trajet le plus long est le suivant:
1-3-5-10-8-6-7-9-4-2-1
ce qui fait une longueur maximale de:2+2+1+2+2+1+2+1+2+1=16

Posté par
ksad
re : Enigmo 288 : Saute-mouton le plus long, la suite 08-01-13 à 20:23

gagnéme re-voilà vite fait, comme promis...
je trouve une longueur de parcours maximale de 24 avec par exemple:

1  3  8  6 10  7  9  4  2  5  1
1  3  8  7 10  6  9  4  2  5  1
1  4  2  7  9  6 10  8  3  5  1
1  4  2  7 10  6  9  8  3  5  1
1  4  3  8  9  6 10  7  2  5  1
1  4  3  8 10  6  9  7  2  5  1
1  4  9  6 10  7  8  3  2  5  1
1  4  9  7 10  6  8  3  2  5  1

et leurs inverses...
merci pour l'énigmo !
à tout bientôt

Posté par
plumemeteore
re : Enigmo 288 : Saute-mouton le plus long, la suite 08-01-13 à 22:29

perduBonjour.
Un parcours de longueur 22 : 1 5 10 7 9 6 8 3 2 4 1.

Posté par
brubru777
re : Enigmo 288 : Saute-mouton le plus long, la suite 09-01-13 à 12:37

gagnéBonjour,

Je propose le trajet suivant :
1 5 3 8 10 6 9 7 2 4 1
Longueur : 4 + 2 + 1 + 2 + 4 + 3 + 2 + 1 + 2 + 3 = 24

Merci pour l'énigme.

Posté par
manpower
re : Enigmo 288 : Saute-mouton le plus long, la suite 09-01-13 à 21:52

gagnéBonjour, pour cette suite (un peu moins évidente),

je propose : 1-5-3-8-10-6-9-7-2-4-1 de longueur 24.

Avec les interdits, c'est moins simple de dénombrer tous les cas, mais il me semble (sauf erreur) qu'il devrait y en avoir 16.

Merci pour l'énigme.
PS: Le poisson c'est bêêêurk !

Posté par
rschoon
re : Enigmo 288 : Saute-mouton le plus long, la suite 12-01-13 à 10:06

gagnéBonjour à tous.

Ma réponse :
- Trajet : 24
- Parcours : 1-3-8-6-10-7-9-4-2-5-1

Merci pour l'énigme

Posté par
Luc1408
re : Enigmo 288 : Saute-mouton le plus long, la suite 17-01-13 à 18:00

perduJe propose
1-5-2-4-3-8-10-7-9-6-1 soit
4+3+2+1+1+2+3+2+3+1 = 22

Pour la réflexion :
1) Il est naturel de limiter le nombre de changement de ligne, puisque chaque changement consomme une case et n'apporte qu'un point. On la franchira donc 2 fois.
2) La première ligne peut donner 10 points au maximum sous 2 trajets. L'un tombe sur 3, l'autre sur 4.
3) La première ligne effectuée, le reste découle logiquement. Si l'on part de la case 4, on a (...)-4-9-7-10-8-6-1 et 21 points. Si l'on part de la case 3, (...)-3-8-10-7-9-6-1 et 22 points.

Posté par
Chatof
re : Enigmo 288 : Saute-mouton le plus long, la suite 20-01-13 à 09:30

gagné24,    [1,3,8,6,10,7,9,4,2,5,1]

12 solutions :[1,3,8,6,10,7,9,4,2,5,1],[1,3,8,7,10,6,9,4,2,5,1],[1,4,2,7,9,6,10,8,3,5,1],[1,4,2,7,10,6,9,8,3,5,1],[1,4,3,8,9,6,10,7,2,5,1],[1,4,3,8,10,6,9,7,2,5,1],[1,4,9,6,10,7,8,3,2,5,1],[1,4,9,7,10,6,8,3,2,5,1],[1,5,2,7,9,6,10,8,3,4,1],[1,5,2,7,10,6,9,8,3,4,1],[1,5,3,8,9,6,10,7,2,4,1],[1,5,3,8,10,6,9,7,2,4,1]]

Merci Jamo,

Posté par
jonjon71
re : Enigmo 288 : Saute-mouton le plus long, la suite 24-01-13 à 20:08

gagnéBonjour,

Voici ma réponse :

La longueur totale du trajet le plus long est 24 et le trajet est 1 - 3 - 8 - 6 - 10 - 7 - 9 - 4 - 2 - 5 - 1.

Merci !

Posté par
jamo Moderateur
re : Enigmo 288 : Saute-mouton le plus long, la suite 30-01-13 à 16:50

Clôture de l'énigme

La longueur maximale est de 24, avec plusieurs trajets possibles.

Pour information, il existe aussi une formule qui donne la longueur maximale pour un échiquier de dimension quelconque.

Posté par
manpower
re : Enigmo 288 : Saute-mouton le plus long, la suite 30-01-13 à 22:26

gagnéBonsoir jamo,

bon après nous avoir mis l'eau à la bouche... serait-il possible d'avoir cette formule ? (ou un lien)
Merci d'entretenir notre curiosité (et culture) et de nous abreuver d'énigmes.

Posté par
dpi
re : Enigmo 288 : Saute-mouton le plus long, la suite 31-01-13 à 09:01

perduBonjour


Ne pas se fier aux calculs
5-->10 10-5 =5 mais 1.
Celle là je l'archive....

Posté par
Manga2
re : Enigmo 288 : Saute-mouton le plus long, la suite 01-06-13 à 15:24

Salut,
Je n'ai pas participé à l'énigme mais en passant je conjecture la formule suivante:
(n/2)^2 -1
Effectivement pour n=6 on a 3^2 -1=8
Pour n=10 on a 5^2 -1=24

Posté par
jamo Moderateur
re : Enigmo 288 : Saute-mouton le plus long, la suite 02-06-13 à 11:08

Je crois me souvenir que là où je me suis inspiré pour cette énigme, il y avait les formules générales pour un échiquier de dimension quelconque.

Les formules ne sont pas évidentes, il faudrait que je les recherche si certains sont intéressés.

Posté par
Manga2
re : Enigmo 288 : Saute-mouton le plus long, la suite 02-06-13 à 11:50

Merci bien!
Ah au fait celle que jai donné nest que dimension 2.

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 75:06:30.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !