Accueil > Vie Scolaire > Autres rubriques > Jeux mathématiques et logiques > Une énigme par semaine > Catégorie Lycée / Grand Public > Énigme de la semaine 26

Énigme de la semaine 26

par MOTTIER Pierre

La horde des uns.

(Extrait de Mathématiques sans frontières)

Charlotte a trouvé le plus petit multiple de 7 qui s’écrit uniquement avec des chiffres 1.
Puis elle imagine le nombre entier naturel N qui s’écrit uniquement avec 2 014 fois le chiffre 1.
Elle se demande quel est le reste de la division euclidienne de N par 7.
Quel est le multiple de 7 trouvé par Charlotte ?
Trouver le reste de la division euclidienne de N par 7.

Messages

  • Bonjour M. Tux,

    J’ai trouvé 111 111 et 5 comme réponses. Je ne pense pas avoir trouvé la plus simple des preuves (tout comme je ne suis pas sûr d’avoir trouvé la solution) mais en revanche cela m’aura permis de recroiser mes vieux amis Newton, Fermat et Gauss.

    Bien à vous,
    Le Pingouin Masqué

  • Sherlock Tux a publié cette semaine une énigme pour laquelle je n’ai pas la réponse, et me demande de valider les réponses des joueurs !
    Me voilà donc contraint de chercher aussi... Et finalement, j’en éprouve du plaisir aussi !
    Ma solution est un peu savante (et pas forcément la plus efficace pourtant) puisqu’elle fait appel à des notions d’arithmétique étudiées en spécialité mathématiques de terminale S...
    Enfin, j’arrive au même résultat que le Pingouin Masqué (plus astucieux que moi, avec mes gros sabots...) :
    10^0 \equiv 1 \pmod 7
    10^1 \equiv 3 \pmod 7
    10^2 \equiv 2 \pmod 7
    10^3 \equiv -1 \pmod 7
    10^4 \equiv -3 \pmod 7
    10^5 \equiv -2 \pmod 7
    Donc 111~;111 \equiv 0 \pmod 7 (le plus petit multiple de 7 s’écrivant avec uniquement des 1 est 111 111)
    10^6 \equiv 2 \pmod 7
    On retrouve comme reste 2 ! Plus besoin de faire de calculs ! On aura assurément :
    10^7 \equiv -1 \pmod 7
    10^8 \equiv -3 \pmod 7
    10^9 \equiv -2 \pmod 7
    Et 10^6+10^7+10^8+10^9 \equiv -4 \equiv 3 \pmod 7
    De même, 10^{10}+10^{11}+10^{12}+10^{13} \equiv 3 \pmod 7, etc.
    Le nombre s’écrivant avec 2 014 fois le chiffre 1 s’écrit aussi N=10^{2013}+10^{2012}+\cdots+10^2+10^1+10^0
    N \equiv \underbrace{ 10^6+10^7+10^8+10^9 }_{3}+\underbrace{ 10^{10}+10^{11}+10^{12}+10^{13} }_{3}+\cdots+10^{2012}+10^{2013} \pmod 7
    Chaque regroupement est congru à 3 modulo 7.
    2~;013-8=2~;008=52 \times 4
    Il y a 52 regroupements exactement...
    N \equiv 52 \times 3 \pmod 7
    N \equiv 4 \times 3 \pmod 7
    N \equiv 5 \pmod 7 (le reste de la division euclidienne de N par 7 est 5)
    Un peu fastidieux, quand même, non ?

  • Bonjour Sherlock,

    Le plus petit nombre composé de chiffres 1, multiple de 7 est 111111.
    Le reste de la division du chiffre composé de 2014 chiffres 1 par 7 est 5.

    Notations :
    Sn : nombre correspondant à n chiffres 1
    R : reste de la division de Sn par 7
    DIV : Sn/7

    Calcul de la somme en fonction du rang n :
    Sn = \sum_{k=0}^{n-1} 10^k
    Sn = \frac {1-10^n} {1-10}
    Sn = \frac {10^n -1} {9}

    Avec un programme algobox on calcule la somme jusqu’au rang N :
    On constate que le plus petit nombre composé de chiffres 1 multiple de 7 s’obtient pour rang 6 : S6=111111

    Toutes les sommes divisibles par 7 sont de rang multiple de 6 : S6,S12,S18,...
    On observe également une périodicité du reste en fonction du rang (0<R<7) : 1, 4, 6, 5, 2, 0 ...
    (NB : Si l’on prend un rang N supérieur à 15, algobox donne des résultats un peu faux (sauf pour les divisions entières), à cause des approximations sur le calcul de Sn.
    Le calcul manuel confirme bien cette périodicité du reste)

    On recherche le nombre le plus proche de 2014 qui est un multiple de 6 (Toutes les sommes divisibles par 7 sont de rang multiple de 6) : c’est 2016
    Pour 2016 R=0

    Pour trouver le reste de 2014, il suffit d’effectuer la correspondance année/reste, vu que les restes sont périodiques :
    2014 R=5, 2015 R=2, 2016 R=0

    Donc pour un chiffre constitué de 2014 chiffres 1 (S14), le reste de la division par 7 est 5

    Sortie du programme algobox :
    ***Algorithme lancé***
    Saisir N (nombre de 1) :
    Entrer N : 15
    I=1 : S1=1, DIV=0.14285714, R=1
    I=2 : S2=11, DIV=1.5714286, R=4
    I=3 : S3=111, DIV=15.857143, R=6
    I=4 : S4=1111, DIV=158.71429, R=5
    I=5 : S5=11111, DIV=1587.2857, R=2
    I=6 : S6=111111, DIV=15873, R=0
    I=7 : S7=1111111, DIV=158730.14, R=1
    I=8 : S8=11111111, DIV=1587301.6, R=4
    I=9 : S9=1.1111111e+8, DIV=15873016, R=6
    I=10 : S10=1.1111111e+9, DIV=1.5873016e+8, R=5
    I=11 : S11=1.1111111e+10, DIV=1.5873016e+9, R=2
    I=12 : S12=1.1111111e+11, DIV=1.5873016e+10, R=0
    I=13 : S13=1.1111111e+12, DIV=1.5873016e+11, R=1
    I=14 : S14=1.1111111e+13, DIV=1.5873016e+12, R=4
    I=15 : S15=1.1111111e+14, DIV=1.5873016e+13, R=6

    ***Algorithme terminé***

  • En PJ le programme algobox de calcul de Sn

  • Bonjour M.Tux,

    Le plus petit multiple de 7 que Charlotte a trouvé est le nombre 111 111.
    Car :

    1 ≡ 1[7]
    1*10+1≡ 1*10+1[7] ≡ 4[7]
    11*10+1≡ 4*10+1[7] ≡ 6[7]
    111*10+1≡ 6*10+1[7] ≡ 5[7]
    1111*10+1≡ 5*10+1[7] ≡ 2[7]
    11111*10+1≡ 2*10+1[7] ≡ 0[7]

    Soit n le nombre de chiffres 1,le reste d’un nombre s’écrit avec 6n chiffres 1 par 7 est 0 (Exemple : 111 111 ou 111 111 111 111)

    Donc le nombre qui s’écrit avec 2010 chiffres 1 est divisible par 7. Appelons ce nombre X.
    X≡ 0[7]
    X*10+1 ≡ 1[7]
    X1*10+1 ≡ 10+1[7] ≡ 4[7]
    X11*10+1 ≡ 6[7]
    X111*10*1≡ 5[7]
    Donc le reste de la division euclidienne de N par 7 est 5.

  • Dans un premier temps, j’utilise la calculatrice pour essayer de trouver ce multiple de 7 : donc le multiple de 7 trouvé par Charlotte est 111 111 (avec 6 chiffres 1). Autrement dit, 111 111≡0 [7].

    Ensuite, j’ai créé un programme sur Algobox pour trouver le reste de la division des nombres avec uniquement des chiffres 1 par 7 en espérant qu’il y aurait une sorte de boucle. Voici les résultats :
    (0 ≡ 0 [7])
    1 ≡ 1 [7]
    11 ≡ 4 [7]
    111 ≡ 6 [7]
    1 111 ≡ 5 [7]
    11 111 ≡ 2 [7]
    111 111 ≡ 0 [7]
    1 111 111 ≡ 1 [7]
    11 111 111 ≡ 4 [7]
    111 111 111 ≡ 6 [7]
    ...

    On a ainsi l’évolution du reste de ce type de division. Ainsi, lorsqu’on divise 111 111 111 111 (12 chiffres 1) par 7, on obtiendra 0 comme reste, et il sera le même pour 111 111 111 111 111 111 (18 chiffres) et le nombre avec 24 chiffres 1. On sait aussi que 2 014 = 335*6 + 4 donc la division du nombre avec 2 014 chiffres 1 sera 5.

  • Bonjour Monsieur,

    Avec un algorithme, on trouve le multiple trouvé par Charlotte est 111 111.

    On cherche maintenant le tableau de congruence des nombres en « 1 » :
    1 ≡ 1[7] (1 chiffre 1)
    11 ≡ 4[7] (2 chiffres 1)
    111 ≡ 6[7] (3 chiffres 1)
    1 111 ≡ 5 [7] (4 chiffres 1)
    11 111 ≡ 2 [7] (5 chiffres 1)
    111 111 ≡ 0[7] (6 chiffres 1)
    1 111 111 ≡ 1[7] (7 chiffres 1)
    11 111 111 ≡ 4 [7] (8 chiffres 1)

    Il semble qu’il y a un cycle de 6 concernant les congruences modulo 7. À chaque fois que on ajoute 6 chiffres 1, on retrouve le même reste. Il faut donc trouver le reste de la division euclidienne de 2 014 par 6.
    2 014 = 2 010 + 4
    2 010 est divisible par 2 et par 3 donc aussi par 6
    donc 2 014 ≡ 4 [6]

    Avec 2 014 chiffres 1 on a donc le même reste qu’avec 4 chiffre 1, soit un reste de 5.
    Le reste de la division euclidienne de N par 7 est 5.

  • Le multiple de 7 trouvé par Charlotte est 111 111.
    On observe que les restes se répètent.
    Donc on fait la division euclidienne de 2 014 par 6.
    Le reste de cette division est 4 alors c’est le 4e reste : 5

  • Bonjour Sherlock

    Première partie :

    Le multiple de 7 trouvé par Charlotte est probablement relativement petit : On cherche donc le reste de la division euclidienne des « petits » nombres s’écrivant uniquement avec des 1 :

    11 = 7*1 + 4
    111 = 7*15 + 6
    1 111 = 7*158 + 5
    111 11 = 7*1587 + 2
    11 1111 = 7*15873 + 0

    111 111, composé de six 1, est donc le multiple de 7 trouvé par Charlotte.

    Deuxième partie

    On cherche le reste de la division euclidienne de N, composé de 2 014 fois le chiffre 1, par 7. Si l’on continue les tests de la première partie, il semble que les restes de la division euclidienne par 7 soient récurrents, dans l’ordre suivant : 1, 4, 6, 5, 2, 0. Si l’on admet que ce cycle est valide jusqu’au nombre composé de 2 014 chiffres 1, on trouverait un reste de 5.

    Le nombre N est la somme de toutes les puissances de 10 de 0 à 2014.
    De plus :

    10^(n+6) ≡ 10^n * 10^6 [7]
    ≡ 10^n * (7*142 857 + 1) [7]
    ≡ 10^n * 1 [7]
    ≡ 10^n [7]

    Le « cycle » des restes est donc vérifié.
    Soit R le reste de la division euclidienne de N par 7.

    R est égal au reste de la division euclidienne de la somme des restes de ce cycle multipliée par 2 013/6, par 7.

    Soit R = reste de [ ((1+4+6+5+2+0)- 14) * 2 013/6 ]
    R = reste de (4*2 013/6)
    R = 1 342 - 7*191
    R = 5

    Le reste de la division de N par 7 est donc bien 5.

  • Le multiple de 7 trouvé par Charlotte est 111 111. On remarque que lorsqu’on divise un nombre écrit avec des chiffres 1 par 7, le résultat est un nombre composé de la suite répétitive des chiffres 158730158730...ainsi de suite. Donc le reste de la division euclidienne de N par 7 est 5.

Vie Scolaire

Dans cette rubrique

Plan du site |