🔢 mathematics

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

Dit artikel onderzoekt het bestaan en de uniciteit van partities van de verzameling $\{1, \dots, n\}$ in deelverzamelingen van grootte ten hoogste $m$ met sommen die machten van $m$ zijn, waarbij wordt bewezen dat dergelijke partities voor oneindig veel $n$ niet bestaan wanneer $m > 3$ , ze waarschijnlijk wel voor alle $n$ bestaan wanneer $m = 3$ (onder specifieke beperkingen op potentiële tegenvoorbeelden) en het exacte aantallen voor het aantal dergelijke partities voor diverse waarden van $n$ vaststelt.

Oorspronkelijke auteurs: Vladimir Gurvich, Mariya Naumova

Gepubliceerd 2026-07-17

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Vladimir Gurvich, Mariya Naumova

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een meesterarchitect bent die een stad moet bouwen met precies $n$ unieke bakstenen, genummerd van 1 tot $n$ . Je doel is niet alleen om ze op te stapelen; je moet ze groeperen in wijken (genaamd "delen") waarbij twee strikte regels van kracht zijn. Ten eerste mag een wijk niet te druk zijn; deze kan maximaal $m$ bakstenen bevatten. Ten tweede moet het totale "gewicht" van de bakstenen in elke wijk een macht van een specifiek magisch getal $m$ zijn (zoals $m^0=1$ , $m^1=m$ , $m^2$ , enzovoort). Dit puzzelspel behoort tot de wereld van de combinatoriek, een tak van de wiskunde die bestudeert hoe objecten kunnen worden gerangschikt, geteld en gegroepeerd. Het is als het oplossen van een gigantische, oneindige Sudoku waarbij de regels veranderen afhankelijk van de grootte van het raster. Wiskundigen geven erom omdat het begrijpen van hoe getallen kunnen worden afgebroken en weer samengesteld, diepe geheimen onthult over de structuur van de wiskunde zelf, net zoals het begrijpen van hoe atomen binden helpt bij het bouwen van nieuwe materialen.

Het artikel dat je nu gaat lezen, behandelt een specifieke, lastige versie van deze puzzel, waarbij de auteurs Vladimir Gurvich en Mariya Naumova het magische getal $m$ op 3 hebben gezet. Dit betekent dat zij proberen de getallen 1 tot en met $n$ te verdelen in groepen van grootte 1, 2 of 3, waarbij de som van elke groep een macht van 3 is (1, 3, 9, 27, etc.). Ze wisten al dat voor $m=2$ , er voor elke $n$ altijd precies één manier is om dit te doen. Ze wisten ook dat voor een $m$ groter dan 3, de puzzel voor oneindig veel waarden van $n$ onmogelijk is. Maar voor $m=3$ was het antwoord een mysterie. De auteurs vermoeden sterk (conjectuur) dat er voor elk getal $n$ , ongeacht hoe groot, een oplossing bestaat.

Om dit te testen, hebben ze niet alleen gegokt; ze hebben een wiskundig vangnet gebouwd. Ze hebben bewezen dat als er voor een bepaald getal $n$ geen oplossing bestaat, dat "slechte" getal een zeer specifieke, vreemde vorm moet hebben. Het moet eruitzien als $n = 3t + 3k + 2$ , en het moet bepaalde andere specifieke patronen vermijden. Denk aan een detective die zegt: "Als er een misdaad is gepleegd, moet de verdachte een rode hoed dragen, een mank lopen en linkshandig zijn." Als je een verdachte vindt die niet aan die beschrijving voldoet, weet je dat hij niet de dader is. De auteurs hebben deze logica gebruikt om enorme delen van de getallen uit te sluiten. Ze hebben ook computersimulaties uitgevoerd om elk getal tot 844 te controleren, en in elk geval werd er een oplossing gevonden. Ze hebben zelfs een iets lossere versie van de puzzel verkend, een "quasi-partitie" genoemd, waarbij één getal twee keer mag worden gebruikt, en bewezen dat er daar ook oplossingen bestaan. Hoewel ze nog niet hebben bewezen dat de puzzel voor elk $n$ oplosbaar is, hebben ze de zoektocht naar een tegenvoorbeeld beperkt tot een zeer kleine, specifieke lijst met getallen, en ze zijn ervan overtuigd dat voor bijna alle andere getallen de oplossing niet alleen mogelijk is, maar vaak ook uniek.

Het Grote Getallen-Groeperingsspel

Stel je voor dat je een zak met genummerde tegels hebt, van 1 tot een groot getal $n$ . Jouw taak is om deze tegels in stapels te sorteren. Maar er zijn regels!

De Grootte-regel: Elke stapel mag maximaal 3 tegels bevatten.
De Som-regel: De getallen in elke stapel moeten samen optellen tot een "macht van 3". Dat wil zeggen dat de som 1, 3, 9, 27, 81, enzovoort moet zijn.

Dit is het "3-goede partitie"-probleem. De auteurs stellen een eenvoudige maar hardnekkige vraag: Kunnen we dit altijd doen, ongeacht hoeveel tegels we beginnen met?

Lange tijd wisten wiskundigen het antwoord te weten voor "2-goede" partities (waarbij stapels maximaal 2 tegels bevatten en de sommen machten van 2 zijn). Het blijkt dat er voor deze altijd precies één manier is om het te doen. Maar voor 3 worden de regels rommelig. De auteurs vermoeden dat het antwoord "Ja, het is altijd mogelijk" is, maar ze hadden het nodig om dit te bewijzen.

De "Kritische" Verdachten

In plaats van te proberen te bewijzen dat het voor elk getal werkt (wat moeilijk is), besloten de auteurs te zoeken naar de "slechteriken"—de getallen waar het faalt. Ze redeneerden dat als er een getal $n$ bestaat waar je de stapels niet kunt maken, dat een "kritiek" getal moet zijn.

Ze bewezen dat als een dergelijk kritiek getal bestaat, het niet zomaar een willekeurig getal kan zijn. Het moet een heel specifieke vermomming dragen. Het moet van de vorm zijn:
$n = 3t + 3k + 2$
En het moet aan extra voorwaarden voldoen over hoe groot $k$ is ten opzichte van $t$ .

Denk aan een uitsmijter bij een club. De uitsmijter zegt: "Als je probeert binnen te sluipen zonder kaartje, moet je een groene hoed dragen en een blauwe tas bij je hebben." Als je iemand ziet met een rode hoede, weet je zeker dat diegene niet de sluipende indringer is. De auteurs bewezen dat elk getal dat niet aan deze "groene hoed"-beschrijving voldoet, veilig is; we weten hoe we die getallen moeten groeperen. Dit elimineert een enorme hoeveelheid mogelijkheden.

De Computercontrole

Zelfs met hun slimme wiskunde waren er nog steeds enkele getallen die aan de "groene hoed"-beschrijving voldeden. Om er zeker van te zijn, hebben de auteurs (met hulp van een programmeur genaamd Dmitry Rybin) een programma geschreven om elk getal tot en met 844 te controleren.

Het resultaat: Voor elk getal van 1 tot 844 hebben ze een manier gevonden om de tegels perfect te groeperen.
De conclusie: De computer heeft geen enkel "slecht" getal gevonden. Dit ondersteunt hun vermoeden sterk dat de puzzel voor iedereen oplosbaar is.

De "Quasi-partities" Twist

De auteurs probeerden ook een iets ander spel. Wat als we één getal twee keer mogen gebruiken? Ze noemen dit een "quasi-partitie". Stel je voor dat je een reserve-tegel hebt van het getal 3, zodat je deze in twee verschillende stapels kunt gebruiken.
Ze bewezen dat je voor een specifiek bereik van getallen deze versie van de puzzel altijd kunt oplossen, en dat het getal 3 (specifiek $3^t$ ) degene is die twee keer wordt gebruikt. Dit was een nuttige tussenstap om het moeilijkere probleem te begrijpen.

Hoeveel Manieren Zijn Er?

Een van de leukste onderdelen van het artikel is het tellen van hoeveel verschillende manieren er zijn om de getallen te groeperen.

Voor sommige getallen (zoals 1, 2, 3, 4, en vele anderen) is er precies één manier om het te doen. Het is als een slot met slechts één sleutel.
Voor het getal 13, en voor getallen zoals $3t - 3$ , zijn er precies twee manieren.
Voor bijna alle andere getallen vermoeden ze dat er meer dan twee manieren zijn.

Ze ontdekten zelfs een speciale regel (Propositie 2) die stelt dat als je weet welke groepen van drie getallen (triplets) in de oplossing zitten, je de hele puzzel kunt begrijpen. Het is alsoals zeggen: "Als je weet wie de drie beste vrienden in een kamer zijn, ken je de hele sociale dynamiek."

De Kern van het Verhaal

De auteurs hebben het puzzelstukje voor elk getal in het universum nog niet volledig opgelost. Er zijn nog steeds een paar lastige getallen (zoals 35, 서38, 89 en 101) die nog niet volledig door hun wiskunde zijn vrijgepleit. Echter, ze hebben aangetoond dat als een oplossing niet bestaat, het een van deze zeer specifieke, zeldzame getallen moet zijn.

Ze zijn erover overtuigd dat de "3-goede partitie" voor elk getal $n$ bestaat. Ze hebben de makkelijke fouten uitgesloten, de eerste 844 getallen met een computer gecontroleerd en vastgesteld dat de puzzel altijd een oplossing heeft. De vraag is niet of we de getallen kunnen groeperen, maar hoeveel manieren we het kunnen doen voor de echt grote getallen. De reis om te bewijzen dat het voor elk getal werkt, zet door, maar het pad is nu veel duidelijker geworden.

Technische Samenvatting: Over de partiëring van de verzameling [n] in deelverzamelingen van grootte hoogstens m zodanig dat alle sommen machten van m zijn

Probleemstelling
Het artikel behandelt een combinatorisch partiëringsprobleem gedefinieerd op de verzameling van de eerste $n$ natuurlijke getallen, $[n] = \{1, \dots, n\}$ . Gegeven zijn gehele getallen $m > 1$ en $n > 0$ ; een deelverzameling van $[n]$ wordt gedefinieerd als $m$ -goed als de kardinaliteit hoogstens $m$ is en de som van de elementen een macht van $m$ is (d.w.z. $m^t$ voor een geheelal $t \ge 0$ ). Een partiëring van $[n]$ is $m$ -goed als elke deel van de partiëring een $m$ -goede verzameling is.

De auteurs onderzoeken de existentie en uniciteit van dergelijke partiëringen. Er wordt vastgesteld dat:

Voor $m=2$ bestaat er voor elke $n$ een unieke 2-goede partiëring.
Voor $m > 3$ zijn er oneindig veel $n$ waarvoor geen $m$ -goede partiëring bestaat (specifiek voor $n = 2(m^t + 1)$ ).
De casus $m=3$ is het primaire focuspunt, waarbij de existentie van een 3-goede partiëring voor elke $n$ niet onmiddellijk duidelijk is en een onderwerp van vermoeden blijft.

Methodologie
De auteurs maken gebruik van een combinatie van constructieve bewijzen, recursieve reducties en computationele verificatie.

Reductietechnieken: De kernmethodologie betreft "reducties", waarbij een partiëring van $[n]$ wordt geconstrueerd door specifieke delen toe te voegen aan een bekende partiëring van een kleinere verzameling $[n']$ . De auteurs definiëren specifieke reductieformules voor diverse vormen van $n$ (bijv. $n = 3t + 3k$ , $n = 3t + 3k + 1$ ) die een constructie van een 3-goede partiëring voor $n$ mogelijk maken op basis van een partiëring voor een kleinere $n'$ .
Symmetrische intervallen: Het artikel maakt gebruik van partiëringen van symmetrische gehele getalintervallen $[-\ell; \ell]$ om reducties te faciliteren. Lemma 1 toont aan dat dergelijke intervallen 3-goede partiëringen toelaten (met tripletten die sommeren tot 0) wanneer $\ell \equiv 0, 1 \pmod 3$ .
Quasi-partitiëringen: Om gevallen te behandelen waarin standaard partiëringen moeilijk te construeren zijn, introduceren de auteurs 3-goede quasi-partitiëringen. Dit zijn families van deelverzamelingen die alle getallen in $[n]$ precies één keer dekken, behalve één specifiek getal (specifiek $3^t$ ) dat tweemaal wordt gedekt.
Recursieve algoritmen: Voor uniciteitsbewijzen maken de auteurs gebruik van een recursief algoritme (toegeschreven aan Oleg Polubasoff) dat de plaatsing van het grootste vrije getal $i$ bepaalt. Als $i$ een macht van 3 is, moet het een singleton zijn; anders moet het gepaard worden met $3^j - i$ (waarbij $3^{j-1} < i < 3^j$ ).

Belangrijkste bijdragen en resultaten

Existentievermoeden (Conjecture 1): De auteurs vermoeden dat er voor elke positieve gehele $n$ een 3-goede partiëring van $[n]$ bestaat.
Karakterisering van minimale tegenvoorbeelden (Theorem 1): Uitgaande van de aanname dat er een tegenvoorbeeld bestaat, bewijzen de auteurs dat het minimale tegenvoorbeeld $n$ $n$ aan strikte voorwaarden moet voldoen:
- $n = 3^t + 3k + 2$ voor $t > 0$ .
- $0 \le k < \frac{3^{t-1}-1}{2}$ .
- $k \neq \frac{3^\ell-1}{2}$ voor elke niet-negatieve gehele $\ell < t$ .
- Equivalent aan: $n \equiv 2 \pmod 3$ , $3k+2 < \frac{3^{t+1}+1}{2}$ , en $3k+2 \neq \frac{3^{\ell+1}+1}{2}$ .
- Dit verkleint de zoekruimte voor potentiële tegenvoorbeelden aanzienlijk.
Existentie van quasi-partitiëringen (Theorem 2): De auteurs bewijzen dat voor elke $n$ die voldoet aan de voorwaarden van Theorem 1 (d.w.z. de potentiële vorm van een tegenvoorbeeld), een 3-goede quasi-partitie bestaat waarbij het getal $3^t$ tweemaal wordt gedekt. Dit suggereert dat de obstructie voor een standaard partiëring minimaal is.
Uniciteitsresultaten (Theorem 3): Het artikel stelt de uniciteit van 3-goede partiëringen vast voor specifieke bereiken van $n$ $n$ :
- Unieke partiëringen bestaan voor $n \in \{1, 2, 3, 4\}$ en voor $n$ van de vorm $3^t - 4, 3^t - 2, 3^t - 1, 3^t, 3^t + 1, 3^t + 2, 3^t + 3, 3^t + 5$ (voor $t \ge 2$ ).
- Er bestaan exact twee 3-goede partiëringen voor $n = 3^t - 3$ en voor $n = 13$ .
- De auteurs vermoeden dat voor alle andere $n$ (met uitzondering van 13), het aantal 3-goede partiëringen groter is dan 2.
Computationele verificatie: Met behulp van code geschreven door Dmitry Rybin, zijn de vermoedens betreffende de existentie en het aantal partiëringen geverifieerd voor alle $n \le 844$ .

Betekenis en claims
Het artikel claimt de eerste rigoureuze gedeeltelijke resultaten te bieden met betrekking tot de existentie van 3-goede partiëringen voor alle $n$ . Door de vorm van elk potentieel minimaal tegenvoorbeeld te karakteriseren, beperken de auteurs de probleemruimte aanzienlijk. De introductie van quasi-partitiëringen dient als een cruciale tussenstap, die aantoont dat zelfs in de moeilijkste gevallen (waar een standaard partiëring zou kunnen falen), een structuur die zeer dicht bij een oplossing ligt, aanwezig is.

De auteurs erkennen dat hoewel de algemene reductiemethoden (voorgesteld door Oleg Polubasoff) het bereik van bewijsbare gevallen uitbreiden, het een open vraag blijft of deze methoden voldoende zijn om Conjecture 1 volledig te bewijzen voor alle $n$ . Het artikel claimt niet het algemene existentieprobleem te hebben opgelost, maar biedt een structureel kader en sterk bewijs dat het vermoeden ondersteunt.