Salut tout le monde !
Désolé, mais je n'ai pas beaucoup de temps ces derniers jours ! C'est pour ça que je ne poste pas trop d'énigmes
En voilà une petite énigme !
Dans un très grand pré, comme celui que vous voyez sur l'image d'ailleurs, y avait des petites chèvres matheuses ! C'est normal : Etilarkov est le berger !
Bon, alors qu'il était assis sur un grand banc à côté de ses petites chèvres il remarqua un truc surprenant !
Son troupeau se formait de 3 rangées d'effectifs identiques. Soudain, une vielle chèvre retardataire a rejoint le troupeau, ce dernier s'est transformé en 5 rangées toujours d'effectifs identiques! 2 minutes après, une autre chèvre est arrivée ! En rejoignant le troupeau, ce dernier se forme de 7 rangées identiques toujours au point de vue effectif. Et voilà une troisième chèvre retardataire qui arrive ! Le troupeau comporte 9 rangées d'effectifs identiques.
QUESTION 1 Quel est le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées?
Plus dur !!
La nuit même, Etilarkov rêve de ce problème là :
On avait au début un troupeau de 2 rangées. 12 chèvres qui sont venues en retard ! Mais ce qui est étonnant, c'est qu'au fur et à mesure de que chacune arrive, le nombre de rangées prenait comme valeur : 3,5,7,11,…. c'est-à-dire des nombres premiers jusqu'à 41.
QUESTION 2 Quel est le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées?
_______________________________________________
2 questions = 2 réponses
QUESTION 1
Une démonstration logique est obligatoire pour avoir son ! L'utilisation de la programmation est interdite !
QUESTION 2
Vous avez le choix entre une démonstration complète ou un programme ! L'une des deux est obligatoire ! Donner le résultat sans aucun argument vaudera un grand même s'il est juste !
_______________________________________________
Bon courage !
L'équation du premier degré px+r=0 (mod r) admet une solution unique si p est premier avec r.
Question 1: Si le nombre initial de chèvres est n=3a, après la première retardataire, 3a+1=0 (mod5) donc a=3 (mod5) a=5b+3, et n=15b+9; n+2=0 (mod7) donc 15b+11=0 (mod7) ou encore b+4=0 (mod7) donc b=3 (mod7), b=7c+3, n=105c+54. Enfin n+3=0 (mod9) donc 105c+57=0 (mod9), donc 6c+3=0 (mod9) ou 2c+1=0 (mod3) donc c=3d+1, n=315d+159. La plus petite solution correspond à d=0, soit 159+3=162 chèvres au total.
Question 2: Soit n le nombre de chèvres cherché
Nous avons donc les équations de congruence suivantes, en notant les modules entre parenthèses:
n=0 (41); n=1 (37);n=2 (31); n=3 (29); n=4 (23); n=5 (19); n=6 (17); n=7 (13); n=8 (11); n=9=2 (7); n=10=0 (5); n=11=2 (3) et n=12=0 (2). On en déduit que n est divisible par 410=2*5*41, donc n=410a. Les équations ci-dessus peuvent alors s'écrire:
3a=1 (37); 7a=2 (31); 4a=3 (29); 19a=4 (23); 11a=5 (19); 2a=6 (17); 7a=7 (13); 3a=8 (11); 4a=2 (7); 2a=2(3), dont les solutions sont:
a=25 (37); a=18 (31); a=8 (29); a=22 (23); a=16 (19); a=3 (17); a=1 (13); a=10 (11); a=' (7); a=1 (3). En combinant les deux premières, on a a=31*37b+173, et on voit que b est divisible par 17: b=17c et a=19499c+173. Donc
11c=9 (29); 18c=10 (23); 5c=14 (19) 12c=10 (13); 7c=2 (11); 4c=6 (7); 2c=2 (3), qui se résolvent:
c=14 (29); c=21 (23); c=18 (19); c=3 (13); c=5 (11); c=5 (7); c=1 (3). Là encore à partir des deux premières on déduit c=29*23d+159, et on voit alors que d est divisible par 7, 11 et 13, donc d=1001e, c=667667e+159 et il reste
7e=11 (19) et 2e=1 (3) soit e=7 (19) et e=2 (3) dont la plus petite solution est e=26. Ce qui donne c=17359501, a=338492910172 et
n=138782093170520, sauf erreur de calcul!!!
1. Il faut trouver le nombre minimal de chèvres à la fin de l'histoire. Soit X cette valeur.
On a donc :
X=2 (mod 5)
X=1(mod 7)
X=0 (mod 9)
On applique le théorème des restes chinois.
M= 5*7*9=315
M1 = 63, M2=45 et M3=35
2*63 = 1 (mod 5)
5*45 = 1 (mod 7)
9*35 = 1 (mod 9)
X=(2*126) + (1*225)=252+225 = 477 modulo (315)
X= 162 chèvres
2. Si on applique le même théorème cela nous donne des calculs …déments.. !
Voici le programme Matlab qui m'a permis de trouver la solution.
On cherche les valeurs par incrément, en augmentant le « pas de recherche » (produit des nb premiers précédents) à chaque étape. Le résultat est instantané.
Le résultat est : X= 138 782 093 170 520 chèvres
Programme :
function tmp()
nombrePremier=[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41];
N = 12;
% Solutions pour 0 mouton en plus
solution(1) = 2;
produitNbPremiers(1) = 2;
for moutonsEnPlus = 1:N
nbMoutons = solution(moutonsEnPlus);
while ( mod(nbMoutons+moutonsEnPlus, nombrePremier(moutonsEnPlus)) ~= 0 )
nbMoutons = nbMoutons + produitNbPremiers(moutonsEnPlus);
end
solution(moutonsEnPlus+1) = nbMoutons;
produitNbPremiers(moutonsEnPlus+1) = produitNbPremiers(moutonsEnPlus) * nombrePremier(moutonsEnPlus);
[moutonsEnPlus, vpa(nbMoutons+moutonsEnPlus)]
end
return
et l'affichage
ans = [ 1, 3.]
ans = [ 2, 10.]
ans = [ 3,161.]
ans = [4, 792.]
ans = [5, 793.]
ans = 6, 211004.]
ans = 7, 5316105.]
ans = 8, 34415176.]
ans = 9, 703693787.]
ans = 10, 194794490688.]
ans =11, 5208806743939.]
ans =12, 138782093170520.]
bonjour Monrow
premier problème : 162
soit x le nombre de chèvres au début
x, 2x et 2x-3 sont divibles par 3
x+1, 2x+2 et 2x+2-5 sont divisibles par 5
x+2, 2x+4 et 2x+4-7 sont divisibles par 7
x+3, 2x+6 et 2x+6-9 sont divisibles par 9
le dernier terme de chaque trio est 2x-3, il est divisible par 3, 5, 7, 9 donc par 315 et doit être impair
donc 2x-3 est au minimum 315; 2x = 158; x = 159
deuxième problème
il y a 138 782 093 170 520 chèvres
le programme suivant donne la solution pour autant que le système supporte d'aussi grands nombres entiers
dim p(12)
p = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}
'équivaut à p(1) = 3 : p(2) = 5 etc
produit = 2 : solution = 2
for i = 1 to 12
while (solution + 1) mod p(i) <>0
solution = solution + produit
endwhile
solution = solution + 1
produit = produit * p(i)
next (i)
print solution
en pratique
chaque fois qu'on arrive à un palier divisible par les n premiers nombres premiers, on ajoute 1 et on calcule le modulo (ma) de ce palier + 1 par rapport au nombre premier suivant (ps)
on calcule aussi le modulo (mb) du produit (pr) des n premiers nombres premiers par rapport à ce même (ps)
on ajoute à ma autant de fois mb qu'il faut pour arriver à un résultat divisible par (ps), soit f fois
le palier suivant est donc palier + 1 + (f*pr)
cela marche très bien avec la calculatrice de Windows
si les chèvres se répartissaient sur les terres émergées, elles occuperaient environ un mètre carré chacune
Ma solution n'est peut-être pas logique à tes yeux mais elle l'est aux miens. elle est cependant assez longue. Dans la question je note a, b, c, et d, les nombre de rangées avec resp. 3, 5, 7, et 9 chèvres. N est le nombre total de chèvres. On a donc N = 9d = 7c+1 = 5b+2 = 3a+3.
je ne pense qu'on puisse utiliser dans ce cas un simple PPCM :/ donc ma solution est .. calculatoire est fait appelle à la résolution d'équation diophantienne successives dont la première est :
9d = 7c+1 ce qui donne d = 4+7x et c = 5+9y on continue et on obtient d = 3+5z et b = 5+9w (x, y, z, w étant des entier naturels). Enfin la dernière équation ne sert à rien car 3a+3 = 3(a+1) = 9d .
En combinant les deux premiers systèmes on obtient un nombre 162 chèvres (d=18, c=23, et b=32) calcul fait à la main :/
Toujours en reprennant ce principe (avec des modulos) mon programme pour la seconde question est assez simple : on boucle sur un indice (i) jusqu'à ce que ce dernier 42 divise i (i modulo 42 = 0), que 37 divise i-1, .... 5 divise i-10, 3 divise i-11 et 2 divise i-12. Au final cela donne (testé sous matlab):
Ce nombre étant nécessairement multiple de 41 ma boucle s'incrémente par pas 41 (ce qui considérablement les calculs)
stop=0;
i=41;
while stop==0
i=i+41;
if(mod(i-12,2)==0 && mod(i-11,3)==0 && mod(i-10,5)==0 && mod(i-9,7)==0 && mod(i-8,11)==0 && mod(i-7,13)==0 && mod(i-6,17)==0 && mod(i-5,19)==0 && mod(i-4,23)==0 && mod(i-3,29)==0 && mod(i-2,31)==0 && mod(i-1,37)==0 && mod(i,41)==0)
stop=1;
end
end
On peut enlever éventuellement le mod(i,41)==0 de la boucle car on incrémente par pas de 41 en commencant à 41, c'est donc toujours le cas, mais je le laisse par souci pédagogique. Je ne pense pas que la condition (le gros If) soit simplifiable car ce sont des nombres premiers que l'on utilise ... :/
Mon résultats est donc :
> 1963492829 (pas encore terminé)
(attention c'est très long à calculer, même si c'est 41x plus rapide qu'en incrémentant de 1 à chaque fois
Bonsoir,
QUESTION 1 :
Si x est le nombre initial de chèvres
x est divisible par 3, x+1 divisible par 5, x+2 divisible par 7 et x+3 divisible par 9
ce qui se traduit par le système suivant :
( x 0 [3] condition inutile car contenue dans la 4ème équation )
x 4 [5]
x 5 [7]
x 6 [9]
Je commence par résoudre le sous-système constitué des deux premières équations :
x 4 [5]
x 5 [7]
(5;7)=1 (i.e. 5 et 7 sont premiers entre eux) donc, d'après Bezout,
il existe (u,v) tel que 5u+7v=1
(u,v)=(3;-2) convient
on en déduis alors une solution particulière x0=553+47(-2) 19 [35]
Reste alors à résoudre le système équivalent :
x 19 [35]
x 6 [9]
De même, (35;9)=1 et d'après Bezout (u,v)=(-1;4) vérifie 35u+9v=1
d'où finalement x0 = 635(-1)+1994 474 [315]
soit encore x 159 [315].
La plus petite solution est donc x=159, ce qui donne 162 chèvres après l'arrivée des trois retardataires.
INTERLUDE :
J'ai commencé hier soir à chercher une solution « à la main »,
mais devant la grandeur des nombres je me suis ensuite tourné vers la programmation
( du genre bourrin : une boucle si x+12 mod 41 = 0, si x+11 mod 37 = 0… hideux ! )
mais là encore je n'ai pas été fichu de contourner la grandeur des nombres
( en Pascal, je ne dispose que d'entiers longint largement insuffisant et les fonctions mod ou int refusent obstinément de s'appliquer à des nombres non entiers… grrrrr ! )
Je n'ai pas eu le courage de programmer la méthode ci-dessous (Bezout…) parfaitement algorithmique mais que me renvoie sur des grands nombres encore !
Enfin, j'ai pris mon courage à deux mains pour faire aboutir les dernières étapes de la résolution (sur le même modèle que la 1).
QUESTION 2 :
La divisibilité des entiers de x à x+12 par les nombres premiers de 2 à 41 se traduit par :
0<i<12 x pi+1-i [pi+1] où pi est le i-ème nombre premier
(12) x 29 [41]
(11) x 26 [37]
(10) x 21 [31]
(9) x 20 [29]
(8) x 15 [23]
(7) x 12 [19]
(6) x 11 [17]
(5) x 8 [13]
(4) x 7 [11]
(3) x 4 [7]
(2) x 3 [5]
(1) x 2 [3]
(0) x 0 [2]
J'ai alors résolu des sous-systèmes, des conditions les plus restrictives aux plus larges.
(12) x 29 [41]
(11) x 26 [37]
(41;37)=1, d'après Bezout, (u,v)=(-9;10) d'où x=26x41x(-9)+29x37x101136 [1517]
puis j'ajoute les autres équations une à une
x 1136 [1517]
x 21 [31]
(1517;31)=1, d'après Bezout, (u,v)=(15;-734) d'où x=15172115+113631(-734) 23891 [47027]
et ainsi de suite… oh puis non ! comme j'ai tout fait (à la main) vous aurez la totale !
x 23891 [47027]
x 20 [29]
(u,v)=(-8;12973) puis x 164972 [1363783]
x 164972 [1363783]
x 15 [23]
(u,v)=(11;-652244) puis x 16530368 [31367009]
x 16530368 [31367009]
x 12 [19]
(u,v)=(5;-8254476) puis x 204732422 [595973171]
x 204732422 [595973171]
x 11 [17]
(u,v)=(3;-105171736) puis x 204732422 [10131543907]
( jusqu'ici une calculette fait l'affaire, ensuite j'ai eu recours à wims )
x 204732422 [10131543907]
x 8 [13]
(u,v)=(-3;2338048594) puis x 91388627585 [131710070791]
x 91388627585 [131710070791]
x 7 [11]
(u,v)=(-5;59868213996) puis x 1145069193913 [1448810778701]
x 1145069193913 [1448810778701]
x 4 [7]
(u,v)=(-1 ;206972968386) puis x 6940312308717 [10141675450907]
x 6940312308717 [10141675450907]
x 3 [5]
(u,v)=(-2;4056670180363) puis x 37365338661438 [50708377254535]
x 37365338661438 [50708377254535]
x 2 [3]
(u,v)=(1;-16902792418178) puis, un dernier Bezout
(assez costaud : 50708377254535x2x1+37365338661438x3x-16902792418178 = 140772789925831856582915913 )
donne enfin x 138782093170508 [152125131763605]
Le résultat proposé étant déjà pair la dernière condition est inutile.
Ainsi, x 138782093170508 [304250263527210]
La plus petite valeur est donc 138782093170508, soit 138782093170520 chèvres à la fin.
Par ailleurs, cette démonstration permet en outre de déterminer toutes les solutions…
( la prochaine est 138782093170508+304250263527210=443032356697718, soit 443032356697730 chèvres… )
Merci pour l'énigme.
(j'aurais bien mis quatre étoiles pour les calculs...)
Vérification: 138782093170508/2= 69391046585254
(138782093170508+1)/3 = 46260697723503
(138782093170508+2)/5 = 27756418634102
(138782093170508+3)/7 = 19826013310073
(138782093170508+4)/11 = 12616553924592
(138782093170508+5)/13 = 10675545628501
(138782093170508+6)/17 = 8163652539442
(138782093170508+7)/19 = 7304320693185
(138782093170508+8)/23 = 6034004050892
(138782093170508+9)/29 = 4785589419673
(138782093170508+10)/31 = 4476841715178
(138782093170508+11)/37 = 3750867382987
(138782093170508+12)/41 = 3384929101720
PS: Si quelqu'un a une solution à mon problème de limitation d'entiers (Pascal) ou a le courage de programmer cette méthode, je suis preneur !
Bonjour Monrow et merci d'être revenu dans l'île.
Et en plus avec une belle énigme.
Ce qui m'étonne c'est que le berger se soit endormi en comptant des chèvres: d'habitude, on utilise plutôt les moutons.. Enfin bref!
Question1:
Il s'agit de trouver 4 entiers consécutifs (les effectifs successifs du troupeau) qui soient respectivement multiples de 3,5,7 et 9.
En fait, il suffit de trouver 3 entiers consécutifs multiples de 5,7 et 9 . Le dernier étant multiple de 3, celui qui est 3 rangs avant lui est automatiquement multiple de 3.
Les multiples de 5 sont 5,10,15,20,25.. Les nombres qui les suivent sont 6,11,16,21,26.. Le premier qui est suivi d'un multiple de 7 est 20. Pour retrouver cette circonstance favorable il faut ajouter à 20 un multiple de 5 et à 21 un multiple de 7. Mais, pour maintenir un écart de 1, il faut que ce nombre ajouté soit le même dans les deux cas, donc un multiple de 35.
La suite des multiples de 5 intéressants est donc:
20,55,90,125,160,.. Ceux qui les suivent à deux rangs derrière sont: 22,57,92,127,162, qui est multiple de 9.
La réponse attendue est donc 162
Vérification: en prenant un effectif initial de 158 chèvres, on vérifie que ça marche.
Question 2
On généralise immédiatement la question 1.
Le premier x multiple de 2 tel que x+1 soit multiple de 3 est 2. Les suivants sont 8,14,20,26..
Le premier x tel que, en plus, x+2 soit multiple de 5 est 8. Les suivants sont 38,68,98,128,158,..(on ajoute 30=2x3x5).
Le premier x tel que, en plus, x+3 soit multiple de 7 est 158. Pour les suivants, il faut ajouter 2x3x5x7 un certain nombre de fois.
Pour chaque x obtenu, il faut tester la divisibilité de x+4 par 11.
Ca devient pénible. J'ai écrit un petit programme avec Maple (mais n'importe quelle calculatrice programmable devrait faire l'affaire): une boucle extérieure où le compteur varie de 1 à 12; une boucle intérieure où l'on ajoute 2x3x5 .. jusqu'à obtenir la divisibilité souhaitée.
J'ai fabriqué au préalable la liste des nombres premiers et la liste des 2x3,2x3x5..
J'arrive ainsi à l'effectif final demandé de 138782093170520
Heureusement, c'était un rêve!
Remarque: on pourrait utiliser des résultats d'arithmétique plus sophistiqués (Euclide et Bézout) mais il me semble que cela ferait autant de calculs (même plus); en plus, il faut songer aux jeunes mathiliens qui ne les ont pas encore étudiés.
Un tout grand merci à Monrow pour cette énigme, j'ai pris un pied d'enfer à cogiter dessus...
Question 1
Le système d'équations est le suivant, n étant le nombre de chèvres initial:
(1):
(2):
(3):
(4):
Pour résoudre ce type de système, je crois qu'il vaut mieux s'attaquer en priorité aux équations de module le plus élevé.
Pour calculer la taille du troupeau en posant N=nombre final de chèvres, le système devient:
(4):
(3):
(2):
(1):
Remarque : les équations (1) et (4) sont potentiellement dangereuses, les modules de ces deux équations n'étant pas premier entre eux!
Résolvons:
(4): N=9.i où i est entier
Introduisons la nouvelle forme de N dans l'équation (3)
(3):
(3): solution i=7.j+4
(3): N=9.(7.j+4)
Introduisons la nouvelle forme de N dans l'équation (2)
(2):
(2):
(2): solution j=5.k+2
(2): N=9.(7.(5.k+2)+4)
Introduisons la nouvelle forme de N dans l'équation (1)
(1):
(1):
(1): et on s'aperçoit que l'on s'en tire bien!
La solution générale de l'énigme pour la question 1 est N=9.(7.(5.k+2)+4).
Le nombre minimal de chèvres qu'il y avait à la fin de l'histoire est donc 9.(7.(5.0+2)+4)=.
Question 2
Pour le troupeau rêvé par Etilarkov, le système d'équations est le suivant(N=nombre final de chèvres).
( 0):
( 1):
( 2):
( 3):
( 4):
( 5):
( 6):
( 7):
( 8):
( 9):
(10):
(11):
(12):
Dans ce cas-ci, toutes les équations ont un nombre premier pour module. Pas de danger de tomber sur une incompatibilité donc.
La méthode utilisée pour la question 1 est d'application.
A chaque étape, il faut résoudre une équation de la forme
où
Ces coefficients sont astronomique! On peut réduire les coefficients et en les remplacant par et .
On utilise les formules
pour éviter de charrier des nombres astronomiques.
Pour 'automatiser' la méthode, je me suis bricolé l'abaque suivant dans une feuille de calcul ( copier/coller LaTeXé ):
Voici une saisie après résolution des équations (0),(1) et (2)
Dans la colonne 1 apparaît le nombre de chèvres (fin->début) du troupeau [Calcul]
Dans la colonne 2, le nombre de chèvres qui sont soustraites à l'étape i par rapport au troupeau final [Donnée]
Dans la colonne 3, le nombre de rangs que forment les chèvres à l'étape i [Donnée]
Dans la colonne 4, initialisation pour le calcul du tableau à droite [Constante]
Le tableau (entre les lignes de séparation) situé à droite est construit ainsi:
L'entête au dessus du tableau reprend les rangs comme dans la colonne 3
La ligne encore au dessus () reprendra les racines des équations .
Attention, la racine de l'équation de module sera placé au dessus du module
Les cellules dans le tableau sont calculées suivant
La colonne 'A' reprend la diagonale du tableau càd les coefficients A de l'équation
La colonne 'B' donne le coefficient de l'équation: .
Enfin la dernière colonne donnera la racine de l'équation formée par avec les coefficients A et B() calculés dans les deux cellules qui précèdent.
Cette racine est calculée à l'aide de la fonction suivante (désolé, c'est du VBA...):
Bonjour Monrow,
1)le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées
Soit n le nombre de chèvres à la fin de l'histoire n=
n=9x
n-1=7y
n-2=5z
n-3=9x-3=3(3x-1)
9x-7y=1 ,résolution d'équations diophantiennes
9*4-7*5=1
soit l , m
x= 7l+4
9x-5z=2
9*3- 5*5=2
x= 5m+5
7l+4= 5m+5
7l-5m= -1
l= 5k+7 avec k=0 pour avoir la valeur minimale
l=7
n=9x=(7*7+4)*9=477
2)le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées est
On trouve facilement que n doit se terminer par 0 donc divisible par 41,par 2 et par 5
(n-2) se termine par 8 et est divisible par 3 ,(comme n-5;n-_ et n-11 )donc n-2 est divisible par 31 et 3 soit 93
n=410x ;n-1=37y ; n-2=93z ; n-3= 29t ;n-4= 23u ;n-5= 19 v; n-6=17 w ;n-7= 13 h n-8=11i et n-9=7j
on résout plein d'équations diophantiennes
410x - 7j=9==>x=7a+4 ; 410x-11i=8==> x= 11b+10 ; 410x-13h=7==> x= 13c +14 ; 410x-17w=6==> x=17d+3; 410x-19v=5==>x=19e+16; 410x- 23u=4==> x= 23f+22; 410x- 29t=3==> x=29g+8; 410x-93z=2==> x=93*l+49 et 410x-37y=2==>x=37m+25
ensuite encore des équations diophantiennes...
7a+4=11b+10==>b=7k+2 on reporte b dans 11b+10=13c+14==>c=7*11k+31 on reporte c dans 13c+14=17d+3==>d= 7*11*13k+201
on reporte d dans 17d+3=19e+16==>e=7*11*13*17k+12718 on reporte e dans 19e+16= 23f+22==>f=7*11*13*17*19k+66736
on reporte f dans 23f+22= 29g+8==> g= 7*11*13*17*19*23k+4412215 on reporte dans 29g+8=93*l+49==>l=7*11*13*17*19*23*29k+189205655 on reporte dans 93*l+49=37m+25 ==>m=9148457031 (k=0 pour obtenir valeur minimale)
n= (37*9148458031 +25)*410= 138 782 093 170 520
Bonjour,
bon je me lance....
QUESTION 1
Je pose C nombre de chèvre initial.
3 rangées soit C/3 = p avec p
5 rangées avec 1 chèvre de plus soit (C+1)/5 = q avec q
p = 1 C = 3p = 3 q = (C+1)/5 = 4/5
p = 2 C = 6 q = 7/5
d'ou pour p = 1 on a q = 3/5 ce qui donne une périodicité de 3 entre les différents q entier.
p = 3 C = 9 q = 2 OK
7 rangées avec 2 chèvres de plus soit (C+2)/7 = r avec r
q = 2 C = 5q - 1 = 9 r = (C+2)/7 = 11/7
q = 2+3 = 5 C = 24 r = 26/7
d'ou pour q = 3 on a r = 15/7 ce qui donne une périodicité de 15 entre les différents r entier.
q = 5+3 = 8 C = 39 r = 41/7
q = 8+3 = 11 C = 54 r = 8 OK
9 rangées avec 3 chèvres de plus soit (C+3)/9 = s avec s
r = 8 C = 7r - 2 = 54 s = (C+3)/9 = 57/9
r = 8+15 = 23 C = 159 s = 162/9 = 18 OK
CONCLUSION :
Le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées est de 159 + 3 soit :
QUESTION 2
J'ai programmé une macro en Visual Basic sous excel sur le principe de la résolution manuelle précédente avec :
k = C/2 ; l = C/3 ; m = C/5 ; n = C/7 ; o = C/11 ; p = C/13 ; q = C/17 ; r = C/19 ; s = C/23 ; t = C/29 ; u = C/31 ; v = C/37 ; w = C/41
y est la périodicité
x est la partie décimale de k, l, m, n, o, p, q, r, s, t, u, v ou w et permet de tester s'ils sont entiers.
Les différentes valeurs de C à chaque étape sont affichées dans les cellules.
LE PROGRAMME :
de l'enigme on a
R £ IN*
K £ IN*
V £ IN*
S £ IN*
r,v,s,k Sont le nombre de chevres dans une rangé tout au long de l'histoire
k : au debut
r : a l'arriver de la deuxieme chevre
v : de la 3eme
S : de la 4eme (la fin)
Donc on peux dire que le nombre de chevre qu'on a est:
n=9s = 7v+1
7v=5r+1
5r=3k+1
k £ IN* donc k £ {1,2,3,4,......}
pour que n £ IN* on a : 9s £ IN* => 7v+1 £ IN* => 5r+2 £ IN* => 3k+1 £ IN*
Donc pour que v £ IN il faut que r prend {2,5,8,11,14,....}
et pour que s £ IN il faut que v prend {8,13,18,23,....}
et pour que n £ IN il faut que s prend {18,25,32,....}
pour que (k,r,v,s,n)£ IN5 il faut que s=18 => n= 162
Donc la reponse 1 est 162
La reponse de la deuxieme :
bon a la deuxieme c le meme troupeau sauf qu'au debut on avait +3 et au deuxieme on a +12 donc le nombre au deuxieme on a n2=162+(12-3)= 171
j'espere que j'ai pue vous communiquer mon analyse ^^', et aussi que jai la bon reponsse ^^ : donc
Rep1 = 162
Rep2 = 171
Bon je vais tenter mais vu que je suis pas un as de la démonstration on verra
QUESTION 1 Quel est le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées?
Voila le résultat auquel je suis arrivé apres quelques essais:
3x53=159
5x32=160
7x23=161
9x18=162
Donc selon moi le nombre minimal de chevres qu'il y avait a la fin est 162.
QUESTION 2 Quel est le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées?
Bon celui la j'ai eu un peu plus de mal. Je dirai que la réponse est:
138782093170508 + 12 = 138782093170520
Ca fait donc un paquet de moutons
Pour en arriver la j'ai fait un petit programme en visual basic. Le code est disponible ci-dessous. Pour information je n'ai pas laissé les memes parametres pendant toute l'opération, étant donné la grandeur du résultat. J'ai rapidement modifié l'incrementation de la valeur de test et d'autres détails mais la base du code est la:
Bonjour.
QUESTION 1 :
On cherche un entier N tel que
N divisible par 3
N+1 divisible par 5
N+2 divisible par 7
N+3 divisible par 9
RQ 1 : si N+3 est divisible par 9, alors N est divisible par 3
N+3=9k -> N=3(3k-1)
Donc il suffit de trouver N tel que
Si N et N' sont solutions, alors
La différence N' - N est divisible par 5, 7 et 9. Ces trois nombres sont premiers entre eux, donc
N' - N est divisible par 5*7*9=315
Donc si on trouve une valeur N qui satisfait à la relation, il suffira de prendre son reste dans la division euclidienne par 315 pour avoir la valeur minimale.
Or 7 et 5 sont premiers entre eux (Bezout) :
Toutes les valeurs qui vérifient cette relation sont de la forme
Nous obtenons donc
9 et 35 sont premiers entre eux (Bezout)
Nous avons donc
est de la forme
Et pour finir
La question demandait le nombre minimal de chèvres après l'arrivée de la dernière retardataire, c'est à dire N+3 = 792 modulo 315 = 162
Pour vérification :
N = 159 = 0 [3]
N+1 = 160 = 0 [5]
N+2 = 161 = 0 [7]
N+3 = 162 = 0 [9]
Question 2 :
Nous cherchons N vérifiant les contraintes ci-dessous
N = 0 [2]
N+1 = 0 [3]
N+2 = 0 [5]
N+3 = 0 [7]
N+4 = 0 [11]
N+5 = 0 [13]
N+6 = 0 [17]
N+7 = 0 [19]
N+8 = 0 [23]
N+9 = 0 [29]
N+10 = 0 [31]
N+11 = 0 [37]
N+12 = 0 [41]
Deux résolutions sont proposées :
Soit i variant de 1 à 12
soit à l'étape i, le couple (L,P) qui vérifie N=L [P]
soit à l'étape i, le nombre premier q, alors N+i=0 [q]
Soient c et d tel que N=L+Pc, N+i=qd
Donc L,P,q vérifient : L+i=qd-Pc
P et q premiers entre eux, il existe (a,b) tel que 1=qa-Pb
alors il existe e tel que d=(L+i)a+Pe
donc N=-i+q(L+i)a [qP]
La difficulté de cette approche est que la recherche au rang 12 nous mène à des produits qui dépassent largement avec les opérations disponibles les capacités des entiers signés 64 bits dont la valeur maximale est 2^63-1=Long.MaxValue.
Alors pour effectuer les modulo, on utilise la propriété suivante : (a+b)%M = ((a%M)+(b%M))%M
Si un produit m*n risque de dépasser la capacité d'entier long, on décompose m et n en sommes de nombres tels que leurs produits ne risquent pas d'opérer ce dépassement. On utilise pour cela l'entier 2^31-1=Integer.MaxValue
Les calculs donnent les valeurs suivantes :
N=2 [6]
N=8 [30]
N=158 [210]
N=788 [2 310]
N=788 [30 030]
N=210 998 [510 510]
N=5 316 098 [9 699 690]
N=34 415 168 [223 092 870]
N=703 693 778 [6 469 693 230]
N=194 794 490 678 [200 560 490 130]
N=5 208 806 743 928 [7 420 738 134 810]
N=138 782 093 170 508 [304 250 263 527 210]
Donc la solution (nombre minimal de chèvres après que la dernière soit arrivée) :
N+12=138 782 093 170 520
Deuxième approche, beaucoup moins gourmande en calculs :
Pour trouver la valeur -i+q(L+i)a [qP] à partir de L [P], on utilise les remarques suivantes :
On note P0=2, P1=3, P2=5, ... Pj= jième nombre premier dans cette série
Pour j de 0 à 12
N + j = 0 [Pj]
Toute solution N' vérifie N'+j-(N+j)=0 [Pj].
Donc N'-N divisible par Pj
Or les Pj sont des nombres premiers, donc en particulier premiers entre eux.
Donc N'-N divisible par le produit des Pj
N' = N + k*(produit de 0 à i-1 Pj)
si N' vérifie aussi N' + i = k'*Pi, alors on doit avoir
N' + i = N + k*(produit des Pj de 0 à i-1) + i doit être divisible par Pi
A chaque étape i, on recherche une nouvelle valeur de N qui vérifie cette contrainte en faisant varier k de 0 à Pi - 1
En effet, pour les valeurs de k en dehors de cette fourchette, le modulo nous ramène à une valeur de k dans cet intervalle.
Le programme est simplissime à écrire et les résultats donnent
i=1, k=1, N=2
i=2, k=1, N=8
i=3, k=5, N=158
i=4, k=3, N=788
i=5, k=0, N=788
i=6, k=7, N=210 998
i=7, k=10, N=5 316 098
i=8, k=3, N=34 415 168
i=9, k=3, N=703 693 778
i=10, k=30, N=194 794 490 678
i=11, k=25, N=5 208 806 743 928
i=12, k=18, N=138 782 093 170 508
Evidemment, on trouve la même solution
N+12=138 782 093 170 520
Si après avoir compté tous ces moutons, notre brave berger continue à en rêver, ce deviendront alors des cauchemars.
ENIGME CLOTUREE
C'est vrai que ce n'est plus des chèvres avec ce nombre diabolique ...
Torio>> je suis désolé, mais c'est bien précisé qu'il faut trouver le nombre minimal de chèvres qu'il y avait à la fin de cette histoire dans le troupeau quand toutes les chèvres sont arrivées...
vNz>> Ta démonstration pour la première question n'a aucun sens selon moi ...
Merci de votre participation
Bonjour,
En fait il s'agit d'un Chevrier (et non d'un berger)
Il est partout ! Déjà au radar de Jamo
A+, KiKo21.
pour Mikayaou
peut-être mais j'ai oublié un ligne de calcul...
je me souviens avoir terminer par ce calcul!!!!j'aurais du attendre le lendemain , et surtout vérifier!!!!
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :