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 !
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 .
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.
Bonjour Jamo,
Je pense qu'il existe 48 chemins possibles.
Merci pour cette énigme très intéressante.
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!
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
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.
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
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
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
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
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 : Un= 1 + Un-1 + n*2n/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*2n/4 de possibilités possédant un symétrique.
On a donc:
U1=1
U2=1+1+2*22/4=4
U3=1+4+3*23/4=11
U4=1+11+4*24/4=28
U5=1+28+5*25/4=69
Je propose donc la solution: Il y a 69 possibilités pour un échiquier de 3 lignes et 5 colonnes.
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
...)
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.
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 Tn est ce nombre de trajets, on a
Tn = 2Tn-1 + Tn-2 + 2
Les premiers Tn sont donc :
T1 = 1
T2 = 4
T3 = 11
T4 = 28
T5 = 69
T6 = 168
T7 = 407
T8 = 984
T9 = 2377
T10 = 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
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.
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
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :