0%

Problème 101

Polynôme optimal

Énoncé:

Si l'on nous présente les k premiers termes d'une suite, il est impossible de dire avec certitude la valeur du terme suivant, car il existe une infinité de fonctions polynomiales qui peuvent modéliser la suite.

À titre d'exemple, considérons la suite des nombres cubiques. Celle-ci est définie par la fonction génératrice
un=n3:1,8,27,64,125,216,

Supposons que l'on ne nous donne que les deux premiers termes de cette suite. En partant du principe que "le plus simple est le mieux", nous devrions supposer une relation linéaire et prédire que le terme suivant sera 15 (différence commune 7). Même si on nous présentait les trois premiers termes, selon le même principe de simplicité, il faudrait supposer une relation quadratique.

Nous définirons PO(k,n) comme étant le nième terme de la fonction génératrice polynomiale optimale pour les k premiers termes d'une suite. Il devrait être clair que PO(k,n) générera avec précision les termes de la suite pour nk, et potentiellement le premier terme incorrect (PTI) sera PO(k,k+1) ; dans ce cas nous l'appellerons un mauvais PO (MPO).

Comme base, si on nous donne seulement le premier terme de la suite, il serait plus raisonnable de supposer la constance ; c'est-à-dire, pour n2, OP(1,n)=u1.

Par conséquent, nous obtenons les POs suivants pour la suite cubique:

PO(k,n) Premiers termes
PO(1,n)=1 1,1,1,1,
PO(2,n)=7n6 1,8,15,
PO(3,n)=6n211n+6 1,8,27,58,
PO(4,n)=n3 1,8,27,64,125,

Clairement, aucun MPO n'existe pour k4.

En considérant la somme des PTI générés par les MPO (indiqués en rouge ci-dessus), on obtient 1+15+58=74.

Considérons la fonction génératrice polynomiale du dixième degré suivante:

un=1n+n2n3+n4n5+n6n7+n8n9+n10.

Trouve la somme des PTI pour les MPO.

Lien du problème originel