Énigme montée des marches

[Deedee81]

Salut,

Merci.

et j'ai laissé des pistes au fond des spoilers précédents...

Le message #25 ? il a failli me rendre fou avant que je clique sur "modifier" (pour voir directement le tout), privilège de modérateur
-----

[polo974]

Salut,
...
Le message #25 ? il a failli me rendre fou avant que je clique sur "modifier" (pour voir directement le tout), privilège de modérateur

Tricheur...

 Cliquez pour afficher

Ce truc de spoiler imbriqué, c'est aussi un sujet genre, j'en mets 20 les un dans les autres, combien de clics faut-il pour ouvrir sans ouvre-boite...

Le truc marrant avec les séries du sujet, c'est que:

• ça commence par un "seed" composé de:
  • n-1 zéro,
  • un
• puis ça continue avec les n premières puissances de 2,
• et enfin, ça entre dans le "vif du sujet".

le spoiler dans le #30, ça aide pour Versailles...

[Médiat]

[QUOTE=Frydman Charles;7144896]
Concernant fibonacci, il s'agit de l"approximation d'un entier par un irrationnel contenant sqrt(5),le nombre d'or ! ⁣Non, la formule de Binet donne les termes de la suite de Fibonacci sans aucune approximation

[Frydman Charles]

Screenshot_20231027-203144_Chrome.jpg

Sur le lien de Gerard Villemin.
Le tableau suivant montre la difference entre l'entier et la valeur donnée par la formule de Binet. La difference est si faible, que c'est pratiquement un entier.

[Frydman Charles]

J'ai un doute, sqrt(5) doit s'eliminer pour toutes les valeurs de n ,et on trouve un entier. Le tableau montre que pour les grandes valeurs de n on peut utiliser serulement le premier terme de la formule de Binet.

[Frydman Charles]

Demonstration de la formule de Binet
http://serge.mehl.free.fr/anx/form_binet.html

[Frydman Charles]

Bien que √5 soit un réel irrationnel, si on applique la formule complète de Binet on obtient effectivement un entier puisque √5
s'élimine. Pour le cas de n=3 par exemple, si on pose a=1 et b=√5 on a :
(a+b)^3=a^3+3a^2×b+3ab^2+b^3
(a-b)^3=a^3-3a^2×b+3ab^2-b^3
Donc
(a+b)^3-(a-b)^3=6a^2×b+2b^3
Soit 6b+2b^3
D'où F3=(6b+2b^3)/(2^3×b)=16/8=2
Donc F3=2

[Frydman Charles]

Bonjour Juzo

Une autre question que je me pose : comment fait-on un lien entre la formule de Binet et la somme de combinaisons autrement qu'avec cette représentation de la montée des marches ?

La liaison se fait par le triangle de Pascal.
Triangle de Pascal Fibonacci.jpg
https://www.mathraining.be/chapters/38?type=1&which=126

[Deedee81]

Bonjour,

Frydman, s'il te plaît, essaie d'éviter le flood. 5 messages à la suite c'est pas agréable sur un forum de discussion.

Merci,

[Frydman Charles]

Bonjour
Le temps pour modifier un message semble très limité...Il serait moins lourd de modifier un message que d'ajouter un message correctif.

[albanxiii]

Bonjour
Le temps pour modifier un message semble très limité...Il serait moins lourd de modifier un message que d'ajouter un message correctif.

D'où l'utilité de ne pas poster compulsivement et de prendre un peu de temps pour réfléchir et préparer ses réponses.

[pm42]

D'où l'utilité de ne pas poster compulsivement et de prendre un peu de temps pour réfléchir et préparer ses réponses.

Et ce d'autant plus qu'il ne s'agissait pas de réponses au sujet du fil mais de l'évolution de la compréhension de la formule de Binet par le posteur.
Poster des copies d'écran sur ce sujet élémentaire n'apporte pas grand chose non plus.

[Frydman Charles]

Au départ c'était une réponse à la question de Juzo. Je pense que la capture d'écran y repond. F(n+1) pouvant s'obtenir par la formule de Binet.
Entre les deux, j'ai effectivement cafouilllé sur Binet.

[Juzo]

Bonjour,

Merci Frydman Charles pour ces explications.
Il reste je crois le défi de polo974 où je n'ai pas tout compris (j'ai au moins réussi à comprendre comment fonctionnent les spoilers imbriqués. )

[polo974]

Vu qu'il a été demandé (à juste titre) de redescendre, j'ai proposé de dévaler l'escalier 4 à 4 ou moins.
Donc même question que pour la montée, mais en descendant d'une, deux, trois ou quatre marches...

Ce qui augmente le nombre de combinaisons...

Donc, combien pour descendre les 30 marches et surtout comment le calculer.

[Juzo]

Eh bien à priori Fabien arrive en bas de l'escalier en sautant 1, 2, 3 ou 4 marches donc en ayant franchi précédemment 29, 28, 27, ou 26 marches donc on a affaire à la suite de 4-bonacci ou Tétranacci dont il faut prendre le 34ème terme...
Fabien s'appelle maintenant Tétrien et il a 201 061 985 manières de descendre l'escalier.

[Frydman Charles]

Bonjour
Comment trouver le 34 eme terme de la suite de Tetranacci ? Je l'ai trouve sur ce site en anglais, en comptant jusqu'au 34 eme terme :
https://oeis.org/A000078
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533, 28074040, 54114452, 104308960, 201061985, 387559437, 747044834, 1439975216, 2775641472 (list; graph; refs; listen; history; text; internal format)
L'utilisation d'une extension de la formule de Binet semble compliquée. Existe-il un calculateur en ligne ?

[polo974]

Oui,
c'est bien la suite "Tetranacci"
https://oeis.org/A000078

et en gros, si mf (>0) est le nb de marches max franchissables en un pas et n le nombre de marches de l'escalier, il faut utiliser fibo_étendu_<mf> (n + mf - 1)
donc ici
pour monter fibo_étendu_2 (30 + 2 - 1) = fibonacci (31)
pour descendre r fibo_étendu_2 (30 + 4 - 1) = tetranacci (33)

Je me suis amusé à coder une classe python pour les différentes suites "fibonacci étendues" (il y a une blague pour the cas particulier, je la laisse pour rigoler).
(dans un spoiler pour pas faire trop long)

 Cliquez pour afficher

class Fibo:
    deja = {}
    
    def __init__(self, ordre=2):
        self.ordre = ordre
        self.deja = Fibo.deja.get(ordre)
        if self.deja is None:
            self.reset()

    def __call__(self, val):
        dval = 1 + val - len(self.deja)
        mordre = - abs(self.ordre)
        while dval > 0:
            dval -= 1 
            next = sum(self.deja[mordre:])
            self.deja.append(next)
        return self.deja[val]

    def reset(self):
        if self.ordre < 0:
            self.deja =  [0] * (-self.ordre-1) + [-1]
        else:
            self.deja =  [0] * (self.ordre-1) + [1]
        Fibo.deja[self.ordre] = self.deja 

if __name__ == "__main__": 
    fibo = Fibo()
    tetra = Fibo(4)
    uno = Fibo(1)

    print("fibo(10) = %d" % fibo(10))
    print("fibo(30+1) = %d" % fibo(30+1))

    print("tetra(10) = %d" % tetra(10))
    print("tetra(30+3) = %d" % tetra(30+3))
    print("tetra(10) = %d" % tetra(10))
    print("tetra(30+3) = %d" % tetra(30+3))
    tetra.reset()

    print("tetra(30+3) = %d" % tetra(30+3))

    print("uno(10) = %d" % uno(10))
    for ordre in 1,2,4 : print("deja%d: %r" % (ordre, Fibo.deja[ordre]))

En gros, on peut instancier des Fibo d'ordre n, (2 étant la valeur par défaut pour la vraie fibonacci).
puis appeler la classe directement avec l'indice voulu.
chaque série est mémorisée, donc 2 fois de suite fibo(30) ne fera construire la série qu'une fois (jusqu'à l'indice 30).
pour jouer, on peut reseter une série (sans autre intérêt que "pour voir" ...)

Ah, on peut aussi accéder directement aux (débuts des) suites déjà mémorisées...

[Frydman Charles]

Pour la montée de l'escalier, j'ai noté que le total des possibilités lorsque le nombre de sauts est pair, est égal à la moitié du nombre total des possibilités. A une unité prés.

C(0,30)=1
C(2,28)=378
C(4,26)=14950
C(6,24)=134396
C(8,22)=319770
C(10,20)=184756
C(12,18)=18564
C(14,16)=120
.............
Total :
673135
2*673135=1346270
134627-1=1346269

Le nombre total des possibilités lorsque le total des sauts est impair est : 673134

C'est vrai également pour un nombre de marches de 12,13 ou 20....
J'ai essayé de généraliser pour un nombre n de marches.
Plus généralement pour un nombre n de marches, le total des possibilités est sigma[k=(0,n/2)][C(k,n-k)]=F(n+1)
F nombre de Fibonacci
Pour les nombres pairs de bonds
sigma[k=(0,n/4)][C(2k,n-2k)] si n est pair
sigma[k=(0,n/4)][C(2k,n-1-2k)] si n est impair
Est-ce une propriété remarquable des combinaisons , a une unité près ,le total pour un nombre pair de sauts est la moitié du total des possibilites, et egal au total pour un nombre impair de sauts.

[ArchoZaure]

	1	2	3	4	5	6	7	8	9	10
1	1	0	0	0	0	0	0	0	0	0
2	1	2	0	0	0	0	0	0	0	0
3	1	3	4	0	0	0	0	0	0	0
4	1	5	7	8	0	0	0	0	0	0
5	1	8	13	15	16	0	0	0	0	0
6	1	13	24	29	31	32	0	0	0	0
7	1	21	44	56	61	63	64	0	0	0
8	1	34	81	108	120	125	127	128	0	0
9	1	55	149	208	236	248	253	256	256	0
10	1	89	274	401	464	492	504	509	511	512

[ArchoZaure]

C'est le tableau avec en ligne le nombre de marches (j'ai arrêté à 10) et en ligne le nombre de marches qu'on peut franchir en un pas.

Le calcul a été réalisé avec ce programme en C :

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

const int C_NB_MARCHE_MAX = 40;               // Nombre de Marches max

int Saisie(char lib[], int vm, int vmax);   // Declaration forward de la fonction Saisie

//***********************************************************************************************//
//** Calcul du nombre de façons de monter un escalier en fonction de la possibilité de monter  **//
//** les marches                                                                               **//
//***********************************************************************************************//
int main()
{
  long nbp;                         // Nombre de Possibles à calculer
  int nbm;                          // Nombre de marches à tester
  int ct [C_NB_MARCHE_MAX + 1];     // Tableau contenant l'escalier testé en cours
  int i, j, k;
  int t,n ;
  bool fin_max;
  bool fin_inc;
  int nb_marche;
  int nb_pas;
  char s1[]="Nombre de Marches";
  char s2[]="Nombre de marches montees en une fois max ";

  // Saisie des valeurs pour le calcul
  nb_marche = Saisie(s1, 2, C_NB_MARCHE_MAX);
  nb_pas    = Saisie(s2, 1, nb_marche);

  nbp=0;
  // On fait varier le nombre de marches du mini au maxi et on regarde si on peut caser les pas dedans
  for(nbm=1; nbm<=nb_marche; nbm++)
    {
      // Initialise le tableau avec la marche minimale
      for (i=0; i<nbm; i++) ct[i] = 1;

      fin_max = false;
      for (j=0; fin_max==false; j++)
        {
          // Si on a réussi à créer un escalier de la bonne taille
          t=0;
          for (n=0; n<nbm; n++) t = t + ct[n];
          if (t==nb_marche) nbp++;      // Incrémente le nombre de possibilités

          // Incrémente le tableau
          fin_inc = false;
          k = 0;
          do
          {
            if (ct[k]<nb_pas)
              {
                ct[k]++;
                fin_inc=true;
              }
            else
              {
                if (ct[k]==nb_pas)
                  {
                    if (k==nbm-1)
                      {
                        fin_inc=true;
                        fin_max=true;
                      }
                    else
                      {
                        ct[k]=1;
                        k++;
                      }
                  }
                else
                  {
                    ct[k]=1;
                    k++;
                  }
              }
          } while (fin_inc==false);
        }
    }
    printf("Nombre de facons de monter l'escalier   : %ld\n", nbp);
}

//**************************************************************************//
//** Fonction retournant une valeur entière saisie au clavier             **//
//** lib : Libellé du prompt de la saisie                                 **//
//** vm : Valeur minimum autorisée                                      **//
//** vmax : Valeur maximum autorisée                                      **//
//**************************************************************************//
int Saisie(char lib[], int vm, int vmax)t
{
  bool saisie;
  char sn;
  int n;

  saisie = false;
  do
    {
      printf(lib);
      printf(" ( Valeurs autorisees [%d - %d] ) : " , vm, vmax);
      scanf("\n%s", &sn);
      if(sscanf(&sn, "%d", &n) == 1) if ((n>=vm) && (n<=vmax)) saisie = true;
     } while (saisie == false);

  return(n);
}

[ArchoZaure]

Errata.

C'est le tableau avec en ligne le nombre de marches (j'ai arrêté à 10) et en ligne le nombre de marches qu'on peut franchir en un pas.

Et en colonne le nombre de marches qu'on peut franchir en un pas.

[Frydman Charles]

Le tableau et son explication ne sont pas clairs. Le tableau ressemble à un triangle de Pascal translaté. Mais ce n'est pas un triangle de Pascal ! On obtient quoi à la jonction d'une ligne et d'une colonne ?
...... .
Petite coquille à mon dernier post,il manque un zéro :
134627-1=1346269
Il manque un zéro.
1346270-1= 1346269
Pas de réactions à ce dernier post ?

[polo974]

	1	2	3	4	5	6	7	8	9	10
1	1	0	0	0	0	0	0	0	0	0
2	1	2	0	0	0	0	0	0	0	0
3	1	3	4	0	0	0	0	0	0	0
4	1	5	7	8	0	0	0	0	0	0
5	1	8	13	15	16	0	0	0	0	0
6	1	13	24	29	31	32	0	0	0	0
7	1	21	44	56	61	63	64	0	0	0
8	1	34	81	108	120	125	127	128	0	0
9	1	55	149	208	236	248	253	256	256	0
10	1	89	274	401	464	492	504	509	511	512

les cellules à zéro sont fausses.
voici le bon tableau:

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	2	2
3	1	3	4	4	4	4	4	4	4	4
4	1	5	7	8	8	8	8	8	8	8
5	1	8	13	15	16	16	16	16	16	16
6	1	13	24	29	31	32	32	32	32	32
7	1	21	44	56	61	63	64	64	64	64
8	1	34	81	108	120	125	127	128	128	128
9	1	55	149	208	236	248	253	255	256	256
10	1	89	274	401	464	492	504	509	511	512

[polo974]

...... .
Petite coquille à mon dernier post,il manque un zéro :
134627-1=1346269
Il manque un zéro.
1346270-1= 1346269
Pas de réactions à ce dernier post ?

En fait, j'ai rien compris... Mais j'avoue que je n'ai pas (trop) cherché...

[ArchoZaure]

Le tableau et son explication ne sont pas clairs. Le tableau ressemble à un triangle de Pascal translaté. Mais ce n'est pas un triangle de Pascal ! On obtient quoi à la jonction d'une ligne et d'une colonne ?

Les 1,2...10 de la colonne qui descend à gauche (avec la case vide au dessus) c'est le nombre total des marches.
Par exemple dans l'énigme proposé on s'est limité à 1 cas : Un escalier à 30 marches.
On aurait pu avoir 20 ou 10 ou 3 au lieu de 30, c'est ce que j'ai fait mais de 1 à 10.
Je ne vais pas jusqu'à 30 (inutile de faire surchaufer le PC alors qu'il s'agit simplement de trouver une logique, des rapports. (On a suffisamment de nombres ici et je m’arrête donc à 10.)

Les 1,2...10 de la ligne du haut qui va vers la droite (avec la case vide à gauche) c'est le nombre de marches qu'on peut monter en une seule fois.
Par exemple dans l'énigme proposée on s'est limité à 1 cas : On peut faire des pas de 2 => Donc on peut monter l'escalier en mixant des pas de 1 ou de 2
Deuxième cas qui est apparu dans la discussion, c'est la montée avec des pas de 4 => Donc on peut monter l'escalier en mixant des pas de 1, de 2, de 3 et de 4.
Lorsqu'on voit dans la ligne des 1 des 2 des 3 ou des 4 il faut bien entendu comprendre que par exemple 4 reprend les 4 possibilités 1,2,3,4 et donnera le résultat à l’intersection de la ligne et de la colonne pour ces 4 possibilités (noté 4 donc).

Donc si je voulais répondre à l'énigme 30/2 il faudrait se référer au résultat indiqué au croisement du 30 dans la colonne et du 2 dans la ligne.
Pareil, si je voulais répondre à l'énigme 30/4 il faudrait se référer au résultat indiqué au croisement du 30 dans la colonne et du 4 dans la ligne.

Si vous voulez les résultats il suffit de lancer le programme, qui est prévu jusqu'à 40/40, mais n'attendez pas un résultat immédiat...
Le 30/2 donne bien 1346269

les cellules à zéro sont fausses.
voici le bon tableau:

Les cellules à zéro sont justes.
Par exemple ligne 3 colonne 5, donc un escalier de 3 marches avec la possibilité de monter de 5 marches, ce n'est pas possible de monter de 5 marches pour un escalier de 3 marches, donc 0
Vous pouvez toujours imaginer donner un résultat qui laisserait tomber les cas 4 et 5 et donc vous retombez sur le cas 3/3 mais c'est pas cohérent avec la question.
Mais libre à vous de penser autrement si ça vous amuse.

[polo974]

...

Les cellules à zéro sont justes.
Par exemple ligne 3 colonne 5, donc un escalier de 3 marches avec la possibilité de monter de 5 marches, ce n'est pas possible de monter de 5 marches pour un escalier de 3 marches, donc 0
Vous pouvez toujours imaginer donner un résultat qui laisserait tomber les cas 4 et 5 et donc vous retombez sur le cas 3/3 mais c'est pas cohérent avec la question.
Mais libre à vous de penser autrement si ça vous amuse.

ben non, elles sont fausses. rien ne t'interdit de les monter par 1 ou 2 ou 3 même si le nombre max de marches d'un pas est de 5.

même la ligne 1 colonne 2, c'est le second 1 de la suite de fibonacci.

[ArchoZaure]

ben non, elles sont fausses. rien ne t'interdit de les monter par 1 ou 2 ou 3 même si le nombre max de marches d'un pas est de 5.

Et donc dans une formule de généralisation vous allez faire comment ?
Ajouter la fonction min() ?
Mais bon comme déjà dit, libre à vous d'imaginer des cas qui rendent compliqué les choses simples.

même la ligne 1 colonne 2, c'est le second 1 de la suite de fibonacci.

Et ainsi de suite, ligne 1 colonne 8 c'est le huitième 1 de la suite de Fibonacci ?
Je ne connaissais pas.

[Juzo]

Les cellules à zéro sont justes.

Pour moi aussi elles sont fausses, par exemple pour la 1ere ligne 3eme colonne, si on a la possibilité de monter les marches par 3 et qu'il y a une marche à monter, il existe quand même une manière de monter cette marche, donc la case devrait valoir 1 et pas 0.

[ArchoZaure]

Pour moi aussi elles sont fausses, par exemple pour la 1ere ligne 3eme colonne, si on a la possibilité de monter les marches par 3 et qu'il y a une marche à monter, il existe quand même une manière de monter cette marche, donc la case devrait valoir 1 et pas 0.

Trouvez la formule permettant de généraliser le résultat selon le nombre de marches et de pas max et revenez nous en parler.