Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 16-12-2017 08:54:09

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Une somme de 3 produist

Bonjour à tous.

Pour nous changer un peu les idées.

Soit l'expression S = 2017a + 1789b + 1492c, où a,b, c sont entiers naturels non nuls.

Trouver le plus petit S qui s'exprime avec 2 triplets (a;b;c) distincts.

Trouver un S qui s'exprime avec 100 triplets distincts.

Tout ça à la main, bien entendu, laissez reposer vos machines. 

Bonne recherche

  • |
  • Répondre

#0 Pub

 #2 - 16-12-2017 19:13:34

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Une somme de 3 prdouits

Je ne détaille pas tous les petits raisonnements, mais l'idée générale de la solution.

On se ramène à rechercher (x,y,z) trois entiers >0 tels que 2017x+1789y=1492z (il faut aussi considérer les cas où c'est 2017x, ou alors 1789y qui sont tous seuls, mais ils conduisent à de moins bonnes solutions).

On résout déjà 2017x+1789y=1 dans Z avec par exemple l'algorithme d'Euclide étendu. On trouve une solution particulière x=-102 et y=115.

On résout ensuite 2017x+1789y=1492z dans Z, en multipliant la solution particulière par 1492z. Les solutions sont du type :
* x = -152184z+1789k
* y = 171580z-2017k, avec k dans Z.

Donc on recherche le plus petit z tel qu'il existe k dans N tel que -152184z+1789k>0 et 171580z-2017k>0.

Ceci fournit 152184z/1789 < k < 171580z/2017.
En supprimant la partie entière, on obtient 119z/1789 < k' < 135z/2017 : on cherche le premier z tel que ces deux quotients encadrent un entier.

La première valeur de z qui convient est 15. On en déduit k=1276, x=4 et y=8, soit finalement :

2017*5+1789*9+1492*1=2017*1+1789*1+1492*16=27678.

On obtient facilement un S qui s'exprime avec 100 triplets distincts : il suffit de multiplier 119/1789 et 135/2017 par un z suffisamment grand pour que l'écart entre eux deux contienne au moins 99 entiers.

Par exemple, avec z=241000, on calcule x = -152184z+1789k et y = 171580z-2017k pour k entre (20485000+16031) et (20485000+16130), et on en déduit 100 sommes différentes valant 359577298.

 #3 - 16-12-2017 19:31:38

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Une somme de 3 produiits

Bravo Ebichu !

J'ai eu la même démarche à une nuance près, je n'ai travaillé qu'avec les entiers relatifs, jamais de fractions.

Ce n'était pas demandé de chercher le plus petit nombre à 100 solutions, mais celui que j'ai trouvé est nettement plus petit que le tien.

 #4 - 17-12-2017 06:39:23

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

Une somme ed 3 produits

Soient [latex]\underline{u}=\begin{pmatrix}2017\\ 1789\\ 1492\end{pmatrix}[/latex] et [latex]\underline{v}=\begin{pmatrix}a\\ b\\ c\end{pmatrix}\in \mathbb{N^*}^3[/latex]

On cherche l'intersection de [latex]\mathbb{N}^3[/latex] avec le plan d'équation [latex]\underline{u}\cdot \begin{pmatrix}x\\ y\\ z\end{pmatrix}=\underline{u}\cdot \underline{v}[/latex]

Les solutions sont de la forme [latex]\begin{pmatrix}x\\ y\\ z\end{pmatrix}=\underline{v}+\underline{w}[/latex] avec [latex]\underline{w} \in \mathbb{Z}^3,\, \underline{u}\cdot \underline{w}=0[/latex]

On considère donc une base orthogonale du plan : [latex][\underline{o_1},\underline{o_2}]=[\begin{pmatrix}-1789\\ 2017\\ 0\end{pmatrix},\begin{pmatrix}1504682\\ 1334594\\ -3634405\end{pmatrix}][/latex]

Tout vecteur [latex]\underline{w}[/latex] s'écrit alors [latex]\underline{w}=d\underline{o_1}+e\underline{o_2}[/latex] avec [latex]d\in \mathbb{Z},\, e\in \mathbb{Z}[/latex] puisque les composantes des vecteurs de la base n'ont pas de facteurs premiers communs.

Application pour 2 solutions :

On chercher maintenant le plus petit scalaire [latex]\underline{u}\cdot \underline{v}[/latex] tel qu'il existe un unique vecteur [latex]\underline{w}[/latex] vérifiant [latex]\underline{v}+\underline{w}\in\mathbb{N^*}^3[/latex]

Minimiser [latex]\underline{u}\cdot \underline{v}[/latex] c'est minimiser [latex]2017a+1789b+1492c[/latex]

Soit la fonction [latex]\phi : x \mapsto \frac{|x|+x}{2}[/latex]

Alors la condition de positivité sur la solution supplémentaire [latex]\underline{v}+\underline{w}[/latex] s'écrit :
[TeX]\begin{cases}a &\geq 1+\phi(1789d-1504682e) \\ b &\geq 1+\phi(-2017d-1334594e)\\ c &\geq 1+\phi(3634405e) \end{cases}[/TeX]
Si [latex]e=0[/latex] et [latex]d>0[/latex] :
[TeX]\begin{cases}a &\geq 1+1789d\\ b &\geq 1\\ c &\geq 1\end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298+3608413d[/latex]

Elle est minimale pour [latex]d=1[/latex] ou elle vaut [latex]3613711[/latex]

Si [latex]e=0[/latex] et [latex]d<0[/latex] :
[TeX]\begin{cases}a &\geq 1\\ b &\geq 1-2017d\\ c &\geq 1\end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298-3608413d[/latex]

Elle est minimale pour [latex]d=-1[/latex] ou elle vaut [latex]3613711[/latex]

Si [latex]1789d-1504682e>0[/latex] et [latex]-2017d-1334594e<0[/latex] et [latex]e>0[/latex] :
[TeX]\begin{cases}a &\geq 1+1789d-1504682e \\ b &\geq 1\\ c &\geq 1+3634405e \end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298+3608413d+2387588666e[/latex]

Elle est minimale pour [latex]d=842[/latex] et [latex]e=1[/latex] ou elle vaut [latex]5425877710[/latex]

Si [latex]1789d-1504682e>0[/latex] et [latex]-2017d-1334594e<0[/latex] et [latex]e<0[/latex] :
[TeX]\begin{cases}a &\geq 1+1789d-1504682e \\ b &\geq 1\\ c &\geq 1\end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298+3608413d-3034943594e[/latex]

Elle est minimale pour [latex]d=662[/latex] et [latex]e=-1[/latex] ou elle vaut [latex]5423718298[/latex]

Si [latex]1789d-1504682e>0[/latex] et [latex]-2017d-1334594e>0[/latex] et [latex]e>0[/latex] :

Impossible.

Si [latex]1789d-1504682e<0[/latex] et [latex]-2017d-1334594e<0[/latex] et [latex]e>0[/latex]:
[TeX]\begin{cases}a &\geq 1 \\ b &\geq 1\\ c &\geq 1+3634405e \end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298+5422532260e[/latex]

Elle est minimale pour [latex]e=1[/latex] et [latex]d>662[/latex] ou elle vaut [latex]5422537558[/latex]

Si [latex]1789d-1504682e<0[/latex] et [latex]-2017d-1334594e>0[/latex] et [latex]e>0[/latex] :
[TeX]\begin{cases}a &\geq 1 \\ b &\geq 1-2017d-1334594e\\ c &\geq 1+3634405e \end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298-3608413d+3034943594e[/latex]

Elle est minimale pour [latex]e=1[/latex] et [latex]d=-661[/latex] ou elle vaut [latex]5420109885[/latex]

Si [latex]1789d-1504682e<0[/latex] et [latex]-2017d-1334594e<0[/latex] et [latex]e<0[/latex] :

Impossible.

Si [latex]1789d-1504682e>0[/latex] et [latex]-2017d-1334594e>0[/latex] et [latex]e<0[/latex] :
[TeX]\begin{cases}a &\geq 1+1789d-1504682e\\ b &\geq 1-2017d-1334594e\\ c &\geq 1 \end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298-5422532260e[/latex]

Elle est minimale pour [latex]e=-1[/latex] et [latex]d<662[/latex] ou elle vaut [latex]5422526962[/latex]

Si [latex]1789d-1504682e<0[/latex] et [latex]-2017d-1334594e>0[/latex] et [latex]e<0[/latex] :
[TeX]\begin{cases}a &\geq 1 \\ b &\geq 1-2017d-1334594e\\ c &\geq 1 \end{cases}[/TeX]
La somme pondérée des minorants vaut alors [latex]5298-3608413d-2387588666e[/latex]

Elle est minimale pour [latex]e=-1[/latex] et [latex]d=-842[/latex] ou elle vaut [latex]5425877710[/latex]

On en déduit en conservant la plus petite minoration, obtenue pour [latex]d=1[/latex] et [latex]e=0[/latex], le vecteur [latex]\underline{v}=\begin{pmatrix}1790\\ 1\\ 1\end{pmatrix}[/latex]

Puis [latex]\underline{u}\cdot \underline{v}=3613711[/latex] qui est donc le plus petit scalaire à pouvoir s'écrire avec deux triplets : [latex]\underline{v}=\begin{pmatrix}1790\\ 1\\ 1\end{pmatrix}[/latex] et [latex]\underline{v}+\underline{w}=\begin{pmatrix}1\\ 2018\\ 1\end{pmatrix}[/latex]

Application pour 100 solutions :

Même chose sauf que l'on considère [latex]d=99[/latex] ce qui nous mène à [latex]\underline{v}=\begin{pmatrix}177112\\ 1\\ 1\end{pmatrix}[/latex]

Puis [latex]\underline{u}\cdot \underline{v}=357238185[/latex] qui est donc le plus petit scalaire à pouvoir s'écrire avec 100 triplets : [latex]\underline{v},\,\underline{v}+\underline{w},\,\underline{v}+2\underline{w},\,...\, ,\underline{v}+99\underline{w}[/latex]

 #5 - 17-12-2017 09:46:20

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

une somme de 3 produitq

@ Sydre: approche vectorielle dans un espace 3D intéressante, malheureusement, il y a mieux comme minorant. En fait, ta solution comporte des coefficients 1, je crois que c'est de là que vient le problème.

Pour la somme 100 solutions possibles, j'ai bien plus petit, mais j'ignore si c'est le min.

 #6 - 17-12-2017 21:30:35

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 245

Une somme e 3 produits

J'ai apporté quelques modifications et je trouve maintenant des résultats bien plus petits smile

 #7 - 18-12-2017 08:22:05

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Une soomme de 3 produits

@ Sydre:
Malheureusement, ça reste encore assez loin du résultat attendu. La somme que j'obtiens pour 100 solutions est plus petite que celle que tu obtiens pour 2 solutions.
Peut être ton approche n'est elle pas la bonne, je ne sais pas trop où ça pêche dans ton raisonnement, j'ai du mal à le suivre.

 #8 - 18-12-2017 22:39:58

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,973E+3

une somme de 3 produots

La manière la plus simple, à mon avis, d'aborder le problème est de trouver des substitutions en partant d'une solution triviale.

1 solution pour 2017 + 1789 + 1492 = 5298. ( 1,1,1 )

On cherche ensuite à résoudre l'équation :

2017 x + 1789 y = 1492 z
1492 ( x + y ) + 525 x + 297 y = 1492 z
Et donc 525 x + 297 y = 1492 n
(on peut recommencer si on le souhaite.)
On trouve assez facilement une solution : x = 4 , y = 8 et n = 3.

On a donc : 4 * 2017 + 8 * 1789 = 15 * 1492 = 22380

Si on a un certain nombre de solutions pour N, on en aura donc autant pour N + 22380 , plus une obtenue par substitution.

=> pour 5298 + 22380 : (5,9,1) et ( 1,1,16 )

On peut donc déjà prévoir que pour 5298 + 99 * 22380 = 2 220 918 il y aura au moins 100 solutions


Mais, on peut aussi chercher à substituer 1789 :

De la même façon, on trouve 2017 * 119 + 1492 = 1789 * 135 autrement dit, à partir de la 17e substitution 1 , j'ai 17 * 8  = 136  coeff de 1789 en réserve. On peut donc faire la seconde.

Il y a alors 2 solutions de plus tous les 22380 et un nouvel optimum est donc

363378 + 72 * 22380 / 2 = 1 169 058 pour au moins 100 solutions

On refait la même chose avec 2017, puis avec d'autre substitutions pour lesquelles wolfram aide un peu :

On arrive à un optimum estimé de 1080229 pour 100 solutions minimum.

Et ensuite, on en a marre, donc on utilise un petit programme qui donne beaucoup plus vite un optimum par dichotomie en testant par tranche de 22380.

Le plus petit nombre pour 100 solutions est 997561.

 #9 - 19-12-2017 08:05:32

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

une somme de 3 produiys

Bien Gwen, très bon travail !

Je ne demandais pas spécialement la somme minimale pour 100 solutions, je savais qu'on pouvait trouver mieux que les 2,2 millions, mais que pour cette recherche la machine était nécessaire.

 #10 - 19-12-2017 08:09:15

enigmatus
Expert de Prise2Tete
Enigmes résolues : 0
Messages : 561

ube somme de 3 produits

Bonjour,
1) Recherche d'un petit triplet tel que : 2017*a + 1789*b + 1492*c = 0
   (a,b,c) = (4,8,-15)
2) Pour 2 triplets donnant la même somme 27678
   (1,1,16), (5,9,1)
3) Pour 100 triplets donnant la même somme 2220918
   ((1,1,1486), ....., (397,793,1)
(décalage de (4,8,-15) pour passer d'un triplet au suivant)

 #11 - 19-12-2017 11:28:30

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Une sommme de 3 produits

Bravo Enigmatus, c'est bon !

Vous pouvez lire les solutions de chacun maintenant.

Je donne la mienne pour archivage.

Merci @ tous pour vos participations.

-------------------------------------------------------------------------------------

On exprime la solution double :

1789 a + 1492 b + 2017 c = 1789 a' + 1492 b' + 2017 c'
1789 ( a - a' ) + 1492 ( b - b' ) + 2017 ( c - c' ) = 0

1789 da + 1492 db + 2017 dc = 0

On ne sait pas résoudre directement un tel système, en revanche on sait résoudre par l'algorithme d'Euclide en fixant 1 valeur, par exemple dc = -1

1789 da + 1492 db = 2017 * 1
Les couples solutions : da = -375 + 1492 k et db = 451 - 1789 k.
On cherche maintenant le min du plus grand de (da, db, dc) : On essaye le reste de 1492 / 375 et on arrive au triplet (-8,15,-4) qui est bien équilibré, dont on extrait les 2 triplets (a,b,c) et (a',b',c') :
( 1 16 1 ) et ( 9 1 5 ) qui donne la somme 27678.

Pour contrôle, on résout aussi les 2 autres options en fixant "da =-1 " puis "db =-1", qui donne le même résultat.

A partir du triplet (da, db, dc) = ( -8, 15, -4) on peut fournir tous les triplets qu'on veut : (8 k , -15 k , 4 k ).
On fixe 1 max pour k : n
Il suffit alors de fixer pour "a" la valeur : 8n+1. Les solutions pour "a' " qui en découlent seront : 8(n-1) + 1, 8(n-2) + 1,....8*1 + 1, 1. de sorte que chaque écart avec "a" donne 8k.
On fixe "c" à la valeur 4n+1, les solutions pour " c' " seront : 4(n-1) + 1, 4(n-2) + 1,.....4*1 + 1, 1. 
On fixe "b" à la valeur 1, les solutions pour " b' "  seront : -1, -15 -1, -30-1,......-15n-1.

On remarque alors que les sommes successives 1789 a + 1492 b + 2017 c, selon le nombre de solutions qu'on veut, suivent une progression arithmétique de raison 8*1789 + 4*2017 = 22380.
On remarque que si ôte 22380 à la solution double, on obtient 5298, c'est à dire 1789 + 1492 + 2017 (triplet  1 1 1 )

On a alors l'expression simple d'une somme à n + 1 solutions : 5298 + n * 22380. 

Pour avoir une somme à 100 solutions : 5298 + 99 * 22380 = 2 220 918.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete