X Maths PC 2006

Thème de l'épreuve Polynômes à coefficients 1 ou -1
Principaux outils utilisés arithmétique, récurrences d'ordre 1 et 2, calcul algébrique, équivalents de fonctions, séries entières

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES CONCOURS D'ADMISSION 2006 FILIÈRE PC COMPOSITION DE MATHÉMATIQUES (Durée : 4 heures) L'utilisation des calculatrices n'est pas autorisée pour cette épreuve. *** Polynômes à coefficients 1 ou --1 Les polynômes étudiés dans ce problème ont été introduits lors de recherches sur la spectroscopie multi--fentes. Ils ont donné lieu à des développements mathématiques en combinatoire, théorie des codes, analyse harmonique, et a de très nombreuses applications en optique, télécommunications, théorie des radars et acoustique. Toute affirmation devra être soigneusement justifiée. La précision, la clarté et la concision des raisonnements seront particulièrement appréciées. Soit EUR un entier au moins égal à. 1. Dans ce problème, un vecteur @ de Re sera appelé séquence de longueur EUR si chacune de ses EUR coordonnées vaut 1 ou ----1. Les coordonnées d'une séquence _a_ de longueur EUR seront numérotées de 0 à EUR -- 1, a = (ao, a1, . . . ,ag_1). On notera 8g l'ensemble des séquences de longueur 6. On appellera simplement séquence, tout vecteur qui est une séquence de longueur 6, pour un certain entier EUR > 1. On dira que des séquences a et Q forment une paire complémentaire si elles ont même longueur K (qui sera appelée dorénavant longueur de la paire) et si elles vérifient, dans le cas où EUR > 1, pour tout entier j tel que 1 < j { EUR -- 1, la j--ième condition de corrélation : Æ--1--j z (az--a...-- + b,--b,--+j) = @. i=0 Par convention, tout couple de séquences de longueur 1 est une paire complémentaire. Ainsi, pour tout entier EUR > 1, la complémentarité d'une paire de longueur EUR implique EUR -- 1 conditions de corrélation. Première partie On désigne par E l'ensemble des entiers EUR pour lesquels il existe au moins une paire complé-- mentaire de longueur EUR . Autrement dit, L est l'ensemble des longueurs de paires complémentaires. Dans cette partie, on se propose d'étudier certaines propriétés de l'ensemble £. 1. Montrer que 2 appartient a £ et que 3 n'appartient pas a [... Soit EUR un entier au moins égal à 1. Pour toute séquence, Q = (cm, (il, . .. ,ag_1), de longueur EUR, on définit le polynôme Pg_ par la formule ê--1 PQ(X) = z a,;X' . i=0 Un tel polynôme est appelé polynôme séquentiel. 2.3) Soient g,_ et Q des séquences. On considère la fonction définie pour au réel, a: # 0, par 50 '--> Pg(OE)Pg_(OE_1) + PQ(OE)Pg(OE_1) - Montrer que si g_ et Q ne sont pas deux séquences de même longueur, cette fonction n'est pas bornée sur ]0, +oo[. Montrer que deux séquences _C_L_ et Q de même longueur forment une paire complémentaire si et seulement si cette fonction est constante. Exprimer cette constante en fonction de la longueur EUR de la paire complémentaire _a_, Q. 2.b) Montrer que si Q et Q sont des séquences de même longueur, PQ (1) et Pg(1) sont des entiers de même parité. En déduire que tout élément de £ peut s'écrire comme la somme de deux carrés d'entiers. 2.c) Montrer que le complémentaire de E dans N est un ensemble infini [on pourra étudier le reste de la division par 4 d'un carré d'entier]. 3.a) Soient Q et Q des séquences de même longueur. On pose U = %(ngPg) et V = %(PQ--PQ). Montrer que Q et Q forment une paire complémentaire si et seulement si la fonction oe +----> U(æ)U(oe"') + V(oe)V(af') est constante sur son domaine de définition. 3.b) Les séquences, de longueur 10, g = (1,1,-1,1,-1,1,-1,-1,1,1) et Q = (1,1,--1,1,1,1,1,1,--1,--1) forment--elles une paire complémentaire ? 4. Démontrer, pour toute séquence @ de longueur paire 2m (m E N, non nul), l'équivalence des assertions suivantes : (i) 4 divise la somme % + m + ' - - + v2m_1, (ii) le nombre de coordonnées de @ égales à --1 a la même parité que m, (iii) 'U() 111 ° ° ' Uzm_1 = (_1)m_ 5. Soit EUR E E, EUR > 2, et soient g et Q des séquences qui forment une paire complémentaire de longueur EUR. Pour tout entier i, 0 { i EUR EUR -- 1, on pose oe,-- = a,b,--. 5.a) Montrer que, pour tout entier j , 1 { j { EUR -- 1, Ë--1--j ,_. H OEkOEk+j = (--1) ? k=0 [considérer la somme des coordonnées de la séquence (ago,--, . . . , ag_1_ jag_1, bobj, . . . , bg_1_ jbg_1)]. 5.b) En déduire que, pour tout entier j, 0 < j EUR EUR -- 1, OEjOEg_1_j = ----1 . 5.0) Montrer que tout élément EUR de £, EUR > 2, est pair. Deuxième partie Si deux polynômes séquentiels sont associés à des séquences qui forment une paire complé-- mentaire, on dit qu'ils forment une paire complémentaire de polynômes. Cette partie est consacrée à l'étude de certaines paires complémentaires de polynômes, dites paires de Rudin-Shapim. On définit deux suites de polynômes (Pn)neN et (Qn)nEURN par les conditions initiales P0(X) = Q0(X) = 1 et les relations de récurrence Pn+1(X) : Pn(X) + X2nQn(--X)v (1) Qn+1(X) = P,,(X) --X2nQn(X)- (2) 6.21) Calculer P1 et Q1, puis P2 et Q2. 6.b) Calculer les valeurs respectives de P,,(1), Q,,(1), P,,(--1) et Q,,(--l) en fonction de l'entier n. 7. Démontrer que, pour tout entier positif n, les polynômes P,, et Q,, sont des polynômes séquentiels et qu'ils forment une paire complémentaire. Qu'en déduire vis--à--vis de l'appartenance des entiers de la forme 2h, pour k entier positif ou nul, à l'ensemble £ ? 8. Démontrer, pour tout entier positif ou nul n et tout nombre complexe non nul 2 E C, l'égalité Qn(z) = (--1)"z2n_an(--z_l). _ 9.a) Soit T un polynôme quelconque de C[X], de degré exactement d, d > 1, qu'on écrit T (X ) = to +t1X +- - -+thd (avec td non nul). Montrer que les racines de T sont toutes majorées en module par la quantité 1 + sup0 

Extrait du corrigé obtenu par reconnaissance optique des caractères


 X Maths PC 2006 -- Corrigé Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été relu par Walter Appel (Professeur en CPGE) et Tristan Poullaouec (Professeur agrégé). Le sujet de l'École Polytechnique de cette année est particulièrement original. On aurait tendance à dire qu'il s'agit d'algèbre, et pourtant pratiquement aucune connaissance de cours n'est nécessaire à part quelques outils d'analyse ! Comme bien souvent dans ce genre de cas, la difficulté est élevée en grande partie à cause de l'originalité des questions. Le sujet est composé de deux parties qui sont dans une très large mesure indépendantes. Il traite de vecteurs et de polynômes à coefficients dans l'ensemble {-1, 1}. On cherche des couples de tels objets satisfaisant certaines conditions dites de complémentarité. L'ensemble des entiers pour lesquels il existe deux vecteurs de taille (respectivement deux polynômes de degré -1) satisfaisant ces conditions est noté L. · La première partie s'attache à trouver des conditions nécessaires pour qu'un entier soit un élément de L. À part une brève utilisation des équivalents de fonctions et un tout petit peu d'arithmétique, on peut la traiter sans aucune connaissance de cours. · La deuxième partie est un peu plus proche de ce qui peut être demandé habituellement. On montre un certain nombre de propriétés portant sur deux familles de polynômes. Naturellement, il faut utiliser à de nombreuses reprises le raisonnement par récurrence (certaines preuves sont relativement longues à rédiger). Les séries entières font leur apparition en toute fin de sujet et ce pour deux petites questions. Il ne s'agit certainement pas d'un sujet destiné à contrôler la maîtrise des connaissances du cours. En revanche, c'est sûrement un très bon test pour vérifier que vous savez produire des raisonnements moins classiques, ce qui est nécessaire pour présenter les concours de l'École Polytechnique et des Écoles Normales Supérieures. Indications 1 Pour montrer que 3 n'appartient pas à L, montrer que si la deuxième condition de complémentarité est satisfaite, alors la première ne peut pas l'être. 2.a Déterminer les équivalents en + des fonctions x 7- Pa (x)Pa (x-1 ) et 2.b 2.c 3.a 3.b 4 Pour la deuxième partie de la question, développer l'expression Pa (x)Pa (x-1 ), puis regrouper dans la double somme obtenue les termes suivant l'exposant de x. Si Pa (1) et Pb sont de même parité, il existe un entier m Z tel que Pa (1) soit égal à Pb (1) + 2m. Utiliser alors des identités remarquables pour écrire comme somme de deux carrés l'entier (Pa (1)2 + Pb (1)2 )/2. Montrer qu'un entier de la forme 4k + 3 ne peut s'écrire comme somme de deux carrés d'entiers. Développer l'expression U(x)U(x-1 ) + V(x)V(x-1 ) et l'exprimer en fonction de Pa (x)Pa (x-1 ) + Pb (x)Pb (x-1 ). Calculer les fonctions U(x) et V(x) pour ces séquences, puis utiliser le résultat de la question précédente. Introduire les ensembles I = {i [[ 0 ; 2m - 1 ]], 5.a 5.b 5.c 6.b 7 x 7- Pb (x)Pb (x-1 ) vi = 1} et J = {i [[ 0 ; 2m - 1 ]], vi = -1} puis exprimer la somme et le produit des éléments v0 , . . . , v2m-1 en fonction du cardinal de J. Introduire la séquence proposée par l'énoncé et remarquer que la somme de ses termes est nulle (donc multiple de 4) en raison de la j-ième condition de complémentarité. Considérer le quotient de deux relations consécutives obtenues à la question précédente. Si est impair, regarder ce que donne la relation précédente avec un choix de j judicieux. Utiliser les formules de récurrence (1) et (2) du problème pour en déduire une relation de récurrence entre ces suites. Interpréter matriciellement cette relation. Montrer par récurrence que les polynômes Pn et Qn sont à coefficients entiers, de degré 2n - 1 et que la fonction de la variable réelle x 7- Pn (x)Pn (x-1 ) + Qn (x)Qn (x-1 ) est constante. 8 Raisonner une nouvelle fois par récurrence. 9.a Considérer une racine z de T. Traiter dans un premier temps le cas |z| 6 1. d Pour l'autre cas, commencer par majorer grossièrement |z| en utilisant le fait que z est racine de T. 9.b Utiliser le fait que Pn et Qn sont à coefficients dans {-1, 1} et le résultat de la question précédente. 10.a Remarquer que les 2n premiers coefficients de Pn sont les mêmes que les 2n premiers de Pn+1 . 10.b Considérer une racine de S de module strictement inférieur à 1/2. Utiliser le fait que S est à coefficients dans {-1, 1} et l'inégalité triangulaire pour minorer le module de S(z). Première partie 1 Considérons une paire de séquences a et b de longueur 2. Pour une telle longueur de séquence, il n'y a qu'une seule condition de corrélation qui s'écrit a0 a1 + b 0 b 1 = 0 Il suffit donc de prendre a = (1, 1) et b = (-1, 1) pour la satisfaire. Par conséquent, L'entier 2 est un élément de L. Considérons maintenant des séquences a et b de longueur 3. Il y a alors deux conditions de corrélation qui sont données par a0 a2 + b0 b2 = 0 et a0 a1 + a1 a2 + b0 b1 + b1 b2 = 0 Supposons la première condition satisfaite. Puisque les quatre coefficients a0 , a2 , b0 , b2 sont des éléments de {-1, 1}, alors celle-ci impose que a0 a2 = -1 et b0 b2 = 1 ou a0 a2 = 1 et b0 b2 = -1 Quitte à échanger les rôles de a et b, on peut supposer que ce sont a0 et a2 qui sont opposés et que b0 = b2 = + - 1. Dans ce cas, il vient a0 a1 + a1 a2 = a1 (a0 + a2 ) = 0 ce qui entraîne |a0 a1 + a1 a2 + b0 b1 + b1 b2 | = |b1 | |b0 + b2 | = 2 6= 0 Les deux conditions de corrélation ne peuvent ainsi être simultanément satisfaites. Il n'existe donc aucune paire de séquences complémentaires de longueur 3, ce qui veut dire que L'entier 3 n'est pas un élément de L. 2.a Soit a une séquence de longueur 1 et Pa le polynôme séquentiel associé. Pour simplifier, on note également Pa sa fonction polynomiale associée. Cette fonction est alors continue et équivalente en l'infini à son terme de plus haut degré. Or, celui-ci est le terme de degré 1 - 1, puisque a1 -1 est non nul car il appartient à l'ensemble {-1, 1}. On a ainsi Pa (x) x+ a1 -1 x1 -1 et lim Pa (x-1 ) = Pa (0) = a0 x+ ce qui donne par conséquent l'équivalent Pa (x)Pa (x-1 ) x+ a0 a1 -1 x1 -1 Rappelons que les produits de ces équivalents ne sont valides que parce que a0 n'est pas nul (il appartient lui aussi à l'ensemble {-1, 1}). Nous nous permettrons de ne plus refaire ce type de justification dans tout le corrigé, en particulier de mentionner à chaque instant que les éléments d'une séquence sont non nuls (pour des divisions par exemple). Soit maintenant b une seconde séquence de longueur 2 différente de 1 . Quitte à échanger les séquences, on peut supposer que 2 est strictement inférieur à 1 et donc 1 > 2, puisque 2 est par définition supérieur à 1. Le même raisonnement que précédemment montre que la fonction polynomiale associée à Pb admet en + l'équivalent Pb (x)Pb (x-1 ) b0 b2 -1 x2 -1 = o x1 -1 x+ On a donc l'équivalent suivant en + Pa (x)Pa (x-1 ) + Pb (x)Pb (x-1 ) x+ a0 a1 -1 x1 -1 ce qui montre que la fonction tend vers + ou - en + (selon le signe de a0 a1 ) et n'est en particulier pas bornée. Par conséquent, Si a et b ne sont pas des séquences de même longueur, la fonction x 7- Pa Pa (x-1 ) + Pb (x)Pb (x-1 ) n'est pas bornée sur ] 0 ; + [. Considérons maintenant deux séquences a et b de même longueur et un réel x non nul. Le réel Pa (x)Pa (x-1 ) peut s'écrire en fonction des coefficients de a -1 -1 P P P Pa (x)Pa (x-1 ) = ak xk ai x-i = ak ai xk-i (a) i=0 k=0 06k,i6-1 Regroupons maintenant dans cette double somme les termes suivant l'exposant de x. · Les termes d'exposant 0 sont ceux pour lesquels i = k, avec i [[ 0 ; - 1 ]]. Il y en a ainsi et le coefficient de x0 dans (a) est donné par -1 P 2 ai = i=0 puisque les éléments a0 , . . . , a-1 sont dans l'ensemble {-1, 1}. · Pour chaque j [[ 1 ; - 1 ]], pour avoir k - i = j, l'indice i peut varier entre 0 et - 1 - j, et alors k = i + j. Le coefficient de xj dans la somme (a) est donc -1-j P ai+j ai i=0 · Enfin, la fonction x 7 Pa (x)Pa (x-1 ) est symétrique par l'opération x 7 x-1 : on a donc les mêmes valeurs pour les puissances négatives de x (c'est-à-dire en regroupant les termes pour lesquels k - i = j < 0). Le réel Pa (x)Pa (x-1 ) s'écrit donc finalement ! -1 -1-j X P Pa (x)Pa (x-1 ) = + ai ai+j xj + x-j i=0 j=1 En effectuant les mêmes calculs pour le terme Pb (x-1 )Pb (x), on obtient ainsi ! -1 -j-1 X P -1 -1 Pa (x)Pa (x ) + Pb (x)Pb (x ) = 2 + ai ai+j + bi bi+j xj + x-j j=1 i=0 ce qui montre que si a et b sont deux séquences complémentaires, alors la fonction est constante égale à 2. Réciproquement, supposons qu'il existe au moins un entier j > 1 tel que la j P somme ai ai+j + bi bi+j soit non nulle. Soit j0 le plus grand d'entre eux. Alors, i=0 Pa (x)Pa (x -1 ) + Pb (x)Pb (x -1 ) x+ -1-j P 0 ai ai+j0 + bi bi+j0 i=0 ! xj0 -1 ce qui montre que la fonction n'est pas bornée et donc pas constante. Par conséquent, Deux séquences a et b de même longueur sont complémentaires si et seulement si la fonction x 7 Pa (x)Pa (x-1 ) + Pb (x)Pb (x-1 ) est constante. Elle est alors égale à 2.