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
[+]

 #26 - 09-02-2016 19:32:33

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

Entiers sans zéo

@masab: c'est OK, mais c'est loin de prendre en compte tous les cas.

#0 Pub

 #27 - 09-02-2016 20:05:47

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

entiers sand zéro

Là je suis d'accord Gwen bravo !
C'est une méthode assez différente de la mienne. Ton procédé est assez alambiqué, mais très efficace à l'arrivée.

 #28 - 09-02-2016 20:30:43

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,996E+3

Entiesr sans zéro

Pas facile d'expliquer des trucs clairement parfois mad surtout pour moi lol
En fait, "par groupes de 9 (x9 x9 x9 ...)" je n'utilise que le critère de divisibilité par 9 grâce à la factorisation à chaque étape.

Un exemple partiel était plus parlant finalement .

 #29 - 09-02-2016 21:07:38

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

entiers sans zéeo

C'est effectivement loin de prendre en compte tous les cas !
Mais ça donne une formule donnant une infinité d'entiers divisibles par la somme de leurs chiffres.

 #30 - 10-02-2016 08:19:17

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

entiets sans zéro

@masab: tu as raison, mais si on suppose que si pour tout k il y a une solution,
alors la proportion des solutions que tu as prouvées est assez maigre dans N.

@Gwen: oui, c'était bien clair avec l'exemple. Il aurait fallu que tu indiques clairement les décalages à chaque étape dans ton explication. Je l'ai refait et c'est devenu évident.
Sinon, je viens de trouver un bug dans ma solution en la rédigeant, ce qui fait que je n'ai que 96% des nombres, et non 100 % comme toi.

 #31 - 12-02-2016 22:54:13

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

Entiers sans zér

On va donner une solution pour 100% des valeurs de k.

On note
[TeX]\displaystyle \quad  f(k) = \frac{10^k-1}{9}\,.[/TeX]
f(k) est un entier à k chiffres tous égaux à 1.

Dans un message précédent on a prouvé que [latex]f(3^r)[/latex] est divisible par [latex]3^r[/latex].

Soit [latex]k\geq 1[/latex] un entier.

Il existe [latex]r\geq 0[/latex] entier tel que [latex]9^r<k\leq 9^{r+1}[/latex].

Il existe des entiers [latex]q ,u[/latex] tels que [latex]k = 9^r\,q+u[/latex],  [latex]q\geq 0[/latex], [latex]1\leq u\leq 9^r[/latex].
C'est une forme de la division euclidienne.
On a alors [latex]1\leq q<9[/latex].

On considère l'entier sans zéro n défini par
[TeX]n = f(k) + (9-q)\,f(9^r)-f(u)[/TeX]
Alors [latex]n[/latex] possède [latex]k[/latex] chiffres et la somme des chiffres de [latex]n[/latex] est égale à [latex]s(n)=9^{r+1}[/latex].
De plus [latex]n[/latex] est divisible par la somme de ses chiffres.

Preuve
On a [latex]10^{9^r} = 1 + 9\times f(9^r)[/latex] donc [latex]10^{9^r}[/latex] est congru à [latex]1[/latex] modulo [latex]9\times f(9^r)[/latex].
On divise [latex]n[/latex] en blocs de [latex]9^r[/latex] chiffres à partir de la droite, on fait la somme de ces blocs.
Cette somme est égale à [latex]9\times f(9^r)[/latex] ; par suite [latex]n[/latex] est congru à [latex]0[/latex] modulo [latex]9\times f(9^r)[/latex].
Autrement dit n est divisible par [latex]9\times f(9^r)[/latex].
Or on a vu dans un message précédent que [latex]f(9^r)[/latex] est divisible par [latex]9^r[/latex].
Donc [latex]n[/latex] est divisible par [latex]9^{r+1} = s(n)[/latex].
cqfd

On a explicité ci-dessous les valeurs de n pour 1<=k<=90 :

Code:

k=1  r=0  q=1  u=0  n=9
k=2  r=0  q=2  u=0  n=18
k=3  r=0  q=3  u=0  n=117
k=4  r=0  q=4  u=0  n=1116
k=5  r=0  q=5  u=0  n=11115
k=6  r=0  q=6  u=0  n=111114
k=7  r=0  q=7  u=0  n=1111113
k=8  r=0  q=8  u=0  n=11111112
k=9  r=0  q=9  u=0  n=111111111
k=10  r=1  q=1  u=1  n=1999999998
k=11  r=1  q=1  u=2  n=11999999988
k=12  r=1  q=1  u=3  n=111999999888
k=13  r=1  q=1  u=4  n=1111999998888
k=14  r=1  q=1  u=5  n=11111999988888
k=15  r=1  q=1  u=6  n=111111999888888
k=16  r=1  q=1  u=7  n=1111111998888888
k=17  r=1  q=1  u=8  n=11111111988888888
k=18  r=1  q=2  u=0  n=111111111888888888
k=19  r=1  q=2  u=1  n=1111111111888888887
k=20  r=1  q=2  u=2  n=11111111111888888877
k=21  r=1  q=2  u=3  n=111111111111888888777
k=22  r=1  q=2  u=4  n=1111111111111888887777
k=23  r=1  q=2  u=5  n=11111111111111888877777
k=24  r=1  q=2  u=6  n=111111111111111888777777
k=25  r=1  q=2  u=7  n=1111111111111111887777777
k=26  r=1  q=2  u=8  n=11111111111111111877777777
k=27  r=1  q=3  u=0  n=111111111111111111777777777
k=28  r=1  q=3  u=1  n=1111111111111111111777777776
k=29  r=1  q=3  u=2  n=11111111111111111111777777766
k=30  r=1  q=3  u=3  n=111111111111111111111777777666
k=31  r=1  q=3  u=4  n=1111111111111111111111777776666
k=32  r=1  q=3  u=5  n=11111111111111111111111777766666
k=33  r=1  q=3  u=6  n=111111111111111111111111777666666
k=34  r=1  q=3  u=7  n=1111111111111111111111111776666666
k=35  r=1  q=3  u=8  n=11111111111111111111111111766666666
k=36  r=1  q=4  u=0  n=111111111111111111111111111666666666
k=37  r=1  q=4  u=1  n=1111111111111111111111111111666666665
k=38  r=1  q=4  u=2  n=11111111111111111111111111111666666655
k=39  r=1  q=4  u=3  n=111111111111111111111111111111666666555
k=40  r=1  q=4  u=4  n=1111111111111111111111111111111666665555
k=41  r=1  q=4  u=5  n=11111111111111111111111111111111666655555
k=42  r=1  q=4  u=6  n=111111111111111111111111111111111666555555
k=43  r=1  q=4  u=7  n=1111111111111111111111111111111111665555555
k=44  r=1  q=4  u=8  n=11111111111111111111111111111111111655555555
k=45  r=1  q=5  u=0  n=111111111111111111111111111111111111555555555
k=46  r=1  q=5  u=1  n=1111111111111111111111111111111111111555555554
k=47  r=1  q=5  u=2  n=11111111111111111111111111111111111111555555544
k=48  r=1  q=5  u=3  n=111111111111111111111111111111111111111555555444
k=49  r=1  q=5  u=4  n=1111111111111111111111111111111111111111555554444
k=50  r=1  q=5  u=5  n=11111111111111111111111111111111111111111555544444
k=51  r=1  q=5  u=6  n=111111111111111111111111111111111111111111555444444
k=52  r=1  q=5  u=7  n=1111111111111111111111111111111111111111111554444444
k=53  r=1  q=5  u=8  n=11111111111111111111111111111111111111111111544444444
k=54  r=1  q=6  u=0  n=111111111111111111111111111111111111111111111444444444
k=55  r=1  q=6  u=1  n=1111111111111111111111111111111111111111111111444444443
k=56  r=1  q=6  u=2  n=11111111111111111111111111111111111111111111111444444433
k=57  r=1  q=6  u=3  n=111111111111111111111111111111111111111111111111444444333
k=58  r=1  q=6  u=4  n=1111111111111111111111111111111111111111111111111444443333
k=59  r=1  q=6  u=5  n=11111111111111111111111111111111111111111111111111444433333
k=60  r=1  q=6  u=6  n=111111111111111111111111111111111111111111111111111444333333
k=61  r=1  q=6  u=7  n=1111111111111111111111111111111111111111111111111111443333333
k=62  r=1  q=6  u=8  n=11111111111111111111111111111111111111111111111111111433333333
k=63  r=1  q=7  u=0  n=111111111111111111111111111111111111111111111111111111333333333
k=64  r=1  q=7  u=1  n=1111111111111111111111111111111111111111111111111111111333333332
k=65  r=1  q=7  u=2  n=11111111111111111111111111111111111111111111111111111111333333322
k=66  r=1  q=7  u=3  n=111111111111111111111111111111111111111111111111111111111333333222
k=67  r=1  q=7  u=4  n=1111111111111111111111111111111111111111111111111111111111333332222
k=68  r=1  q=7  u=5  n=11111111111111111111111111111111111111111111111111111111111333322222
k=69  r=1  q=7  u=6  n=111111111111111111111111111111111111111111111111111111111111333222222
k=70  r=1  q=7  u=7  n=1111111111111111111111111111111111111111111111111111111111111332222222
k=71  r=1  q=7  u=8  n=11111111111111111111111111111111111111111111111111111111111111322222222
k=72  r=1  q=8  u=0  n=111111111111111111111111111111111111111111111111111111111111111222222222
k=73  r=1  q=8  u=1  n=1111111111111111111111111111111111111111111111111111111111111111222222221
k=74  r=1  q=8  u=2  n=11111111111111111111111111111111111111111111111111111111111111111222222211
k=75  r=1  q=8  u=3  n=111111111111111111111111111111111111111111111111111111111111111111222222111
k=76  r=1  q=8  u=4  n=1111111111111111111111111111111111111111111111111111111111111111111222221111
k=77  r=1  q=8  u=5  n=11111111111111111111111111111111111111111111111111111111111111111111222211111
k=78  r=1  q=8  u=6  n=111111111111111111111111111111111111111111111111111111111111111111111222111111
k=79  r=1  q=8  u=7  n=1111111111111111111111111111111111111111111111111111111111111111111111221111111
k=80  r=1  q=8  u=8  n=11111111111111111111111111111111111111111111111111111111111111111111111211111111
k=81  r=1  q=9  u=0  n=111111111111111111111111111111111111111111111111111111111111111111111111111111111
k=82  r=2  q=1  u=1  n=1999999999999999999999999999999999999999999999999999999999999999999999999999999998
k=83  r=2  q=1  u=2  n=11999999999999999999999999999999999999999999999999999999999999999999999999999999988
k=84  r=2  q=1  u=3  n=111999999999999999999999999999999999999999999999999999999999999999999999999999999888
k=85  r=2  q=1  u=4  n=1111999999999999999999999999999999999999999999999999999999999999999999999999999998888
k=86  r=2  q=1  u=5  n=11111999999999999999999999999999999999999999999999999999999999999999999999999999988888
k=87  r=2  q=1  u=6  n=111111999999999999999999999999999999999999999999999999999999999999999999999999999888888
k=88  r=2  q=1  u=7  n=1111111999999999999999999999999999999999999999999999999999999999999999999999999998888888
k=89  r=2  q=1  u=8  n=11111111999999999999999999999999999999999999999999999999999999999999999999999999988888888
k=90  r=2  q=1  u=9  n=111111111999999999999999999999999999999999999999999999999999999999999999999999999888888888

 #32 - 12-02-2016 23:42:18

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 382

Entiers sans zééro

J'ai une piste.

L'idée est de constituer une suite d'ensemble de nombres "En" tels que les éléments de En vérifient chacun :

- la somme de ses chiffres est égale à 9*2^n
- Le nombre composé de ses n derniers chiffres est le plus petit nombre de n chiffres divisible par 2^n qui ne contient pas de 0 que l'on note Kn

La somme des chiffres restant à placer est donc 9*2^n-Kn soit autant de 1 que l'on peut placer devant le postfix de divisibilité par 2^n

Il y a différentes vérifications à faire. La méthode permet elle d'aboutir ?

 #33 - 13-02-2016 07:19:57

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

entiers sabs zéro

@Portugal: je ne crois pas que tu puisses aboutir, pour les raisons que j'ai déja expliquées plus haut.

@masab: q<=0 ?

 #34 - 13-02-2016 10:54:33

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

Entiers ssans zéro

@ fix33: je ne t'ai pas répondu car, même si l'idée semble bonne, tu n'apportes pas la moindre preuve de ce que tu avances. Il faut creuser un peu.

 #35 - 13-02-2016 11:09:36

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

Entiers sans éro

@masab: u est il le reste de la division de k par 9^r ?

 #36 - 13-02-2016 13:56:45

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 971

rntiers sans zéro

Ce n'est pas tout à fait le reste habituel ; c'est le reste au sens
[TeX]\ a = b\,q+r\quad \mathrm{avec}\quad  1\leq r\leq b[/TeX]
Habituellement on impose   [latex]\ \quad 0\leq r < b[/latex]

 #37 - 13-02-2016 17:00:36

MrHall
Amateur de Prise2Tete
Enigmes résolues : 0
Messages : 2

Enteirs sans zéro

Soit k le nombre de chiffres dans tout nombre recherché. Soit X l'ensemble des nombres entiers naturels qui ne possèdent aucun zéro. Soit P la proportion de nombres appartenant à X et divisible par la somme de leurs propres chiffres, par rapport à la totalité des nombres appartenant à X.

J'ai établi empiriquement que P(k) est une décroissance exponentielle, proche de P(k) = 4,10935 * e^(-1,42233). La proportion P de nombres divisibles par la somme de leurs chiffres diminue par rapport au nombre k de leur chiffres, P n'atteint jamais zéro.

Ensuite, soit Q la quantité de nombres entiers n'ayant aucun chiffre zéro et divisibles par la somme de leurs chiffres. Alors Q(k) = 0,173298 * e^(2,03862). Les nombres qui ne comportent ni chiffre zéro et qui sont divisibles par la somme de leurs chiffres deviennent de plus en plus nombreux (croissance exponentielle) au fur et à mesure que k augmente. Par conséquent, dans l'ensemble des nombres naturels, il existe une infinité de nombres n'ayant ni zéros dans leurs digits, et étant également divisibles par la somme de leurs chiffres. Testé empiriquement entre le nombre 1 et le nombre 999999999.
Dans l'intervalle [1 ; 999999999], il existe exactement 19 086 485 nombres n'ayant aucun zéro dans leurs digits, et qui sont divisibles par la somme de leurs digits.

Je sais qu'une démonstration mathématique aurait été plus convaincante, mais les outils empiriques au moyen de la programmation informatique sont particulièrement efficaces. lol

 #38 - 13-02-2016 17:29:14

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

Entiers sanss zéro

@masab: donc c'est bien le reste de la division de k par 9^r, puisque tu mets en préalable que k > 9^r. Je voulais juste être certain que c'était bien la division euclidienne, car tu ne le précises pas.

@Mr Hall: bienvenue sur le site. Difficile en effet de voir tous les cas jusqu'à l'infini avec l'informatique. Même avec une densité nulle de nombres divisibles par la somme de leur chiffre, ça ne veut pas dire qu'il n'y en a pas une infinité.

 #39 - 13-02-2016 17:40:19

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

entiers sans zéeo

@masab: OK, je valide. La même preuve que Gwen, mais avec une formalisation bien plus acamédique. Bravo à toi.

 #40 - 14-02-2016 15:22:50

unecoudée
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 319

rntiers sans zéro

bonjour. 
peut-être en travaillant avec des nombres à k chiffres congrus à 0 (mod9)
la somme S  de leurs chiffres est aussi congrue à 0 (mod9).
Maintenant , dans l'écriture de N  , on écrit  N de cette façon:
N = X S S S S S S S  avec [latex]X = 2^m \times S[/latex]

par exemple N est un nombre de k=18 chiffres .S = 81 . Alors :

N = 818181818181818181

si N est un nombre de k=19 chiffres , alors

N = 1628181818181818181 ou 3248181818181818181

si k = 21

N = 162818181818181818181

en raisonnant comme ça :  k = 400 par exemple :  [latex]S_x[/latex] est la somme des chiffres de X     
et [latex]S_s[/latex]  est la somme des chiffres de S

pour S à 4 chiffres et Ss =18  , et X a 8 chiffres  avec Sx = 27
[TeX]S = S_x + n\times{S_s}[/TeX]
alors S = 27 + 98 x 18

alors : [latex]X = 1791 \times 111\times 2^6 = 12723264[/latex] par exemple

Et N = 12723264 1791 1791 ... (98 fois)...1791 1791  est divisible
par S = 1791  et contient k = 400 chiffres

pour chaque k , il y a plusieurs solutions possibles , après il suffit d'éviter les 0
dans les nombres X  et S  qui forment le nombre N.

 #41 - 14-02-2016 18:53:52

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

entierq sans zéro

@une coudée: une seule solution pour chaque k suffit, maintenant il faut être sûr que ça marche pour tout k. Ce que tu ne prouves pas vraiment pour l'instant.

 #42 - 15-02-2016 10:17:40

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

Entiers ssans zéro

Merci à tous les participants d'avoir sué sur cette énigme pas facile. Et pour cause: il s'agit d'un problème posé en Olympiades internationales. Même si c'est du niveau Lycée, c'est tout de même adressé aux meilleurs.

Mention particulière à Gwen et Masab qui ont pu brillamment en venir à bout, à l'aide de sommes de nombres composés uniquement d'une succession de 9.

J'avais perso cru tenir une solution sans les 9, mais elle s'est avérée fausse en partie. Je donne pour info la démarche que j'avais entreprise.


1) Un nombre n de k chiffres est divisible par un nombre m si on construit n en additionnant des m à n'importe quel rang. Par exemple, pour 5 chiffres, la somme de ces 6 nombres:

12000+
01200+
00120+
00012+
12000+
01200=

26532 qui est divisible par 12.

2) La somme des chiffres du résultat n vaut  k fois la somme des chiffres de m si on a construit n avec k fois m et si on s'est arrangé pour qu'à aucun rang l'addition ne dépasse 9.
S(n) = k * S(m)

3) Compte tenu de 1) et 2), il suffit d'additonner m/S(m) fois un nombre m divisible  par S(m) pour obtenir un nombre n dont la somme des chiffres est m et divisible par m.

Par exemple 111=37*3.
Il suffit d'additionner 37 fois 111 en répartissant correctement sur k chiffres pour obtenir un nombre divisible par 111.

Le problème qui reste à résoudre est de savoir combien de chiffres au MIN. doit avoir n pour accueillir k fois m sans qu'aucun rang de l'addition des k*m ne dépasse 9. Et combien de chiffres au MAX n peut avoir pour qu'il n'y ait aucun zéro dans le nombre n.

Pour le cas de l'exemple 111:
MIN pour 3 chiffres: 999. ratio R pour un rang: 3/27=1/9. Nb MIN= m*R = 111/9=12,3.. on prend bien sûr la valeur modulo 3 supérieure (car 111 comporte 3 chiifres) donc 15.
Le nombre 111 999 999 999 999 a une somme de chiffres 111 et est divisible par 111. 

MAX pour 3 chiffres: 111. ratio R=3/3=1. Nb MAX= m* R= 111/1= 111. On peut écrire un nombre de 111 chiffres MAX divisible par 111 et ayant pour somme de chiffres 111.

Donc pour 15 <= k <= 111, on a toujours une solution par le diviseur 111.

Il faut maintenant trouver les bons nombres pour qu'il y ait superposition d'intervalle.

Avec 12
MIN pour 2 chiffres: 48 R=2/12=1/6 ---> MIN=12/6 = 2.  MAX: R=2/3 MAX = 12*2/3= 8

Résolu pour 2 <= k <= 8 par le diviseur 12.

Avec 21
MIN: 84, R=1/6 ---> MIN=21/6=4. MAX: R=2/3 MAX= 14.

4 <= k <= 14 par 21.

Avec 111:
15 <= k <= 111

Avec 201:
MIN:
804+
0804=
8844
R=4/24=1/6---->MIN= 201/6=33,5--->36.

MAX
201+
0201=
2211
R=2/3 ---->MAX=134

Avec 201, solutions pour 36 <= k <= 134.

Avec 1002, solutions pour 168 <= k <= 668
Avec 2001, solutions pour 336 <= k <= 1334
Avec 10002,solutions pour 1670 <= k <= 6668
 
Général
Avec 100...002 solutions pour 166...6667 <= k <= 666...667 environ
Avec 200...001 solutions pour 33...33336 <= k <= 133...3337 environ

Il existe un vide entre 133... et 166.. soit environ 3,5 % d' inconnues.

 #43 - 20-03-2020 08:10:47

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

Entiers sans zééro

Ce message pour rendre justice à Godisdead qui avait trouvé la solution la plus simple, sans toutefois l'avoir prouvée formellement....

Dans un autre message, on avait prouvé qu'on pouvait écrire un nombre de n chiffres divisible par 2^n, uniquement avec des 1 et des 2. Il suffit alors, pour notre cas ici, de compléter le nombre à k chiffres pour obtenir que leur somme fasse 2^n.

Exemple, avec un nombre à 47 chiffres.

On vise le nombre 2^7 = 128.

La fin du nombre sera ....2122112.

Reste plus qu'à répartir le reste de la somme 128-11 = 119 dans les 47 - 7 = 40 autres chiffres.

Un aménagement est toutefois à prévoir pour les petites valeurs de k.

 

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 : Pif, Paf et ?

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