Montrer que tout entier peut s'écrire comme la somme de puissances de 2 distinctes

a marqué ce sujet comme résolu.

Salut à tous (ça fait longtemps :) ),

l’objet de ce topic tient sur une question d’un exercice de spé maths (terminale S) que je n’arrive pas à traiter.

Voici la question en cause :

Établir un algorithme décomposant un entier N non nul en une somme de puissances de 2 distinctes. Justifier que cet algorithme s’arrête.

Pour ce qui est de l’algorithme : aucun problème, le voici en langage naturel (je l’ai programmé et testé sur ma calculette) :

Demander N

1 -> K
Tant que NK
    2*K -> K
Fin Tant que

Tant que N0
    K/2 -> K
    Si KN alors
        N-K -> N
        Afficher K
    Fin Si
Fin Tant que

Le problème réside dans le fait de montrer que ce programme s’arrête, et plus particulièrement la seconde boucle.

En effet, pour la première on sait que limx+2x=+\lim_{x\to+\infty}2^x=+\infty et donc par définition il existe KNK\in\mathbb{N} tel que 2K>N2^K>N.

Pour la seconde, cela revient à montrer que tout entier (naturel) peut être exprimé comme une somme de puissances de 2 distinctes. Et pour cela je galère pas mal. À mon avis il faut quelque part utiliser le fait que :

nN,2n+2n=2×2n=2n+1\forall n \in\mathbb{N}, 2^n+2^n = 2\times 2^n = 2^{n+1}

j’ai aussi pensé utiliser une preuve par récurrence mais je n’arrive pas à faire aboutir l’hérédité et je pense que mon plus gros problème est que je ne sais pas vraiment comment écrire la somme de puissances de 2 distinctes mathématiquement.

Merci d’avance pour votre aide. :D

+0 -0

Tu peux aussi te demander ce qu’une écriture binaire d’un nombre entier signifie :)

Holosmos

Oui, c’est l’objectif final de l’exo, l’idée que par exemple :

10100112=1×26+0×25+1×24+0×23+0×22+1×21+1×201010011_2 = 1×2^6 + 0×2^5 + 1×2^4 + 0×2^3 + 0×2^2 + 1×2^1 + 1×2^0

+0 -0

Pas besoin de raisonner finement sur la décomposition pour montrer que la seconde boucle termine, il suffit de montrer une quantité qui décroit strictement à chaque étape, et qui ne peut pas décroire strictement pendant un temps infini. Ici, je proposerais de remarquer que N décroit strictement à certaines étapes de la boucle (donc il va forcément finir par devenir nul ou négatif; écrire N > 0 comme condition de boucle rend le raisonnement plus simple), et de réfléchir à la répartition des tours de boucles où N ne décroit pas strictement (tu as un problème s’il peut y en avoir un nombre infini, sans étape strictement décroissante au milieu).

+2 -0

Édit : ce message correspond à une réponse à la remarque d’Holosmos, @gasche, je réflichis sur ton message ;)

J’arrive à quelque chose en utilisant une récurrence forte.

Initialisation : On a n=1=20n = 1 = 2^0 qui s’écrit bien comme une somme de puissances de deux distinctes.

Hérédité : On fixe nNn \in \mathbb{N}, supposons que tout k<nk < n s’écrit comme une somme de puissances de deux distinctes et montrons que cette propriété s’applique aussi à nn.

Soit mNm\in\mathbb{N}, le plus grand entier tel que 2mn2^m \le n.

On a (n,2m)N2(n,2^m)\in\mathbb{N^2} donc par la division euclidienne :

!(q,r)N2/n=q×2m+ravec 0r<2m\exists! (q,r)\in\mathbb{N}^2 / n = q\times 2^m + r \, \text{avec } 0 \le r < 2^m

Montrons maintenant que q=1q=1.

Supposons par l’absurde que q2q\ge 2, alors :

n=q×2m+r=(q2+2)×2m+r=2m+1+(q2)×2m+rn = q\times 2^m +r = (q-2+2)\times 2^m +r = 2^{m+1} + (q-2)\times2^m + r

ce qui implique k2m+1k \ge 2^{m+1} car (q2)×2m+r0(q-2)\times2^m + r \ge 0.

Donc par définition de mm, on aboutit à mm+1m \ge m+1, ce qui est absurde.

Notre hypothèse de départ est fausse, donc q=1q=1.

Ainsi, on a :

n=1×2m+r avec 0r<2mn = 1\times 2^m + r \text{ avec } 0 \le r < 2^m

Or r<2mnr<2^m\le n donc par hypothèse, rr s’écrit comme une somme de puissance de 2 distinctes.

De plus r<2mr<2^m, donc nn s’écrit comme une somme de puissance de 2 distinctes.

Conclusion : par principe de récurrence, tout entier naturel s’écrit comme une somme de puissances de 2 distinctes.

+0 -0

Pour répondre à la remarque de @gasche.

J’avais pensé vite fais à remplacer N0N≠0 par N<0N<0 mais en fait ça ne simplifie pas vraiment le problème puisqu’on vérifie que KNK\le N avant de retrancher KK à NN. Toutefois on peut le faire, les deux algorithmes sont équivalents.

En effet, si on met comme condition d’arrêt N<0N<0 alors la boucle s’arrête ssi N0N\le 0.

Or NKNN-K \to N ssi KN0KNK \le N \iff 0 \le K -N

La valeur finale de NN vérifie donc 0N00\le N \le 0, ie. N=0N=0.

Pour montrer qu’on arrivera toujours à une boucle telle que la valeur de NN va décroître strictement, on peut remarquer que KK prend les valeurs successives de f:ZRf: \mathbb{Z \to R} avec f(x)=2xf(x) = 2^x, quand xx tend vers moins l’infini.1

Or limxf(x)=0\lim_{x\to-\infty} f(x) = 0 donc par définition de la limite, si ε=N>0ε = N > 0 :

KZ/2KN\exists K \in \mathbb{Z} / 2^K \le N

Ainsi, tant que N>0N>0 il y aura une boucle telle que NN décroît strictement. (ça me parait un peu bancal comme démonstration :/ )


  1. Je sais pas si vous m’avez compris, mais je vois pas trop comment dire ça :/

+0 -0

Je trouve ta rédaction (f:ZRf : \mathbb{Z} \to \mathbb{R}, etc.) un peu compliquée pour dire que la suite décroissante des K/2nK/2^n devient plus petite que toute borne NN en un nombre fini d’étape. (Il me semble qu’il suffit de juste dire ça ?). Une fois que tu as montré que NN décroit strictement après un nombre fini de tours de boucle, si la condition de boucle est N>0N > 0, il suffit de dire qu’après un nombre fini de décroissances strictes on a forcément N0N \leq 0, donc la boucle s’arrête. La preuve (en entier) est terminée.

Edit: un avantage de cette technique de preuve est qu’elle s’adapte à plein d’autres situations (je m’en sers régulièrement dans mon travail), contrairement à une preuve "par existence de la décomposition en base 2" qui est spécifique à ton problème.

+0 -0

Si tu utilises une TI-83+ ou une calculatrice dans le même style (avec la fonction partie entière), tu peux quand même remplacer ta première boucle par :

2log2nK2^{\lceil \log_2 n \rceil} \to K

Et c’est mieux que du O(logn)\mathcal{O}(\log n).

N.B : je ne sais pas pourquoi la partie entière supérieur s’affiche comme une valeur absolue… (en utilisant \rceil, \lceil).

EDIT : ah bah c’est bon maintenant. C’est bizarre en prévisualisation je vois une valeur absolue mais dans le thread je vois bien la partie entière.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte