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 - 25-04-2019 19:43:57

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

nombre impair exprilé en puissances de 2.

Bonsoir @ tous.

Évidemment, on peut exprimer un nombre impair en binaire. Cependant, est ce qu'on peut toujours l'exprimer comme une somme de n (suffisamment grand, mais aussi grand que l'on veut) puissances de 2 ( de 0 à n-1 ), chacune étant exprimée une fois et une seule en positif ou négatif ?

Par exemple 13 = 32-16-8+4+2-1.

C'est facile, mais il faut la preuve.

Bonne recherche !



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 25-04-2019 20:05:26

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 822

nimbre impair exprimé en puissances de 2.

Salut nodgim,

sur un exemple : prenons 281, qui vaut 256+16+8+1 soit 100011001 en binaire.

Si on veut l'exprimer de la façon voulue en partant de 512, on l'écrit avec des zéros inutiles en binaire jusqu'à atteindre le rang de 512, soit 0100011001.

Puis on fait apparaitre dans cette écriture des groupes du type 00...001 (avec un nombre de zéros >=0) : c'est (01)(0001)(1)(001).

Pour chaque groupe de ce type, on écrit la somme de puissances de deux avec le premier terme positif et les autres négatifs :
281 = (512-256) + (128-64-32-16) + (8) + (4-2-1).

Ça utilise juste que 2^n = 2^(n+k) - 2^(n+k-1) - ... - 2^n.

 #3 - 26-04-2019 08:12:49

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

nombre impair exprimé en puissances dr 2.

@ Ebichu : c'est exactement la réponse que j'attendais.

 #4 - 27-04-2019 15:08:01

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 295

nombre impair exprimé en puossances de 2.

Pour tout n, soit k tel que n < 2^k
n s'écrit donc de manière unique comme somme de puissance de 2 strictement plus petites que 2^k.
2^k - 2^k-1 - 2^k-2 - ... - 1 = 1
2n+1 s'écrira donc sous la forme recherchée, avec des + correspondant aux 1 dans l'écriture binaire de n.

 #5 - 27-04-2019 17:34:11

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

nombre impair exprimé en puissabces de 2.

Attention Caduk, je me demande si je me suis bien exprimé dans l'énoncé.

Pour former 19 par exemple :

On peut le faire avec k  = 4 ou 5, ou 6, ou 7, .....( tu pourras vérifier )

Il faut démontrer que ça marche pour tout k au dessus d'une certaine valeur.

 #6 - 28-04-2019 16:44:34

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 691

NNombre impair exprimé en puissances de 2.

Ex : 19 = 2^4 + 2^3 -2^2 - 2^1 + 1
On peut augmenter N à volonté.
2^4 = 2^5 - 2^4
2^5 = 2^6 - 2^5
donc
2^4 = 2^6 - 2^5 - 2^4
etc.

 #7 - 29-04-2019 08:02:36

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

Nombre impair exprimé en puissancces de 2.

Salut Godisdead.

ça marche certes pour 19, mais est ce que ça marche pour tout nombre impair ?

Y a un truc bien net qui le dit....

Penser binaire !

 #8 - 29-04-2019 08:05:41

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

nombre impair exptimé en puissances de 2.

Bon, ben le temps est déjà écoulé, voyez la réponse d'Ebichu et essayez là, vous verrez ça marche très bien !

 #9 - 29-04-2019 12:48:59

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 295

Nombre impair exprimé en puissances de .2

nodgim
Je ne comprend pas ta remarque, j'ai montré qu'on pouvait le faire pour tout k tel que n < 2^k
n peut alors s'écrire comme expression binaire de k termes (avec éventuellement des 0 non significatifs.
2n+1 s'écrira alors sous la forme recherchée, les 1 de l'expression binaire de n transformant les - en +
Je pense que ta confusion vient du fait que mon n n'est pas le même que celui de ton énoncé...

Je donne un exemple pour exlaircir ma solution:
pour écrire 23:
23 = 2*11 + 1
11 = 001011 (une écriture binaire possible)

1 = 2^6 - 2^5 - ... -2^0 = 1(-1)(-1)(-1)(-1)(-1)(-1)

2*11 + 1 = 1(-1+2*0)(-1+2*0)(-1+2*1)(-1+2*0)(-1+2*1)(-1+2*1) = 1(-1)(-1)1(-1)11 = 2^6 - 2^5 - 2^4 + 2^3 -2^2 + 2^1 + 2^0

 #10 - 30-04-2019 16:57:38

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

Nombre mipair exprimé en puissances de 2.

@Caduk.

Tu avais écrit en 1er message :.... avec des + correspondants aux 1. C'est ça qui m'a fait dire que c'était faux.

Pour écrire le nombre 0000111000101001, il faut:

00001... 1... 1.... 0001... 01.....001
+----.....+....+....+---......+-....+--

Le 1(+) est repoussé à droite d'une unité pour chaque (-).

J'avoue n'avoir toujours pas compris convenablement ton 2ème message, ça vient sûrement de moi.

 #11 - 30-04-2019 19:17:04

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 295

nombre impait exprimé en puissances de 2.

Je vais refaire ma méthode sur ton nombre.
x = 0000111000101001
(x - 1)/2 = 000011100010100

Si on étend la notation binaire à des coefficients pouvant valoir -1 ou 2, on obtient

1 + 2*(x - 1)/2 = 1(-1)(-1)(-1)(-1)...(-1) + 000022200020200
En opérant bit à bit:
x = 1(-1)(-1)(-1)(-1)111(-1)(-1)(-1)1(-1)1(-1)(-1)

 #12 - 30-04-2019 19:36:55

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3587

Nombre imppair exprimé en puissances de 2.

C'est OK pour moi maintenant, et en relisant ton 1er message, il est effectivement correct. C'est que le passage de n à 2n+1 est un peu abscons, mais bon je comprends que tu voulais faire coïncider les + avec les 1.

Donc tu avais bien la bonne réponse dès le départ, bravo à toi également !

 

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 : Pim, Pam et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

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