Hello Mathman
- mathman a écrit:
- Un polynôme P est dit k-acceptable si tous ses coefficients sont des entiers compris entre 0 et k (inclus).
a) Soit a_n le nombre des polynômes P 5-acceptables tels que P(3) = n.
Prouver que a_n passe par tous les entiers, mais seulement un nombre fini de fois.
P(x) 5-acceptable ==> Q(x)=(P(x)-P(0))/x est aussi 5-acceptable
Q(3) = (n-P(0))/3 est un entier positif ou nul et P(0) dans {0,1,2,3,4,5}. On a donc nécessairement P(0)=mod(n,3) ou P(0)=mod(n,3)+3 (si n>2).
Donc :
P(x) 5-acceptable et P(3)=n <=>
1) si n<3 : Q(x) 5-acceptable et Q(3)=[n/3]
2) si n >=3 : Q(x) 5-acceptable et Q(3) = [n/3] ou [n/3]-1
Et donc :
si n<3 a_n = a_0 = 1
si n>=3 a_n=a_([n/3]) + a_([n/3]-1)
La suite a_n peut donc être définie ainsi :
a0=a1=a2=1
a_(3n)=a_(3n+1)=a_(3n+2)=a_(n) + a_(n-1)
Il est facile de voir que a_(n+1) = a_(n) ou a_(n)+1 et qu'elle couvre bien tous les entiers.
Comme, par ailleurs, elle est croissante au sens large mais tend vers +oo, chaque entier ne peut être couvert qu'un nombre fini de fois.
CQFD!
- mathman a écrit:
- Un polynôme P est dit k-acceptable si tous ses coefficients sont des entiers compris entre 0 et k (inclus).
b) Soit b_n le nombre des polynômes 4-acceptables tels que P(3) = n.
Prouver que b_n passe par tous les entiers une infinité de fois.
P(x) 4-acceptable ==> Q(x)=(P(x)-P(0))/x est aussi 4-acceptable
Q(3) = (n-P(0))/3 est un entier positif ou nul et P(0) dans {0,1,2,3,4}. On a donc nécessairement P(0)=mod(n,3) ou P(0)=mod(n,3)+3 (si n>2 et si mod(n,3)<2).
Donc :
P(x) 4-acceptable et P(3)=n <=>
1) si n<3 : Q(x) 4-acceptable et Q(3)=[n/3]
2) si n >=3 et mod(n,3)<2 : Q(x) 4-acceptable et Q(3) = [n/3] ou [n/3]-1
3) si n >=3 et mod(n,3)=2 : Q(x) 4-acceptable et Q(3) = [n/3]
Et donc :
si n<3 b_n = b_0 = 1
si n>=3 et mod(n,3)<2 : b_n=b_([n/3]) + b_([n/3]-1)
si n>=3 et mod(n,3)=2 : b_n=b_([n/3])
La suite b_n peut donc être définie ainsi :
b0=b1=b2=1
b_(3n)=b_(n) + b_(n-1)
b_(3n+1)=b_(n) + b_(n-1)
b_(3n+2)=b_(n)
de b_(3n+2)=b_(n) on tire que si une valeur A est atteinte par un b_n, elle est atteinte une infinité de fois (b_n, b_(3n+2), b_(3(3n+2)+2), ...).
De b_(3n+2)= b_n et de b_0=1, on tire b_(3^n - 1)=1
Alors : b_(3^n) = b_(3^(n-1)) + b_(3^(n-1)-1) = b_(3^(n-1)) + 1
et comme b_1=1, on a b_(3^n)=n et donc tous les entiers sont atteints une infinité de fois.
CQFD!
Très joli problème, mathman,
Merci
Accueil 
