🔢 mathematics

Partitioning set $[n] = \{1, \dots, n\}$ into subsets of size at most $m$ such that all sums are powers of $m$

Diese Arbeit untersucht die Existenz und Eindeutigkeit von Partitionen der Menge $\{1, \dots, n\}$ in Teilmengen der Größe höchstens $m$ , deren Summen Potenzen von $m$ sind, wobei bewiesen wird, dass solche Partitionen für unendlich viele $n$ versagen, wenn $m > 3$ , sie jedoch wahrscheinlich für alle $n$ existieren, wenn $m = 3$ (unter Berücksichtigung spezifischer Einschränkungen potenzieller Gegenbeispiele), und etabliert exakte Zählungen für die Anzahl solcher Partitionen für verschiedene Werte von $n$ .

Ursprüngliche Autoren: Vladimir Gurvich, Mariya Naumova

Veröffentlicht 2026-07-17

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Vladimir Gurvich, Mariya Naumova

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Meisterarchitekt, der beauftragt wurde, eine Stadt mit genau $n$ einzigartigen Ziegeln zu bauen, die von 1 bis $n$ nummeriert sind. Ihr Ziel ist nicht nur das bloße Stapeln; Sie müssen sie in Nachbarschaften (genannt „Teile“) gruppieren, wobei zwei strenge Regeln gelten. Erstens darf eine Nachbarschaft nicht zu überfüllt sein; sie kann höchstens $m$ Ziegel aufnehmen. Zweitens muss das Gesamtgewicht der Ziegel in jeder Nachbarschaft eine Potenz einer spezifischen magischen Zahl $m$ sein (wie $m^0=1$ , $m^1=m$ , $m^2$ , und so weiter). Dieses Rätsel gehört in die Welt der Kombinatorik, eines Zweigs der Mathematik, der untersucht, wie Dinge angeordnet, gezählt und gruppiert werden können. Es ist wie das Lösen eines riesigen, unendlichen Sudokus, bei dem sich die Regeln mit der Größe des Gitters ändern. Mathematiker interessieren sich dafür, weil das Verständnis darüber, wie Zahlen zerlegt und wieder zusammengesetzt werden können, tiefe Geheimnisse über die Struktur der Mathematik offenbart, ganz so wie das Verständnis darüber, wie Atome binden, uns hilft, neue Materialien zu bauen.

Das Papier, das Sie gleich lesen werden, befasst sich mit einer speziellen, kniffligen Version dieses Rätsels. Die Autoren, Wladimir Gurwich und Marija Naumowa, haben die magische Zahl $m$ auf 3 festgelegt. Das bedeutet, sie versuchen, die Zahlen 1 bis $n$ in Gruppen der Größe 1, 2 oder 3 aufzuteilen, wobei die Summe jeder Gruppe eine Potenz von 3 ist (1, 3, 9, 27, etc.). Sie wussten bereits, dass es für $m=2$ für jedes $n$ immer genau einen Weg gibt. Sie wussten auch, dass das Rätsel für ein $m$ größer als 3 für unendlich viele Werte von $n$ unmöglich ist. Aber für $m=3$ war die Antwort ein Mysterium. Die Autoren vermuten (konjekturieren) stark, dass eine Lösung für jede Zahl $n$ existiert, egal wie groß sie ist.

Um dies zu testen, haben sie nicht einfach geraten; sie haben ein mathematisches Sicherheitsnetz gebaut. Sie haben bewiesen, dass, falls für eine bestimmte Zahl $n$ keine Lösung existiert, diese „schlechte“ Zahl eine sehr spezifische, seltsame Gestalt haben muss. Sie muss die Form $n = 3t + 3k + 2$ haben und bestimmte andere spezifische Muster vermeiden. Stellen Sie sich das wie einen Detektiv vor, der sagt: „Wenn ein Verbrechen geschah, muss der Verdächtige einen roten Hut getragen haben, einen Hinkschwäche haben und linkshändig sein.“ Wenn Sie einen Verdächtigen finden, der nicht dieser Beschreibung entspricht, wissen Sie, dass er nicht der Täter ist. Die Autoren haben diese Logik verwendet, um riesige Teile der Zahlen auszuschließen. Sie haben auch Computersimulationen durchgeführt, um jede Zahl bis 844 zu überprüfen, und in jedem einzelnen Fall wurde eine Lösung gefunden. Sie haben sogar eine etwas lockerere Version des Rätsels namens „Quasi-Partition“ untersucht, bei der eine Zahl zweimal verwendet werden darf, und bewiesen, dass Lösungen auch dort existieren. Obwohl sie nicht bewiesen haben, dass das Rätsel für jedes $n$ lösbar ist, haben sie den Suchraum für ein Gegenbeispiel auf eine sehr kleine, spezifische Liste von Zahlen eingegrenzt, und sie sind zuversichtlich, dass für fast alle anderen Zahlen die Lösung nicht nur möglich, sondern oft auch eindeutig ist.

Das große Gruppierspiel der Zahlen

Stellen Sie sich vor, Sie haben einen Beutel mit nummerierten Kacheln, von 1 bis zu einer großen Zahl $n$ . Ihre Aufgabe ist es, diese Kacheln in Stapel zu sortieren. Aber es gibt Regeln!

Die Größenregel: Jeder Stapel darf höchstens 3 Kacheln enthalten.
Die Summenregel: Die Zahlen in jedem Stapel müssen sich zu einer „Potenz von 3“ aufaddieren. Das heißt, die Summe muss 1, 3, 9, 27, 81 usw. sein.

Dies ist das „3-gute Partitionierungsproblem“. Die Autoren fragen eine einfache, aber hartnäckige Frage: Können wir das immer machen, egal wie viele Kacheln wir zu Beginn haben?

Lange Zeit wussten Mathematiker die Antwort für „2-gute“ Partitionen (bei denen Stapel höchstens 2 Kacheln haben und die Summen Potenzen von 2 sind). Es stellt sich heraus, dass es dafür immer genau einen Weg gibt. Aber für 3 wird die Sache kompliziert. Die Autoren vermuten, dass die Antwort „Ja, es ist immer möglich“ lautet, aber sie mussten dies beweisen.

Die „kritischen“ Verdächtigen

Anstatt zu versuchen zu beweisen, dass es für jede Zahl funktioniert (was schwierig ist), beschlossen die Autoren, nach den „bösen Jungs“ zu suchen – den Zahlen, bei denen es scheitert. Sie argumentierten, dass, falls eine Zahl $n$ existiert, bei der man die Stapel nicht bilden kann, diese eine „kritische“ Zahl sein muss.

Sie bewiesen, dass, falls eine solche kritische Zahl existiert, sie nicht einfach irgendeine zufällige Zahl sein kann. Sie muss eine sehr spezifische Tarnung tragen. Sie muss der Form:
$n = 3t + 3k + 2$
sein und muss einige zusätzliche Bedingungen über das Verhältnis von $k$ zu $t$ erfüllen.

Stellen Sie sich das wie einen Sicherheitswachmann bei einem Club vor. Der Wachmann sagt: „Wenn Sie versuchen, ohne Ticket hineinzuschleichen, müssen Sie einen grünen Hut tragen und eine blaue Tasche bei sich haben.“ Die Autoren bewiesen, dass jede Zahl, die nicht dieser „grünen Hut“-Beschreibung entspricht, sicher ist; wir wissen, wie wir diese Zahlen gruppieren können. Dies eliminiert eine massive Menge an Möglichkeiten.

Der Computer-Check

Selbst mit ihrer klugen Mathematik gab es noch einige Zahlen, die der „grünen Hut“-Beschreibung entsprachen. Um sicherzugehen, schrieben die Autoren (mit Hilfe des Programmierers Dmitry Rybin) ein Programm, um jede Zahl bis 844 zu überprüfen.

Das Ergebnis: Für jede einzelne Zahl von 1 bis 844 fanden sie einen Weg, die Kacheln perfekt zu gruppieren.
Das Fazit: Der Computer fand nicht eine einzige „schlechte“ Zahl. Dies stützt ihre Vermutung stark, dass das Rätsel für jeden lösbar ist.

Der „Quasi-Partitionen“-Twist

Die Autoren versuchten auch ein etwas anderes Spiel. Was wäre, wenn wir erlaubt wären, eine Zahl zweimal zu verwenden? Sie nennen dies eine „Quasi-Partition“. Stellen Sie sich vor, Sie haben eine Ersatzkachel der Nummer 3, sodass Sie sie in zwei verschiedenen Stapeln verwenden können.
Sie bewiesen, dass für einen bestimmten Bereich von Zahlen Sie diese Version des Rätsels immer lösen können, und die Zahl 3 (speziell $3^t$ ) ist diejenige, die zweimal verwendet wird. Dies war ein hilfreicher Zwischenschritt zum Verständnis des schwierigeren Problems.

Wie viele Wege gibt es?

Einer der interessantesten Teile des Papers ist das Zählen, wie viele verschiedene Möglichkeiten es gibt, die Zahlen zu gruppieren.

Für einige Zahlen (wie 1, 2, 3, 4 und viele andere) gibt es genau einen Weg. Es ist wie ein Schloss mit nur einem Schlüssel.
Für die Zahl 13 und für Zahlen wie $3t - 3$ gibt es genau zwei Wege.
Für fast alle anderen Zahlen vermuten sie, dass es mehr als zwei Wege gibt.

Sie fanden sogar eine spezielle Regel (Proposition 2), die besagt, dass, wenn man weiß, welche Gruppen von drei Zahlen (Triplets) in der Lösung enthalten sind, man das gesamte Rätsel lösen kann. Es ist, als würde man sagen: „Wenn du weißt, wer die drei besten Freunde in einem Raum sind, kennst du die gesamte soziale Dynamik.“

Das Fazit

Die Autoren haben das Rätsel noch nicht für jede Zahl im Universum gelöst. Es gibt noch einige knifflige Zahlen (wie 35, 38, 89 und 101), die sie noch nicht vollständig geklärt haben. Dennoch haben sie gezeigt, dass, falls eine Lösung nicht existiert, sie eine dieser sehr spezifischen, seltenen Zahlen sein muss.

Sie sind zuversichtlich, dass die „3-gute Partitionierung“ für jede Zahl $n$ existiert. Sie haben die einfachen Ausfälle ausgeschlossen, die ersten 844 Zahlen mit einem Computer überprüft und festgestellt, dass das Rätsel immer eine Lösung hat. Das Rätsel, ob wir die Zahlen gruppieren können, ist nicht das Problem, sondern vielmehr die Frage, wie viele Wege es für die wirklich großen Zahlen gibt. Die Reise, dies für jede einzelne Zahl zu beweisen, geht weiter, aber der Pfad ist nun viel klarer.

Technische Zusammenfassung: Über die Partitionierung der Menge [n] in Teilmengen der Größe höchstens m, sodass alle Summen Potenzen von m sind

Problemstellung
Die Arbeit befasst sich mit einem kombinatorischen Partitionierungsproblem auf der Menge der ersten $n$ natürlichen Zahlen, $[n] = \{1, \dots, n\}$ . Gegeben seien die ganzen Zahlen $m > 1$ und $n > 0$ . Eine Teilmenge von $[n]$ wird als $m$ -gut definiert, wenn ihre Kardinalität höchstens $m$ beträgt und die Summe ihrer Elemente eine Potenz von $m$ ist (d. h. $m^t$ für eine ganze Zahl $t \ge 0$ ). Eine Partitionierung von $[n]$ heißt $m$ -gut, wenn jedes Teil der Partitionierung eine $m$ -gute Menge ist.

Die Autoren untersuchen die Existenz und Eindeutigkeit solcher Partitionierungen. Es wird festgestellt, dass:

Für $m=2$ für jedes $n$ eine eindeutige 2-gute Partition existiert.
Für $m > 3$ gibt es unendlich viele $n$ , für die keine $m$ -gute Partition existiert (speziell für $n = 2(m^t + 1)$ ).
Der Fall $m=3$ ist der primäre Fokus, wobei die Existenz einer 3-guten Partition für jedes $n$ nicht unmittelbar offensichtlich ist und Gegenstand einer Vermutung bleibt.

Methodik
Die Autoren verwenden eine Kombination aus konstruktiven Beweisen, rekursiven Reduktionen und computergestützter Verifizierung.

Reduktionstechniken: Die Kernmethodik besteht aus „Reduktionen“, bei denen eine Partitionierung von $[n]$ durch Hinzufügen spezifischer Teile zu einer bekannten Partitionierung einer kleineren Menge $[n']$ konstruiert wird. Die Autoren definieren spezifische Reduktionsformeln für verschiedene Formen von $n$ (z. B. $n = 3t + 3k$ , $n = 3t + 3k + 1$ ), die die Konstruktion einer 3-guten Partition für $n$ basierend auf einer Partitionierung für ein kleineres $n'$ ermöglichen.
Symmetrische Intervalle: Die Arbeit nutzt Partitionierungen symmetrischer Ganzzahlintervalle $[-\ell; \ell]$ , um Reduktionen zu erleichtern. Lemma 1 zeigt, dass solche Intervalle 3-gute Partitionen zulassen (unter Verwendung von Tripletts, die 0 summieren), wenn $\ell \equiv 0, 1 \pmod 3$ .
Quasi-Partitionen: Um Fälle zu behandeln, in denen Standardpartitionierungen schwierig zu konstruieren sind, führen die Autoren 3-gute Quasi-Partitionen ein. Dies sind Familien von Teilmengen, die alle Zahlen in $[n]$ genau einmal abdecken, mit Ausnahme einer spezifischen Zahl (genauer gesagt $3^t$ ), die doppelt abgedeckt wird.
Rekursive Algorithmen: Für Eindeutigkeitsbeweise nutzen die Autoren einen rekursiven Algorithmus (zugeschrieben Oleg Polubasoff), der die Platzierung der größten freien Zahl $i$ bestimmt. Wenn $i$ eine Potenz von 3 ist, muss sie ein Singleton sein; andernfalls muss sie mit $3^j - i$ gepaart werden (wobei $3^{j-1} < i < 3^j$ ).

Wesentliche Beiträge und Ergebnisse

Existenzvermutung (Vermutung 1): Die Autoren vermuten, dass für jede positive ganze Zahl $n$ eine 3-gute Partition existiert.
Charakterisierung minimaler Gegenbeispiele (Theorem 1): Unter der Annahme, dass ein Gegenbeispiel existiert, beweisen die Autoren, dass das minimale Gegenbeispiel $n$ $n$ strengen Bedingungen genügen muss:
- $n = 3^t + 3k + 2$ für $t > 0$ .
- $0 \le k < \frac{3^{t-1}-1}{2}$ .
- $k \neq \frac{3^\ell-1}{2}$ für irgendeine nicht-negative ganze Zahl $\ell < t$ .
- Äquivalent dazu: $n \equiv 2 \pmod 3$ , $3k+2 < \frac{3^{t+1}+1}{2}$ und $3k+2 \neq \frac{3^{\ell+1}+1}{2}$ .
- Dies schränkt den Suchraum für potenzielle Gegenbeispiele erheblich ein.
Existenz von Quasi-Partitionen (Theorem 2): Die Autoren beweisen, dass für jedes $n$ , das die Bedingungen von Theorem 1 erfüllt (d. h. die potenzielle Form eines Gegenbeispiels), eine 3-gute Quasi-Partition existiert, bei der die Zahl $3^t$ doppelt abgedeckt wird. Dies deutet darauf hin, dass die Behinderung für eine Standardpartitionierung minimal ist.
Eindeutigkeitsergebnisse (Theorem 3): Die Arbeit stellt die Eindeutigkeit von 3-guten Partitionen für spezifische Bereiche von $n$ $n$ fest:
- Eindeutige Partitionen existieren für $n \in \{1, 2, 3, 4\}$ und für $n$ der Form $3^t - 4, 3^t - 2, 3^t - 1, 3^t, 3^t + 1, 3^t + 2, 3^t + 3, 3^t + 5$ (für $t \ge 2$ ).
- Genau zwei 3-gute Partitionen existieren für $n = 3^t - 3$ und für $n = 13$ .
- Die Autoren vermuten, dass für alle anderen $n$ (ausgenommen 13) die Anzahl der 3-guten Partitionen größer als 2 ist.
Computergestützte Verifizierung: Unter Verwendung eines von Dmitry Rybin geschriebenen Codes wurden die Vermutungen bezüglich der Existenz und der Anzahl der Partitionen für alle $n \le 844$ verifiziert.

Bedeutung und Ansprüche
Die Arbeit beansprucht, die ersten fundierten Teilergebnisse bezüglich der Existenz von 3-guten Partitionen für alle $n$ zu liefern. Durch die Charakterisierung der Form eines jeden potenziellen minimalen Gegenbeispiels schränken die Autoren den Problemraum signifikant ein. Die Einführung von Quasi-Partitionen dient als kritischer Zwischenschritt, der zeigt, dass selbst in den schwierigsten Fällen (in denen eine Standardpartitionierung fehlschlagen könnte) eine Struktur existiert, die einer Lösung sehr nahe kommt.

Die Autoren räumen ein, dass die verallgemeinerten Reduktionsmethoden (vorgeschlagen von Oleg Polubasoff) zwar den Bereich der beweisbaren Fälle erweitern, es jedoch eine offene Frage bleibt, ob diese Methoden ausreichen, um Vermutung 1 für alle $n$ vollständig zu beweisen. Die Arbeit behauptet nicht, das allgemeine Existenzproblem gelöst zu haben, sondern liefert einen strukturellen Rahmen und starke Belege, die die Vermutung stützen.