Probleme arithmétique

[ilelogique]

Bonjour, savez vous prouver cela svp :

soit n dans N
et soit p=max {i tel que 2 exp i <n}

alors il existe a0, a1....ap chacun dans {0,1} tels que :

n=somme (ak . 2 exp k) pour k va de 0 à p

merci.
-----

[invited979e304]

Dans le principe, cela revient à montrer la possibilité de passer du décimal vers le binaire, mais dans le détail, c'est plus une histoire de dual et cie.

[ilelogique]

pourquoi décimal vers binaire ?
La suite des a0...ap serait l'écriture du nombre en binaire ?

[ilelogique]

non ce n'est pas ça,
car par exemple 13 = 1+4+8, donc a0=1 ; a1=0 ; a2=1 et a3=1, soit 1011
or 13= 1101 en binaire

[A voir en vidéo sur Futura]

[invited979e304]

Oui.
Par exemple, on a pour 14: 14 = 1 x 2^3 + 1 x 2^2 + 1 x 2^1 + 0 x 2^0
Ce qui donne la suite (1,1,1,0).

[ilelogique]

ça voudrait dire que concaténation de (ap/.../a1/a0) serait l'écriture de n en binaire ??

[invited979e304]

En binaire, on écrira les coefficients dans l'ordre inverse : n = (ak, ...,a2,a1,a0).

[ilelogique]

oui ça a l'air vrai
mais comment prouver ça ?

[ilelogique]

par récurence ?

si n = somme de ak.2expk pour k de 0 à p
alors n+1= 1 + somme de ak.2expk pour k de 0 à p
Si a0=0 alors n+1 s'écrit bien comme n en binaire sauf que le dernier chiffre passe de 0 à 1 et le coef a'0 de n+1 vaut 1

mais si a0=1 alors
si a1=0 on a a'0=0 et a'1= 1
si a1=1 alors si a2=0 ok et si a2=1 on passe à a3 etc

mouais, pas très clair mon truc

[invited979e304]

Quand il y a une base et des coeffs dans un problème, il y a souvent une histoire de duals cachée derrière le rideau, mais je ne saurais pas dire que faire exactement. Tu pourras surement trouver une démonstration pour la conversion décimal binaire en ligne.

[ilelogique]

je ne trouve pas cette preuve mais ça semble vrai, comment le prouver ???

[ilelogique]

je ne trouve la preuve nulle part !!

[Médiat]

Bonjour,

Par récurrence sur p, c'est plutôt simple...

[ilelogique]

sur p ?
comment ça ?

[Médiat]

Vous n'auriez pas oublié, le minimum de courtoisie nécessaire sur un forum ?

[gg0]

Bonjour Ilelogique.

"récurrence sur p" c'est assez clair, non ? Tu vérifies que si p=0 c'est vrai (combien vaut n ?). Puis tu supposes la propriété vraie pour un certain p, puis tu démontre que si n est tel que " p+1=max {i tel que 2ⁱ <n}" (*) alors " il existe a₀, a₁....a_p, a_p+1 chacun dans {0,1} tels que n=somme (ak . 2^k) pour k va de 0 à p+1"
Pour t'aider à bien saisir ce qui se passe, trouve les réponses à ces questions :
* combien vaut a_p (p=max {i tel que 2ⁱ <n})
* si p = max {i tel que 2ⁱ <n} = 3, que peut-on dire de n ?
* n étant donné, on définit p(n)=max {i tel que 2ⁱ <n}. Soit m=n-2^p(n); combien vaut p(m) ? Tu peux commencer par expérimenter avec n=7, ou n=6, ou n=8.

Cordialement.

(*) comment est n, combien vaut-il ?

[ilelogique]

Bonjour,
Si on récure sur p, il faut que ça soit pour tout n à chaque étape (p est défini selon n et p n'est pas défini si n=0, même en prenant une inégalité large dans la définition de p, ce qu'il faut d'ailleurs faire, erreur de ma part dans le post 1)
si p=0 on a n=1
si p=3 par exemple alors on a 8 <= n < 16
en gros pour tous n et p(n), on a : 2exp(p) <= n < 2exp(p+1) non ?

je suis sans doute mal réveillé mais un truc m'échappe,
en gros pour tout n on définit p=f(n) puis on a affirmé qu'une certaine propriété Q(n,p) est vraie pour tout n
or prouver par récurrence sur p demanderait d'exprimer n en fonction de p d'abord non ?
or la fonction f plus haut n'est pas surjective, pour chaque p il y a un ensemble (fini) de n.

c'est là que je me perds....

étape de récurrence, soit p=max {i tel que 2 exp i <=n} on a a0, a1....ap chacun dans {0,1} tels que n=somme (ak . 2 exp k) pour k va de 0 à p

si p+1=max {i tel que 2i <n}
montrons qu'il existe a0, a1....ap, ap+1 chacun dans {0,1} tels que n=somme (ak . 2k) pour k va de 0 à p+1 c'est ça ?

mais le n n'est pas le même alors non ???

[gg0]

Tu l'as peut-être remarqué, j'ai noté p(n) à la place de p. Car comme tu le dis, p dépend de n. Ce qui n'interdit pas de faire une récurrence sur p, puisque une fois p connu, n n'est pas quelconque. Et qu'à chaque n, il y a un seul p possible. En gros, pour un p donné il y a un ensemble Ep de n possibles pour lesquels p(n)=p.

Donc tu supposes que pour un p donné, si n est tel que p=max {i tel que 2 exp i <=n} on a a0, a1....ap chacun dans {0,1} tels que n=somme (ak . 2 exp k) pour k va de 0 à p. Puis tu considères p+1, et un n quelconque tel que p+1=max {i tel que 2 exp i <=n}. Il ne te reste plus qu'à justifier que on a a0, a1....ap chacun dans {0,1} tels que n=somme (ak . 2 exp k) pour k va de 0 à p+1.
J'ai fait ma part du travail, à toi de faire la tienne (sans recommencer tes "mais ..").

A noter que j'ai posé plusieurs questions pour t'aider à réfléchir, et que si tu regardes des valeurs particulières de n, tu verras comment ça marche. Ça on ne va pas le faire à ta place; comprendre, on ne peut pas le faire à ta place.

[ilelogique]

Bonsoir et merci,
mais...
Non je suis taquin,
Vous, tu, noteras, noterez, que mon premier post demandait la preuve de la conjecture.
Aussi je suis fort étonné, mais pas désagréablement, que personne ne parvienne ou ne veuille fournir ladite preuve, on me laisse ma part de travail, bon, ok.
C'est sûr que toi ou n'importe qui fait sa part de travail ici puisque rien n'y est obligatoire !
Je vais donc me pencher sur cette preuve, en suivant tes recommandations, et reviendrai vers tous quand, je l'espère, nous pourrons clôturer le sujet, merci.

Au demeurant, suite à tes propos, me vient une question :
lorsqu'un entier p est défini en fonction de n et qu'on veut prouver une propriété Q(n) faisant intervenir p aussi : peut-on récurer sur p dès lors que n n'est pas quelconque ??
En ce sens que tu affirmes que c'est possible du fait que n n'est pas quelconque une fois p choisi,
Mais (oups pardon) qu'entends-tu par n quelconque ???? Car ici si l'ensemble des n candidats à un p donné est certes fini, il est arbitrairement grand lorsque p croît quand même...
Existe-t-il une règle, des critères sur n, p et les liens qu'ils tissent, qui font qu'il est possible de récurer sur un p défini à partir d'un n sur une propriété portant sur n ?
Le fait que p soit unique pour chaque n suffit-il ? Si p=f(n) alors on peut prouver par récurrence sur p la propriété Q(n) ?? je vais chercher un contre-exemple...
(Mais) c'est un autre sujet j'en conviens...

Je vais bosser sur ce que tu-vous proposez demain, ou après, et reviendrai vers tous,
merci,

[gg0]

Bon,

je ne vois pas l'intérêt de rédiger à ta place une preuve de cette propriété connue. Si tu n'es pas capable de le faire toi-même, accepte l'avis des "experts", comme tu le fais dans de très nombreux domaines de la vie courante. Ta "conjecture" n'est que la possibilité d'écrire tout nombre en base 2. Tu utilises la même conjecture en base 10 depuis l'école primaire.

Ciao.

[Médiat]

Bonsoir gg0

je ne vois pas l'intérêt de rédiger à ta place une preuve de cette propriété connue.

Surtout pour une démonstration dont nous avons déjà tout dit et qui tient en 2 lignes !

[ilelogique]

Bonjour,
Accepter l'avis d'experts ???
Ah non, pas en maths, ou disons le moins possible.
Elle tient en deux lignes ? Alors pourquoi faire traîner deux pages ici ?
Et pourquoi on ne la trouve pas sur le web ?
Je vais la chercher et la trouver, rassurez-vous !
Pas dit que je la mette ici cela dit, c'est tellement évident que les modestes internautes ne la méritent pas...

Bon allé,
désolé pour le dérangement,
Je ne vous embêterai plus,
un peu surpris quand même...

Merci de votre aide

[gg0]

Voilà ce qu'on gagne a essayer d'aider les ingrats ...

"Je vais la chercher et la trouver .." Il serait temps, après tous ces messages d'aide et ce refus systématique de s'y mettre, sous divers prétextes. Quant à des preuves, il y en a da&ns des bouquins de maths et sans doute sur Internet, présentées un peu différemment, ce qui explique l'échec à les trouver : Quand on ne comprend pas bien de quoi on parle, il est difficile de trouver des références.

Mais une fois la preuve trouvée, Ilelogique, garde-la pour toi, elle n'a quasiment pas d'intérêt. Même pour un exercice, il est plus facile de faire soi-même la preuve que de comprendre celle qu'un autre a rédigé

[Médiat]

Bonjour,

Voilà ce qu'on gagne a essayer d'aider les ingrats ...

Allons soyons honnête, il y a une vraie difficulté dans cette démonstration :

 Cliquez pour afficher

Il faut savoir que

[ilelogique]

Re bonjour,
je ne vois pas en quoi je suis ingrat, et si vous le sentez comme ça je vous prie de m'excuser, je n'ai jamais eu cette intention et je vous remercie très sincèrement pour l'aide que vous avez tenté de m'apporter.
je l'ai déjà cherchée, je dis "je vais chercher" car je n'ai pas encore pris en considération votre mail d'hier, mais seulement celui-là, cette récurrence sur p, je n'ai pas que ça à faire et je veux prendre mon temps.
Bien sûr que si je mettrai la preuve ici, car je vous assure que si elle est sur le net alors elle est bien cachée.
Et je ne crois pas qu'elle tienne en deux lignes (ou alors très longues...)

Merci à tous pour votre aide.

[ilelogique]

je suis désolé de vous sembler idiot mais je ne comprends pas ce qu'a mis Mediat.

[gg0]

Pour gagner du temps,

tu peux lire des documents sur "calcul binaire", "écriture en base 2", "codage binaire", ...

[ilelogique]

Bonjour,
Au fond la preuve c'est tout simplement l'algorithme d'Euclide, et ça on trouve sur le net.
merci,