Discussion :

[laurent_ott]

Bonjour.
Je vous sollicite pour m'aider à résoudre ce problème : (10a x 10b) + 10a + 10b = 563 250
Comment trouver que "a" vaut 48 et "b" vaut 117 (ou l'inverse) ?
Ou, si c'est plus simple, que a x b = 5 616 ?

Merci d'avance pour votre aide.
Laurent.

[WhiteCrow]

Bonjour,
Comme il y a une autre solution entière triviale : (56325,0) tes conjectures sont fausses, on n'a pas forcément ab=5616.

Sinon, en partant du principe que l'on cherche les solutions entières positives, et en posant sans perte de généralité 0≤b≤a :
10ab+a+b=56325
⇒ 10b²+2b ≤ 10ab+a+b = 56325
⇒ -75 ≤ b ≤ 75
tu testes les 151 possibilités et tu trouves les deux solutions entières.

[Pierre Fauconnier]

Salut.

Perso, je suis étonné qu'on pose sans perte de généralité 0≤b≤a (=> b positif ou nul) puis que l'on cherche b dans l'intervalle [-75;75]

[WhiteCrow]

Je partais du principe que l'on cherchais les solutions entières positives. Du coup c'est vrai qu'on a que 76 tests à faire.
Sinon pour toutes les solutions entières, la partition est |b|≤75≤|a|.

[laurent_ott]

Bonjour.
Voici ce que j'ai compris : (10a x 10b) + 10a + 10b = 563 250 peut être simplifié en 10 x a x b + a + b = 56 325
Donc :
b = (56 325 - a - b) / 10a
b = MOD((56 325 - a) / 10a)

Je boucle sur cette formule pour a = 1 jusqu'à 75 pour trouver b
Je vérifie chaque fois que 10 x a x b + a + b = 56 325
Ce qui est le cas quand a = 48 alors b = 117, c'est donc la solution.

Ce que je n'ai pas compris, c'est :
- comment à été calculé 75 ?
- est-ce qu'il existe une façon de faire pour éviter la force brute ?

Cordialement.

[Pierre Fauconnier]

Salut Laurent,

Avec une équation pour deux inconnues et sans être un crack en algo, je ne vois pas comment ce serait possible autrement qu'en force brute après avoir défini les contraintes , notamment en précisant une plage des valeurs possibles pour au moins une des valeurs.

[hocine]

Bonjour,
vue l'équation unique je crois que la question ''Comment trouver que "a" vaut 48 et "b" vaut 117 (ou l'inverse) ?'' est un peut de trop.
on minimisant l'équation à : ab+a+b=56325 donc la solution de boucler su a ou b de 1..nombre de solution .
bonne chance

[Pierre Fauconnier]

Je pense qu'il faut énoncer des contraintes, sinon c'est infaisable

Avec 10ab + a+ b = 56325, je poserais déjà que a et b sont positifs non nuls (car si nullité de l'un, l'autre vaut 56325). Mais ça me semble bien pauvres comme contraintes. Je suppose qu'on y ajoute que a et b sont des entiers. Malgré cela, si on commence avec b = 1 et selon le n (ici 56325), ça pourrait prendre du temps.

On peut écrire cette équation comme ceci: b = (56325-a)/(10a+1). En Excel, on trouve rapidement la première paire d'entiers




On la retrouve inversée un peu plus bas (a = 117 et b = 48), ce qui tendrait à prouver qu'il n'y a que cette paire de valeurs possibles pour des entiers positifs non nuls

@Laurent: C'est juste théorique ou tu as un besoin pratique derrière?

[laurent_ott]

Je pense que je viens de trouver comment est calculé 75 en relisant cette partie : 10b²+2b ≤ 10ab+a+b = 56325.
Racine de (56325/10).

@Laurent: C'est juste théorique ou tu as un besoin pratique derrière?

C'est théorique, en tout cas ce n'est pas pour mon boulot, mais ça permettrait de faire avancer un projet personnel.
Quant aux contraintes : a et b sont des entiers supérieurs à 1.
et n peut être un très grand nombre.

A plus.

[Pierre Fauconnier]

On pourrait aussi la résoudre avec le solveur

[laurent_ott]

On pourrait aussi la résoudre avec le solveur

J'ai pris un exemple avec des petits nombres mais l'objectif est de traiter de grands nombres, plusieurs dizaines de chiffres, donc hors de portée du solveur, ou d'Excel.
C'est un peu dans le domaine de mon tutoriel sur le Crible Quadratique.
Mais je ne suis peut-être pas dans le bon forum. Sans solution je posterai sur le forum des Mathématiques.
A Plus.

[WhiteCrow]

Je suis ptêt allé un peu vite sur ma première réponse, donc plus en détail :

Si on part de (10a x 10b) + 10a + 10b = 563 250, on simplifie par 10 pour obtenir

10ab+a+b=56325

ici on voit que l'équation est symétrique : a et b sont interchangeable, i.e. si (a,b) est une solution alors (b,a) aussi. C'est pourquoi on peut sans perte de généralité poser (arbitrairement) b≤a.
on suppose qu'on ne cherche que des solutions entières d'où la première contrainte : 0≤b.

Ensuite comme b≤a on a b²≤ab (on multiplie par b de chaque côté)
10b²≤10ab
10b²+b≤10ab+a (car b≤a)
10b²+b+b ≤ 10ab+a+b = 56325

On obtient l'inéquation :
10b²+2b-56325 ≤ 0

ici on a deux racines, l'inéquation est donc vérifiée uniquement pour les b compris entre les deux racines → -75.2 < (-1-√(563251))/10 ≤ b ≤ (-1+√(563251))/10 < 74.95
Donc on peut se limiter aux entiers tels que -75≤b<75, et comme on suppose 0≤b on obtient comme espace de recherche pour b : 0≤b<75.

On cherche donc pour quels entiers b dans [0;75[ l'expression a=(56325-b)/(10b+1) est également un entier.
Et voilà.

La démarche pour un n quelconque dans l'équation initiale est similaire. n doit être un multiple de 10 sinon pas de solutions.
Avec Δ=√(1+n), b doit être entre [ (-1-Δ)/10 ; (-1+Δ)/10 ] ou [0 ; (-1+Δ)/10 ] avec la contrainte supplémentaire 0≤b.
Les solutions doivent en plus vérifier a = (n/10-b)/(10b+1) ∈ ℕ.

[laurent_ott]

Merci WhiteCrow pour ces précisions et aussi pour le temps que tu consacres à cette discussion.

Grâce à toi j'ai mieux compris le problème.
Tu dois bien deviner que je ne suis pas très doué en mathématiques.
Reste juste à savoir si une solution hors force brute existe ?
Cordialement.

[Pierre Fauconnier]

Merci WhiteCrow pour le complément d'info

[Guesset]

Bonjour,

Même si la simplification par 10 est très tentante, on peut y résister :

10a*10b+10a+10b = (10a+1)(10b+1) - 1 = N = 563250 = A*B -1 c'est à dire A*B = 563251

Avec l'hypothèse d'entiers et que 0 < a <= b, A <= sqrt(N+1) soit 750 et comme A va de 10 en 10 (11, 21, 31...751), on retrouve les 75 tests.

On peut diminuer le nombre de tests en remarquant que 563251 n'est pas un multiple de 3 donc pas de 21, 51, 81, 111... ce qui diminue de 33 % le nombre de tests à faire.

Salutations

[Pierre Fauconnier]

Merci Guesset. J'apprécie beaucoup!!

[Flodelarab]

Bonjour

Avec une équation pour deux inconnues et sans être un crack en algo, je ne vois pas comment ce serait possible

Cette phrase est particulièrement fausse. Quand tu cherches les coefficients de Bézout, tu a une équation, deux inconnues, et une seule expression solution.
Par exemple : 47*u+43*v=1 a pour ensemble de solutions { (u,v) = (43*k+11, -12-47*k), k dans Z}.

Bonjour.
Je vous sollicite pour m'aider à résoudre ce problème : (10a x 10b) + 10a + 10b = 563 250
Comment trouver que "a" vaut 48 et "b" vaut 117 (ou l'inverse) ?
Ou, si c'est plus simple, que a x b = 5 616 ?

Merci d'avance pour votre aide.
Laurent.

Et ben alors ? On a oublié son lycée ?
Soit S = a+b et P = ab
On sait alors que S et P sont la solution d'une équation du second degré:
x^2-Sx+p=0

Mais comme 10ab+a+b=56325 alors 10P+S=56325, donc S=56325-10P
L'équation devient : x^2-(56325-10P)x+p=0
On reconnaît une équation paramétrique. On va donc discuter des solutions en fonction de P.


On cherche le signe de Delta. Vu le signe du coefficient de P^2 (positif), Delta est négatif entre les racines et positif à l'extérieur des racines. (On parle ici des racines du discriminant, bien sûr)



Comme il semblerait que x soit entier, le cas du discriminant nul ne se pose pas.


Tu veux savoir où sont les entiers ? Il faut que le discriminant reste entier, donc 100P^2-1126504P+3172505625 est un carré. Ça se complique. Mais Wolfram alpha trouve P=5616 sans sourciller. Ça doit être faisable...

y^2=100P^2-1126504P+3172505625
100y^2=10000P^2-112650400P+317250562500
(10y)^2=(100P-563252)^2 - 563252^2 +56325^2
(10y)^2 - (100P-563252)^2 = - 2253004
(100P-563252)^2 - (10y)^2 = 2*2*13*37*1171
(100P-563252-10y)((100P-563252+10y) = - 2*2*13*37*1171

Il faut factoriser en 2 éléments de même signe, mais pas forcément positifs. Les facteurs possibles sont les 24 cas suivants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1
2
4
13
26
37
52
74
148
481
962
1171
1924
2342
4684
15223
30446
43327
60892
86654
173308
563251
1126502
2253004

On comprend que la différence doit être multiple de 20. Et la somme, plus ou moins 1126504, multiple de 200.
Les quatre seuls couples qui survivent sont (P,y)=(0;56325) ou (P,y)=(5616;69) ou (P,y)=(0;-56325) ou (P,y)=(5616;-69)

Dès lors c'est gagné. Les solutions pour "x" vont donner 48 pour l'un et 117 pour l'autre, avec un P=5616.
Au moins, tu auras une méthode sans tâtonnement.

[Flodelarab]

Bon, à la réflexion, c'est même encore plus simple.

10ab + a + b = 56325
a(10b + 1) + b = 56325
10a(10b + 1) + 10b = 563250
10a(10b + 1) + 10b + 1 = 563251
(10a + 1)(10b + 1) = 563251
Il suffit de trouver les facteurs de 563251 qui terminent par 1, et prendre les dizaines.

1 563251
13 43327
37 15223
481 1171

Solutions : (0,56325) et (48;117)

Tout ça pour ça.

[laurent_ott]

Bon, à la réflexion, c'est même encore plus simple.[...]

Dommage que tu n'y aies pas pensé plus tôt, car je planche sur le message précédent depuis ce matin...
Pour tout t'avouer, j'ai fait comptabilité au lycée, et pas S, donc ça me prend un peu de temps pour comprendre.
Surtout pour retrouver 2253004 dans ta démonstration.
Mais je viens tout juste d'y arriver, et j'ai confirmé en prenant deux autres premier au hasard.
Bref, je m'y remets mais avec la formule simplifiée.

Un grand merci à toi.
Laurent.

[Guesset]

Bonjour Flodelarab,

Bon, à la réflexion, c'est même encore plus simple.
...
Il suffit de trouver les facteurs de 563251 qui terminent par 1, et prendre les dizaines.

Quand j'ai proposé de poser le problème sous la forme d'un simple produit, ce n'est pas avec le sentiment de simplifier le problème car la factorisation reste un problème difficile (NP encore). De plus utiliser la forme générale d'algorithmes de factorisation pour ensuite décimer - pour une fois c'est le bon terme - les solutions apparaît peu optimal.

Mais il est vrai qu'il est confortable de transformer un problème atypique en un problème plus standard. Cela ne le simplifie pas mais permet de bénéficier de toutes les solutions existantes.

Salut