Enigmo 176 : Des petits tours pour une tour

Posté par jamo jamo

Bonjour,

une tour est sur un échiquier rectangulaire. Elle est située dans le coin supérieur gauche (croix bleue) et doit se rendre dans la coin inférieur gauche (croix rouge).
La tour ne peut se placer que sur des cases en se déplaçant horizontalement ou verticalement. Elle ne doit jamais repasser par la même case (et donc la trajectoire ne peut pas se croiser).

Pour un échiquier de 3 lignes et 2 colonnes, il existe 4 trajets possibles (voir le dessin).

Question : combien existe-t-il de trajets différents pour un échiquier de 3 lignes et 5 colonnes ?


Bonne recherche !

Posté par pierrecarre pierrecarre

Bonjour !

Je compte 26 trajets possibles.

Cordialement,

r².

Posté par LeDino LeDino

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 .

Posté par Nofutur2 Nofutur2

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

Posté par manpower manpower

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.

Posté par jonwam jonwam

52

Posté par godefroy_lehardi godefroy_lehardi

Bonjour Jamo,

Je pense qu'il existe 48 chemins possibles.

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

Posté par Daniel62 Daniel62

Bonjour Jamo,

nombre de trajets différents  

Posté par pacou pacou

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.

Posté par integral integral

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

Posté par miss_estrella miss_estrella

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.

Posté par Rudi Rudi

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

Posté par MatheuxMatou MatheuxMatou

bonjour Jamo

Personnellement je dirais 25 trajets possibles

MM

Posté par totti1000 totti1000

Salut Jamo,
Je propose 69 trajets différents.

Posté par jolenul jolenul

Bonjour

je pense qu'il y a 30 possibilités

Posté par sanantonio312 sanantonio312

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.

Posté par seb13009 seb13009

je dirais 16

Posté par frenicle frenicle

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 !

Posté par lo5707 lo5707

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

Posté par majda majda

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

Posté par lièvre59 lièvre59

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

Posté par ehiernard ehiernard

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

Posté par Ugreno Ugreno

bonjour Jamo,

Je propose 69

Posté par dpi dpi

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

Posté par Daniel62 Daniel62

Re bonjour Jamo,

voici les différents trajets possibles:
.

Posté par rezoons rezoons

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

Posté par LEGMATH LEGMATH

Bonsoir jamo,

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

Posté par Aurelien_ Aurelien_

Bonjour,

Pour moi : 69
quel beau chiffre !

Posté par CQR_67 CQR_67

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.

Posté par torio torio

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

A+
Torio

Posté par hhh86 hhh86

Je dirais 32

Posté par Rumbafan Rumbafan

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

Posté par sankukai51 sankukai51

13 Trajets !

Posté par ptitjean ptitjean

Bonjour,

69 trajets possibles

Merci
Ptitjean

Posté par archer archer

il peut y avoir 32 déplacement possible

Posté par Daysone Daysone

Il existe 15 trajets différents.

Posté par dagwa dagwa

Bonjour,

je dirais 36.

Posté par pierre-remy pierre-remy

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

Posté par jw_dagon jw_dagon

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.

Posté par 1emeu 1emeu

Bonjour,

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

1emeu

Posté par aajli aajli

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

Posté par frenicle frenicle

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

Posté par jamo jamo

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 !

Posté par lièvre59 lièvre59

Bonsoir

Bravo totti1000

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

Merci jamo

Louisa

Posté par frenicle frenicle

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...

Posté par manpower manpower

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.

Posté par lo5707 lo5707

il m'en manque un seul...

Posté par 1emeu 1emeu

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

Posté par manpower manpower

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...

Posté par caylus caylus

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