le soldat core pas d'accord (énigme : recheche justification mathématique)

[invitefbe26600]

bonjour,

je poste dans la partie maths plutôit qu'énigme car je souhaiterai avoir vos idées sur la manière de résoudre de manière rigoureuse celle-ci :
Un général souhaite faire deux régiments de ses hommes, soit par ligne de 5 soit par ligne de 13.

chercher la borne supérieur des effectifs pour lesquels ce n'est pas possible (soit N l'effectif total, trouver le plus grand entier tel que N ne puisse s'écrire 5a+13b (a,b) entiers)

de manière intuitive et par essais je pense que 47 est cette borne supérieur, et je peux ensuite le démontrer par récurrence : par contre, j'aimerai savoir s'il est possible directement de trouver la réponse de facon rigoureuse et quels outils utiliser

merci de vos suggestions

cordialement,

(ps : énigme parue dans le dernier numéro de la recherche)
-----

[invite4ef352d8]

Salut!

on peut commencer par chercher pour n donné l'ensemble des solutions de N=13*a+b*5 avec a et b dans Z et regarder en suite pour qu'elle valeur de N il n'y a pas de solution dans N...

2*13-5*5 = 1

donc 13*a+5*b = N admet pour solution particulière
(2*N)*13 +(-5*N)*b=N

et comme 5 et 13 sont premier entre eux l'ensemble des solutions de cette equation est
a=2*N-5*k
b=13k-5*N
(résolution d'equation diophantienne)

bon il reste a savoir pour qu'elle valeur de N il existe k telle que on ai simultanement 2*N-5*k>0 et 13k-5*N>0

2*N-5*k>0 => k < 2/5 * N
13k-5*N>0 => k > 5/13 * N

donc k est compris entre 5/13 et 2/5 et heuresement pour nous 5/13 < 2/5, mais de peu.

donc il existe un telle k si et seulement si il y a un entier compris entre 5/13 * N et 2/5 * N.

si 2/5 * N - 5/13 * N > 1 on est sur qu'il y a une telle solution, cela ce produit si N>65

donc il y a des solution dès que N>65. reste plus qu'a calculer 2/5 * N et 5/13 * N pour tous N entre 1 et 65 pour savoir qu'elle est le plus grand entier pour le quelle il n'y a pas d'entier entre les deux.

[invite4ef352d8]

j'oubliait : a chaque fois les inégalité etait large .

et je trouve bien que 47 est le plus grand entier à ne pas pourvoir ce mettre sous cette forme.

[invitefbe26600]

Salut!
2*13-5*5 = 1

donc 13*a+5*b = N admet pour solution particulière
(2*N)*13 +(-5*N)*b=N

et comme 5 et 13 sont premier entre eux l'ensemble des solutions de cette equation est
a=2*N-5*k
b=13k-5*N
(résolution d'equation diophantienne)

Pardonne ma grande ignorance en arithémtique, mais pourquoi recherche tu une solution particulière et qu'est ce qu'une équation diophantienne ?

(merci bcp pour ta réponse, je vais m'appliquer à la comprendre )

[A voir en vidéo sur Futura]

[invitefbe26600]

ok, c'est bon, j'ai trouvé de quoi rassasier ma curiosité, comment résoudre des équations diophantiennes. Merci encore.

[invite4ef352d8]

"qu'est ce qu'une équation diophantienne ?"

le probleme vien de la ^^


je t'explique ce point.

on appelle "equation diophantienne" une equation de la forme a*u+b*v = n (les inconus sont a,b)

on va s'interesser au cas ou u et v sont premiers entre eux (c'est notre cas ici, si il ne le sont pas, il faut soit divier par leur pgcd pour ce ramener au cas précedent, et si n n'est pas divisible par le pgcd il n'y a jammais de solution)

la methode consiste a comencer par chercher une solution particulier ao, bo, pour ca il y a des algorithmes, mais pas de formules géneral.

une fois qu'on a cette solution on considere a,b une solution quelconque alors a*u+b*v =n
a0*u + b0*v = n donc :
(a-a0)*u + (b-b0)*v = 0

(a-a0)*u = (b0-b)*v
u divise (b0-b)*v, et u est premier avec v donc (th de Gauss) u divise (b0-b) : b = b0 +k*u avec k quelconque dans Z.

on remplace dans (a-a0)*u = (b0-b)*v :

(a-a0)*u = -k*u*v; on simplifie par u et on obtiens
a-a0 = -k*v
a= a0-k*v


et réciproquement, on vérifie facilement que le couple
a0-k*v et b0 +k*u est solution quelque soit k.

c'est ce que j'ai utilisé pour résoudre 13*a+5*b=N

[invite35452583]

donc k est compris entre 5/13 et 2/5 et heuresement pour nous 5/13 < 2/5, mais de peu.

Enfin bon ce ne serait pas le cas il n'existerait aucun entier positif ne pouvant s'écrire 13xa+5xb, même pas 5,13,18