Produit maximum pour une somme donnée

Pianiste2103 · March 2011

Titre initial : Problème ouvert

Bonjour j'ai énormément de mal avec cet exercice pouvez vous m'aider ? S'il vous plait.

Emma et Elise essaient de battre un record. Il s'agit de décomposer le nombre en une somme de nombres entiers de manière à obtenir le plus grand produit possible

Elise propose : 14 = 10 + 4 et 10 x 4 = 40

Alors Emma s'écrit : 14 = 6 + 6 + 2 et 6 x 6 x 2 = 72

Il y a donc un record a battre ...
Pouvez vous relever ce defi ?
Pourriez vous trouver une stratégie pour être toujours gagnant si on vous propose d'autres nombres ?

Merci d'avance

GreginGre · March 2011

moi j'obtiens $128$, et je pense que c'est le maximum que l'on puisse obtenir.

D'ailleurs, si $m\geq 1$ est un entier, on peut obtenir un produit égal à $2^{[m/2]}$.

A toi de jouer:

- en essayant de trouver comment j'ai trouvé 128 et si c'est le maximum

- en trouvant comment on obtient $2^{[m/2]}$.

- en essayant de voir si le maximum est effectivement $2^{[m/2]}$ ou si on peut faire mieux.

Pianiste2103 · March 2011

14 = 4+4+4+2 4*4*4*2 =128 ( c'est bien le maximum)

Mais après je ne sais plus quoi faire

bs · March 2011

Bonsoir,

14=3+3+3+3+2
et 3*3*3*3*2=162.

A fait l'objet d'une QDM en 2010 avec 2010.

Amicalement.

Pianiste2103 · March 2011

Merci et quelle serait la méthode pour d'autres chiffres ?

Pianiste2103 · March 2011

Quelle stategie puis je avoir pour être toute gagnante pour tous les chiffres

Ga? · March 2011

Bonsoir,

L'étude de la fonction $x\mapsto \left(\dfrac{a}{x}\right)^x$ doit aider.

Pianiste2103 · March 2011

La fonction quoi ? excusez moi je n'est pas compris , je ne suis qu'en 3eme .

Ga? · March 2011

C'était la fonction x donne (a/x)^x. Je ne pense pas que ce soit une approche que l'on puisse expliquer au niveau 3e, mais ça conduit à dire qu'il faut viser un découpage de l'entier a en un nombre à peu près égal à a/2,718 de morceaux égaux à 3 ou 2 (a=14, 5 morceaux : 4 fois 3 + 2; a=2010, je dirais 740 morceaux, 530 fois 3 et 210 fois 2 - bs pourra sans doute préciser)

Pianiste2103 · March 2011

D'accord merci beaucoup je vais essayer de comprendre.

Ga? · March 2011

Non, pour 2010 on a intérêt à ne mettre que des 3 : 670 fois 3 (3² vaut mieux que 2³)

Fin de partie · March 2011

On peut montrer que certaines décompositions comme somme, de 14 ne conduisent pas à un produit maximal:

Pour r compris entre 5 et 14 (strictement) si on décompose: 14=r+.... le produit correspondant sera multiple de r mais il ne sera pas optimal.

Puisque si:
r=13=2+2+2+2+2+2+1 (il y a six 2) et 2^6=64>13 et on peut remplacer 14=r+... par 14=2+2+2+2+2+2+1+...
r=12=2+2+2+2+2+2 (il y a six 2) et 2^6=64>12 et on peut remplacer 14=r+... par 14=2+2+2+2+2+2+...
r=11=2+2+2+2+2+1 (il y a cinq 2) et 2^5=32>11 et on peut remplacer 14=r+... par 14=2+2+2+2+2+1+...
r=10=2+2+2+2+2 (il y a cinq 2) et 2^5=32>10 et on peut remplacer 14=r+... par 14=2+2+2+2+2+...
r=9=2+2+2+2+1 (il y a quatre 2) et 2^4=16>9 et on peut remplacer 14=r+... par 14=2+2+2+2+1+...
r=8=2+2+2+2 (il y a quatre 2) et 2^4=16>8 et on peut remplacer 14=r+... par 14=2+2+2+2+...
r=7=2+2+2+1 (il y a trois 2) et 2^3=8>7 et on peut remplacer 14=r+... par 14=2+2+2+1+...
r=6=2+2+2 (il y a trois 2) et 2^3=8>6 et on peut remplacer 14=r+... par 14=2+2+2+...

En espérant ne pas avoir écrit (trop) d'âneries

PS:
Avec l'inégalité arithmético-géométrique , on peut obtenir un majorant pour le produit maximum cherché.

Pianiste2103 · March 2011

Oula c'est compliqué ...

Fin de partie · March 2011

Pianiste:
Non c'est simple

Dans la décomposition de 14 en somme, on ne doit pas voir apparaitre les nombres de 6 à 14 car autrement à partir d'une telle somme on peut en fabriquer une autre qui donnera un produit plus grand.

Exemple:
14=7+(3+4) le produit correspondant va être 7x(3x4)
De cette somme je peux en déduire une autre:
Puisque 7=2+2+2+1 alors 14=(2+2+2+1)+(3+4) (on n'a pas touché à la deuxième partie de la somme)
donc le produit correspondant sera 2x2x2x(3x4) qui est plus grand que 7x(3x4) produit correspondant à la somme initiale.

Ga? · March 2011

Je ne comprends pas non plus ce que dit Fin de partie, mais je pense la chose suivante :

Si a = (k fois 3) ou (k fois 3 + 2), prendre cette décomposition pour fabriquer le produit maximal
Si a = k fois 3 + 1, prendre la décomposition (k-1) fois 3 + 2 fois 2 pour fabriquer le produit maximal.

Vrai ou faux ?

Pianiste2103 · March 2011

On peut utiliser cette méthode pour tout les chiffres

Fin de partie · March 2011

Ce que je dis est simple si, j'ai bien compris le problème:

A partir du moment que dans la décomposition de 14 en somme d'entiers on a le nombre r (qui est positif et inférieur ou égal à 14) alors le produit correspondant sera un multiple de r.
Le fait est que si on peut décomposer r en une somme de termes dont le produit est plus grand que r alors de la somme initiale considérée on peut en construire une autre décomposition en somme dont le produit correspondant sera plus grand.
(voir l'exemple plus haut)

En espérant ne pas avoir écrit (trop) d'âneries.

PS:
5 ne doit pas apparaitre dans la décomposition en somme de 14 car:
5=2+3 et 2x3>5

Ga? · March 2011

@Fin de partie : j'ai fini par comprendre, mais ça ne me semble pas donner de méthode pour trouver la décomposition optimale d'un entier a quelconque. J'en propose une, qui a l'air de tenir la route... jusqu'au prochain virage

C'est peut-être déjà dans le fil signalé par bs.

Fin de partie · March 2011

BTW:
le produit maximum ne semble pas être 128 pour 14 car:

14=3+3+3+3+2 et 3^4=81 et 81x2=162

Fin de partie · March 2011

Ga2:
On peut généraliser ma constatation initiale par exemple:

On ne peut pas avoir deux 4 dans la décomposition car:
4+4=3+3+2 et 3x3x2=18>4x4

Fin de partie · March 2011

En fait puisque la présence d'un 4 dans la somme est la même chose que si on remplaçait par deux 2,
La somme qui donnera le produit maximum ne doit contenir que des 2 et 3.

PS:
Par ailleurs, dans la somme qui donnera le produit maximum il ne peut y avoir plus de deux 2
car 2+2+2=3+3 et 2^3=8<3^2=9

Fin de partie · March 2011

Il faudrait étudier le signe de la fonction ln(2)x/2-ln(x) pour généraliser mes constatations.

Et je conjecture que :

Si N a pour reste 0 dans la division par 3 alors le produit maximum sera 3^(N/3)
Si N a pour reste 2 dans la division par 3 alors le produit maximum sera 3^((N-2)/3)x2
Si N a pour reste 1 dans la division par 3 alors le produit maximum sera 3^((N-4)/3)x4

Ga? · March 2011

@Fin de partie :
Au cas où tu ne t'en serais pas aperçu, je te signale que tu ne fais que reproduire dans ta conjecture ce que j'ai dit plus haut.

Fin de partie · March 2011

Ga': oui sans aucun doute mais c'est aussi la conclusion logique des constatations (il manque peu de chose pour en faire une preuve) que je faisais.
Rien d'étonnant à ce que j'arrive à la même conjecture puisque c'est plus qu'une conjecture.

PS:
Si tu as une preuve plus simple je suis preneur.

Cidrolin · March 2011

Pour n=3k le maximum est 3^k

Pour n=3k+1 c'est 4.3^(k-1)

Pour n=3k+2 c'est 2.3^k

Voir http://oeis.org/A000792

Fin de partie · March 2011

Pour finir la démonstration esquissée il faut démontrer que:

Pour x>1
2^(x/2)>x <=> xln2/2-ln(x)>0

La fonction f(x)=xln2/2-ln(x) définie sur [1,+OO[ a pour dérivée:
f'(x)=(xln(2)-2)/(2x)
f est croissante pour x>2/ln(2) (nombre qui est compris entre 2 et 3)
f(4)=0.
Donc pour x>=5 2^(x/2)>x
Cela permet de montrer qu'il est inutile de s'intéresser à une décomposition de N qui comporte un entier pair plus grand ou égal à 6 puisque cette somme peut être transformée en une autre somme qui fournit un produit plus grand.

Pour x>1
2^((x-1)/2)>x <=>(x-1).ln2/2-ln(x)>0

La fonction g(x)=(x-1).ln2/2-ln(x) définie sur [1,+OO[ a pour dérivée:
g'(x)=(xln(2)-2)/(2x)
g est croissante pour x>2/ln(2) (nombre qui est compris entre 2 et 3)
g(7)>0
Pour x>=7 2^((x-1)/2)>x
Cela permet de montrer qu'il est inutile de s'intéresser à une décomposition de N comportant un entier impair plus grand ou égal à 7.
Puisque 5=2+3 et 2x3=6>5 on peut oublier une décomposition en somme qui comporte un 5.

Donc une somme qui donne un produit maximum ne doit pas comporter des termes plus grands que 4.
Plus haut j'ai expliqué qu'il ne pouvait il y avoir plus d'un 4, plus de deux 2 dans cette somme.

Il reste à montrer que dans la décomposition en somme il ne peut y avoir de terme égal à 1.
C'est clair qu'il ne peut y en avoir plus de 2 car 1+1=2 et 1x1<2

S'il y en a qu'un seul cela signifie que les autres termes de la somme sont soient des 2 soient des 3.
S'il y a un 2 on constate que 2+1=3>2x1
S'il y a un 3 on constate que 3+1=4>1x1
Ce qui finit de montrer que la décomposition en somme ne comporte aucun 1.

Ga? · March 2011

L'inégalité arithmétique-géométrique montre qu'on a intérêt à diviser en parts égales. D'où l'étude de la fonction (a/x)^x que j'indiquais plus haut ou, avec le changement de variable y=a/x, de la fonction y^a/y qui a son maximum pour y=e, entre 2 et 3. Et en constatant de plus que 3² > 2³ et que 3x1 < 2x2, on a fini, me semble-t-il.

JLT · March 2011

En resume, la solution niveau troisieme est :

s'il y a un 4 on peut le remplacer par 2+2 sans changer le produit.

S'il y a un 5 on peut le changer par 3+2 en augmentant le produit.

S'il y a un 6 on peut le changer en 4+2 en augmentant le produit.

etc.

Donc il n'y a que des 2 et des 3.

S'il y a trois 2, on peut remplacer 2+2+2 par 3+3 en augmentant le produit donc il y a au maximum deux 2.

Une decomposition optimale est donc de la forme:

3+3+...+3 si n est un multiple de 3
3+3+...+3+2 si n+1 est un multiple de 3
3+3+...+3+2+2 si n+2 est un multiple de 3.

Pianiste2103 · March 2011

Merci beaucoup pour toutes ces solutions , mais je souhaiterai que l'ont m'aide a l'expliquer , je n'y arrive pas du tout :S
Du moins la façon de l'écrire pour qu'une personne comprenne , en ne voyant pas ce problème .
S'il vous plait .

Cidrolin · March 2011

Difficile de faire plus simple que la méthode de JLT

Pianiste2103 · March 2011

Ouais c'est sure mais je ne sais pas comment l’écrire .
Et je n'est pas trouver la méthode pour être toujours gagnant si on me propose d'autres nombres.:S

gerard0 · March 2011

Pianiste,

tu montres que tu n'as pas compris ce qu'a écrit JLT. Car il répond exactement à tes questions. Donc lis et pense !

Cordialement.

NB : On ne dit pas "je n'est pas ..." mais "je ne suis pas..." ou je n'ai pas". Quand on ne fait pas l'effort de comprendre les mots que l'on écrit soi-même, difficile de prétendre comprendre ce que disent les autres...

Pianiste2103 · March 2011

J'ai enfin compris:P merci a Fin de partie mais juste une question comment vous faites pour trouver le 2,718 ?

Fin de partie · March 2011

mais juste une question comment vous faites pour trouver le 2,718 ? a écrit:

Si tu es en troisième cela va être difficile de répondre à ta question.
2,718 est une approximation d'un nombre (non rationnel, en fait transcendant) qui est nommé e. Celui-ci intervient partout (ou presque) en mathématiques et ailleurs.

Cidrolin · March 2011

Il y a un problème "dual". Soit n un entier naturel, comment choisir des entiers dont le produit est n

et la somme est minimale?

Pour n=1414, on a 1414=2*707, la somme est 709, on peut mieux faire!