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 - 05-09-2016 14:20:06

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

Décimaux vs binairre

Bonjour,

Existe il un couple [latex](i,j)\in\mathbb{N}^*[/latex] tel que le nombre de décimales de [latex]20^i[/latex] (écrit en base 10) soit égal au nombre de bits de [latex]20^j[/latex](écrit en base 2) ?

exemple:
les premières puissances de 20 sont:
20 ->2 décimales
400 ->3 décimales
8000 -> 4 décimales
160000 -> 6 décimales
3200000 -> 7 décimales
64000000 ->8 décimales

20 en binaire s'écrit 10100 -> 5 bits
aucune puissance de 20 ne contient 5 décimales...

Pour les plus courageux, on pourra chercher à démontrer que pour tout entier k, il existe une unique puissance de 2 qui s'écrit avec k chiffres (en décimal ou en binaire)

Bon courage smile



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 05-09-2016 19:38:14

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

DDécimaux vs binaire

Bonsoir Caduk,

Il me semble qu'on ne peut pas.

Soient les nombres 20^n et 20^m ayant le même nombre k de décimales.

On écrit les encadrements:
10^(k-1) < 20 ^n < 10 ^ k
2 ^ (k-1) < 20 ^m < 2 ^ k
Notons l'encadrement strict, une puissance de 20 n'est ni une puissance de 2, ni une puissance de 10.

Le produit des 2 nombres est encadré par le produit des encadrants :

20 ^(k-1) < 20 ^(n+m) < 20 ^k

Cette inégalité stricte est absurde !

 #3 - 05-09-2016 19:43:20

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

décilaux vs binaire

nodgim Très bien! smile

 #4 - 05-09-2016 19:57:11

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

Déimaux vs binaire

Ce qui est étonnant, sauf erreur, c'est que les nombres manquants dans la liste des nombres de chiffres des puissances de 20 en base 10 correspondent exactement aux nb de chiffres des puissances de 20 écrites en base 2 !

 #5 - 05-09-2016 21:33:41

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

déximaux vs binaire

nodgim C'est exact, et c'est d'ailleurs là que ça devient intéressant big_smile
J'aurais dû l'écrire plus explicitement dans l'énigme.
Spoiler : [Afficher le message] On pourra chercher le nombre de puissances de 20 inférieures à [latex]10^N[/latex] et celles inférieures à [latex]2^N[/latex]et encadrer le nombre de possibilités d'écrire une puissance de 20 en binaire ou en décimal avec moins de N chiffres

 #6 - 06-09-2016 19:31:24

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 304

Déciimaux vs binaire

Ce problème est surprenant. Il n'est pas si dur d'intuiter la solution (un tel couple n'existe pas), mais le rédiger clairement nécessite un certain travail. J'essaie donc.

Notons C_b(n) le nombre de chiffres en n en base b. Par exemple, si n=1024, C_10(n)=4 et C_2(n)=11.

On commence par un lemme : pour tout n>=1, C_10(5^n)+C_10(2^n) = n+1. Il se démontre aisément en considérant l'écriture scientifique de 5^n et de 2^n.

On peut ensuite observer que comme 10<20<100, la suite (C_10(20^n)) augmente de 1 ou de 2 à chaque terme : ses premiers termes sont 2;3;4 ; 6;7;8 ; 10;11;12 ; 14;15;16;17 ; 19... Pour résoudre le problème, il suffit de montrer que les termes de (C_2(20^n)), qui commence par 5;9;13;18... s'insèrent dans les "trous" laissés par (C_10(20^n)).

On considère donc un terme quelconque de cette dernière suite : soit n>=1, on pose C_2(20^n)=k.
Alors C_2(5^n)=k-2n
donc 2^{k-2n-1} <= 5^n < 2^{k-2n}
et en multipliant par 5^{k-2n}, il vient 5.10^{k-2n-1} <= 5^{k-n} < 10^{k-2n}
donc C_10(5^{k-n-1}) = C_10(5^{k-n}) = k-2n.

Enfin, C_10(20^{k-n-1}) = (k-n-1) + C_10(2^{k-n-1}) = (k-n-1) + (k-n-1)+1-C_10(5^{k-n-1}) (par le lemme) = (k-n-1) + (k-n-1)+1-(k-2n) = k-1
et de même, C_10(20^{k-n}) = k+1, cqfd : la valeur k de la deuxième suite s'est insérée entre les valeurs k-1 et k+1 de la première.

NB : on peut même réciproquement démontrer que tous les trous de la première suite sont comblés par des termes de la deuxième, i.e. que les deux suites recouvrent l'ensemble des entiers >=2.

 #7 - 06-09-2016 20:24:59

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

décimaux vq binaire

Ebichu Pas mal, un peu laborieux mais ça marche (quoique ma solution soit à peu près aussi laborieuse... roll)
Si on ne veut que montrer que les nombres de chiffres sont tous différents, nodgim a trouvé une solution très efficace.

Si tu souhaites t'attaquer à la généralisation, essaye de démontrer que pour tout entier k, il existe un unique [latex](ab)^N[/latex] de longueur k  en base a ou en base b à la condition qu'il n'existe pas p et q tels que [latex]a^p = b^q[/latex] (a,b,p,q entiers)

 #8 - 08-09-2016 08:42:00

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

décimauw vs binaire

J'ai une autre solution arithmétique bien plus jolie et plus complète.
Je la rédigerais au besoin, si elle est différente encore de ce qui aura été trouvé.

 #9 - 08-09-2016 14:33:32

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

décimayx vs binaire

Voilà une proposition de résolution:
Le nombre de puissances de 20 inférieures à [latex]10^N[/latex] est [latex]\lfloor log_{20}(10^N)\rfloor+1[/latex]
idem pour 2^N, il y en a [latex]\lfloor log_{20}(2^N)+1\rfloor[/latex]
Le nombre de possibilités d'écrire une puissance de 20 en binaire ou en décimal avec moins de N chiffres est donc [latex]n(N) = \lfloor log_{20}(10^N)\rfloor + \lfloor log_{20}(2^N)\rfloor+2[/latex]
On a alors [latex]log_{20}(10^N) -1 + log_{20}(2^N) -1 +2 < n(N) < log_{20}(10^N) + log_{20}(2^N)+2 \iff N< n(N) < N+2 \iff n = N+1[/latex] (inégalités strictes car [latex]log_{20}(10^N)[/latex] est irrationnel
On en déduit que le  nombre de possibilités d'écrire une puissance de 20 en binaire ou en décimal avec  N chiffres est n(N) - n(N-1) = 1.
Donc cette écriture existe et est unique!

Une autre façon de démontrer le problème est:
Le nombre de chiffres de [latex]20^n[/latex] est [latex]\lfloor log_{10}(20^n) \rfloor +1[/latex] en décimal et [latex]\lfloor log_{2}(20^n) \rfloor +1[/latex] en binaire.
D'après le théorème de Beatty, ces deux suites forment une partition de N (irrationalité et somme des inverses égale à 1 OK)
La démonstration de ce théorème étonnant est finalement la même que ma méthode ci dessus.

nodgim, je serai intéressé de voir ta réponse smile

 #10 - 08-09-2016 17:06:11

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

DDécimaux vs binaire

C'est également par le théorème de Beatty que je suis arrivé à une preuve   plus générale. Tout en ignorant encore ce matin l'existence de ce théorème...

Je vais rédiger quelque chose là dessus, ma démarche est un peu différente de la tienne.

 #11 - 08-09-2016 18:18:27

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

Déimaux vs binaire

Le problème plus général revient à savoir si pour un entier k donné , il existe n tel que (ab) ^ n comporte k chiffres, soit en écriture base a, soit en écriture base b.

Pour cela travaillons en logarithmes:
- Les log des puissances de a, c'est à dire les multiples de a
- Les log des puissances de b, c'est à dire les multiples de b
- Les log des puissances de ab,  c'est à dire les multiples de (a+b)

Et donc la question est de savoir si la partie entière de n(a+b) / a ou n(a+b) / b est unique, d'une part, et si pour tout entier k on trouve un unique multiple de (a+b)/a ou (a+b)/b tel que ce multiple est k < n(a+b)/a < k+1 ou (exclusif) k < m (a+b)/b < k+1, d'autre part. Remarquons que la seconde contrainte englobe de fait la 1ère.

Si on pose x = b/a et b > a, alors on a affaire aux multiples de (1+x) et (1+1/x), avec x > 1 et irrationnel.

Pour un entier k donné, on n'a pas une infinité de choix pour ces multiples :
- 1+x ou
- 2+2x ou
...ou
-[k/2] + [k/2]x ou

- k + k/x ou
-(k-1) +  (k-1)/x ou
...ou
-[(k+1)/2] + [(k+1)/2]/x

Or, chacun de ces choix correspond à une valeur de x dans un intervalle, et tous ces intervalles sont disjoints mais sans trous.
- k + k / x si  k < x
- 1 + x si (k-1) < x < k
- (k-1) + (k-1) / x si (k-1)/2 < x < k-1.
etc....

Les différents jalons entre les intervalles, du plus grand au plus petit, sont :
k/1, (k-1)/1, (k-1)/2, (k-1)/3, (k-2)/3, (k-2)/4, (k-3)/4, (k-3)/5,....1
les intervalles étant occupés alternativement par 1 multiple de (1+ x) et  1 multiple de (1+1/x).

Pour un x donné et un k donné, on a donc bien une solution unique.

CQFD

 #12 - 08-09-2016 18:39:25

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 69

décomaux vs binaire

Pas mal, c'est en effet différent, par contre j'ai l'impression que tu es passé de a et b bases à a et b logarithmes...
J'avais abordé ce problème dans ma réponse à Ebichu, et il se démontre exactement de la même manière avec ma méthode. A noter que la condition que j'avais noté est équivalente à celle que le quotient des logarithmes soit irrationnel.

 

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

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