Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 12-10-2011 11:50:53
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Comment fabriquer n'importe quel entier non nul ?
Hello tutti !
Ce petit sujet a pour unique objectif de mettre le python de totomn en échec* !
Soient l'entier naturel [tex]n= 4[/tex] et les trois règles informatiques suivantes :
1 - [tex]n = \frac{n}{2}[/tex] ;
2 - [tex]n=10\times n[/tex] ;
3 - [tex]n = 10\times n +4[/tex].
Une étape consiste à choisir l'une des trois règles, à l'appliquer, puis à recommencer avec le nombre obtenu.
On peut répéter le processus ad infinitum.
Montrer que cet algorithme permet de générer n'importe quel nombre entier.
* en fait, montrer la limite d'un computer pour une démonstration formelle.
Dernière modification par freddy (12-10-2011 11:53:36)
Hors ligne
#3 12-10-2011 18:03:18
- freddy
- Membre chevronné
- Lieu : Paris
- Inscription : 27-03-2009
- Messages : 7 457
Re : Comment fabriquer n'importe quel entier non nul ?
Salut Freddy.
deux petites questions.
a) 1 , 2 et 3 sont-ils dans les formules ?
b) n , rentre-t-il dans une formule ?
Salut JPP,
on retrouve 1, 2 et 3 à partir du germe n=4 et de l'application répété et ordonnée des 3 règles.
Hors ligne
#6 13-10-2011 13:34:00
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Comment fabriquer n'importe quel entier non nul ?
Bonjour,
@ freddy : Pourquoi cette volonté inutile : "mettre le python de totomm en échec ! " ?
Python n'est qu'un des langages qui permettent d'exécuter un algorithme sur un "computer" (ordinateur). Et s'il fallait un algorithme pour votre problème, je ne choisirais pas celui que vous proposez dont on ne sait pas s'il se terminerait pour tout N entier !
Je définirais plutôt un algorithme de récurrence partant de N pour aboutir à 4 et utilisant les 3 règles :
N := 2N N := N / 10 N := (N-4) / 10 ( := étant le symbole de l'assignation)
On peut démontrer que ces règles conduisent à un entier plus petit (ou multiple d'un plus petit) en un nombre fini d'itérations, et que les premiers entiers s'obtiennent facilement.
Je vous laisse le plaisir de publier une "démonstration formelle"…
Cordialement
Dernière modification par totomm (13-10-2011 13:39:57)
Hors ligne
#7 15-10-2011 17:29:34
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Comment fabriquer n'importe quel entier non nul ?
Bonsoir à tous et en particulier à freddy
Python vous fait dire :
il faut 28 itérations pour fabriquer N=573 (C'est le maximum d'itérations nécessaires pour les nombres N entre 1 et 1000)
il faut 50 itérations pour fabriquer N=8749 (C'est le maximum d'itérations nécessaires pour les nombres N entre 1 et 10000)
Cordialement
Hors ligne
#9 03-01-2012 20:28:59
- jpp
- Membre
- Inscription : 31-12-2010
- Messages : 1 170
Re : Comment fabriquer n'importe quel entier non nul ?
salut.
avec la règle 1 , je peux fabriquer 2 puis 1 . par conséquent avec la règle 2 , tous les nombres de la forme [tex]10^Q[/tex] &[tex]2\times10^Q[/tex] et avec les règles 2 & 3 à la fin, tous les nombres de la forme[tex]10^Q + 4[/tex] et [tex]2\times10^Q + 4[/tex] .
pour les autres qui sont de la forme générale 10Q+R , il y en a qui s'avèrent assez chaud à calculer
par exemple 29 en partant de 4 avec dans l'ordre les règles 1,1,3,3,1,1,1,3,1,1,3,1,1,1&1.
celà signifierait qu'à partir de 29 je peux ainsi continuer en appliquant une des 3 règles. je peux générer
des nombres comme , 290 , 294 ,145,1450,1454, 2900 , 2904 , 2944 etc...
et ça voudrait surtout dire que si on me soutenait que 2944 était impossible à fabriquer , alors294 par exemple le serait aussi. Or il est généré à partir de 29avec la règle 3 ; donc je peux infirmer car 29 est constructible
je crois donc qu'il faut trouver le nombre n = 10Q+R qui déroge à la règle ou alors prouver qu'il n'en est point.
en imaginant que ce nombre ou un de ces nombres existe, il faut trouver le plus petit. par exemple si le plus petit
est de la forme N = 10Q il doit etre généré ou par 2 x 10Q avec la règle 1 ou par Qavec la règle 2
or Q < 10Q et Q est donc impossible à générer donc N = 10Q ne peut pas etre ce nombre.
De la meme manière en raisonnant avec N = 10Q + 4 impossible à générer, en appliquant les règles 3 & 2
10Q & Q sont impossibles à générer . or Q < 10Q < 10Q + 4 . Donc 10Q + 4 n'est pas ce nombre.
maintenant si ce nombre est de la forme N = 10Q + 1 , avec la règle 1 il est généré avec 20Q +2 qui est lui meme généré par 40Q + 4 avec toujours la règle 1 , lequel est généré par 4Q en utilisant la règle 3.
mais comme 4Q < 10Q + 1 , alors ce nombre impossible à fabriquer ne peut pas etre de la forme10Q + 1
Si le nombre est de la formeN = 10Q + 2? il peut etre généré parN = 20Q + 4 avec la règle 1, ce dernier par N= 2Q avec la règle 3 . mais comme 2Q < 10Q + 2 , alors N = 10Q + 2 n'est pas non plus ce nombre.
Si N est de la forme N= 10Q + 3 , on ne peut pas générer N = 20Q + 6 , N = 40Q + 12 , N = 80Q + 24 avec la règle 1 , ainsi que N = 8Q + 2 avec la règle 3. Mais comme 8Q + 2 < 10Q + 3, alors N = 10Q + 3 n'est pas non plus ce nombre.
Si N est de la forme N = 10Q + 5 ça signifierait que la génération de N = 20Q +10 avec la règle 1 , puis celle de N =2Q + 1 avec la règle 2 sont impossibles . Or 2Q + 1 < 10Q +5 . Le plus petit nombre cherché n'est pas non plus dans cette famille.
Si N est de la forme N = 10Q + 6 ça signifierait aussi que les générations de N = 20Q + 12 , de N = 40Q + 24 avec la règle 1 , et enfin N = 4Q + 2 avec la règle 3 , sont impossibles . Or 4Q + 2 < 10Q + 6 . alors le plus petit nombre impossible n'est pas non plus dans cette catégorie.
Si N est de la forme N = 10Q + 7 signifierait que N = 20Q + 14 , avec la règle 1 , N = 2Q + 1 avec
la règle 3 sont impossibles à générer ; or 2Q + 1 < 10Q + 7 ---> le plus petit nombre impossible à générer n'est pas non plus dans cette catégorie.
Si N est de la forme N = 10Q + 8 signifierait que N = 20Q + 16 ; N = 40Q + 32 ; N = 80Q + 64 avec la règle 1 ; N = 8Q + 6 avec la règle 3 sont impossibles à générer ; or 8Q + 6 < 10Q + 8 --> Le plus petit nombre impossible à générer n'est pas non plus dans cette catégorie.
Si N est de la forme N = 10Q + 9 , je n'ai pas trouvé N < 10Q + 9 . J'ai du créer plusieurs familles de nombres me permettant de formuler tous les nombres se terminant par 9. Et malgré celà je n'ai pas pu confirmer
l'inexistance d'un nombre de la forme 50N + 49 . et pourtant je peux générer 99
Pour les 5 familles , j'ai considéré N = 50Q + 9 ; 50Q + 19 ; 50Q + 29 ; 50Q + 39 & 50Q + 49
a) N = 50Q + 9 --> 100Q + 18 --> 200Q + 36 --> 400Q + 72 --> 800Q + 144 --> 80Q + 14 --> 8Q + 1 alors 8Q + 1 < 50Q + 9 --> le nombre n'appartient pas à cette famille.
b) N = 50Q + 19 --> 100Q + 38 --> 200Q + 76 --> 400Q + 152 --> 800Q + 304 --> 80Q + 30 --> 8Q + 3 alors 8Q + 3 < 50Q + 19--> le nombre n'appartient pas à cette famille.
c) N = 50Q + 29 --> 100Q + 58 --> 200Q + 116 --> 400Q + 232 --> 800Q + 464 --> 80Q + 46 --> 160Q + 92
160Q + 92 --> 320Q + 184 --> 32Q + 18 < 50Q + 29 ; ce nombre n'appartient pas à cette famille.
d) N = 50Q + 39 --> 100Q + 78 --> 200Q + 156 --> 400Q + 312 --> 800Q + 624 --> 80Q + 62
80Q + 62 --> 160Q + 124 --> 16Q + 12 < 50Q + 39 ; le nombre n'appartient pas à cette famille.
e) avec N = 50Q + 49 avec Q = 1 je sais que 99 peut etre généré car :
50Q + 49 --> 100Q + 98 --> 200Q + 196 --> 400Q + 392 --> 800Q + 784 --> 1600Q + 1568
--> 3200Q + 3136 --> 6400Q + 6272 --> 12800Q + 12544 --> 1280Q + 1254 --> 128Q + 125 --> 256Q + 250
--> 512Q + 500 --> 1024Q + 1000 avec Q=1 --> 1020Q + 1004 --> 102Q + 100 --> 204Q + 200
--> 20Q + 20 --> 2Q + 2 = 4 ---> 99 est un nombre que l'on peut générer.
pour N = 50Q + 49 je reste bloqué et parce que je me suis arrèté ici:
50Q + 49 --> 100Q + 98 --> 200Q + 196 --> 400Q + 392 --> 800Q + 784 --> 80Q + 78 > 50Q + 49
J'ai bien peur qu'il faille trouver une autre famille de nombres . 49 & 99 , qui sont dans la famille 50Q + 49 , avec Q = 0 & Q = 1 je les ai trouvés à la calculette. mais il reste à démontrer que 149 , 199 , 249 , 299 ...etc... peuvent etre générés. donc mon boulot n'est pas terminé . Si quelqu'un a une idée ...
à plus.
Dernière modification par jpp (08-01-2012 19:39:45)
Hors ligne
#10 11-01-2012 12:36:36
- jpp
- Membre
- Inscription : 31-12-2010
- Messages : 1 170
Re : Comment fabriquer n'importe quel entier non nul ?
Salut à tous.
je bloquais sur les nombres de la forme50Q + 49
En fait , comme tous les nombres de la forme 10Q + 8 peuvent etre générer ( voir #9 ) , j'en conclus que les nombres de la forme générale 10Q + 9 sont automatiquement générés par les nombres N = 20Q + 18 après application de la règle 1
par exemple 49 , 99 , 149 ... sont respectivement générés par les nombres 98 , 198 , 298 ... via la règle (1) n=n/2
en conclusion , tous les nombres entiers non nuls peuvent etre générés à partir de ces 3 règles , en partant de 4.
à plus.
Hors ligne
#11 16-01-2012 20:23:17
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
Re : Comment fabriquer n'importe quel entier non nul ?
Hi,
Bien joué jpp!
Personnellement, j'avais chercher à faire simple en me demandant si on ne pouvait pas réduire le problème en montrant que tous entier peut s'écrire comme combinaison linéaire des composition des 3 règles, puis j'avais arrêter, mais là je viens de retomber sur mon papier, alors autant partager si quelqu’un saura trouver!
Une combinaison de compositions des 3 règles A b et C(ce qui n'est pas commutatif) peut s’écrire
[tex]{k}_{1}A\,.\,{k}_{2}B\,.\,{k}_{3}C[/tex] t donne l'entier formé n. Ou les ki sont le nombre de fois que l'on répéte la règle.
les combinaisons des 3 règles sont ABC, CBA, BCA, .. etc (il y'en a 6) mais heureusement, on tombe sur des équivalences(j'en est trouvé deux, je ne sait pas si il y'en a plus), ce qui permet d'écrire, [tex]{k}_{1}A\,.\,{k}_{2}B\,.\,{k}_{3}C\,=\,{k}_{2}B\,.\,{K}_{1}A\,.\,{k}_{3}C[/tex]
et aussi
[tex]{k}_{1}C\,.\,{k}_{2}B\,.\,{k}_{3}A\,=\,{k}_{1}C\,.\,{K}_{3}A\,.\,{k}_{2}B[/tex]
Si je ne me suis pas trompé car je n'ais plus le papier qui traite de ça..
En mettant ça sous formule, on obtient 4 cas:
[tex]{k}_{1}A\,.\,{k}_{2}B\,.\,{k}_{3}C\,\,=\,\,{\frac{1{0}^{{k}_{3}+{k}_{2}}.4}{{2}^{{k}_{1}}}}_{}-\,\left(\frac{4}{9}\right)\left(1-1{0}^{{k}_{3}}\right)[/tex]
[tex]{k}_{1}B\,.\,{k}_{2}C\,.\,{k}_{3}A\,=\,[/tex][tex]\frac{1{0}^{{k}_{2}+{k}_{1}}.4\,-\,\left(\frac{4}{9}\right)\left(1-1{0}^{{k}_{2}}\right)}{{2}^{{k}_{3}}}[/tex]
[tex]{k}_{1}C\,.\,{k}_{2}B\,.\,{k}_{3}A\,=\,[/tex][tex]\frac{1{0}^{{k}_{2}}}{{2}^{{k}_{3}}}\left(1{0}^{{k}_{1}}.4\,-\,\left(\frac{4}{9}\right)\left(1-1{0}^{{k}_{1}}\right)\right)[/tex]
et
[tex]{k}_{1}A\,.\,{k}_{2}C\,.\,{k}_{3}B[/tex][tex]=1{0}^{{k}_{3}}\left(\frac{1{0}^{{k}_{2}}.4}{{2}^{{k}_{1}}}\,-\,\left(\frac{4}{9}\right)\left(1-1{0}^{{k}_{2}}\right)\right)[/tex]
Dés lors, en montrant que pour tous les entiers n il existe 3 nombres k1 k2 et k3 tels que remplacés dans une de ces formules, la formule donne le nombre, on résous le problème.
Dernière modification par Golgup (16-01-2012 20:54:55)
Hors ligne