Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 13-05-2008 21:21:33

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

eteange fonction

Soit [latex]\alpha \in \mathbb{N}^*[/latex] premier, on définit la fonction [latex]f_\alpha : \mathbb{N} \rightarrow \mathbb{N}[/latex] comme étant la fonction suivante:
[TeX]f_\alpha : x \rightarrow y[/latex] tel que [latex]x!=z.\alpha^y[/latex] avec [latex]z \in \mathbb{N}\ tq\ z % \alpha \ne 0[/TeX]
Dit en français de manière plus simple, ça signifie: si je décompose les entiers de 2 à x en facteurs premiers, [latex]f_\alpha(x)[/latex] est la somme des exposants de [latex]\alpha[/latex].

Vous pouvez vous amusez à le montrer, mais bon ce n'est pas le problème pour l'instant. En réalité, j'ai construit cette fonction sur mesure pour qu'elle soit égale à ça.

Le problème est le suivant:
Il me semble (ie. je n'ai pas encore fini la démonstration moi-même, mais pour l'instant toujours vérifié) que:
[TeX]\forall n \in \mathbb{N}\\
\forall A,B \in \mathbb{N}\ tq\ A+B = \alpha^n-1[/TeX]
on a:
[TeX]f_\alpha^(\alpha^n-1) = f_\alpha(A) + f_\alpha(B)[/TeX]
Le but est bien entendu de démontrer cette propriété (ou son contraire, le contre-exemple étant bien évidemment une démonstration acceptée).

Il s'agit en fait d'une généralisation de ce problème (avec alpha=2)

  • |
  • Répondre

#0 Pub

 #2 - 13-05-2008 21:52:35

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Ettrange fonction

Aaaah, enfin des vrais maths lol

J'y planche et je te dis si je trouve hmm


EDIT, une demi-heure plus tard :

Arf, j'abandonne sad


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #3 - 13-05-2008 23:07:50

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Etrannge fonction

Ok voilà donc la démonstration
Spoiler : [Afficher le message]
Etape 1: Définition et étude d'une fonction g

Etape 1.1: Définiton de g
On définit la fonction [latex]g_\alpha(x) = y[/latex] avec [latex]x = z.\alpha^y, z \in \mathbb{N}\ tq\ z%\alpha \ne 0[/latex]

Autrement dit, si je décompose x en facteurs premiers, j'ai y la valeur de l'exposant devant [latex]\alpha[/latex]

Etape 1.2: Simplification de f en utilisant g
En posant
[TeX]
g_\alpha(x+1) = y_2\\
f_\alpha(x+1) = y_1\\
f_\alpha(x) = y_0
[/TeX]
on a:
[TeX]\exists z_2, z_1, z_0 \in \mathbb{N} \ tq\\
z_2%\alpha \ne 0,\\
z_1%\alpha \ne 0,\\
z_0%\alpha \ne 0\\
\\
x+1 = z_2.\alpha^{y_2}\\
x! = z_0.\alpha^{y_0}\\
(x+1)! = z_1.\alpha^{y_1}\\
z_1.\alpha^{y_1} = (x+1).x! = (x+1).z_0.\alpha^{y_0}\\
z_1.\alpha^{y_1} = z_2.z_0.\alpha^{y_0}.\alpha^{y_2}
[/TeX]
On en déduit de la que [latex]y_0+y_2=y_1[/latex]
Autrement dit:
[TeX]f_\alpha(x+1) = f_\alpha(x)+g_\alpha(x+1)[/TeX]
ou plus généralement
[TeX]f_\alpha(x+m) = f_\alpha(x)+\sum_{i=1}^{m}g_\alpha(x+i)[/TeX]
On a aussi les deux formules équivalentes:
[TeX]f_\alpha(x-1) = f_\alpha(x)-g_\alpha(x)\\
f_\alpha(x-m) = f_\alpha(x)-\sum_{i=1}^{m}g_\alpha(x-i+1)[/TeX]
Fin de l'étape 1
On se retrouve avec deux super formules qui vous nous être très utiles.


Etape 2: Résolution du problème

Etape 2.1: Introduction de g
On repart de notre énoncé.

Etape 2.1.1: Cas particulier
Pour [latex]A=0[/latex] et [latex]B=\alpha^n-1[/latex], le cas est trivial, vu que [latex]f_\alpha(0)=0[/latex]

Etape 2.1.2: Cas général
Pour A et B quelconques cette fois (vérifiant bien sûr leur propriété sur leur somme), on a: [latex]A = 0+A[/latex] et [latex]B = \alpha^n-1-A[/latex]

Donc
[TeX]f_\alpha(A) + f_\alpha(B)=\\
f_\alpha(0) + f_\alpha(\alpha^n-1) +\sum_{i=1}^{A}g_\alpha(i)
-\sum_{i=1}^{A}g_\alpha(\alpha^n-1-i+1)
[/TeX]
Il nous faut donc montrer que
[TeX]\sum_{i=1}^{A}g_\alpha(i) -\sum_{i=1}^{A}g_\alpha(\alpha^n-i) = 0[/TeX]
Etape 2.2: Calcul de la différence
Là ça tombe vachement bien: ce ne sont pas les sommes qui s'annulent mais directement les termes 2 à 2 !
La preuve:

Etape 2.2.1: Cas trivial
[TeX]
i%\alpha \ne 0\\
\Rightarrow (\alpha^n-i)%\alpha \ne 0\\
[/TeX]
Dans ce cas:
[TeX]
\Rightarrow g_\alpha(i) = g_\alpha(\alpha^n-i) = 0
[/TeX]
Etape 2.2.2: Autres cas, par récurrence
[TeX]
i%\alpha = 0 \Leftrightarrow (\alpha^n-i)%\alpha = 0\\
[/TeX]
On va alors faire une récurrence
Si [latex]\exists J < n-1, i%(\alpha^J) = (\alpha^n-i)%(\alpha^J) = 0[/latex]
alors [latex]i%(\alpha^{J+1}) = 0 \Leftrightarrow (\alpha^n-i)%(\alpha^{J+1})=0[/latex]
Allez, on y va. Dans un sens
[TeX]
i%(\alpha^{J+1}) = 0\\
\Rightarrow i=k.\alpha^{J+1}\\
\Rightarrow \alpha^n-i = \alpha^{J+1}.(\alpha^{n-J-1}-k)\\
\Rightarrow (\alpha^n-i)%(\alpha^{J+1}) = 0
[/TeX]
Et dans l'autre, par contraposée:
[TeX]
i%(\alpha^{J}) = 0\\
i%(\alpha^{J+1}) \ne 0\\
\Rightarrow i=k.\alpha^{J}, k%\alpha \ne 0\\
\Rightarrow \alpha^n-i = \alpha^{J}.(\alpha^{n-J}-k)\\
k%\alpha \ne 0 \Rightarrow (\alpha^{n-J}-k)%\alpha \ne 0\\
\Rightarrow (\alpha^n-i)%(\alpha^{J+1}) \ne 0
[/TeX]
CQFD.

Etape 2.3: Conclusion
On résume: la plus petite puissance de [latex]\alpha[/latex] qui ne divise pas i ne divise pas non plus [latex]\alpha^n-i[/latex], donc la plus grande puissance de [latex]\alpha[/latex] qui divise i est aussi la plus grande puissance de [latex]\alpha[/latex] qui divise [latex]\alpha^n-i[/latex].
Par construction donc [latex]g_\alpha(i) = g_\alpha(\alpha^n-i)[/latex]
Donc [latex]\sum_{i=1}^{A}g_\alpha(i) -\sum_{i=1}^{A}g_\alpha(\alpha^n-i) = 0[/latex]
Et donc enfin:
[TeX]f_\alpha(A) + f_\alpha(B)=f_\alpha(0) + f_\alpha(\alpha^n-1) = f_\alpha(\alpha^n-1)[/TeX]
Ouf ca y est, on a gagné !

 #4 - 14-05-2008 23:17:40

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2131

etrange donction

J'adore big_smilebig_smilebig_smilebig_smilebig_smilebig_smilebig_smile

Je suis un vieux papi d'Auch qui n'a plus joué à ça depuis un moment.
Mais qui sait voir que quand Scarta s'y met, ça donne...

Sur sa suite étrange, j'ai à peu près vu le coup.

Là, pour l'instant tongue

Il n'aime pas Lucas (dont je n'ai pas connu la belle-soeur) pour les lignes impaires du triangle de Pascal.
Il généralise à tous les nombres premiers (mais Lucas aussi).

C'est ininintelligible en l'état.
Donc génial (parce que c'est du Scarta).

Ca me prendra un jour, un mois ou un an, mais je finirai par piger.

Je raconterai à ce moment-là smile


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #5 - 14-05-2008 23:48:57

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Etraneg fonction

Merci papiauche, je ne connaissais pas le théorème de Lucas mais il est assez bluffant; je me demande si ce théorème est équivalent à mon résultat, je pense que oui d'ailleurs, c'est une bonne idée de démo à faire smile

En gros pour le coup du Pascal, en partant de mon résultat, on peut dire que pour tout p premier, les lignes de la forme p^n-1 ne comportent aucun multiple de p, chose qu'on peut montrer aussi avec le théorème de Lucas il est vrai.
Si tu as du mal à comprendre à un endroit de ma démo, pas de soucis pour que j'eclaircisse.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete