Vous devez partager 100 en une somme d'entiers naturels. Votre score est alors égal au produit de tous les termes de votre partage.
Par exemple si j'écris 100 = 50 + 30 + 20, mon score est de 50 * 30 * 20 = 30 000.
Quel est le score maximal que l'on puisse atteindre ?
Variante : tous les nombres positifs même non entiers sont autorisés. Quel est alors le score maximal ?
Ma réponse : intuitivement je dirais 2 puissance 50 soit 1125899906842624
Bon score, mais on peut faire mieux.
Je sais pas, mais le produit pour moi, c'est la multiplication... pas la puissance.
zaknafein666 dit:Je sais pas, mais le produit pour moi, c'est la multiplication... pas la puissance.
La puissance c'est une multiplication.
Par exemple dans le problème dire 100 = 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10
Donc le résultat est 10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 x 10 soit 10 puissance 10 (soit 10 000 000 000).
2*2*3^32 c'est mieux, mais je ne sais pas pourquoi
solution trouvée de manière empirique
Bon, mes premières idées, dont je ne suis pas forcément sûr. Je parle de la version "réelle" du problème, en appelant A la valeur à partager.
On remarque que si on ajoute la contrainte : "on veut partager A en DEUX parties", la meilleur solution est de le partager en deux parties égales. En effet, en notant x la taille de la première partie, l'autre partie fait (A-x). On a alors le produit des deux qui vaut x(A-x), qui est croissant sur x compris entre 0 et A/2, maximum en A/2 et décroissant entre A/2 et A.
Ensuite, comme la somme et le produit sont des opérations commutatives et associatives, on peut en déduire que quelques soit le nombre de parties que l'on souhaite définir, le meilleur score est obtenu avec des parties de tailles égales.
En effet, si deux parties x et y sont différentes, alors on remarque qu'en remplaçant x et y par (x+y)/2, on augmente le produit de ces deux termes (comme vu précédement) et donc le produit total.
Il faut donc décomposer A en n valeurs égales à A/n. Le produit de ces valeurs sera (A/n)^n.
Reste à calculer pour quel n cette valeur est maximale...
Voilà, mais je me trompe peut-être. 
EDIT : Après calcul bourrin sur toutes les valeurs de n, je trouve que le meilleur partage (si ce que j'ai dit avant est bon) est en 33*(100/33), pour un score de 7745331031732790,0115053536318454
EDIT : Erreur dans mon calcul bourrin : le meilleur n est 37, pas 33.
Bien vu Lucco pour les entiers.
Le meilleur score lorsque les non entiers sont autorisés n'a toujours pas été donné.
On peut réécrire cela comme un problème de maximisation sous contraintes d'égalité (sauf que l'on ne connait pas le nombre de variables).
En appelant N le nombre de découpages :
on veut le max de x_1 * ... * x_N sous contrainte de x_1+...+x_N = 100
Un petit coup de multiplicateurs de Lagrange plus tard on obtient qu'au(x) maximum(s)/minimum(s) x_1=...=x_N
(tout se simplifie)
Au passage sur les multiplicateurs de Lagrange une excellente vidéo :
http://video.google.com/videoplay?docid ... 1900812573
J'aurais aimé assister à ce genre de cours plus jeune même si la il traine un peu... Mais bon, je n'ai pas trop à me plaindre et l'enseignant dessus est quand même Denis Auroux (qui à ma connaissance a le record du plus jeune Ulmard).
N est forcément entier <100 (sinon on fait apparaitre des x_i < 1) et on a x_i = 100/N. La question est donc de trouver N entier tel que (100/N)^N soit maximum. On trouve (en dérivant ou par la force brute - pas trop forte) N=37
Donc le max est (100/37)^37 ~ 9.474062e+15
Jeremie dit:On peut réécrire cela comme un problème de maximisation sous contraintes d'égalité (sauf que l'on ne connait pas le nombre de variables).
En appelant N le nombre de découpages :
on veut le max de x_1 * ... * x_N sous contrainte de x_1+...+x_N = 100
Un petit coup de multiplicateurs de Lagrange plus tard on obtient qu'au(x) maximum(s)/minimum(s) x_1=...=x_N
(tout se simplifie)
Au passage sur les multiplicateurs de Lagrange une excellente vidéo :
http://video.google.com/videoplay?docid ... 1900812573
J'aurais aimé assister à ce genre de cours plus jeune même si la il traine un peu... Mais bon, je n'ai pas trop à me plaindre et l'enseignant dessus est quand même Denis Auroux (qui à ma connaissance a le record du plus jeune Ulmard).
N est forcément entier <100 (sinon on fait apparaitre des x_i < 1) et on a x_i = 100/N. La question est donc de trouver N entier tel que (100/N)^N soit maximum. On trouve (en dérivant ou par la force brute - pas trop forte) N=37
Donc le max est (100/37)^37 ~ 9.474062e+15
J'étais arrivé au même résultat de (100/N)^N sans passer par les multiplicateurs de Lagrange, mais en faisant la force brute j'avais trouvé N=33. Bizarre que j'ai réussi à me gourer sur la force brute.
A oui c'est bizarre... Dans les énigmes je ne lis pas les posts autre que ceux de l'auteur alors je n'avais pas vu que tu avais fait le plus dur (enfin je n'ai pas vérifié ton raisonnement).
Je ne sais pas ou tu a pu manquer un truc car pour 33 cela fait ~7.745331e+15
Jeremie dit:A oui c'est bizarre... Dans les énigmes je ne lis pas les posts autre que ceux de l'auteur alors je n'avais pas vu que tu avais fait le plus dur (enfin je n'ai pas vérifié ton raisonnement).
Je ne sais pas ou tu a pu manquer un truc car pour 33 cela fait ~7.745331e+15
Il y avait une erreur dans le code du programme que j'avais écrit pour le brute force ( l'opérateur /, appliqué à des integers, faisait une division euclidienne ).
J'ai corrigé l'erreur et effectivement, je tombe sur 37.
Lucco dit:2*2*3^32 c'est mieux, mais je ne sais pas pourquoi
solution trouvée de manière empirique
Voici une démonstration que j'espère juste (et qui fonctionne en fait pour toute valeur, pas seulement 100) :
*Déjà on ne doit utiliser que des 2 et 3. En effet, on peut toujours remplacer les nombres supérieurs par une somme de 2 et 3 donnant un meilleur produit : 4=2+2, 5=3+2 (3*2=6>5), 6=3+3 (3*3=9>6), et par récurrence, on peut montrer que c'est toujours le cas.
Et pas de 1 car si on x+1, on utilise (x+1) plutôt que x+1 car (x+1)>x*1.
*Ensuite comment répartit-on les 3 et 2 ? On remarque que si on a 2^3=8 dans notre produit, qui correspond à 2+2+2=6, on obtient un meilleur résultat en le remplaçant par 3+3 : 3*3=9>8. Donc on doit avoir au maximum 2 à la puissante 2 dans notre produit.
Pour 100, 100 n'est pas divisible par 2, donc on a au moins un 2, 100-2 n'est toujours pas divisible par 3, donc 100-4=96=3*32. Ce qui nous donne bien 2*2*3^32.
Simboubou dit:Jeremie dit:A oui c'est bizarre... Dans les énigmes je ne lis pas les posts autre que ceux de l'auteur alors je n'avais pas vu que tu avais fait le plus dur (enfin je n'ai pas vérifié ton raisonnement).
Je ne sais pas ou tu a pu manquer un truc car pour 33 cela fait ~7.745331e+15
Il y avait une erreur dans le code du programme que j'avais écrit pour le brute force ( l'opérateur /, appliqué à des integers, faisait une division euclidienne ).
J'ai corrigé l'erreur et effectivement, je tombe sur 37.
Au hasard je dirais que tu utilises Python, si c'est le cas pense à ajouter systématiquement en 2.x
from future import division
Lucide dit:Lucco dit:2*2*3^32 c'est mieux, mais je ne sais pas pourquoi
solution trouvée de manière empirique
Voici une démonstration que j'espère juste (et qui fonctionne en fait pour toute valeur, pas seulement 100) :
*Déjà on ne doit utiliser que des 2 et 3. En effet, on peut toujours remplacer les nombres supérieurs par une somme de 2 et 3 donnant un meilleur produit : 4=2+2, 5=3+2 (3*2=6>5), 6=3+3 (3*3=9>6), et par récurrence, on peut montrer que c'est toujours le cas.
Et pas de 1 car si on x+1, on utilise (x+1) plutôt que x+1 car (x+1)>x*1.
*Ensuite comment répartit-on les 3 et 2 ? On remarque que si on a 2^3=8 dans notre produit, qui correspond à 2+2+2=6, on obtient un meilleur résultat en le remplaçant par 3+3 : 3*3=9>8. Donc on doit avoir au maximum 2 à la puissante 2 dans notre produit.
Pour 100, 100 n'est pas divisible par 2, donc on a au moins un 2, 100-2 n'est toujours pas divisible par 3, donc 100-4=96=3*32. Ce qui nous donne bien 2*2*3^32.
Tu as parfaitement traduit le raisonnement que j'ai fait intuitivement avec des mots
Jeremie dit:Simboubou dit:Jeremie dit:A oui c'est bizarre... Dans les énigmes je ne lis pas les posts autre que ceux de l'auteur alors je n'avais pas vu que tu avais fait le plus dur (enfin je n'ai pas vérifié ton raisonnement).
Je ne sais pas ou tu a pu manquer un truc car pour 33 cela fait ~7.745331e+15
Il y avait une erreur dans le code du programme que j'avais écrit pour le brute force ( l'opérateur /, appliqué à des integers, faisait une division euclidienne ).
J'ai corrigé l'erreur et effectivement, je tombe sur 37.
Au hasard je dirais que tu utilises Python, si c'est le cas pense à ajouter systématiquement en 2.x
from future import division
C'était du C#.
Bravo Jeremie et Simboubou pour vos réponses.
Maintenant, sauriez vous trouver le meilleur score pour un entier N quelconque ?
Pour le cas non-entier c'est inclus dans ce qu'on disait : c'est le maximum sur x (x entier naturel strictement positif inférieur à N) de (N/x)^x
La dérivée est (N^x*log(N)+(-log(x)-1)*N^x)/x^x
la chose s'annule en
x = exp(log(N) - 1) (qui vaut ~36.78 dans le cas précédent)
Ya plus que deux candidats entiers à tester. Doit y avoir moyen de deviner lequel mais faut redériver et je ne vois pas trop l'intérêt.
Oui c'est ça, on peut simplifier en x=N/e donc N/x=e.
Il faut donc couper en parts égales qui doivent être proches du nombre e.