Spezielle Teilmengen-Summen: Meta-Testen
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:
- S(B) ≠ S(C); das bedeutet, Summen von Teilmengen dürfen nicht gleich sein.
- Wenn B mehr Elemente als C enthält, dann gilt S(B) > S(C).
Für dieses Problem nehmen wir an, dass eine gegebene Menge n streng monoton steigende Elemente enthält und bereits die zweite Regel erfüllt.
Überraschenderweise muss von den 25 möglichen Teilmengen-Paaren, die von einer Menge mit n = 4 entnommen werden können, nur 1 dieser Paare auf Gleichheit getestet werden (erste Regel). Ebenso müssen, wenn n = 7, nur 70 der 966 Teilmengen-Paare getestet werden.
Für n = 12, wie viele der 261625 Teilmengen-Paare, die erhalten werden können, müssen auf Gleichheit getestet werden?
HINWEIS: Dieses Problem ist verknüpft mit Problem 103 und Problem 105.