Une énigme sur la parité des coefficients d'un polynô.me

Olympiades mathématiques, énigmes et défis
duchere
Membre Relatif
Messages: 235
Enregistré le: 17 Juin 2006, 01:39

Une énigme sur la parité des coefficients d'un polynô.me

par duchere » 30 Aoû 2008, 01:29

Bonjour, voici une petite énigme pas facile du tout !

Soit un polynôme P de degré N.

Soit

Soit R le polynôme Q tronqué au degré N.

Donner une condition nécessaire et suffisante sur m pour que les coefficients de R aient même parité que les coefficients de P

Par exemple, prenons





Et vous pouvez vérifier que m=8 est le premier entier différent de 1 qui convient.
Le deuxième qui convient est 16.
Vous devinerez quels sont les suivants.

En revanche, devinerez-vous quelle est la condition nécessaire et suffisante dans le cas général ?

Bonne chance.



Imod
Habitué(e)
Messages: 6474
Enregistré le: 12 Sep 2006, 13:00

par Imod » 30 Aoû 2008, 11:55

Il me semble qu'il y a un problème dans la formulation de l'exercice ! Si P a tous ses coefficients pairs alors pour tout m , R aura aussi ses coefficients pairs :doh:

Imod

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 30 Aoû 2008, 12:23

On a donc et on veut .
Autrement dit, il faut résoudre en m l'équation

A vue de nez, si m est une puissance de 2 strictement supérieure au degré de P, alors ce sera bon car . Ceci est donc une condition suffisante. Mais est-elle nécessaire ?

Imod a écrit:Il me semble qu'il y a un problème dans la formulation de l'exercice ! Si P a tous ses coefficients pairs alors pour tout m , R aura aussi ses coefficients pairs :doh:

Imod


Cela indique que la condition sur m dépend peut-être du nombre (et de leur place) de coefficients impairs de P : si P n'a pas de coefficients impairs, il n'y a pas de contrainte sur m, ok. Mais si P contient des coefficients impairs, alors m est contraint... mais par quelle loi ?

Avatar de l’utilisateur
leon1789
Membre Transcendant
Messages: 5475
Enregistré le: 27 Nov 2007, 17:25

par leon1789 » 30 Aoû 2008, 12:39

Alors je dirais, à tout hasard, que le plus petit entier m qui convient est 2^k avec 2^k le plus petit puissance strictement supérieure aux degrés de tous les monômes de coefficients impairs de P.

C'est un truc comme ça ?

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 30 Aoû 2008, 13:34

On se place dans Z/2Z, et soit v le nombre de facteurs X dans P (le degré de la plus petite puissance qui a un coefficient impair)
On a les équivalences

P = P(1+X)^m mod X^(N+1)
P((1+X)^m - 1) = 0 mod X^(N+1)
(1+X)^m - 1 = 0 mod X^(N+1-v)
(1+X)^m = 1 mod X^(N+1-v)
Et là, avec Frobenius, on peut montrer que l'ordre de (1+X) est 2^k, où k est le plus petit entier tel que 2^k >= N+1-v.
Donc tout ça équivaut à m = 0 mod 2^k.

duchere
Membre Relatif
Messages: 235
Enregistré le: 17 Juin 2006, 01:39

par duchere » 30 Aoû 2008, 14:05

Je crois qu'on est assez prôche de la solution, même si je ne comprends pas tout de la solution de Doraki, sûrement parce que je sors de spé PC, et non pas MP...

Ma solution s'inspire des triangles de Sierpinski.

Et la solution qui a été plus ou moins dite est :
Il faut prendre le degré de la plus grande puissance qui a un coefficient impair, luis ajouter 1, et prendre la première puissance de 2 qui suit.

Par exemple,

Le degré de la plus grande puissance qui a un coefficient impair est 3, en lui ajoutant 1, on a 4, et la puissance de 2 qui suit 4 est .... 4.

Donc la réponse est m=0 ou m=4*2^k, k entier naturel quelconque.
Mais il me semble que ce n'est pas ce que trouve Doraki.
Si vous voullez ma démo, dites le moi

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 30 Aoû 2008, 14:21

Tu obtiens quoi si tu essayes avec P = X^n avec ta méthode ?
Avec P = 2X^n + 1 ?

duchere
Membre Relatif
Messages: 235
Enregistré le: 17 Juin 2006, 01:39

par duchere » 30 Aoû 2008, 14:38

Avant de donner ma réponse, il faut que je corrige mon erreur...
Je me suis embrouillé dans mon post précédent...
Il faut bien considérer, comme tu l'as bien dit la plus petite puissance dont le coefficient est impair qu'on note V ! et non pas la plus grande !
Ensuite, prendre le degré de P, lui soustraire V et lui ajouter 1.
On note j=n-V+1
Le premier m non nul cherché est la plus petite puissance de 2 suivant j.

Donc, si je reprends mon exemple,
v=1
j=n-v+1=5
La plus petite puissance de 2 suivant 8 est ... 8.
Et ensuite, les m qui conviennent sont tous les multiples de 8.
Donc, ta solution est LA solution.

Voilà.

Donc, avec ma (nouvelle) méthode, je dois trouver la même chose que toi.

Pour P=X^n, ça donne 1.

Pour P=2X^n+1, ça donne la plus petite puissance de 2 suivant n+1

Désolé pour mon erreur du post précédent, j'ai réfléchi à cet énigme hier soir tard, et la nuit m'a embrouillé...

Bonne journée.

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 30 Aoû 2008, 14:48

ouais j'avais bien oublié un décalage de 1 dès le début.
attention dans ton exemple j = 5-1+1 = 5 d'où m = 0 mod 8 comme dans ton premier post.

duchere
Membre Relatif
Messages: 235
Enregistré le: 17 Juin 2006, 01:39

par duchere » 30 Aoû 2008, 16:36

Merci, j'ai rectifié.
En tout cas, ta solutin est plus rapide que la mienne, bien que moins élémentaire.

duchere
Membre Relatif
Messages: 235
Enregistré le: 17 Juin 2006, 01:39

par duchere » 30 Aoû 2008, 16:37

Qu'est-ce-que Frobenius ?

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 30 Aoû 2008, 17:41

Dans un corps de caractéristique p, (a+b)^p = a^p + b^p, parceque si tu regardes les coefficients des autres termes, ils sont tous multiples de p car p est premier.
Ici, dans Z/2Z (caractéristique 2), en l'appliquant k fois, ça implique que (1+X)^(2^k) = 1 + X^(2^k).
Ça doit être dans ce que tu vois en regardant le triangle de sierpinski (qui ressemble au triangle de pascal modulo 2).

duchere
Membre Relatif
Messages: 235
Enregistré le: 17 Juin 2006, 01:39

par duchere » 30 Aoû 2008, 18:18

Oui, (1+X)^(2^k) = 1 + X^(2^k), c'est bien ce que je vois dans le triangle de sierpinski... qui est carrément le triangle de pascal modulo 2 me semble-t-il...
En fait, tu utilises un résultat plus général, que je ne connais pas.

Dans cet exercice, je généralise le triangle de sierpinski pour le faire devenir un rectangle de sierpinski.

Le triangle de sierpinski, c'est :

10000000
11000000
10100000
11110000
10001000
11001100
10101010
11111111
10000000


Et ce que j'appelle le rectangle de sierpinski, c'est la même relation de récurrence entre deux lignes, mais la ligne initiale est quelconque.

Par exemple,

100100
110110
101101
111011
100110
110101
101111
111000
100100
etc...

Tandis que le triangle de sierpinski donnait les coefficients modulo 2 de (1+x)^n, le rectangle de sierpinski donne les coefficients modulo 2 de (1+x)^n multiplié par le polynôme dont les cofficients modulo 2 sont ceux de la 1ère ligne(par ordre croissant).

Il fallait donc montrer que les rectangles de sierpinski avaient même périodicité verticale que le triangle de sierpinski, ce qui n'est pas si facile à montrer..

Bonne journée.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite