[Concours Kangourou] Dernier chiffre

Bonjour tout le monde !

J'ai un petit problème à vous poser (que je n'arrive pas à résoudre moi-même). Le but est donc double : comprendre sa résolution, et voir qui est balèze ici ^^

Donc le voici : "Quel est le dernier chiffre (autre que 0) du produit des 100 premiers entiers naturels non nuls ?"

Ce problème est tiré du concours kangourou des mathématiques.
Voilà bonne chance.

PS: je connais la réponse et j'ai trouvé une seule explication sur le net mais je n'ai pas trop compris...

Bonsoir,

L'exercice est vraiment très intéressant en soi. Il s'agit en fait de trouver le dernier entier non nul de 100! (lu "100 factoriel" ou "factoriel 100" ce qui revient à faire la multiplication des 100 premiers entiers non nul).

On peut utiliser les congruences pour pouvoir résoudre le problème mais bon cette notion est vu seulement à partir de la Terminale scientifique spécialité mathématiques.

Par contre pour qu'on sache avec quel niveau cela doit être résolu, peux-tu préciser le niveau du concours Kangourou en question. D'ailleurs le concours kangourou est à choix multiple, il doit donc y avoir des choix de proposer pour cette question, tu peux les ajouter si tu le souhaites.

Car il faut savoir que certaines questions du concours kangourou ne sont résolvable que par testes et déduction vu le temps qu'il faut passer par question. Mais ensuite rien ne nous empêche de reprendre les questions pour en chercher des solutions constructives.

Bon courage!

Il s'agit d'une des deux dernières questions subsidiaires (sujet 2004) qui sert à départager d'éventuels ex-oequo ! Donc y'a aucune aide, ils ne proposaient aucun choix.
Et en +, c'était la même question subsidiaire pour les Benjamins (6ème - 5ème), Cadets (4ème - 3ème - CAP / BEP), Juniors (Lycées) et Etudiants (TS, Bac+) ! Les fous, comment ils veulent que des petits 6ème trouvent la réponse ? En même temps je crois que t'a pas besoin de justifier le jour de l'épreuve pour ces deux questions subsidiaires donc tu peut mettre au pif...

En effet, c'est déconcertant de voir que cette question est la même à tous les niveaux mais bon, il faut prendre son mal en patience et tenter des astuce de calcul.

On peut déjà réduire la probabilité de faire une erreur, en montrons que le dernier chiffre est forcément pair ce qui ne laisserait plus que 2,4,6 ou 8 comme solution possible (ce qui fait en fait un choix de type kangourou avec 4 propositions possibles).

Ouai sauf que là y'avait pas les 4 choix possibles ^^

Donc le fait que le dernier chiffre du produit (à part 0) soit pair j'y avais déja pensé car on fait le produit de 50 nombres impairs et 50 pairs. Or impair*impair = impair et pair*impair= pair. La déduction est vite faite (je détaille pas). Après je me suis dit qu'on pouvait enlever le 1 (car il n'influence pas le résultat du produit), et tous ceux qui se terminent par un "0" : donc 10, 20, 30, 40, 50, 60, 70, 80, 90 et 100. et enfin 2 et 5 car 2*5=10 !!! Après je vois pas si on peut en supprimer d'autres pour simplifier notre recherche.

Le fait que pair*impair=pair et pair*pair=pair ne permet pas de conclure sur la parité du dernier chiffre non nul.

Par contre les suppressions que tu fais sont justes en effet. Pour trouver que le chiffre que nous cherchons est forcément pair, il faut regarder les multiples de 5 et les multiples de 2 (dont on sait qu'il y en a 50 vu qu'il y a 50 nombres pairs dans la série multiplicative).

Blagu'cuicui a écrit:

Le fait que pair*impair=pair et impair*impair=impair ne permet pas de conclure sur la parité du dernier chiffre non nul.

Ben après toutes les suppressions de nombres (tous ceux qui se terminent par 0, 1, 2, et 5), on sait que le produit de tous les impairs donnera un nombre impair et comme à chaque fois qu'on mulitplie un nombre impair par un nombre pair on obtient un nombre pair, les formules permettent bien de conclure que le dernier chiffre non nul est pair donc je vois pas pourquoi tu dis qu'on ne peut pas conclure ! non ?

Cela est vrai si après suppression des 5, il reste des multiples de deux.

C'est en effet, le cas car il y a plus de nombre pair que de multiple de 5 cependant, il fautl e dire sinon, ton argumentation ne tient pas .

Nous sommes donc devant le fait qu'il y a comme solution 2, 4, 6 ou 8.

Ensuite, nous savons que la multiplication d'un nombre qui se termine par 1 ne changera pas a valeur du dernier chiffre. Nous pouvons donc enlever encore 9 nouveaux chiffres.

Il reste pour le moment:

(3*4*6*7*8*9)*(12*13*14*15*16*17*18*19)*20*(22*23*24*.....)*.....

Mais dans le même style que pour les chiffre terminant par 1, il y a tous les multiple de 11 qui ne contribuent seulement par leur multiplication par exemple 22=2*11 et par conséquent seul le 2 nous intéresse.

On peut calcyuler à la main le premier groupe qui nous donne 36288. Par conséquent, seul le 8 va contribuer dans notre recherche.

Il faut enlever la contribution de toutes les multiplication étant égale à 10. Par exemple 20=2*10 donc seul le 2 nous intéresse 12*15=(2*6)*(3*5)=18*10 donc seul 8 nous intéresse.

Le but étant dépurer le plus rapidement possible les calculs et les chiffres qui ne servent pas. Le conseil serait d'écrire la multplication par dizaine les uns en-dessous des autres:

3*4*6*7*8*9*
12*13*14*15*16*17*18*19*
20*
22*23*24*25*26*27*28*29*
.....
90*
92*93*94*95*96*97*98*99*

On peut ainsi déduire les chiffres sur chaque ligne qui serve à la détermination du dernier chiffre non nul.

Bon courage!

BsR Natty , BsR Blagu'cuicui !


Dsl pour l'absence , On vient de terminer Les Examens De Premiere annee Bac au Maroc ce Mardi !


Bon retournant a not' probleme , Je propose une petite methode Simple , et qui ressemble trop a celle de Mr.Blagu'cuicui , presque la meme idee !

Dans notre 100! , On peut remarquer aisemment que de : 10 nombres se terminent par 2 et dix nombres se terminent par 5, ce qui donne déjà 10 zéros à la fin
il y a aussi dix nombres qui se terminent par 0, ce qui fait 10 zéros de plus.

Dans la somme c'est 20 zéros.

Donc il nous reste les Nombres 1,3,4,6,7,8,9 , 10 fois chacune ! Donc (1*3*4*6*7*8*9)^10

Voila ce qui est Plus difficile dans le probleme ! le reste est Facile ! je te laisse deduire Mr.Natty

Erreur mon cher MouaDos! (avec l'accent de sherlock holmes bien sur ).

En effet, je te donne un contre exemple à ton raisonnement:

la première série est bien 1*3*4*6*7*8*9 je suis d'accord mais parce que 2*5=10 ce qui permet de les supprimer.

Cependant, dans la deuxième série nous avons: 11*12*13*14*15*16*17*18*19 et tu ne gardes selon ton raisonnement que 11*13*14*16*17*18*19 puis seulement les unités de ces nombres ce qui nous donnent 1*3*4*6*7*8*9 mais là il y a une erreur !!

En effet, 12*15 n'est pas égale à 10 !!! 12*15=(2*6)*(3*5)=18*10=180 et le chiffre 8 à son importance ici !!! Car c'est le dernier chiffre non nul avant le 0 ce qui implique donc qu'il aura sa contribution dans le calcul du dernier chiffre non nul de la multiplication totale.

Il se trouve que ton raisonnement qui s'avère faux donne en fait le bon résultat (pour avoir tenter ce raisonnement avant de m'apercevoir de mon erreur ).

Ce n'est pas si simple, je vous laisse revoir vos calculs .

Bon courage!

Donc une fois qu'on a supprimé tous les chiffres "inutiles" (qui produiront des zéros à la fin), il faut faire quoi ?

L'idée de MouaDos (1*3*4*6*7*8*9)^10 est-elle bonne ? comment déduire après ?

J'aimerais bien une petite récapitulation car avec tous vos messages et Cuicui qui dit que MouaDos s'est trompé, je ne suis plus ^^

L'idée de MouaDos donne le bon résultat mais il s'agit d'un coup de chance car la méthode n'est pas exacte.

Pour ma part je n'ai pas de méthode miracle pour faire cette question mis à part d'effectuer les calculs à la mains après les simplifications.

1*2*3*4*5*6*7*8*9*
10*
11*12*13*14*15*16*17*18*19*
20*
...
...
90*
91*92*93*94*95*96*97*98*99*
100

Pour les multiples de 10, on ne garde que le chiffre des dizaine vu que le reste ne sert pas (cela donne des 0 en plus), nous arrivons donc à:

1*2*3*4*5*6*7*8*9*
1*
11*12*13*14*15*16*17*18*19*
2*
...
...
9*
91*92*93*94*95*96*97*98*99*
1

On constate que les multiple de 10, nous donne donc 1*2*3*4*5*6*7*8*9*1=1*2*3*4*5*6*7*8*9. Nous en sommes donc à:

[(1*2*3*4*5*6*7*8*9)²]*
11*12*13*14*15*16*17*18*19*
21*22*23*24*25*26*27*28*29*
...
...
91*92*93*94*95*96*97*98*99

Dans la première ligne, on constate que 2*5=10 ce qui va donc juste ajouter un 0 sans changer le chiffre vu que le chiffre des dizaine est égale à 1. Ce qui donne (on en profite pour enlever le 1 qui ne sert à rien):

[(3*4*6*7*8*9)²]*
11*12*13*14*15*16*17*18*19*
21*22*23*24*25*26*27*28*29*
...
...
91*92*93*94*95*96*97*98*99

Ensuite, on peut regarder le première terme pour voir ce qu'il donne:

3*4*6*7*8*9=3*2²*(2*3)*7*2³*3²=2⁶*3⁴*7=64*81*7

81 fini par 1, il n'y a donc pas de contribution pour le dernier chiffre non nul ce qui donne: 64*7=448

Le dernier chiffre est donc un 8 et si je l'élève au carré, je trouve 64 ce qui nous donne comme contribution pour cette première ligne un 4.

Conclusion, on a:

4*
11*12*13*14*15*16*17*18*19*
21*22*23*24*25*26*27*28*29*
...
...
91*92*93*94*95*96*97*98*99

Maintenant, passons à la suite, on sait que tout ce qui se termine par un 1 a une contribution nulle pour le dernier chiffre non nul, on peut donc les supprimer et de même pour les multiple de 11, on ne garde que la valeur de l'unité (ou des dizaine c'est la même de toute façon) ce qui nous donne:

4*
12*13*14*15*16*17*18*19*
2*23*24*25*26*27*28*29*
32*3*34*35*36*37*38*39*
42*43*4*45*46*47*48*49*
52*53*54*5*56*57*58*59*
62*63*64*65*6*67*68*69*
72*73*74*75*76*7*78*79*
82*83*84*85*86*87*8*89*
92*93*94*95*96*97*98*9

On constate donc qu'il y a encore la contribution du 2*3*4*5*6*7*8*9 ce qui nous donne comme chiffre des unité d'après l'étude déjà faite un 8. Et vu que nous avions une multiplication par 4, cela donne 4*8=32 c'est à dire une contribution d'un 2.

2*
12*13*14*15*16*17*18*19*
23*24*25*26*27*28*29*
32*34*35*36*37*38*39*
42*43*45*46*47*48*49*
52*53*54*56*57*58*59*
62*63*64*65*67*68*69*
72*73*74*75*76*78*79*
82*83*84*85*86*87*89*
92*93*94*95*96*97*98

On va s'attaqué maintenant au chiffre ayant des multiple finissant par un 1 car toute multiplication par un nombre finissant par un 1 n'a aucune contribution pour le chiffer que nous cherchons:

Les multiple de 21: 2*21=42, 3*21=63, 4*21=84 (4*21=104>100) => contribution seulement du 2, du 3 et du 4
Les multiple de 31: 2*31=62, 3*31=93 (4*31=124>100)=> contribution seulement du 2 et du 3
Les multiple de 41: 2*41=82 (3*41=123>100)=> contribution seulement du 2
(Les multiple de 51 sont exclus car 2*51=102>100)

On a donc (2*3*4)*(2*3)*2=24*6*2=144*2=288 => contribution du 8 seulement.

Il restait une contribution en début de chaîne du 2 ce qui donne 2*8=16 => contribution de 6.

Conclusion (j'en profite pour décomposer les multiples de 5):

6*
12*13*14*(3*5)*16*17*18*19*
23*24*(5*5)*26*27*28*29*
32*34*(7*5)*36*37*38*39*
43*(9*5)*46*47*48*49*
52*53*54*56*57*58*59*
64*(13*5)*67*68*69*
72*73*74*(3*5*5)*76*78*79*
83*(17*5)*86*87*89*
92*94*(19*5)*96*97*98

Pour supprimer la contribution d'un 5, il suffit de le multiplier par 2, j'ai donc mis en évidence des nombre pair dans la ranger où les 5 doivent disparaître.

12*5=60 => contribution du 6
24*5*5=120*5=600 => contribution du 6
32*5=160 => contribution du 6
46*5=230 => contribution du 3
64*5=320 => contribution du 2
72*5*5=360*5=1800 => contribution du 8
86*5=430 => contribution du 3
92*5=460 => contribution du 6

Ce qui nous donne une contribution de: 6*6*6*3*2*8*3*6=36*36*24*6=(36)²*(144)
36 contribue par son 6 et 144 par son 4 ce qui donne 6²*4=36*4=144 => contribution du 4

nous avions une contribution de 6 au première ligne ce qui nous donne 6*4=24 => contribution du 4.

Conclusion:

4*
13*14*3*6*17*18*19*
23*26*27*28*29*
34*7*36*37*38*39*
43*9*47*48*49*
52*53*54*56*57*58*59*
13*67*68*69*
73*74*3*76*78*79*
83*17*87*89*
94*19*96*97*98

Nous savons que le seul moyen d'obtenir un 0 était une multiplication par un multiple de 10 c'est à dire un multiple de 5 multiplié par un multiple de 2. Or nous venons d'éradiquer tous les multiple de 5. Par conséquent, il n'y a plus de 0 à la fin du chiffre qu'il nous reste sous les yeux (si on effectue les multiplication).

Conclusion, il n'y a que les chiffres des unités qui contribuent pour connaître le chiffre des unité du nombre que nous avons sousl es yeux. Il nous reste doncà calculer:

4*
3*4*3*6*7*8*9*
3*6*7*8*9*
4*7*6*7*8*9*
3*9*7*8*9*
2*3*4*6*7*8*9*
3*7*8*9*
3*4*3*6*8*9*
3*7*7*9*
4*9*6*7*8

On a:
4
3*4*3*6*7*8*9=9*4*42*72 =>(seul le chiffre des unités nous intéresse) 9*4*2*2=36*4 => 6*4=24 => 4
3*6*7*8*9=3*42*72 => 3*2*2=12 => 2
4*7*6*7*8*9=28*42*72 => 8*2*2=32 => 2
3*9*7*8*9=27*7*72 => 7*7*2=49*2 => 9*2=18 => 8
2*3*4*7*8*9=6*28*72 => 6*8*2=6*16 => 6*6=36 => 6
3*7*8*9=21*72 => 1*2=2 => 2
3*4*3*6*8*9=12*18*72 => 2*8*2=32 => 2
3*7*7*9=21*63 => 1*3=3 => 3
4*9*6*7*8=36*42*8 => 6*2*8=12*8 => 2*8=16 => 6

Ce qui nous donne:

(4*4)*(2*2)*(8*6)*(2*2)*(3*6)=16*4*48*4*18 => 6*4*8*4*8=24*32*8 => 4*2*8=8*8=64

Conclusion générale: le chiffre cherché est un 4 !!!!!!!!!!!!!!!

Il y a plus simple comme raisonnement vu que le but est seulement d'enlevé tous les 0, on est pas obligé d'enlever tous les multiple de nombre finissant par 1 comem j'ai commencer par le faire ici ce qui allège pas mal es calcul en aparte mais bon, j'ai donner un raisonnement parmi d'autre. Je vous laisse si vous voulez écrire le raisonnement en enlevant seulement les multiples de 5 vous verrez que c'est vraiment beaucoup plus rapide et ça vous fera manipuler les deux ou trois raisonnements que j'ai évoqués dans ma démarche.

Bonne continuation!

Pas mal ! C'était joli.
En fait j'avais pas en tête l'idée que l'on pouvait garder que les derniers chiffres de chaque nombre comme tu la fait.

Au tout début du poste tu as dit que l'on pouvait utiliser les congruences pour résoudre ce problème. Ce serait plus rapide dans ce cas là ?

J'utilise les congruence sans le dire à partir du moment où j'ai enlevé tous les zéro.

En effet, lorsque je dis que je garde seulement le 3 de 13 j'écris que 13=3+1*10 c'est à dire que 13 est congru à 3 modulo 10. Mais pour utiliser les congruence, il faut commencer par enlever tous les zéros car si le chiffre est un multiple de 10, il est congru à 0 modulo 10 ce qui n'a donc aucun intérêt.

C'est pour cela que je dis à la fin qu'il suffit en fait "d'enlever" les multiples de 5 pour s'en sortir beaucoup plus rapidement.

Bonne continuation!

Bon je déterre ce vieux sujet.

Maintenant que j'ai vu les congruences en spé maths, ça m'intéresserais de savoir comment résoudre ce problème avec ces dernières.

Merci d'avance !



PS : pour ton message sur les anneaux Z/nZ sur l'autre partie du forum, je le lirai et essayerai de vraiment me pencher dessus plus tard car là je n'ai pas trop trop le temps donc ne tkt pas si tu me voies poster d'autres messages et ne pas répondre à ce très long message tout de suite

Bonsoir,

A brûle pour point, je n'ai pas de démonstration via les congruences de façon formelle. Mais pour faire simple, il faut effectuer sur chaque terme une congruence modulo 10 lorsqu'on n'a pas de multiple de 10. Et dès qu'on a un multiple de 10 qui apparaît, on considère la congruence modulo 9 ce qui permet d'éviter de multiplier par 0 (sinon tout serait nul ).

C'est ce que j'avais fait dans cette démarche lorsque je disais que "j'enlevais" les 0 supplémentaires, je les remplaçais par 1 tout simplement. Par exemple 20 est congru à 2 modulo 9, ....

Voilà, une démarche plus algorithmique en quelque sorte pour effectuer les choses. Ce qui peut se réécrire comme ceci:

Initialiser a <- nombre à tester
Initialiser b <- le reste de la division euclidienne de a par 10
Si b=0
Alors r <- le reste de la division euclidienne de a par 9
Sinon r <- b
Afficher b

Voilà quelques idées pour formaliser cela de façon algorithmique (ce n'est sans doute pas ultra rigoureux par rapport à la définition donnée en seconde actuellement mais ceci est bien un algrothime qui me sort ce que je souhaite faire c'est à dire le reste par la bonne congruence).

Bonne continuation!

Bon, j'ai retenté "par hasard" cet exo tout à l'heure, et j'ai enfin trouvé un solution satisfaisante.

En gros : pour avoir accès au dernier chiffre non nul, j'ai commencé par enlever tous les chiffres et nombres qui produisaient des zéro : à savoir 10, 20, 30, ..., 90, puis les "couples" qui se terminent par 2 et 5 à savoir : 2 et 5, 12 et 15, 22 et 25, ..., 92 et 95.

Après j'ai enlevé ceux qui n'influançaient pas le dernier chiffre, soit ceux qui se terminent par 1.
Donc au final il me reste : 3, 4, 6, 7, 8, 9, 13, 14, 16, 17, 18, 19, ..., 93, 94, 96, 97, 98, 99.

Donc comme moi c'est le dernier chiffre de ce nombre qui m'intéresse, je vais prendre juste les chiffres des unités de chacun des nombres. Donc en gros le dernier chiffre non nul de 100! c'est le dernier chiffre du nombre :

A = (3 * 4 * 6 * 7 * 8 * 9)¹⁰

soit A = (2⁶ * 3⁴ * 7)¹⁰

or 2⁶ = 64 ≡ 4 [10]
3³ ≡ 7 [10] donc 3⁴ ≡ 3*7 ≡ 1 [10]
7 ≡ 7 [10]

donc 2⁶ * 3⁴ * 7 ≡ 4 *1*7 ≡ 28 ≡ 8 [10]

d'où A ≡ 8¹⁰ ≡ 2¹⁰*2¹⁰*2¹⁰ ≡ 4*4*4 ≡ 64 ≡ 4 [10]

Le dernier chiffre non-nul de 100! est donc un 4

Bonsoir,

Ce raisonnement a déjà été donné et est toujours faux en fait.

90*20=180 et le chiffre 8 rentre en compte car il est différent de 1 par exemple! Donc on ne peut pas enlever les chiffres se terminant par 0 de façon brute. ET c'est la même remarque pour les nombre produisant des 0.

En effet, 2*5=10 donc ne contribue pas pour le dernier chiffre. Cependant 12*15=180 et ici encore le 8 contribue pour le dernier chiffre.

Tu as donc fait la même erreur de raisonnement que MouadoS dans son premier message en page 1.

Le résultat est juste mais comme on le sais bien en logique si l'hypothèse de départ est fausse on peut aussi bien trouver quelque chose de faux comme quelque chode de vraie en fin de course.

En espérant que ton erreur sera plus visible ainsi.

Bon courage!

bonsoir,
vos explications m'ont paru très longues et je ne les ai pas lues en entier (ce n'est pas bien)
voici ma méthode, dites-moi s'il y a une faille dans le raisonnement, merci

de 1 à 100,
il y a 10 nombres ayant pour unité 1, leur produit est congru à 1[10], (ou 10 nombres que l'on peut éliminer)
il y a 10 nombres ayant pour unité 2, leur produit est congru à 2^10 soit 4[10]
il y a 10 nombres ayant pour unité 3, leur produit est congru à 3^10 soit 9[10]
il y a 10 nombres ayant pour unité 4, leur produit est congru à 4^10 soit 6[10]
il y a 10 nombres ayant pour unité 5, leur produit est congru à 5^10 soit 5[10]
il y a 10 nombres ayant pour unité 6, leur produit est congru à 6^10 soit 6[10]
il y a 10 nombres ayant pour unité 7, leur produit est congru à 7^10 soit 9[10]
il y a 10 nombres ayant pour unité 8, leur produit est congru à 8^10 soit 4[10]
il y a 10 nombres ayant pour unité 9, leur produit est congru à 9^10 soit 1[10]
il y a 10 nombres multiple de 10, leur produit privé des zéros de fin est congru à 8[10]
en multipliant les résultats
1x4x9x6x5x6x9x4x1x8, j'obtiens 1866240 soit 4 comme dernier chiffre non nul

Bonsoir!

Ce raisonnement est excellent !!! Bien plus algorithmique que celui que j'ai proposé et en plus très intuitive.

Franchement rien à redire!

Merci pour cette nouvelle explication qui éclaircira encore les sceptiques vu que tu n'a pas oublier le reste des multiple de 10 qui sont souvent enlevé à tord.

Bonne continuation!

ps: j'ai fusionné les sujets pour une meilleur clarté.