Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques DétentePour discuter des JFF, des problèmes intéressants. ExercicesExercices ludiques [tout]Lister tous les topics de mathématiques
Niveau exercices
Partager :

Partition et optimisation

Posté par
jsvdb 04-04-20 à 23:02

Bonjour et santé à tous

Je fais suite à ce fil : Entier

C'est intéressant et on peut généraliser le problème.

Si n \in \N^*, on appelle partition de n, toute suite finie décroissante d'entiers non nuls telle que la série correspondante soit de somme n.
On note \mathcal P(n) l'ensemble des partitions de n.

Pour une partition P\in \mathcal P(n), on note \pi(P) le produit des termes de la partition.

On note \mathfrak M(n) = \max\{\pi(P)~/~P\in \mathcal P(n)\}

L'objet du fil cité en seconde ligne était de trouver \mathfrak M(1976)

On a les premiers termes de la suite \mathfrak M et entre parenthèses une partition gagnante (il peut y en avoir plusieurs)
Et en rouge la différence avec le terme d'avant :

\mathfrak M(1) = 1~(1) \\ \mathfrak M(2) = 2~(2) {\red +1}\\ \mathfrak M(3) = 3~(3){\red +1}\\ \mathfrak M(4) = 4~(2,2){\red +1}\\ \mathfrak M(5)=6~(3,2){\red +2}\\ \mathfrak M(6) = 9~(3,3){\red +3}\\ \mathfrak M(7) = 12~(3,2,2){\red +3}\\ \mathfrak M(8) = 18~(3,3,2){\red +6}\\ \mathfrak M(9) = 27~{\blue (3,3,3)}{\red +9}\\ \mathfrak M(10) = 36~{\blue (3,3,2,2)}\text{ ou } (4,3,3){\red +9}\\ \mathfrak M(11) = 54~{\blue (3,3,3,2)}{\red +18}\\ \mathfrak M(12) = 81~{\blue (3,3,3,3)}{\red +27}

Évidemment, vu que c'est un calcul personnel, vous me dites de suite si vous voyez des erreurs.
Mais on peut d'ores et déjà constater que les grands vainqueurs sont les 2 et les 3.

Cette suite est à continuer et à étudier.

Mais je m'aperçois que

si une partition gagnante est de la forme (3,3,3,\cdots,3) avec n termes, la suivante est constituée de n+1 termes (3,3,3,\cdots,3,2,2)

puis la suivante avec est constituée de n+1 termes (3,3,3,\cdots,3,3,2)

puis la suivante est constituée de n+1 termes (3,3,3,\cdots,3,3,3)

et on recommence.

Si cette hypothèse est exacte, \mathfrak M(1976) ne devrait poser de soucis

Posté par
Sylvieg Moderateurre : Partition et optimisation 05-04-20 à 07:38

Bonjour et merci pour cette proposition de généralisation
En utilisant les arguments de verdurin et la division euclidienne de n par 3, on trouve 3 cas :
M(3q) = 3q
M(3q+1) = 3q-14 = 3q-122
M(3q+2) = 3q2

Posté par
Sylvieg Moderateurre : Partition et optimisation 05-04-20 à 08:01

Une formule un peu alambiquée :
M(n) = 3q-1(3 + r(r+1)/2) \; où \; q = E(n/3) \; et \; r = n-3q .

Posté par
LittleFoxre : Partition et optimisation 07-04-20 à 10:00


Au début je me suis dit qu'on avait été vite à la conclusion en ne testant que les nombres jusqu'à 12.
Voyant que ça avait toujours l'air vrai jusqu'à 100, je me suis demandé pourquoi

Si on relâche le problème dans les réels, il devient: maximiser p=bq avec s=bq constant.
Autrement dit, \max_b{b^{s/b}} = (b^{1/b})^s.
Une dérivée plus tard et on obtient b=e \approx 2.7, peut importe s.

C'est donc déjà moins surprenant de voir les facteurs 2 et 3 qui sont les entiers qui encadrent e.

Il doit y avoir une preuve par récursion ceci dit

Posté par
Sylvieg Moderateurre : Partition et optimisation 07-04-20 à 11:21

Oui, on peut faire intervenir le nombre e.
On peut aussi être plus terre à terre :
Si un entier \; a \; figure dans la somme, peut-on le remplacer par \; b \; et \; c \; tels que \; b+c =a \; et \; bc-a > 0 \; ?

Si \; a \; est pair, on peut choisir \; b = c = a/2 .
On a alors \; bc-a = a(a-4)/4 . Positif si \; a 5 .

Si \; a \; est impair, on peut choisir \; b = (a-1)/2 \; et \; c = (a+1)/2 .
On a alors \; bc-a = ((a-2)2-5) / 4 . Idem.

Posté par
Sylvieg Moderateurre : Partition et optimisation 07-04-20 à 11:21

Pas de récursion

Posté par
LittleFoxre : Partition et optimisation 07-04-20 à 11:57


Donc pas de facteur 5.
En ajoutant que 4 = 2+2 = 2x2, on peut retirer les facteurs 4.
Et avec 2+2+2 = 3+3 et 2x2x2 = 8 < 3x3 = 9, on ne peut pas avoir plus de deux 2.
Les 1 étant inutiles pour toute somme > 1.

On a donc au plus deux 2 et sinon que des 3

Posté par
Sylvieg Moderateurre : Partition et optimisation 07-04-20 à 12:04

Je n'ai rien inventé : Entier

Posté par
LittleFoxre : Partition et optimisation 07-04-20 à 12:05


La définition de jsvdb pour une partition de n ne dit jamais que les facteurs doivent être positifs (juste non-nuls), en utilisant des facteurs négatifs, on peut rendre le produit aussi grand que l'on veut

Pour toute décomposition s (avec p > 0) de n, la décomposition s' donne un produit plus grand.
s' = s + 2 - 2 +2 - 2 => p' = p x 2 x -2 x 2 x -2 = p x 16 > p

Mais je crois que c'est plutôt un trou dans l'énoncé

Posté par
jsvdbre : Partition et optimisation 10-04-20 à 18:37

Il me semble que quand on ne précise pas, entier = entier naturel.
Mais bon, je n'ai pas du tout l'intention d'entrer dans ce type de débat futile.
Donc précisons :

Citation :
Si n \in \N^*, on appelle partition de n, toute suite finie décroissante d'élément de \N^* telle que la série correspondante soit de somme n


Cela précisé, si récurrence il y a au niveau de la formule que je laisse apparaître en bleu dans le fil initial, elle ne laisse aucune place au fait que ce soit le max cherché ... autrement dit, je ne vois en quoi une récurrence peut montrer qu'il s'agisse du max.

Posté par
LittleFoxre : Partition et optimisation 11-04-20 à 17:06


En effet, la preuve par récursion ne nécessite pas que la formule soit une récurrence. D'ailleurs ce n'est pas cette récurrence que je voulais prouver mais la formule close de Sylvieg.
Mais sa démonstration est bien plus simple qu'une preuve par récursion:

Admettons que la formule soit juste jusqu'à n-1:
\forall m \in [2, n[, M(m) = \begin{cases} 3^q & \text{ si } m=3q \\ 3^{q-1}4 & \text{ si } m=3q+1 \\ 3^q2 & \text{ si } m=3q+2 \\ \end{cases}


Si n \ge 4:
Alors soit M(n) = n, soit M(n) = M(n-1), soit M(n) = \max_{m \in [2,n-2]}  M(m)M(n-m).

Si n=3q:
M(n)M(n-m) = \begin{cases} 3^p \times 3^{q-p} = 3^q & \text{ si } m= 3p \\ 3^{p-1} 4 \times 3^{q-p-1}2 = 3^{q-2}8 & \text{ si } m= 3p+1 \\ 3^{p} 2 \times 3^{q-p-2}4 = 3^{q-2}8 & \text{ si } m= 3p+2 \\ \end{cases}

Donc M(n) = max(3q, 3^{q-1}, 3^q, 3^{q-2}8) = 3^q

Si n=3q+1:
M(n)M(n-m) = \begin{cases} 3^p \times 3^{q-p-1}4 = 3^{q-1}4 & \text{ si } m= 3p \\ 3^{p-1} 4 \times 3^{q-p} = 3^{q-1}4 & \text{ si } m= 3p+1 \\ 3^{p} 2 \times 3^{q-p-1}2 = 3^{q-1}4 & \text{ si } m= 3p+2 \\ \end{cases}

Donc M(n) = max(3q, 3^{q}, 3^{q-1}4) = 3^{q-1}4

Si n=3q+2:
M(n)M(n-m) = \begin{cases} 3^p \times 3^{q-p}2 = 3^q2 & \text{ si } m= 3p \\ 3^{p-1} 4 \times 3^{q-p-1}4 = 3^{q-2}16 & \text{ si } m= 3p+1 \\ 3^{p} 2 \times 3^{q-p} = 3^{q}2 & \text{ si } m= 3p+2 \\ \end{cases}

Donc M(n) = max(3q, 3^{q-1}4, 3^q2, 3^{q-2}16) = 3^q2

La formule est donc juste pour n \ge 4 si elle est juste pour n \in [2,3]

Il est facile de vérifier qu'elle est juste pour n \in [2,3] et donc elle est juste pour n \ge 2

Voilà une démonstration par récursion. Celle de Sylvieg est quand même bien plus belle et évidente.


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !