27 décembre 2017

9 messages - Retourner à l'article
  • Démarrage trompeur

    le 28 décembre 2017 à 10:05, par Arnaud Chéritat

    Merci pour ce bel article.

    Je ne connaissais pas la formulation de la solution comme une somme de nombres de combinaisons, je savais seulement que c’était un polynôme de degré 4.

    C’est d’ailleurs l’unique polynôme de degré au plus 4 et qui prend successivement les valeurs 1, 2, 4, 8 et 16 pour les valeurs de 1 à 5 de la variable.

    Notons l’ironie : cette suite, définie de façon bien naturelle, fait « semblant » de valoir 2^n. Non seulement ça mais la première valeur en désaccord ne diffère de 2^5 que de la plus petite valeur possible : un ! Et pour finir, elle vaut le polynôme de plus bas degré prenant les valeurs 2^n sur les 5 premiers entiers>0... C’est comme si la question était dotée d’une âme et que celle-ci n’avait d’autre occupation que de nous jouer des tours.

    J’aime bien cette suite et la propose souvent en exercice ludique. On dénombre par récurrence (il faut savoir sommer n^k). On encore découvrir expérimentalement qu’en appliquant 4 fois l’opérateur « différences » on obtient une suite qui a l’air constante.

    Répondre à ce message
    • Démarrage trompeur

      le 2 janvier 2018 à 13:07, par Antoine Chambert-Loir

      Mes souvenirs de lycéen me disent que cette question faisait partie de l’épreuve de sélection au championnat de jeux mathématiques et logiques de 1988. Je ne me rappelle plus de l’intitulé exact (fallait-il trouver le polynôme, ou seulement sa valeur en $n=5$ ou $6$ ?).

      Sinon, en manipulant l’opérateur de différence, on peut voir plus ou moins facilement d’autres phénomènes de ce genre, par exemple en cherchant un polynôme de degré $n$ qui coïncide avec $x \mapsto x^{n+1}$ sur $0,1,\ldots,n$ (je ne me rappelle plus ce que ça donne, il vaut probablement mieux appeler les polynômes de Bernoulli à la rescousse) ou (comme dans cet exemple, à peine généralisé), un polynôme de degré $n$ qui coïncide avec $x\mapsto 2^x$ sur $0,1,\dots,n$.

      Répondre à ce message
      • Démarrage trompeur

        le 3 janvier 2018 à 17:27, par François Sauvageot

        Oui, merci Patrick pour l’article. C’est un chouette sujet, mais il reste assez difficile. Cette combinatoire n’est plus trop à la mode et donnera donc du fil à retordre à des élèves de secondaire ... et même à des étudiant.e.s du supérieur !

        Que ce soit les coefficients binomiaux (dont l’interprétation n’est pas vraiment donnée dans le secondaire) ou la dérivation discrète (qui est absente des considérations du secondaire), les bases sont fragiles. C’est d’ailleurs pourquoi, en MP*, je passe pas mal de temps sur l’opérateur $\Delta$ de Newton, ou dérivée discrète : $\Delta=\tau-Id$ : $P\mapsto P(X+1)-P$.

        La base adaptée aux calculs avec $\Delta$ est celle des polynômes de Newton \[\Gamma_n={X\choose n}=\frac{X(X-1)\cdots(X-n+1)}{n!}\]
        puisque $\Delta(\Gamma_{n+1})=\Gamma_n$, en parfaite analogie avec la base de Taylor $\frac{X^n}{n!}$ adaptée aux calculs avec la dérivée et donc le développement en série de Taylor.

        On obtient rapidement le fait suivant pour un polynôme $P$ de degré $n$ :
        \[P=\sum_{k=0}^na_k\Gamma_k\Longleftrightarrow\forall k\in[0;n]\,a_k=\Delta^k(P)(0)\]
        puisque tous les $\Gamma_k$ sont nuls en 0, sauf $\Gamma_0$ qui y vaut 1.

        Comme
        \[\Delta^k=(\tau-I)^k=\sum_{i=0}^k(-1)^{k-i}{k\choose i}\tau^i\]
        on en déduit que les coefficients de $P$ dans le développement en série de Newton est obtenu à partir des premières valeurs de $P$ sur les entiers de la façon suivante :
        \[a_k=(-1)^k\sum_{i=0}^k(-1)^i{k\choose i}P(i).\]
        Ce qui est remarquable est que cette construction est stable par élévation du degré ! Donc on peut faire de l’inter(extra)polation itérative à peu de frais : on cherche un polynôme de degré $n$ qui fait le job en s’adaptant aux $n+1$ premières valeurs constatées et ensuite, si on n’est pas satisfait, on augmente le degré en ne calculant qu’un coefficient de plus à chaque fois.

        Ainsi, quand on cherche à deviner une formule que l’on espère polynomiale, on devrait enseigner qu’il faut chercher la décomposition dans la base des polynômes de Newton. C’est d’ailleurs comme ça qu’on peut trouver facilement des erreurs dans des reports dans des listes obtenues avec des formules polynomiales : apparait par linéarité une erreur qui, par itération de $\Delta$, fournit des coefficients binomiaux (correspondant au dévelopement de $X^n$ dans la base de Newton). Il faut aussi faire concorder les observations avec des valeurs de 0 à $n$. Ici on part de $n=2$ et on peut soit décaler de 2, soit commencer à $n=1$ en prenant la valeur 1 (c’est plus dur d’imaginer une valeur avec $n=0$).

        Si $P(k)=b^k$, on trouve $a_k=(b-1)^k$. Il y a d’ailleurs un sujet sympa de l’X à ce propos (X 2011, filière MP, composition B) : accélération de convergence via la transformation d’Euler. Ici $b=2$ et donc les coefficients sont l’unité !
        L’écart entre $P_4=\sum_{k=0}^4\Gamma_k$ et $2^X$ est donc donné par les termes manquants : $2^n-P_4(n)=\sum_{k=5}^n\Gamma_k(n)$. Pour $n=5$, on trouve $\Gamma_5(5)={5\choose 5}=1$. En fait on se balade sur la $n$-ème ligne du triangle de Pascal et on somme les cinq premiers termes, donc sur la cinquième ligne on ne néglige qu’un terme qui vaut 1.

        Autrement dit quand on dit : $1$, $2$, $4$ ... on devrait penser directement $\Gamma_0$, $\Gamma_0+\Gamma_1$, $\Gamma_0+\Gamma_1+\Gamma_2$, etc. i.e. $1$, $n$, $\frac{n^2-n+2}2$, etc. tout en ayant en tête que la somme de la série $\sum\Gamma_k$ est $2^X$ !

        Si $P(k)=k^{n+1}$, on peut en effet penser aux polynômes de Bernoulli puisque, par définition (ou presque) de ces polynômes, on a $\Delta(B_{n+1})=(X^{n+1})'=(n+1)X^n$, i.e. ce sont eux qui permettent de sommer des puissances $n$-èmes. Toutefois aucune formule simple ne m’est apparue en rédigeant ces lignes ...

        Répondre à ce message
        • Démarrage trompeur

          le 4 janvier 2018 à 10:47, par Patrick Popescu-Pampu

          Merci François pour ces explications très intéressantes, qui me semblent parfaites pour des ateliers de maths en licence !

          Et bonne année !

          Répondre à ce message
  • Typos

    le 3 janvier 2018 à 19:25, par François Sauvageot

    Juste pour dire, la numérotation des figures est un peu étrange, peut-être pourrait-on les supprimer (3.12, 3.13 et la référence à 3.11 ...).

    Et par ailleurs il manque le numéro 1 sur le sommet pour n=2 et l’étiquette 123 dans la figure pour n=5.

    Répondre à ce message
    • Typos

      le 4 janvier 2018 à 10:49, par Patrick Popescu-Pampu

      Cher François,

      Tu as raison en ce qui concerne les nombres manquants dans les figures. Quant aux numéros de celles-ci, ce sont ceux du livre, ils permettront aux lecteurs intéressés de retrouver facilement l’endroit précis où les auteurs parlent de cet exemple.

      Répondre à ce message
  • Démarrage trompeur

    le 3 janvier 2018 à 23:06, par aunryz

    Peut-on raisonnablement donner le terme suivant d’une suite ?

    Non !
    Si le thème
    comme c’est le cas dans la suite de l’article
    n’est pas donné

    D’ailleurs
    la suite de la série 2,4,8,16,31
    peut être 61 ; 57 ; 42 ou 56
    et bien d’autres encore
    (à vérifier en tapant ces valeurs)

    Quant au démarrage trompeur
    il n’existe que pour l’esprit informé
    chez lequel certains chemins sont tracés
    avec comme conséquence ce qui est joliment nommé
    « entropie apparente »
    par ceux qui s’intéressent à l’apparent chaos produit par certains automates cellulaires
    au fonctionnement pourtant très simple.

    Répondre à ce message
  • Démarrage trompeur

    le 14 septembre 2019 à 23:23, par M.F.H.

    Il y a certes toujours différents choix possibles pour a(n+1), étant donné a(1..n) et rien d’autre. (Votre phrase « thème pas donné... » n’est pas claire... mais le « thème »(?) et la definition de la suite sont énoncés dès le début et à partir de là il n’y a aucune ambiguïté.)

    Quand il s’agit de deviner a(n+1) sans aucune autre information, la réponse naturelle est celle qui correspond à la formule ou explication la plus simple. Sachant que le polynôme de plus bas degré qui passe par 1,2,4,8,16 (en n=0,...,4) donne comme par magie aussi P(5)=31, il est naturel de se baser sur cela pour « extrapoler » avec P(6)=57. (De manière équivalente on peut considérer la suite des premières, 2ndes, 3ièmes différences et extrapoler à partir de là.)

    Répondre à ce message
  • Démarrage trompeur

    le 30 octobre 2019 à 13:09, par funnix

    Bonjour,

    Je suis à la recherche de la démonstration qui démontre l’unicité de la bijection entre le codage de Conway et les figures codées sur la figure.

    Est-ce que vous ou votre équipe avez un article qui démontre pourquoi l étiquette de chaque sous ensemble est constitué d’au plus 4 éléments de l ensemble 1 à n-1 ?

    Cordialement,

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.