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 - 29-12-2015 17:02:47

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

triqkaidekaphobia

Tout nombre formé de 78 répétitions d'un nombre quelconque est il divisible par 13 ?

  • |
  • Répondre

#0 Pub

 #2 - 29-12-2015 17:13:12

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Trsikaidekaphobia

Oui car [latex]10^{78}\equiv 1[/latex] modulo 13 .

Vasimolo

 #3 - 29-12-2015 17:17:54

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

triskaidekaphobua

La remarque est vraie mais je ne fais pas le lien direct.
Avec cette assertion, toute répétition sextuple marche aussi ?

 #4 - 29-12-2015 17:30:27

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

Triskadiekaphobia

[latex]x\equiv \frac{a(10^{78n}-1)}{10^n-1}\equiv 10^{78}-1\equiv 0 [/latex] modulo 13 .

Vasimolo

 #5 - 29-12-2015 17:43:14

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

triskaidekaphibia

C'est la répétition d'un chiffre que tu ecris non ?
moi je parle de répéter un nombre potnetiellement composé de plusieurs chiffres...

 #6 - 29-12-2015 17:45:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,426E+3

triskaidekzphobia

a est un nombre .

Vasimolo

 #7 - 29-12-2015 17:46:45

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

Triskaidekaphobi

Ah oui...je comprends...Bravo la solution est bien plus simple que ce que j'imaginais..ma méthode partait de la même observation mais prenait quelques détours...bien inutiles...

 #8 - 29-12-2015 18:56:04

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

Triskaiedkaphobia

777 * 13 = 10101
Donc 111111 est divisible par 13.
Tout nombre avec 6 répétitions sera déjà divisible par 13.
78 est divisible par 6
Donc oui, tout nombre de 78 répétitions sera divisible par 13.

 #9 - 29-12-2015 19:14:56

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

triskaidekaohobia

@nodgim
Oui c'est une enigme.
1111111111111 / 13 ?

C'est probablement l'idée godisdead mais j'ai un doute sur ce que tu veux dire précisément

 #10 - 30-12-2015 01:18:36

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

Triskaiedkaphobia

A la main, je trouve qu'il suffit de former une repetition de 6 fois n'importe quel nombre de 1, 2, 3, 4 ou 5 chiffres pour que le resultat soit divisible par 13...
Pour ca il suffisait de montrer que 111111, 10101, 1001, 100010001 et 10000100001000010000100001 sont tous divisible par 13, comme tous les nombres de 1 a 5 chiffres qui se repetent sont forcement divisible par un de ces nombres.


Ensuite, avec un petit programme, je trouve que si on continue:
avec des nombres à 6 chiffres, il faut 13 repetitions.
Donc, pour des nombres à:
- 1 chiffre, il faut au minimum 6 repetitions
- 2 chiffres, il faut au minimum 3 repetitions
- 3 chiffres, il faut au minimum 2 repetitions
- 4 chiffres, sil faut au minimum 3 repetitions
- 5 chiffres, il faut au minimum 6 repetitions
- 6 chiffres, il faut au minimum 13 repetitions
puis au dela, pour des nombres de 7 à 12 chiffres on repete le motif de 6, 3, 2, 3, 6 et 13 repetitions...
et ansi de suite, si on rajoute 6 chiffres au nombres de 7 a 12 chiffres, on a à nouveau 6, 3, 2, 3, 6, 13 repetitions necessaire.

Le plus petit commum multiple de 2, 3, 6 et 13 est bien sur 78.

Donc, oui il semblerait qu'il suffice que l'on repete n'importe quel nombre 78 fois pour qu'il soit divisible par 13.
pour le prouver....
Considerons que 999999 est un multiple de 13.
Donc 1000000 et 1 ont le meme reste, modulo 13.
Donc si 111111 est divisible par 13, alors 100000010000001000000100000010000001000000 est aussi divisible par 13.

Pour generaliser..
pour qu'un nombre de x=6*n+1 chiffres que l'on repete 6 fois soit divisible par 13, il suffit de montrer que 1(6*n zeros)1(6*n zeros)1(6*n zeros)1(6*n zeros)1(6*n zeros)1 soit divisible par 13. (par exemple 111111 ou 100000010000001000000100000010000001)
si on divise ce nombre en sections de 6, 1000000 nous donne 1, qui ajouté au 1 suivant donne 11, 11000000 donne 11, qui ajouté au 1 suivant donne 111, et ansi de suite....
quant on arrive a la fin, on trouve 1111111, qui, on le sait deja est divisible par 13.
Si on rajoute 6 zeros a chaque section, on retombe sur le meme reste modulo 13 et donc le meme motif....

Bon je sais c'est pas tres clair... mais ca marche...


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #11 - 30-12-2015 07:50:39

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

triskaidekzphobia

J'ai effacé tout ce que j'ai écrit hier, c'était un peu hors sujet.

Preuve:

1) Si le nombre comporte k chiffres, k multiple de 6.

S'écrit: a1b1c1d1e1f1 a2b2c2d2e2f2 .....

10^n modulo 13 est une séquence de longueur 6. Les valeurs successives modulo 6 sont -3,-4,-1,3,4,1. Le critère de divisibilité par 13 est donc:
Sai-Sdi+4(Sbi-Sei)+3(Sci-Sfi)=0, S étant la somme des chiffres de rang...

Si le nombre est répété 78 fois  (donc plusieurs fois 13 fois) alors toute somme S... est multiple de 13, et donc le total est nul.

2) Si le nombre n comporte k chiffres, k non multiple de 6.

Répété 78 fois, ce nombre s'écrit:
n(1+10^k+10^2k+....10^77k)=n(10^k^78-1)/(10^k-1)
Or 10^k^78-1=(10^6)^13k-1 qui est multiple de 10^6-1 et donc de 13. Comme 10^k-1 n'est pas multiple de 13, n répété 78 fois est divisible par 13.

 #12 - 30-12-2015 09:11:47

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

Triskaidekahpobia

oui smile

Un tel nombre est un multiple d'une séquence de 78 puissances de 10.

Or, en sommant les chiffres 3 par 3 de cette série de puissances de 10 on obtient un multiple de 13 (critère de divisibilité par 13)

Démonstration :

nombre de chiffres de la puissance égal à 3n :

Code:

100 100  ....
 +   -   

100 000 100 000 ...
 +   -   +   -  

Ceci répété 78/2 = 39 fois donnera 0 ou un multiple de 78

nombre de chiffres de la puissance égal à 3n+1 :

Code:

100 010 001 000
 +   -   +   -

100 000 010 000 001 000 000
 +   -   +   -   +   -   +

Ceci répété 78 / 3  fois donnera 0 ou un multiple de 26

nombre de chiffres de la puissance égal à 3n+2 :

Code:

100 001 000 010 000...
 +   -   +   -   +

100 000 001 000 000 010 000 000
 +   -   +   -   +   -   +   -

Ceci répété 78 / 3  fois donnera 0 ou un multiple de 26

 #13 - 30-12-2015 13:58:26

halloduda
Professionnel de Prise2Tete
Enigmes résolues : 24
Messages : 495
Lieu: Ardèche

triskaodekaphobia

10^78 = 1 modulo 13

78 répétitions de 10^78k, valent donc 78 soit 0 modulo 13 car 78 = 13*6.
On peut multiplier le "1" par n quelconque avec le même résultat.

 #14 - 30-12-2015 18:43:11

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

rriskaidekaphobia

Je me demande si je ne me suis pas fait bluffer par certaines réponses erronées ...


D'autres réponses (celle de nodgim dhrm et gwen entre particulier) correspondent à ce que je pensais... a savoir que 78 est le plus petit multiple qui "assure"

Je laisse ceux qui ont trouvé 6 comme facteur suffisant revoir leur idée.

De manière amusante certains pensaient que 13 etait le minimum,et d'autres 6...78 les met daccord.

Vasimolo: je ne suis toujours pas 100% certain de comprendre précisément mais est ce vrai que tu es dans le clan des 6 ?

Ma démo pour 78 est visuelle est sympa..vous l'aurez  en 2016...

 #15 - 30-12-2015 18:44:15

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

triskaidekaphonia

Ah, non, avec ma démarche, 39 assure aussi...et je pense que c'est le plus petit. Sinon, je montre juste que 78 marche, pas qu'un plus petit est exclu...

Par contre, 6, je n'y crois pas une seconde..; Impossible d'être sûr d'obtenir un total à 13 même s'il y a coïncidence pour 1, 2 et 3 chiffres.

Contre exemple : 1239 ne marche pas.

 #16 - 30-12-2015 18:58:04

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

Trikaidekaphobia

Gwen...
Je vais reverifier  mais j ai l impression que c'est faux quand le nombre de chiffres du nombre est impair.

Par exemple de tête  1111..11 (39 fois) =7 modulo 13.

Ce qui est cohérent avec ton message initial d'ailleurs...ou je ne suis plus...

 #17 - 30-12-2015 19:26:21

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

triskaidekapgobia

Ah, oui, je savais bien que j'avais gardé la parité pour une bonne raison ! Mais ça m'a échappé ! lol

 #18 - 30-12-2015 23:28:52

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

triqkaidekaphobia

Petit supplément rapide en passant : combien de répétitions  assurent la divisibilité par 11 ?

 #19 - 30-12-2015 23:30:30

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

triqkaidekaphobia

Petit supplément rapide et facile en passant : combien de répétitions  assurent la divisibilité par 9 ?  par 5...et par 1001 ?

 #20 - 31-12-2015 06:36:41

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3004
Lieu: Fanning Island-?-Lac Tele,Mali

triskaidzkaphobia

Au cas ou tu rajoutes des supplements:

Pour assurer la divisibilité par X, on a besoin de f(X) repetitions:
X  ->  f(X)
1  ->   1
3  ->   3       (=2*3 / 2)
7  ->   42     (=6*7)
9  ->   9
11  ->   22   (=10*11 / 5)
13  ->   78   (=12*13 / 2)
17  ->   272 (=16*17)
19  ->   342 (=18*19)
21  ->   42   (=2*21) = PPCM( f(3) , f(7) )
23  ->   506 (=22*23)
27  ->   27
29  ->   812 (=28*29)
31  ->   465 (=15*31)
33  ->   66   (=2*33)  = PPCM( f(3), f(11) )
37  ->   111 (=36*37 / 12)
39  ->  78    (=2*39) = PPCM( f(3), f(13) )
41  ->  205  (=40*41 / 8)
43  ->  903  (=42*43 / 2)
47  ->  2162 (=46*47)
49  ->  294 (=48*49 / 8) = ????
51  ->  816 (=16*51)  = PPCM( f(3), f(17) )
53  ->  689 (=52*53 / 4)
57  ->  342 (=6*57)   = PPCM( f(3), f(19) )
59  ->  3422 (=58*59)
61  ->  3660 (=60*61)
63  ->  126   (=2*63) = PPCM( f(7), f(9) )
67  ->  2211 (=66*67 / 2)
69  ->  1518 (=22*69) = PPCM (f(3), f(23) )
71  ->  2485 (=70*71 / 2)
73  ->  584  (= 72*73 / 9)
77  ->  462 (=6*77) = PPCM(  f(7), f(11) )
79  ->  1027
81  ->  81
83  ->  3403
87  ->  2436
89  ->  3916
91  ->  546
93  ->  465
97  ->  9312
99  ->  198
101  ->  404
103  ->  3502
107  ->  5671
109  ->  11772
111  ->  111
113  ->  12656
117  ->  234
119  ->  5712
121  ->  242
123  ->  615
127  ->  5334
129  ->  903
131  ->  17030
133  ->  2394
137  ->  1096
139  ->  6394
141  ->  6486
143  ->  858
147  ->  294
149  ->  22052
151  ->  11325
153  ->  2448
157  ->  12246
159  ->  2067
161  ->  10626
163  ->  13203
167  ->  27722
169  ->  1014
171  ->  342
173  ->  7439
177  ->  10266
179  ->  31862
181  ->  32580
183  ->  3660
187  ->  2992
189  ->  378
191  ->  18145
193  ->  37056
197  ->  19306
199  ->  19701
201  ->  2211 = 11 * 201 = PPCM( f(3), f(67) )
203  ->  2436
207  ->  4554
209  ->  3762
211  ->  6330
213  ->  7455
217  ->  6510
219  ->  1752
221  ->  10608
223  ->  49506
227  ->  25651
229  ->  52212
231  ->  462
233  ->  54056
237  ->  3081
239  ->  1673
241  ->  7230
243  ->  243
247  ->  4446
249  ->  10209
251  ->  12550
253  ->  506
257  ->  65792
259  ->  1554
261  ->  7308
263  ->  68906
267  ->  11748
269  ->  72092
271  ->  1355
273  ->  546
277  ->  19113
279  ->  1395
281  ->  7868
283  ->  39903
287  ->  8610
289  ->  4624
291  ->  9312
293  ->  42778
297  ->  594
299  ->  19734
301  ->  1806
303  ->  1212
307  ->  46971
309  ->  10506
311  ->  48205
313  ->  97656
317  ->  25043
319  ->  8932
321  ->  17013
323  ->  46512
327  ->  11772
329  ->  45402
331  ->  36410
333  ->  333
337  ->  113232
339  ->  37968
341  ->  10230
343  ->  2058
347  ->  60031
349  ->  40484
351  ->  702
353  ->  11296
357  ->  5712
359  ->  64261
361  ->  6498
363  ->  726
367  ->  134322
369  ->  1845
371  ->  28938
373  ->  69378
377  ->  31668
379  ->  143262
381  ->  5334
383  ->  146306
387  ->  2709
389  ->  150932
391  ->  68816
393  ->  51090
397  ->  39303
399  ->  2394
401  ->  80200
403  ->  12090
407  ->  2442
409  ->  83436
411  ->  3288
413  ->  71862
417  ->  19182
419  ->  175142
421  ->  58940
423  ->  19458
427  ->  25620
429  ->  858
431  ->  92665
433  ->  187056
437  ->  86526
439  ->  96141
441  ->  882
443  ->  97903
447  ->  66156
449  ->  14368
451  ->  4510
453  ->  11325
457  ->  69464
459  ->  7344
461  ->  212060
463  ->  71302
467  ->  108811
469  ->  30954
471  ->  12246
473  ->  19866
477  ->  6201
479  ->  114481
481  ->  2886
483  ->  10626
487  ->  236682
489  ->  13203
491  ->  240590
493  ->  55216
497  ->  14910
499  ->  248502
501  ->  83166
503  ->  252506
507  ->  1014
509  ->  258572
511  ->  12264
513  ->  1026
517  ->  23782
519  ->  22317
521  ->  27092
523  ->  136503
527  ->  126480
529  ->  11638
531  ->  30798
533  ->  15990
537  ->  95586
539  ->  3234
541  ->  292140
543  ->  32580
547  ->  49777
549  ->  10980
551  ->  138852
553  ->  43134
557  ->  154846
559  ->  23478
561  ->  8976
563  ->  158203
567  ->  1134
569  ->  161596
571  ->  325470
573  ->  54435
577  ->  332352
579  ->  37056
581  ->  142926
583  ->  15158
587  ->  171991
589  ->  53010
591  ->  57918
593  ->  351056
597  ->  19701
599  ->  179101
601  ->  180300
603  ->  6633
607  ->  122614
609  ->  2436
611  ->  84318
613  ->  31263
617  ->  54296
619  ->  382542
621  ->  13662
623  ->  82236
627  ->  3762
629  ->  30192
631  ->  198765
633  ->  6330
637  ->  3822
639  ->  22365
641  ->  20512
643  ->  68801
647  ->  417962
649  ->  37642
651  ->  6510
653  ->  212878
657  ->  5256
659  ->  433622
661  ->  145420
663  ->  10608
667  ->  205436
669  ->  49506
671  ->  40260
673  ->  150752
677  ->  228826
679  ->  65184
681  ->  76953
683  ->  232903
687  ->  52212
689  ->  4134
691  ->  158930
693  ->  1386
697  ->  55760
699  ->  162168
701  ->  490700
703  ->  12654
707  ->  8484
709  ->  501972
711  ->  9243
713  ->  235290
717  ->  5019
719  ->  258121
721  ->  73542
723  ->  7230
727  ->  527802
729  ->  729
731  ->  245616
733  ->  44713
737  ->  4422
739  ->  181794
741  ->  4446
743  ->  551306
747  ->  30627
749  ->  238182
751  ->  93875
753  ->  37650
757  ->  20439
759  ->  1518
761  ->  289180
763  ->  82404
767  ->  133458
769  ->  147648
771  ->  197376
773  ->  149189
777  ->  1554
779  ->  70110
781  ->  54670
783  ->  21924
787  ->  309291
789  ->  206718
791  ->  37968
793  ->  47580
797  ->  158603
799  ->  294032
801  ->  35244
803  ->  6424
807  ->  216276
809  ->  163418
811  ->  656910
813  ->  4065
817  ->  102942
819  ->  1638
821  ->  673220
823  ->  676506
827  ->  341551
829  ->  228804
831  ->  19113
833  ->  39984
837  ->  4185
839  ->  351541
841  ->  23548
843  ->  23604
847  ->  5082
849  ->  39903
851  ->  56166
853  ->  181689
857  ->  733592
859  ->  22334
861  ->  8610
863  ->  743906
867  ->  13872
869  ->  22594
871  ->  57486
873  ->  27936
877  ->  384126
879  ->  128334
881  ->  387640
883  ->  389403
887  ->  785882
889  ->  5334
891  ->  1782
893  ->  369702
897  ->  19734
899  ->  377580
901  ->  187408
903  ->  1806
907  ->  136957
909  ->  3636
911  ->  414505
913  ->  74866
917  ->  357630
919  ->  421821
921  ->  46971
923  ->  193830
927  ->  31518
929  ->  431056
931  ->  16758
933  ->  144615
937  ->  877032
939  ->  97656
941  ->  884540
943  ->  103730
947  ->  447931
949  ->  22776
951  ->  75129
953  ->  907256
957  ->  26796
959  ->  23016
961  ->  14415
963  ->  51039
967  ->  311374
969  ->  46512
971  ->  941870
973  ->  134274
977  ->  953552
979  ->  3916
981  ->  11772
983  ->  965306
987  ->  45402
989  ->  456918
991  ->  490545
993  ->  109230
997  ->  165502
999  ->  999
1001  ->  6006
1003  ->  465392

Il semblerait que pour tous les nombres premiers* (P), le nombre de repetitions necessaires est soit P*(P-1), soit un diviseur de P*(P-1).
Donc, je postule que si on repete un nombre quelconque N, un nombre de fois R, ou R = P * (P-1) et P est premier, alors, le nombre N répété est divisible par P.
On peut aussi dire que quelque soient N et P (P étant premier*), il est possible de trouver un nombre X qui contienne un répétition de N et est divisible par P.
Note: ici Premier* signifie Premier, mais pas un diviseur de la base dans laquelle on ecrit N, donc en base 10, sauf 2 et 5.

Si on choisi un diviseur Q non-premier, soit Q=A*B, le nombre de repetitions necessaires est le PPCM de f(A) et f(B), si A et B sont premiers entre eux. (ca ne marche pas pour 9, 27, 49, 81, etc... qui sont des puissances de nombres premiers)


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #21 - 31-12-2015 06:50:40

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

Trsikaidekaphobia

pas tout vérifié mais ça m'a l'air bien beau dhrm... cool

C'est amusant cette spécificité du 5 dont les multiples semblent être les seuls à ne pas fonctionner...avec ceux de 2 bien sur (cf nodgim)

 #22 - 31-12-2015 08:59:56

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

truskaidekaphobia

Bonjour,
Les restes de la division par 13 des puissances successives de 10 sont périodiques de période 6 : 1, 10, 9, 12, 13, 4

Pour voir quel est le nombre de répétitions nécessaires d'un nombre de 3 chiffres (par exemple), on va additionner
- le 1er reste :  1
- le 4ème :      12
On s'arrête parce que la somme de ces restes est un multiple de 13, et que le produit de la taille du nombre initial (ici 3) et du nombre de répétitions (ici 2) est un multiple de 6 (la période des restes).

On applique le même raisonnement pour toutes les longueurs de 1 à 6 (on peut s'arrêter là à cause de la périodicité des restes).

Code:

Nb de chiffres      Nb de répétitions nécessaires
 1                   6
 2                   3
 3                   2
 4                   3
 5                   6
 6                  13

Le plus petit multiple commun à tous ces nombres est 78.

 #23 - 31-12-2015 09:31:35

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1960

Triskaidekaphbia

1001 est un multiple de 13. Par conséquent, 1001 * 111 = 111111 aussi.
De là, on en déduit que tout nombre écrit avec 6N fois le chiffre 1 est multiple de 13, et plus généralement que tout nombre écrit avec 6N fois le même chiffre C aussi (puisque ce nombre vaut C * 111111...)

 #24 - 31-12-2015 10:02:35

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

troskaidekaphobia

Correct mais on parle de nombres, pas de chiffres, scarta.

 #25 - 31-12-2015 11:18:25

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

Triskaidekaphoba

La répétition par 5 ou par 2 ne sert à rien, car 2 et 5 ne sont pas premiers avec la base 10.

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

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