Aide pour les futurs mathématiciens
 
AccueilAccueil  PortailPortail  RechercherRechercher  S'enregistrerS'enregistrer  Connexion  

Partagez
 

 Polynômes k-acceptables.

Aller en bas 
AuteurMessage
mathman
Modérateur


Masculin Nombre de messages : 967
Age : 30
Date d'inscription : 31/10/2005

Polynômes k-acceptables. Empty
MessageSujet: Polynômes k-acceptables.   Polynômes k-acceptables. EmptyMar 01 Mai 2007, 12:56

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.
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.
Revenir en haut Aller en bas
pco
Expert sup


Masculin Nombre de messages : 678
Date d'inscription : 06/06/2006

Polynômes k-acceptables. Empty
MessageSujet: Re: Polynômes k-acceptables.   Polynômes k-acceptables. EmptyMar 01 Mai 2007, 15:42

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
Revenir en haut Aller en bas
mathman
Modérateur


Masculin Nombre de messages : 967
Age : 30
Date d'inscription : 31/10/2005

Polynômes k-acceptables. Empty
MessageSujet: Re: Polynômes k-acceptables.   Polynômes k-acceptables. EmptyMar 01 Mai 2007, 18:28

@a) : yep, c'était aussi ma solution.
@b) : ouais ok ^^. Bon, j'avais prouvé que b_{3^n} = n+1 un peu différemment, mais ok ^^.
(après-coup j'avais aussi trouvé toutes ces variations)

Au fait, a_n peut être décrite de manière marrante :
on écrit n en base 3, e.g. n = (10100210120)_3. Ensuite on le considère comme un nombre binaire de la manière suivante :
en commençant à gauche, on recopie les chiffres s'ils sont égaux à 0 ou 1. S'il y a un 2, alors on n'écrit plus que des 1 à partir de cet endroit. Dans l'exemple, ça donne (10100111111)_2. On efface le dernier chiffre, on le considère comme un nombre binaire et enfin on ajoute 1. Alors on obtient a_n. Donc dans notre exemple, a_n = (1010011111)_2 + 1.

Effectivement je l'ai trouvé assez joli moi aussi. Smile
(les deux autres que j'ai posté ne sont pas mal non plus)
Revenir en haut Aller en bas
Contenu sponsorisé




Polynômes k-acceptables. Empty
MessageSujet: Re: Polynômes k-acceptables.   Polynômes k-acceptables. Empty

Revenir en haut Aller en bas
 
Polynômes k-acceptables.
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Présentation Tahitinui
» Une typographie commune aux idéolangues...

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum des amateurs de maths :: Olympiades :: Divers-
Sauter vers: