Dénombrement: Problème de saut

Bonsoir,
J'ai un petit problème de dénombrement que je n'arrive pas à formaliser.

Un escalier comporte 8 marches.
En un saut , on peut monter 1, 2 ou 3 marches.
Initialement, je me trouve au pied de l'escalier.

Combien de façons différentes peut-on monter l'escalier ?

J'ai utilisé la méthode de dénombrement ci-dessous, mais cela ne me convient pas.

Y-a-t- il une méthode plus simple et surtout plus esthétique ?

Méthode :

Il y a 8 marches
Cela revient à trouver les entiers naturels (x,y,z) tels que : 1*x + 2y + 3z = 8

On a clairement x <= 8, y<= 4 et z<= 2

1er cas : x = 8 : Je fais 8 sauts de 1 : => 1 possibilité : (1,1, … ,1,1,11, )

2ème cas : x = 7 : Je fais 7 sauts de 1, impossible

3ème cas : x = 6 : le fais fait 6 sauts de 1, et un saut de 2 => Placer un 2 parmi 7, puis les autres 1 : 7 possibilités

(1,1,1,1,1 ,1,2)
(1,1,1,1,1 ,2,1)
(1,1,1,1,2 ,1,1)
(1,1,1,2,1 ,1,1)
(1,1,2,1,1 ,1,1)
(1,2,1,1,1 ,1,1)
(2,1,1,1,1 ,1,1)

4ème cas : x = 5 : Je fais 5 sauts de 1, et un saut de 3
=> Placer un 3 parmi 6, puis les autres 1 : 6 possibilités

(1,1,1,1,1,3)
(1,1,1,1,3,1)
(1,1,1,3,1,1)
(1,1,3,1,1,1)
(1,3,1,1,1,1)
(3,1,1,1,1,1)




5ème cas : x = 4 : Je fais 4 sauts de 1, et deux sauts de 2
 Placer un premier 2 parmi 6 , puis placer un deuxième 2 parmi 5, puis placer les 1
 Donc il a : 6 *5/2 = 15 possibilités

(2,2,1,1,1,1)
(2,1,2,1,1,1)
(2,1,1,2,1,1)
(2,1,1,1,2,1)
(2,1,1,1,1,2)
(1,2,2,1,1,1)
(1,2,1,2,1,1)
(1,2,1,1,2,1)
(1,2,1,1,1,2)
(1,1,2,2,1,1)
(1,1,2,1,2,1)
(1,1,2,1,1,2)
(1,1,1,2,2,1)
(1,1,1,2,1,2)
(1,1,1,1,2,2)


6ème cas : x = 3 : Je fais 3 sauts de 1, et un saut de 2 et un saut de 3
 Placer un 3 parmi 5 , puis placer un 2 parmi 4, puis placer les 1
 Donc il a : 1*3 = 12 possibilités

(2,3,1,1,1)
(2,1,3,1,1)
(2,1,1,3,1)
(2,1,1,1,3)
(1,2,3,1,1)
(1,2,1,3,1)
(1,2,1,1,3)
(3,2,1,1,1)
(1,1,2,3,1)
(1,1,2,1,3)
(1,3,2,1,1)
(3,1,2,1,1)


7ème cas : x = 2 : Je fais 2 sauts de 1, et deux sauts de 3
 Placer un 3 parmi 4 , puis placer un 3 parmi 3, puis placer les 1
 Donc il a : 4*3/2 = 6 possibilités

(3,3,1,1)
(3,1,3,1)
(3,1,1,3)
(1,3,3,1)
(1,3,1,3)
(1,1,3,3)




8ème cas x = 2 : Je fais 2 sauts de 1, et trois sauts de 2
 Placer un 2 parmi 5 , puis placer un 2 parmi 4, puis placer un 2 parmi 3, puis placer les 1
 Donc il a : 10 possibilités

(1,1,2,2,2)
(1,2,1,2,2)
(1,2,2,1,2)
(1,2,2,2,1)
(2,1,1,2,2)
(2,1,2,1,2)
(2,1,2,2,1)
(2,2,1,1,2)
(2,2,1,2,1)
(2,2,2,1,1)


9ème cas : x = 1, Je fais 1 saut de 1, deux sauts de 2 et un saut de 3
 Placer un 3 parmi 4 , puis placer un 2 parmi 3, puis placer un 2 parmi 2, puis placer les 1

 Donc il a : 4*3*2/2 = 12 possibilités

(1,2,2,3)
(1,2,3,2)
(1,3,2,2)
(2,1,3,2)
(2,1,2,3)
(3,1,2,2)
(2,3,1,2)
(3,2,1,2)
(2,2,1,3)
(2,2,3,1)
(2,3,2,1)
(3,2,2,1)


10ème cas : x=0 on cherche y et z tels que : 8 = 2y +3z
z = 0 => y =4

(2,2,2,2) =>1 possibilité

z = 1 => impossible (impair)
z = 2 => y= 1

(2,3,3)
(3,2,3)
(3,3,2)
 Placer un 2 parmi 3 , puis placer les 3
 Donc il a : 3 possibilités



=> Au total : 1 + 7 + 6 + 15 + 12 + 6 + 10 +12 +1 + 3 = 73 solutions



Merci pour votre aide.

Salutations

Réponses

  • Bonjour,

    Je pense que ton décompte ne va pas.
    Pourquoi ne pas utiliser la relation de récurrence $u_{n+3}=u_n+u_{n+1}+u_{n+2}$ ?
  • Merci pour l'indication, mais je ne vois pas trop le rapport avec une suite récurrente, encore moins les coefficients qui sont présents.
    A quoi correspond Un ?

    merci
  • Au nombre de façons de monter un escalier à $n$ marches en faisant des sauts de 1, 2 ou 3 marches (what else ?). Je te laisse réfléchir un peu pourquoi on a cette formule de récurrence (indication : considérer le dernier saut d'une ascension de $n+3$ marches).
  • Au fait, cette fois-ci, c'est de quel concours que tu cherches à avoir la réponse ?
  • c'est une question pour se moquer ? (:P)
    C'est un concours qui date d'un an et auquel j'ai participé: chasse au trésor cijm novembre 2010. (Donc c'est clean cette fois )
    Sinon, en regardant les topics des sujets que j'ai soumis , tous les sujets m’intéressent : carrés dans la suite de Fibonacci, nombres de Dudeney , olympiades internationales ...


    merci

    A+
  • Ok, j'ai compris.

    Pour la résolution de la récurrence :
    Un+3= Un + Un+1 + Un+2

    Si on cherche des suites géométriques (base d'un espace vectoriel) on doit résoudre une équation du troisième degré.
    Il faut utiliser la méthode de Cardan ?
    Cela n'a pas l'air très simple tout cela ...
Connectez-vous ou Inscrivez-vous pour répondre.