Spezielle Teilmengen-Summen: Optimum

Problem 103

S(A) repräsentiere die Summe der Elemente in der Menge A der Mächtigkeit n. Wir nennen sie eine spezielle Summen-Menge, wenn für zwei beliebige nicht-leere, disjunkte Teilmengen B und C die folgenden Eigenschaften gelten:

  1. S(B) ≠ S(C); das bedeutet, Summen von Teilmengen dürfen nicht gleich sein.
  2. Wenn B mehr Elemente als C enthält, dann gilt S(B) > S(C).

Wenn S(A) für ein gegebenes n minimal ist, nennen wir sie eine optimale spezielle Summen-Menge. Die ersten fünf optimalen speziellen Summen-Mengen sind unten gegeben.

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}

Es scheint, als sei für eine gegebene optimale Menge A = {a1, a2, ... , an} die nächste optimale Menge in der Form B = {b, a1+b, a2+b, ... ,an+b}, wobei b das "mittlere" Element der vorherigen Reihe ist.

Unter Anwendung dieser "Regel" würden wir für n = 6 als optimale Menge A = {11, 17, 20, 22, 23, 24} erwarten, mit S(A) = 117. Jedoch ist dies nicht die optimale Menge, denn wir haben lediglich einen Algorithmus für eine nahezu optimale Menge angewandt. Die optimale Menge für n = 6 ist A = {11, 18, 19, 20, 22, 25}, mit S(A) = 115 und dem dazugehörigen Mengen-String:: 111819202225.

Gegeben, dass A die optimale spezielle Summen-Menge für n = 7 ist, finden Sie ihren Mengen-String.

HINWEIS: Dieses Problem ist verknüpft mit Problem 105 und Problem 106.