Bonjour !

Je compte 26 trajets possibles.

Cordialement,

r².

Bonjour,

Je me lance...
Avec une conviction modérée je propose : 69 trajets différents.

Merci pour cette énigme originale, intéressante et inquiétante .

Je trouve 75 trajets différents.
Mais je suis loin d'en être sûr !!!

Bonjour,

l'attente fut longue mais l'énigmo délectable.

Bon, pas facile d'être sûr d'avoir été exhaustif dans la recherche... mais comme je trouve par deux fois 69, je pense que ça devrait être ça... ^(???)

J'aurais aimé dessiner toutes les solutions mais le travail me semble assez fastidieux... pardon !
^{(ou alors, si personne d'autre ne l'a proposé, je pourrai scanner mon brouillon (que je conserve donc))}

Par ailleurs, le prolongement que Rudi ne manquera pas de proposer m'intéresse également beaucoup:
Existe-t-il une formule générale (comme somme de combinatoire) qui permet de calculer la solution pour une grille (m,n) ? Et si on change les points de départ et d'arrivée ?
Bref, une énigmo riche comme je les aime !
Merci jamo.

52

Bonjour Jamo,

Je pense qu'il existe 48 chemins possibles.

Merci pour cette énigme très intéressante.

Bonjour Jamo,

nombre de trajets différents  

Bonjour Jamo

Hum, ça sent le poisson mais je me sens pas de vérifier, tant pis pour moi.
Je trouve 71 trajets différents.

Merci pour l'énigmo.

Bonsoir jamo
J'en compte 67...
Merci pour l'énigme

Bonsoir!
Merci encore pour cette énigme...
Je pense qu'il existe 48 trajets différents pour un échiquier de 3 lignes et de 5 colonnes.

Bonjour

Sans grande conviction, et sans logique trouvée, 67 trajets possibles pour 5 colonnes

avec 1 colonne : 1 possibilité
avec 2 colonnes : 4 possibilités
avec 3 colonnes : 11 possibilités
avec 4 colonnes : 28 possibilités
avec 5 colonnes : 67 possibilités

Rudy

bonjour Jamo

Personnellement je dirais 25 trajets possibles

MM

Salut Jamo,
Je propose 69 trajets différents.

Bonjour

je pense qu'il y a 30 possibilités

Bonsoir,
Désespérément, je n'ai trouvé aucune manière de commencer quelque chose qui ressemble à une formule.
Alors j'ai essayé de dénombrer.
Heureusement, il n'y a pas 10 lignes et 10 colonnes.
Alors, sur:
1 colonne: 1 trajet
2 colonnes: 3 trajets
3 colonnes: 7 trajets
4 colonnes: 16 trajets
5 colonnes: 38 trajets

Soit un total de 65 trajets possibles.

je dirais 16

Bonjour

Sauf erreur j'en trouve 69 (décidément, Gainsbourg est partout en ce moment !).

Le détail en images :





Merci pour cette énigme fort intéressante !

bonjour,

c'est le genre d'énigme où l'on est pas forcément sûr à 100% (en tout cas quand on cherche "à la main")

Ma réponse est 68 trajets différents



merci pour cette énigme

je dirai 18 cas sont possible les 4 a chaque fois puis on combine  
j'espère que je n'ai rien oublié

Bonjour jamo

je t'ai encore mis un de ce trucs

le résultat

alors que je t'explique, j'ai lettrée et chiffrée ta grille

j'espère que tu vas comprendre et que je n'ai pas d'erreurs



j'aurai pas su te mettre tous les tracés

2 colonnes et 3 lignes

a1,b1,c1
a1,a2,b2,c2,c1
a1,b1,b2,c2,c1
a1,a2,b2,b1,c1

= 4 trajets

3 colonnes et 3 lignes

a1,a2,a3,b3,c3,c2,c1
a1,a2,a3,b3,c3,c2,b2,b1,c1
a1,b1,b2,a2,a3,b3,c3,c2,c1
a1,a2,b2,b3,c3,c2,c1
a1,a2,a3,b3,b2,b1,c1
a1,a2,a3,b3,b2,c2,c1
a1,b1,b2,b3,c3,c2,c1

= 7 trajets

4 colonnes et 3 lignes

a1,a2,a3,a4,b4,b3,c3,c2,c1
a1,a2,b2,b3,b4,c4,c3,c2,c1
a1,b1,b2,a2,a3,a4,b4,c4,c3,c2,c1
a1,a2,a3,a4,b4,c4,c3,b3,b2,b1,c1
a1,b1,b2,b3,a3,a4,b4,c4,c3,c2,c1
a1,b1,b2,a2,a3,a4,b4,b3,c3,c2,c1
a1,a2,a3,a4,b4,c4,c3,c2,c1
a1,a2,b2,b3,a3,a4,b4,c4,c3,c2,c1
a1,b1,b2,b3,b4,c4,c3,c2,c1
a1,a2,a3,a4,b4,c4,c3,b3,b2,c2,c1
a1,a2,a3,b3,b4,c4,c3,c2,c1
a1,a2,a3,b3,b4,c4,c3,c2,b2,b1,c1
a1,b1,b2,a2,a3,b3,b4,c4,c3,c2,c1
a1,a2,a3,a4,b4,b3,b2,b1,c1
a1,a2,a3,a4,b4,c4,c3,c2,b2,b1,c1
a1,a2,a3,a4,b4,b3,c3,c2,b2,b1,c1
a1,a2,a3,a4,b4,b3,b2,c2,c1

= 17 trajets

5 colonnes et 3 lignes

a1,b1,b2,b3,b4,b5,c5,c4,c3,c2,c1
a1,b1,b2,b3,b4,a4,a5,b5,c5,c4,c3,c2,c1
a1,b1,b2,b3,a3,a4,b4,b5,c5,c4,c3,c2,c1
a1,b1,b2,b3,a3,a4,a5,b5,c5,c4,c3,c2,c1
a1,b1,b2,b3,a3,a4,a5,b5,b4,c4,c3,c2,c1
a1,b1,b2,a2,a3,b3,b4,b5,c5,c4,c3,c2,c1
a1,b1,b2,a2,a3,b3,b4,a4,a5,b5,c5,c4,c3,c2,c1
a1,b1,b2,a2,a3,a4,b4,b5,c5,c4,c3,c2,c1
a1,b1,b2,a2,a3,a4,a5,b5,c5,c4,b4,b3,c3,c2,c1
a1,b1,b2,a2,a3,a4,a5,b5,c5,c4,c3,c2,c1
a1,b1,b2,a2,a3,a4,a5,b5,b4,c4,c3,c2,c1
a1,b1,b2,a2,a3,a4,a5,b5,b4,b3,c3,c2,c1
a1,a2,b2,b3,b4,b5,c5,c4,c3,c2,c1
a1,a2,b2,b3,b4,a4,a5,b5,c5,c4,c3,c2,c1
a1,a2,b2,b3,a3,a4,b4,b5,c5,c4,c3,c2,c1
a1,a2,b2,b3,a3,a4,a5,b5,c5,c4,c3,c2,c1
a1,a2,b2,b3,a3,a4,a5,b5,b4,c4,c3,c2,c1
a1,a2,a3,b3,b4,b5,c5,c4,c3,c2,b2,b1,c1
a1,a2,a3,b3,b4,b5,c5,c4,c3,c2,c1
a1,a2,a3,b3,b4,a4,a5,b5,c5,c4,c3,c2,b2,b1,c1
a1,a2,a3,b3,b4,a4,a5,b5,c5,c4,c3,c2,c1
a1,a2,a3,a4,b4,b5,c5,c4,c3,b3,b2,c2,c1
a1,a2,a3,a4,b4,b5,c5,c4,c3,b3,b2,b1,c1
a1,a2,a3,a4,b4,b5,c5,c4,c3,c2,b2,b1,c1
a1,a2,a3,a4,b4,b5,c5,c4,c3,c2,c1
a1,a2,a3,a4,a5,b5,c5,c4,b4,b3,c3,c2,b2,b1,c1
a1,a2,a3,a4,a5,b5,c5,c4,b4,b3,c3,c2,c1
a1,a2,a3,a4,a5,b5,c5,c4,b4,b3,b2,c2,c1
a1,a2,a3,a4,a5,b5,c5,c4,b4,b3,b2,b1,c1
a1,a2,a3,a4,a5,b5,c5,c4,c3,b3,b2,c2,c1
a1,a2,a3,a4,a5,b5,c5,c4,c3,b3,b2,b1,c1
a1,a2,a3,a4,a5,b5,c5,c4,c3,c2,b2,b1,c1
a1,a2,a3,a4,a5,b5,c5,c4,c3,c2,c1
a1,a2,a3,a4,a5,b5,b4,c4,c3,b3,b2,c2,c1
a1,a2,a3,a4,a5,b5,b4,c4,c3,b3,b2,b1,c1
a1,a2,a3,a4,a5,b5,b4,c4,c3,c2,b2,b1,c1
a1,a2,a3,a4,a5,b5,b4,c4,c3,c2,c1
a1,a2,a3,a4,a5,b5,b4,b3,c3,c2,b2,b1,c1
a1,a2,a3,a4,a5,b5,b4,b3,c3,c2,c1
a1,a2,a3,a4,a5,b5,b4,b3,b2,c2,c1
a1,a2,a3,a4,a5,b5,b4,b3,b2,b1,c1

= 41 trajets

4 + 7 + 17 + 41 = 69 trajets en tout

quel truc ! j'ai pratiqué par symétrie pour les trajets

trop long

Merci jamo

Louisa

Alors (à la main...)

1 chemin pour un damier 3x1

3 nouveaux pour un damier 3x2

7 de plus pour un damier 3x3

17 de plus pour un damier 3x4

et 38 de plus pour un 3x5

soit un total de 66

bonjour Jamo,

Je propose 69

Sur les 15 cases ,je trouve que la tour peut aller de A à C  en
2 coups : 1
4 coups : 3
6 coups : 5
8 coups : 9
10 coups :12
12 coups :23
14 coups :3
Soit un total de 56 trajets sauf erreur ou omission

Re bonjour Jamo,

voici les différents trajets possibles:
.

Bonjour ,
le sage a dit qui ne tente rien n'a rien  je pense que c'est une folie de me lancer comme ca sans etre sur de mon résultat mais tant pis je dirais 53 trajets différents (ca sent le ) la méthode utilisée est simple:
chercher le nombre de trajet de longueur 3 cases, ceux de longueur 5 cases, ceux de longueur 7 cases etc..
j'ai trouvé:
1 trajet de 3 cases
3 trajets de 5 cases
5 trajets de 7 cases
9 trajets de 9 cases
11 trajets de 11 cases
20 trajets de 13 cases
4 trajets de 15 cases
soit 53 trajets différents

Bonsoir jamo,

Il existe 66 trajets différents pour un échiquier de 3 lignes et 5 colonnes.

Bonjour,

Pour moi : 69
quel beau chiffre !

Bonjours,

Pour cette énigme j'ai réalisé les différentes possibilités pour un système 3x2 => 4 solutions et 3x3=> 11 solution après plusieurs essais j'ai pu conjecturer une suite : U_n= 1 + U_n-1 + n*2ⁿ/4 avec U1=1 et n le nombre de colonne soit 3xn avec n=2 pour 3x2.
En effet j'ai pu constater que à chaque ajout de colonne on ajoute une possibilité ne comportant pas de possibilité symétrique à celui-ci, plus un certain nombre n*2ⁿ/4 de possibilités possédant un symétrique.
On a donc:
U₁=1
U₂=1+1+2*2²/4=4
U₃=1+4+3*2³/4=11
U₄=1+11+4*2⁴/4=28
U₅=1+28+5*2⁵/4=69

Je propose donc la solution: Il y a 69 possibilités pour un échiquier de 3 lignes et 5 colonnes.

Avec un arbre, j'ai trouvé : 69 trajets différents.

A+
Torio

Je dirais 32

Bonjour,

Ce fut long...mais c'est à ça que sert le week-end  

Je propose 69 chemins possibles...

(sur 1798 chemins au total : les bons, ceux qui sortent du cadre et ceux qui se referment sur eux-même
...)

13 Trajets !

Bonjour,

69 trajets possibles

Merci
Ptitjean

il peut y avoir 32 déplacement possible

Il existe 15 trajets différents.

Bonjour,

je dirais 36.

28 mais je ne suis pas sûr du tout !
merci pour l'énigme !

Bonsoir,

Je trouve 73 trajets possibles.

Bon, j'ai trouvé ça à la main, à l'ancienne, et je ne suis pas du tout sûr du résultat. Si quelqu'un a un algo à proposer, je suis preneur.

Merci pour l'énigme.

Bonjour,

je compte 69 trajets possibles.
Merci pour l'énigme,

1emeu

c'est un peut dure a trouver les jeunes ^^
j'ai trouver  45 trajets différents

J'espère que c'est juste
c combien jamo  ??  ^^
hhh

Bonjour,

Après moult réflexion, je crois avoir enfin démontré la relation de récurrence donnant le nombre de trajets pour un échiquier de 3 n cases. Si T_n est ce nombre de trajets, on a

T_n = 2T_n-1 + T_n-2 + 2

Les premiers T_n sont donc :

T₁ = 1
T₂ = 4
T₃ = 11
T₄ = 28
T₅ = 69
T₆ = 168
T₇ = 407
T₈ = 984
T₉ = 2377
T₁₀ = 5740
...

Merci encore jamo pour cette passionnante énigme.

Cordialement
Frenicle

Clôture de l'énigme

Bon, il est temps d'arrêter le massacre pour cette énigme qui aurait mérité 4 étoiles !

La bonne réponse est : 69 trajets.

Pourtant, j'ai pris cette énigme dans un rallye mathématique de niveau terminale.

Le sujet ici : (exercice 3)

Et le corrigé ici :

Dans ce corrigé, on y démontre la formule de récurrence pour ce problème d'apparence simple mais bougrement complexe !

Qui ose se lancer dans le même problème avec 4 lignes ? 5 lignes ? n lignes ?

Et c'est donc totti1000 qui gagne le mois de janvier !

Bonsoir

Bravo totti1000

formule de récurrence => j'ai regardé

Merci jamo

Louisa

Bonsoir

J'ai trouvé assez rapidement la relation de récurrence mais pour la démontrer je me suis pris la tête pendant quinze jours
Apparemment, ma démonstration est un peu différente de celle du lien de jamo.
Mais c'est presque aussi difficile à exposer clairement qu'à trouver.

Chapeau au lycéen qui a trouvé tout ça en temps limité !!

Dès que j'ai un moment, je regarde ce que ça donne avec 4 lignes, mais ça promet...

Bonsoir,

merci aux courageux qui ont posté les solutions en image (ce dont je n'ai pas eu le courage).
Merci également pour la belle formule de récurrence
et enfin bravo à totti1000 pour sa victoire.

il m'en manque un seul...

Bonjour,

pour ceux que ca interesserait, voici un code en C++ permettant de calculer le résultat et d'afficher tous les chemins possibles pour n'importe quelle taille de rectangle.
Chaque ligne de la sortie contient un chemin donné avec les lettres d,g,h,b (pour droite, gauche, haut, bas).  La dernière ligne contient le nombre de chemins.
Pour choisir les tailles du rectangles, il suffit de changer les valeurs LARGEUR et HAUTEUR (aux lignes 3 et 4 du code).

Par exemple, pour 5 lignes et 7 colonnes, il trouve les 638472 chemins possibles en 43s sur mon ordi.

Bon voilà le code:

#include <iostream>
#include <stdlib.h>
#define LARGEUR 5
#define HAUTEUR 3
using namespace std;
int compteur=0;
int verif (char* tc, unsigned int l)
{
  int i;
  int R1 = 0;
  int R2 = 0;
  for (i = 0; i < l; i++)
    {
        switch(tc[i])
{
case 'd': R1 ++; break;
case 'b': R2 ++; break;
case 'g': R1 --; break;
case 'h': R2 --; break;
}
      if (R1 < 0 || R1 > LARGEUR-1 || R2 < 0 || R2 > HAUTEUR-1)  return 0;
    }
  R1 = 0;
  R2 = 0;
  for (i = 0; i < l; i++)
    {
        switch(tc[l-i-1])
{
case 'd': R1 ++; break;
case 'b': R2 ++; break;
case 'g': R1 --; break;
case 'h': R2 --; break;
}
      if (R1 == 0 && R2 == 0)  return 0;

    }
  if (R1 == 0 && R2 == (HAUTEUR-1)) return 2;
  return 1;
}
void search (char tc[], unsigned int l){
  unsigned int i;
  int v = verif (tc, l);
  switch(v)
    {
    case 0: return;
    case 2:
      for (i = 0; i < l; i++) cout << tc[i];
      cout << endl;
      compteur++;
      return;
    case 1:
      tc[l] = 'd';
      search (tc, l + 1);
      tc[l] = 'b';
      search (tc, l + 1);
      tc[l] = 'g';
      search (tc, l + 1);
      tc[l] = 'h';
      search (tc, l + 1);
    }
}
int main ()
{
  char tc[50];
  unsigned int i;
  for (i = 0; i < 50; i++) tc[i] = 0;
  tc[0] = 'd';
  search (tc, 1);
  tc[0] = 'b';
  search (tc, 1);
  cout<<compteur<<endl;
}


1emeu

Un beau programme pour tous les cas, merci 1emeu !
Bon, dommage que je sois ignare en C++, mais je vais regarder ça de plus près...

Bonsoir 1emeu,

Félicitations pour ce programme.
La 2è boucle de la fonction verif est une très jolie solution pour éviter le bouclage dans un chemin.

Bonsoir ManPower,si le basic ne vous est pas inconnu:


DECLARE SUB See (l AS INTEGER)
DECLARE SUB Init ()
DECLARE SUB Chemin (l AS INTEGER)
DECLARE FUNCTION Verify% (l AS INTEGER)
CONST LARGEUR = 5
CONST HAUTEUR = 3
CONST Droite = 1, Gauche = 2, Haut = 3, Bas = 4
CONST che$ = "EONS"

CONST Faux = (0 = 1), Vrai = NOT (Faux)

DIM SHARED Noeud(50) AS INTEGER
DIM SHARED Compteur AS LONG
CLS
CALL Init
  Noeud(0) = Droite: CALL Chemin(1)
  Noeud(0) = Bas: CALL Chemin(1)
  PRINT "Compteur="; Compteur
END

SUB Chemin (l AS INTEGER)
DIM v AS INTEGER
  v = Verify%(l)
  SELECT CASE v
   CASE 0

   CASE 2
    Compteur = Compteur + 1
    CALL See(l)
   CASE 1
    Noeud(l) = Droite: CALL Chemin(l + 1)
    Noeud(l) = Bas: CALL Chemin(l + 1)
    Noeud(l) = Gauche: CALL Chemin(l + 1)
    Noeud(l) = Haut: CALL Chemin(l + 1)
   END SELECT
END SUB

SUB Init
DIM i AS INTEGER
  FOR i = 1 TO 50
   Noeud(i) = 0
  NEXT i
  Compteur = 0
END SUB

SUB See (l AS INTEGER)
DIM i AS INTEGER
DIM ch AS STRING
LOCATE 2, 1: PRINT SPACE$(80)
LOCATE 2, 1
  ch = ""
  FOR i = 0 TO l - 1
   ch = ch + MID$(che$, Noeud(i), 1)
  NEXT i
  PRINT Compteur, ch
END SUB

FUNCTION Verify% (l AS INTEGER)

  DIM Done AS INTEGER: Done = Faux
  DIM Ret AS INTEGER: Ret = 1
  DIM i AS INTEGER
  DIM R1 AS INTEGER: R1 = 0
  DIM R2 AS INTEGER: R2 = 0

  FOR i = 0 TO l - 1
   SELECT CASE Noeud(i)
    CASE Droite
     R1 = R1 + 1
    CASE Gauche
     R1 = R1 - 1
    CASE Bas
     R2 = R2 + 1
    CASE Haut
     R2 = R2 - 1
   END SELECT
   IF ((R1 < 0) OR (R1 > (LARGEUR - 1)) OR (R2 < 0) OR (R2 > (HAUTEUR - 1))) THEN
    Ret = 0
    Done = Vrai
    EXIT FOR
   END IF
  NEXT i

  IF NOT (Done) THEN
   R1 = 0
   R2 = 0
   FOR i = 0 TO l - 1
    SELECT CASE Noeud(l - i - 1)
     CASE Droite
      R1 = R1 + 1
     CASE Gauche
      R1 = R1 - 1
     CASE Bas
      R2 = R2 + 1
     CASE Haut
      R2 = R2 - 1
    END SELECT
  
    IF ((R1 = 0) AND (R2 = 0)) THEN
    ' on boucle!!!!
     Ret = 0
     Done = Vrai
     EXIT FOR
    END IF
   NEXT i
   IF (R1 = 0 AND R2 = (HAUTEUR - 1)) THEN
    Ret = 2
   END IF
  END IF
Verify% = Ret
END FUNCTION