Dies ist ein Follow-up zu dieser Frage auf math.stackexchange.
Nehmen wir an, dass eine nicht leere Menge S ⊆ ℤ selbsttragend ist, wenn für jedes a ∈ S verschiedene Elemente b, c ∈ S existieren, so dass a = b + c. Einfache Beispiele für positive ganze Zahlen n sind das ideale S = n = oder (für n > 3) das ganzzahlige Intervall [- n , n ].
Wir werden sagen, dass S stark selbsttragend ist, wenn S von −S getrennt ist: das heißt, wenn a ∈ S ist, dann - a ∉ S. Keines der obigen Beispiele ist stark selbsttragend, weil sie tatsächlich geschlossen sind unter Verneinung. Es gibt endliche Mengen, die sich stark selbst tragen: Zum Beispiel die Mengen {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15 , 23} und {–10, –8, –6, –2, 1, 3, 4, 5}.
Frage 1. Gibt es für eine positive ganze Zahl N > 0 einen Poly ( N ) -Zeit- (oder Polylog ( N ) -Zeit-) Algorithmus, um entweder (i) eine stark selbsttragende Menge zu erzeugen, deren maximaler absoluter Wert N ist , oder (ii ) feststellen, dass kein solches Set existiert? [ Bearbeiten : wie in der ältesten Antwort + meinem Kommentar darauf hingewiesen, gibt es immer eine solche Menge für N ≥ 10.]
Frage 2. Können Sie für N > 0 die stark selbsttragende Menge mit dem maximalen Absolutwert N konstruieren , die die wenigsten möglichen Elemente enthält?
quelle
Antworten:
Ich nehme an, dass ein linearer Zeitalgorithmus für Frage 1 möglich sein sollte (und wenn Sie bereit sind, sich mit einer anderen Darstellung zu befassen, ein O (1) -Zeitalgorithmus).
Bei N> = 23 konstruieren wir eine stark selbsttragende Menge, die 1 und N enthält.
Wir können das leicht tun, wenn wir dasselbe für N-1 konstruieren und dann N zu der resultierenden Menge hinzufügen.
Für den Basisfall 23 können wir mit Ihrem Beispielsatz beginnen.
Um die Größe zu verringern, sollten wir in der Lage sein, einen ähnlichen Ansatz zu verwenden:
Konstruiere Mengen, die enthalten
1, N and N-1.Wir verwenden diese beschränkten Mengen und führen diese Konstruktion rekursiv aus, um die Größe wie folgt auf O (logN) zu verringern:
Wenn N gerade ist, um eine Menge mit 1, N und N-1 zu konstruieren, konstruieren Sie rekursiv eine Menge mit 1, N / 2 und N / 2-1 (dh eine Menge, die N / 2 entspricht) und addieren Sie N und N-1 zur Ergebnismenge. Da N-1 = N / 2 + N / 2-1 und N = 1 + N-1 ist, ist dies eine gültige Menge.
Wenn N ungerade ist, konstruiere eine Menge für N-1 und N für die resultierende Menge.
Für die Basisfälle können wir mit {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} für N beginnen = 24. Für 24 <N <= 47 können wir den obigen linearen Zeitalgorithmus verwenden und auf der Menge für N = 24 aufbauen. Für N> = 48 wechseln wir zur Halbierung.
Tatsächlich können wir für zusammengesetztes N die Größe weiter auf die Größe reduzieren, die für eine der kleinen Primzahlen erforderlich ist, die N teilt: Suchen Sie eine Menge für die kleine Primzahl und multiplizieren Sie einfach alle Zahlen mit einem geeigneten Faktor.
Es könnte interessant sein, einige untere Schranken für den Fall zu beweisen, dass N Primzahl ist.
quelle
Für N ≥ 10 kann man einen stark selbsttragenden Größensatz von höchstens elf wie folgt aufbauen:
Das kürzere Beispiel in der ursprünglichen Frage entspricht dem Fall N = 10. Dies ist nahezu optimal, da jede stark selbsttragende Menge eine Kardinalität von mindestens acht haben muss .
Somit ist das Problem in O (log (N)) Zeit lösbar [aufgenommen in weltlichen arithmetischen Operationen mit N], was eine Kardinalitätsmenge zwischen acht und elf ergibt.
Die Konstruktion für diese Antwort wurde zuerst für die Frage math.stackoverflow vorgestellt , die auch die Intuition für die Konstruktion liefert. Können wir noch kleinere Konstruktionen erhalten, zB die untere Grenze von acht für jedes N> 9? Was ist mit den Fällen von N ∈ {8,9}?
quelle