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 - 06-11-2010 19:47:18

luthin
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 124

combien de fois peut-on diviser p! pat 2?

Voici un autre problème que je me suis posé récemment:

Question 1: Vous n'aurez pas de mal à vous convaincre que quelque soit l'entier [latex]n[/latex] positif ou nul, on peut écrire:
[latex](2^n)!=2^k r[/latex], où [latex]k\in\mathbb{N}[/latex] et [latex]r[/latex] est un entier impair.
Alors, je vous demande d'exprimer [latex]k[/latex] en fonction de [latex]n[/latex].

Question bonus: Profitez-en pour exprimer également [latex]r[/latex] en fonction de [latex]n[/latex] (sans faire intervenir [latex](2^n)![/latex]).
Spoiler : Indice:  Vous aurez sûrement besoin d'utiliser la double factorielle .

Question 2: C'est la question initiale que je me suis posé.
Considérons un entier [latex]p[/latex] positif ou nul et notons [latex]b[/latex], la somme de ses chiffres en écriture binaire.
Alors, au maximum, combien de fois peut-on diviser [latex]p![/latex] par 2?
Spoiler : Indice:  La question 1 n'est pas anodine...

Amusez-vous bien. smile

  • |
  • Répondre

#0 Pub

 #2 - 06-11-2010 20:32:34

gabrielduflot
Expert de Prise2Tete
Enigmes résolues : 34
Messages : 609

Combien de fois peut-on divisre p! par 2?

en testant on dirait que [latex]k=2^n-1[/latex]
par recurrence
n=2 on a [latex](2^2)!=2^2\times 3\times 2\times 1=2^3\times 3[/latex] et [latex]3=2^2-1[/latex]
Supposons vraie que [latex](2^n)!=2^{2^n-1}\times r[/latex] montrons le au rang n+1
[TeX](2^{n+1})!=(2^n)!\Pi_{i=2^n+1}^{i=2^{n+1}i[/TeX]
Il y a autant de nombre entre [latex]2^n+1 et 2^{n+1}-1[/latex] que pour [latex](2n)![/latex]et donc il y aura [latex]2\times (2^n-1) + 1[/latex] comme exposant de 2 donc [latex](2^{n+1})!=2^{2^{n+1}-1}\times r'[/latex] ce que l'on voulait démontrer
[TeX]r=\Pi_{i=1}^{i=n}{(2^i-1)!!}[/TeX]

 #3 - 06-11-2010 23:02:04

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Combien de foois peut-on diviser p! par 2?

La question 1 je suis trop d'accord, c'est logique tongue
bon je réitère:
[latex]p![/latex] est un nombre pair. Donc on peut le diviser un fois par deux au minimum
[latex]p!=1*2*....*(p-2)*(p-1)*p[/latex], il y a donc un somme de p terme. Il y a donc p/2 terme pair:
2;4;...
[latex]p![/latex] est donc divisible par le[somme(k=0-->n de p/2)] fois par 2.
Bon fais à la va vite, avec un semblant de logique pure. Pour ne pas rien répondre (ou d'une moins une connerie) big_smile
                                                                                                 Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #4 - 06-11-2010 23:43:26

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

Combien de fois peu-ton diviser p! par 2?

Question 1:
Le nombre de fois où un terme pair apparaît dans la factorielle est 2^n / 2
Pour les multiples de 4, 2^n/4; pour les multiples de 8 2^n/8, etc...
Donc on a
[TeX]k=\sum_{i=1}^n2^{n-i}=\sum_{i=0}^{n-1}2^i=2^n-1[/TeX]
Bon et puis r en fonction de n, trop fastoche du coup :
[TeX]r = \frac{(2^n)!}{2^{(2^n-1)}}[/TeX]
Question 2:
J'ai envie de répondre de la même manière, sauf qu'on aura besoin de E(x), la partie entière de x
[latex]p! = R.2^k, k=\sum_{i=1}^\infty E(\frac{p}{2^i})[/latex] avec R impair
qu'on peut simplifier en
[latex]p! = R.2^k, k=\sum_{i=1}^{2^i\leq p} E(\frac{p}{2^i})[/latex], les autres termes étant nuls.

[latex]E(\frac{p}{2^i})[/latex] correspond en binaire à l'écriture de p à laquelle on retire les i derniers chiffres.

En théorie, on ne comprend pas tout de suite où tu veux en venir avec ton b! Sauf que voila, on remarque assez vite que k = p-b semble bien se vérifier...


Du coup, on suppose que k=p-b pour tout les nombres écrits avec N chiffres en binaire. On peut vérifier que pour N=1, c'est bien le cas (p=1, b=1, k=0)
On suppose que c'est le cas au rang n, est-ce toujours le cas au rang n+1 ?

Soit p un nombre de n+1 chiffres en base 2, soit b la somme de ses chiffres dans cette base et soit k tel que p! = 2^k *r avec r impair

Deux cas possibles:
- p est un nombre pair de n+1 chiffres, qui finit par un 0 et auquel on fait correspondre p' = p/2 (avec n chiffres, un b'=b et un k'=p'-b)
D'après les formules générales un peu plus haut, k=p' + une certaine somme, mais cette certaine somme est la même que celle utilisée pour calculer k'
Donc k = p'+p'-b = p-b

-p est un nombre pair de n+1 chiffres, qui finit par un 1 et auquel on fait correspondre p' = (p-1)/2 (avec n chiffres, un b'=b-1 et un k'=p'-b'=p'-b+1)
Toujours d'après les formules ci-dessus, k=p'+p'-b+1 = 2p'+1-b = p-b

Conclusion: k=p-b

Merci, c'était très sympa

 #5 - 07-11-2010 11:11:04

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1935
Lieu: 86310

combizn de fois peut-on diviser p! par 2?

[TeX]k=\sum^{\frac{n}{2}}_{i=1}E[\frac{n}{2^i}][/TeX]


The proof of the pudding is in the eating.

 #6 - 07-11-2010 18:48:29

Yanyan
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 509
Lieu: Lille si j'y suis

Combien de fois eut-on diviser p! par 2?

[TeX]v_{p}(n!)=\sum_{m\ge 1} \lfl \frac{n}{p^m}\rfl \text{ (formule de Legendre)}[/TeX][TeX] \text{Donc en posant } p=2 \text{ et } n=2^n[/TeX][TeX] k=\sum_{1\leq m\leq n}2^{n-m}=\sum_{i=0}^{n-1} 2^i=2^n-1[/TeX]


Un mathématicien complet est topologiquement fermé!

 #7 - 07-11-2010 20:16:42

Yannek
Passionné de Prise2Tete
Enigmes résolues : 10
Messages : 60

combien de fois peut-on diviser p! oar 2?

En écrivant d'abord les facteurs impairs on trouve :
[TeX](2^n)!=(2^n-1)!!\times(2\times ((2^{n-1})!)))[/TeX]
À partir de cette formule, on peut prouver par récurrence sur n :
[TeX](2^n)!=2^{2^{n}-1}\times r[/latex] avec [latex]r=\prod_{k=1}^n(2^k-1)!![/TeX]
En particulier, si [latex]p=\sum_{k=1}^b2^{n_k}[/latex] avec [latex]n_k>...>n_1[/latex], on obtient :
[TeX]p!=2^{\sum_{k=1}^n2^{n_k}-1}r'=2^{2^{p-b}}\times r'[/TeX]
avec r' impair.

[Edit] mauvais copié-collé, merci Luthin : [latex]p!=2^{\sum_{k=1}^n2^{n_k}-1}r'=2^{p-b}\times r'[/latex]

 #8 - 08-11-2010 11:03:37

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Combien de fois peut-on diviser p! pr 2?

Salut luthin. Merci pour cette nouvelle énigme arithmétique smile
Question 1:
En suivant le même raisonnement qu'évoqué ici, le nombre de facteurs 2 divisant [latex]N=(2^n)![/latex] est: [latex]\sum_{i=1}^{\infty}E(\dfrac{2^n}{2^i})[/latex], ce qui vaut: [latex]\sum_{i=0}^{n-1}2^i=2^n-1[/latex].
On a donc [latex]k=2^n-1\text{ et }(2^n)!=2^{2^n-1}r[/latex].

Pour calculer r, il ne reste que des produits de nombres impairs:
- de 2 en 2 en partant de 1 à [latex]2^n-1=(2^n-1)!![/latex]
- puis de 4 en 4 en partant de 1 à [latex]2^{n-1}-1=(2^{n-1}-1)!![/latex]

Donc [latex]r=\prod_{i=1}^n(2^i-1)!![/latex]
Je n'ai pas trouvé tellement plus simple.

Question 2:
Je vais plancher dessus.
A première vue, sans trop réfléchir, je conjecture que [latex]2^{(p-b)}[/latex] divise p! mais je vais chercher à vérifier ou infirmer.
Je veux dire qu'on peut diviser p-b fois par 2.

Je n'ai pas trouvé comment utiliser le 1...

p s'écrit en base 2: [latex]p=\sum_{k=0}^{\infty}p_k2^k[/latex]. Les [latex]p_k[/latex] sont les chiffres en base 2 et bien que la somme soit notée infinie, c'est simplement un aspect pratique de notation: à partir d'un certain rang tous les chiffres sont nuls et la somme est finie (cela évite d'alourdir en introduisant le nombre de chiffres)

Comme ci-dessus, le nombre de fois par lequel on peut diviser p! par 2 est:
[TeX]N(p)=\sum_{i=1}^{\infty}E(\dfrac{p}{2^i})=\sum_{i=1}^{\infty}E\Biggl(\dfrac{\sum_{k=0}^{\infty}p_k2^k}{2^i}\Biggr)[/TeX]
N'oubliez pas que toutes ces sommes sont FINIES donc le travail sur les écritures est valide.
Bon je sais ça à l'air monstrueux mais pas tant que ça.

Les chiffres valent 0 ou 1 (écriture binaire). Seuls les termes pour lesquels les chiffres sont 1 apportent quelque chose.
Si p0 vaut 1, il est éliminé (toujours divisé par 2 ou plus et on garde la partie entière). C'est normal: si le nombre est impair, cela n'apporte pas de facteur 2.
Si p1 vaut 1, p1 contribuera 1 seule fois à la somme pour i=1 et sa contribution vaudra 1 ([latex]1.\dfrac{2^1}{2^1}[/latex]).
Si p2 vaut 1, p2 contribuera 2 fois à la somme et sa contribution vaudra 1+2.
Si p3 vaut 1, p3 contribuera 3 fois à la somme et sa contribution vaudra: [latex]1+2+4=7=2^3-1[/latex]

On comprend aisément que:
[TeX]N(p)=\sum_{k=1}^{\infty}p_k.(2^k-1)[/TeX]
On peut laisser tous les pk car ceux nuls n'apportent rien.

Cette somme commence à k=1, il faut donc traiter p0 spécialement.
On a finalement:
[TeX]N(p)=\sum_{k=1}^{\infty}p_k.2^k-\sum_{k=1}^{\infty}p_k=(p-p_0)-(b-p_0)=p-b[/TeX]
CQFD.
Sans avoir trouvé simplement comment utiliser le 1.

On vérifie quand même que le 1 est un cas particulier: une puissance de 2 en binaire n'a que son premier chiffre non nul, donc b=1 et [latex]N(2^n)=2^n-1[/latex]

C'était vraiment sympa. Merci.
Un bon devoir à donner en Terminale ou Sup.

 #9 - 09-11-2010 11:11:43

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

combien de fois prut-on diviser p! par 2?

Il y a [latex]\frac{2^n}{2^1}[/latex] multiples de [latex]2^1[/latex], [latex]\frac{2^n}{ 2^2} [/latex]multiples de [latex]2^2,[/latex] ..., [latex]\frac{2^n}{2^n}[/latex] multiples de [latex]2^n[/latex] et 0 multiple de [latex]2^m, m>n[/latex]
Au total on a donc[latex] k = 2^{n-1} + 2^{n-2} + ... + 1 = 2^n - 1[/latex] facteurs de 2


Pour un nombre quelconque p, c'est pareil :
Il y a [latex]\lfloor \frac{p}{2^1}\rfloor[/latex] multiples de [latex]2^1[/latex], [latex]\lfloor\frac{p}{ 2^2} \rfloor[/latex]multiples de [latex]2^2,[/latex] ..., [latex]\lfloor\frac{p}{2^{\log_2{p}}}\rfloor[/latex] multiples de [latex]2^n[/latex] et 0 multiple de [latex]2^m, m>\log_2{p}[/latex]

Soit k=  [latex]\sum_{i=1}^{\log_2{p}} \lfloor \frac{p}{2^i}\rfloor [/latex] facteurs de 2 dans p!

Si on écrit p en binaire, alors k est la somme de ses préfixes stricts



edit : rigolo les double factorielles ^^

On remarque tout d'abord :
[TeX]
2^n!! = 2^n \times (2^n-2) \times \ldots \times 2
= 2 \times 2^{n-1} \times 2 \times (2^{n-1}-1) \times \ldots \times 2 \times 1
= 2^{2^{n-1}} \times 2^{n-1}!
[/TeX]
On en déduit :
[TeX] 2^n! = 2^n!! \times (2^n-1)!! = 2^{2^{n-1}} \times 2^{n-1}! \times (2^n-1)!! [/TeX]
On a une relation entre [latex]2^n![/latex] et  [latex]2^{n-1}![/latex] où intervient le produit d'une puissance de 2 et d'un produit de nombres impairs.
On peut donc facilement séparer les deux parties dans une expression générale :
[TeX]2^n! = 2^{2^{n-1}} \times (2^n-1)!! \times 2^{n-1}!
= 2^{2^{n-1}} \times (2^n-1)!! \times [2^{2^{n-2}} \times (2^{n-1}-1)!! \times 2^{n-2}!]
= \ldots = \prod_{i=0}^{n-1}(2^{2^i} \times (2^{i+1}-1))!!
= 2^{\sum_{i=0}^{n-1} 2^i} \times \prod_{i=0}^{n-1} (2^{i+1}-1))!!
= 2^{2^n-1}\times \prod_{i=1}^{n}(2^i-1)!!
[/TeX]
On retrouve [latex]2^n-1[/latex] facteurs de 2 (ouf) et un produit de nombres impairs

 #10 - 11-11-2010 23:28:16

luthin
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 124

Combien de fois peu-ton diviser p! par 2?

Que des bonnes réponses ou presque, avec diverses méthodes. On a un bon aperçu de ce qu'il était possible de faire.

Les réponses de Rivas et Scarta sont très complètes. Ca ne veut pas dire qu'il n'y a pas de choses intéressantes dans les autres messages.

Je me permets de faire quelques remarques:
gabrielduflot: Il y a quelques erreurs de frappe et ton argument qui te permet de conclure me parait douteux. Il y a un facteur 2 de plus "entre" [latex]2^n+1[/latex] et [latex]2^{n+1}[/latex] que dans [latex](2^n)![/latex] et donc...

shadock: Ton "semblant de logique pure" m'a bien fait rire (ce n'est pas du tout méchant ou moqueur)! lol

scarta: Réponse qui me semble excellente. Très malin la démonstration de la question 2. Sinon, dans le dernier paragraphe, il faut lire "p est un nombre impair".

franck: Oui, ça ressemble un peu à ça! big_smile

yanyan: La formule de Legendre, merci pour la référence, je ne connaissais pas. Ca répondait effectivement à ma question initiale. Si je l'avais su ou même deviné (elle se comprend assez bien en fait), j'en aurais pas fait une énigme. Ceci dit, il me semble que le résultat que je vous propose de démontrer n'en est pas moins intéressant... smile

Yannek: Bien vu ta première équation, ça permet de traiter la question 1 et le bonus d'un coup! Bon après le "on obtient", ça reste un peu mystérieux pour moi. Ne devrait-on pas lire "b" à la place de "n" au dessus de tes deux dernières sommes? hmm

rivas: Une autre excellente réponse. C'est très clair, merci. smile

Nicouj: Il me semble qu'à la place de "[latex]\lfloor\frac{p}{2^{\log_2{p}}}\rfloor[/latex] multiples de [latex]2^n[/latex]", il faut lire "[latex]\lfloor\frac{p}{2^{\lfloor\log_2{p}\rfloor}}\rfloor[/latex] multiples de [latex]2^{\lfloor\log_2{p}\rfloor}[/latex]", et idem pour la borne sup de la somme qui suit. Il doit y avoir aussi une petite coquille à la troisième équation en partant de la fin.

Bon, après tout ça, j'ai pas intérêt à raconter n'importe quoi, ..., si c'est pas déjà fait! big_smile

En fait, personne n'a utilisé la première question pour répondre à la deuxième... Je vous fais donc voir comment j'ai procédé, c'est pas plus malin, mais c'est juste ce qui m'a permis "de tomber" sur ce résultat que je trouve assez joli: [latex]k=p-b[/latex].

Je cherche donc la plus grande puissance [latex]n_1[/latex] de 2 dans [latex]p![/latex]. Elle est donnée par: [latex]n_1=E(\log _2 p)[/latex]

Pour visualiser, on a: [latex]p!=\underbrace{1.2.3.2^2.5...2^3...2^{n_1}}(2^{n_1}+1)...p[/latex]

D'après la première question, dans l'accolade, on a [latex]k_1=2^{n_1}-1[/latex] facteurs 2.

Il faut alors se convaincre qu'il y a autant de facteurs 2 dans le reste [latex]\frac{p!}{(2^{n_1})!}[/latex]que dans [latex](p-2^{n_1})![/latex].

Et là, même principe, je cherche la plus grande puissance [latex]n_2[/latex] de 2 dans [latex](p-2^{n_1})![/latex]. Elle est donnée par: [latex]n_2=E\left((\log _2 (p-2^{n_1})\right)[/latex]. Et on pourra alors ajouter à [latex]k[/latex], un autre terme [latex]k_2=2^{n_2}-1[/latex]...

En observant l'expression des [latex]n_i[/latex], on comprend qu'il correspondent, dans l'écriture binaire de [latex]p[/latex], aux puissances de 2 qui ont un poids non nul. Autrement dit, si [latex]p=\sum_{i=0}^{n_1}b_i2^i[/latex], on aura:
[TeX]k=\sum_{i=0}^{n_1}b_ik_i=\sum_{i=0}^{n_1}b_i(2^i-1)[/latex], soit [latex]\fbox{k=p-b}[/TeX]
A noter que ces résultats se généralisent pour une base entière [latex]a>1[/latex] quelconque.
En effet, on peut écrire [latex](a^n)!=a^kr[/latex], avec [latex]k\in\mathbb{N}[/latex] et [latex]r\in\mathbb{N}^*[/latex] non divisible par [latex]a[/latex].

Alors: [latex]\fbox{k=\frac{a^n-1}{a-1}}[/latex]

De même, si [latex]b_a[/latex] est la somme des chiffres d'un entier [latex]p[/latex] en écriture de base [latex]a[/latex], alors, on peut diviser [latex]p![/latex] par [latex]a[/latex] au maximum [latex]k[/latex] fois avec: [latex]\fbox{k=\frac{p-b_a}{a-1}}[/latex]

Merci à tous les participants! smile

 #11 - 12-11-2010 09:24:11

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Combien de fois peut-on diviser p! paar 2?

Merci luthin pour cette énigme et pour la jolie généralisation. Je n'y avais pas songé.

 

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