Sommes de sous-ensembles spéciaux : optimum
Énoncé:
Soit $S(A)$ la somme des éléments de l'ensemble $A$ de taille $n$. Nous l'appellerons un ensemble à somme spéciale si pour deux sous-ensembles disjoints non vides quelconques, $B$ et $C$, les propriétés suivantes sont vraies :
- $S(B) \ne S(C)$; autrement dit, les sommes des sous-ensembles ne peuvent pas être égales.
- Si $B$ contient plus d'éléments que $C$, alors $S(B) > S(C)$.
Si $S(A)$ est minimisé pour un $n$ donné, nous l'appellerons ensemble à somme spéciale optimale. Les cinq premiers ensembles de sommes spéciales optimales sont donnés ci-dessous.
$n = 1: \{1\}$
$n = 2: \{1, 2\}$
$n = 3: \{2, 3, 4\}$
$n = 4: \{3, 5, 6, 7\}$
$n = 5: \{6, 9, 11, 12, 13\}$
Il semble que pour un ensemble optimal donné, $A = \{a_1, a_2, \dots , a_n\}$, l'ensemble optimal suivant est de la forme $B = \{b, a_1+b, a_2+b, \dots ,a_n+b\}$, où $b$ est l'élément "central" de la rangée précédente.
En appliquant cette "règle", on s'attendrait à ce que l'ensemble optimal pour $n = 6$ soit $A = \{11, 17, 20, 22, 23, 24\}$, avec $S(A) = 117$. Cependant, il ne s'agit pas de l'ensemble optimal, car nous avons simplement appliqué un algorithme pour obtenir un ensemble quasi optimal. L'ensemble optimal pour $n = 6$ est $A = \{11, 18, 19, 20, 22, 25\}$, avec $S(A) = 115$ et la chaîne d'ensemble correspondante : $111819202225$.
Sachant que $A$ est un ensemble optimal à somme spéciale pour $n = 7$, trouve sa chaîne d'ensembles.
NOTE: Ce problème est lié au problème 105 et au problème 106.
Lien du problème originel