🔢 mathematics

Optimally Packing a Large Square by Unit Squares

Het artikel toont aan dat een grote vierkant met zijde $x$ gevuld kan worden met eenhedenvierkanten zodanig dat de resulterende verspilde ruimte begrensd wordt door $O(x^{3/5})$ .

Oorspronkelijke auteurs: Rory McClenagan

Gepubliceerd 2026-02-03

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Rory McClenagan

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 gigantische, vierkante kamer hebt (laten we het Kamer X noemen) en een enorme stapel identieke vloertegels van één bij één voet. Je doel is om zoveel mogelijk van de vloer te bedekken met deze tegels zonder dat ze elkaar overlappen.

Als de kamer precies 10 voet breed is, kun je perfect 10 rijen van 10 tegels leggen. Geen gaten. Maar wat als de kamer 10,3 voet breed is?

Het Probleem: De "Naïeve" Gat

Als je de tegels recht omhoog en omlaag probeert te leggen (parallel aan de muren), loop je tegen een probleem aan. Je kunt 10 volledige tegels kwijt, maar je houdt een dunne strook van 0,3 voet lege ruimte over die de hele lengte van de kamer beslaat.

Als de kamer 1.000 voet breed is, is die strook 1.000 voet lang.
De "verspilde ruimte" (het lege gebied dat je niet kunt bedekken) is enorm.

Decennialang probeerden wiskundigen een betere manier te vinden om deze kamers te tegelen om de verloren ruimte te minimaliseren. De beste eerdere methode bestond uit het licht kantelen van de tegels, wat de verspilling verminderde, maar die was nog steeds behoorlijk groot.

De Oplossing: Een "Trappenhuis" van Hoeken

Dit artikel, door Rory McClenagan, introduceert een nieuwe, slimme manier om de tegels te stapelen die de verloren ruimte aanzienlijk vermindert. In plaats van de tegels slechts één keer te kantelen, gebruikt de auteur een "dans" van twee stappen met hoeken die de fouten tegen elkaar wegstreept.

Hier is de analogie van hoe het werkt:

Stap 1: De "Gekantelde Stapels"

Stel je voor dat je de tegels niet in rechte rijen legt. In plaats daarvan bouw je ze in diagonale stapels.

Je laat de stapels lichtjes tegen de muur leunen.
Omdat ze leunen, passen ze in elkaar op een manier die een grillig, trapsgewijs patroon langs de randen creëert.
Dit laat een paar kleine, driehoekige gaten achter aan de boven- en onderkant van de kamer, maar het vult het midden zeer efficiënt.

Stap 2: De "Hoekcorrectie" (De Twee Algoritmen)

Dit is het lastige deel. Als je de stapels de hele weg naar beneden in dezelfde richting laat leunen, wordt de "grilligheid" steeds erger en erger, wat een grote opening aan het einde creëert.

De doorbraak van de auteur is het gebruik van twee verschillende stapelpatronen die samenwerken als een schaar of een ritssluiting:

Het Eerste Patroon: Je stapelt een gedeelte van de kamer door de tegels in één richting te laten leunen. Dit creëert een specifieke hoek van "verspilling" aan de bovenkant van dat gedeelte.
Het Tweede Patroon: Direct daarna schakel je over naar een tweede patroon waarbij je de tegels de tegenovergestelde kant op laat leunen (of de hoek net genoeg aanpast) om de fout van het eerste patroon te "herstellen".

Denk aan het lopen tegen een heuvel op en vervolgens direct een helling met exact dezelfde steilheid afdalen. Je komt weer op hetzelfde niveau uit, waarbij je de afstand hebt afgelegd zonder hoogte te winnen of te verliezen.

Door deze twee patronen steeds opnieuw af te wisselen, zorgt de auteur ervoor dat de "verspilde ruimte" (de gaten) klein blijft en niet groter wordt naarmate de kamer groter wordt.

Het Resultaat: Een Wiskundige Tovertruc

Het artikel bewijst dat door deze specifieke "gekantelde stapel"-methode met de "hoekcorrectie"-dans te gebruiken:

De verloren ruimte niet langer evenredig is aan de lengte van de kamer.
In plaats daarvan groeit de verloren ruimte veel, veel langzamer.

Wiskundig gezien, als de zijde van de kamer $x$ is, is de verloren ruimte ongeveer $x^{3/5}$ .

Oude manier: Verloren ruimte was ongeveer $x$ (een rechte lijn).
Nieuwe manier: Verloren ruimte is ongeveer $x^{0,6}$ (een curve die afvlakt).

Voor een enorme kamer is dit verschil enorm. Dit betekent dat je een gigantische vierkante vloer met eenheden tegels kunt bedekken en slechts een minuscuul fractie van de lege vloerruimte overlaat vergeleken met eerdere methoden.

Samenvatting

Het artikel zegt niet alleen "kantel de tegels." Het biedt een precies recept voor hoeveel je moet kantelen en wanneer je de kantelrichting moet veranderen, zodat de fouten elkaar opheffen. Hierdoor kunnen we een grote vierkant met eenheden vierkanten efficiënter stapelen dan ooit tevoren, waarbij we de kleinste hoeveelheid "verspilde" vloerruimte achterlaten die wiskundig mogelijk is met deze benadering.

Technische Samenvatting: Optimaal verpakken van een groot vierkant met eenheden vierkanten

Probleemstelling
Het artikel behandelt het probleem van het verpakken van een groot vierkant $S(x)$ met zijde $x$ met eenheden vierkanten met disjuncte interieurs. Het doel is om de verspilde ruimte $W(x)$ te minimaliseren, gedefinieerd als het oppervlak van $S(x)$ dat niet wordt bedekt door de eenheden vierkanten. Hoewel $W(x) = 0$ wanneer $x$ een geheel getal is, wordt het probleem niet-triviaal wanneer $x$ geen geheel getal is. Een naïeve uitlijning van eenheden vierkamen parallel aan de zijden van $S(x)$ levert een verspilde ruimte op van $W(x) = O(x\{x\})$ , wat vereenvoudigt tot $O(x)$ als het breukdeel $\{x\}$ niet naar nul convergeert. De centrale uitdaging is het bepalen van de optimale asymptotische groeisnelheid van $W(x)$ door eenheden vierkamen onder een lichte hoek te laten oriënteren.

Historische Context en Eerdere Grenzen
Het artikel plaatst zijn bijdrage binnen een tijdlijn van gevestigde grenzen:

Ondergrens: Roth en Vaughan (1978) bewezen dat $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$ , waarmee werd vastgesteld dat de grens niet beter kan zijn dan $\Omega(x^{1/2})$ .
Bovengrenzen:
- Erdős en Graham (1975) toonden aan dat $W(x) = O(x^{7/11})$ .
- Montgomery verbeterde dit naar $O(x^{(3-\sqrt{3})/2})$ .
- Chung en Graham (2009) verfijnden de grens verder naar $O(x^{(3+\sqrt{2})/7} \log x)$ .
- In 2020 claimden Chung en Graham een grens van $O(x^{3/5})$ , maar het artikel merkt op dat dit resultaat een fout bevatte, waardoor de best bekende grens terugviel op die van 2009 tot het huidige werk.

Methodologie
Het artikel stelt een nieuw algoritme voor om de $O(x^{3/5})$ grens te bereiken, waarbij de fout in de claim uit 2020 wordt gecorrigeerd. Het bewijs verloopt via vier afzonderlijke stadia:

Initiële Triviale Verpakking: Het vierkant $S(x)$ wordt eerst triviaal verpakt met eenheden vierkamen die parallel aan de zijden zijn uitgelijnd, waarbij twee smalle rechthoekige regio's van breedte $h$ overblijven. Eén dergelijke rechthoek, $R$ , wordt geselecteerd voor verdere verwerking.
Stapelen met Inclinatie: Rechthoek $R$ wordt verpakt met behulp van "stapels" van $n$ eenheden vierkamen die onder een hoek $\theta$ staan gekanteld. Deze stapels raken zowel de verticale als de schuine wanden van de rechthoek. Dit proces laat een trapezoïdale regio $T$ achter aan de uiteinden. De hoek $\theta$ wordt gekozen zodanig dat $\theta \asymp h^{-1/2}$ .
Tweestaps Trapezoïdale Verpakking: De kern van het algoritme omvat het vullen van de trapezoïde $T$ $T$ met behulp van twee complementaire sub-algoritmen:
- Algoritme 1: Verpakt $T$ met bijna horizontale en verticale stapels van afnemende lengte ( $m, m-1, \dots$ ). Dit algoritme introduceert een specifieke hoekverschuiving, waarbij de inclinatie verandert van $\psi$ aan de onderzijde naar $\phi$ aan de bovenzijde, waarbij het verschil $\phi - \psi \approx \theta$ is.
- Algoritme 2: Ontworpen om de hoekverschuiving die door Algoritme 1 is geïntroduceerd, te "ongedaan" te maken. Het begint waar Algoritme 1 eindigt, door stapels van lengte $m+1$ en $m$ te verpakken om de geometrie te herstellen die nodig is om Algoritme 1 te kunnen herstarten.
- Iteratieve Toepassing: Deze twee algoritmen worden achter elkaar toegepast in een cyclus. Het artikel toont aan dat de parameters ( $\phi, \psi, \theta, m$ ) vastgesteld of aangepast kunnen worden zodat de fouttermen ( $\epsilon, \epsilon'$ ) niet destructief accumuleren over iteraties.
Parameteroptimalisatie: De breedte $w$ van de trapezoïde $T$ en het aantal iteraties worden geoptimaliseerd. Het algoritme wordt $\approx \sqrt{h}$ keer toegepast om de trapezoïde te bedekken.

Belangrijkste Resultaten en Analyse
Het artikel leidt de totale verspilde ruimte $W(x)$ af door de verspilling van de verticale stapels op te tellen bij de verspilling gegenereerd binnen de trapezoïdale regio's:

Verspilling van Stapels: Het verpakken van de $O(x)$ verticale stapels met inclinatie $\theta$ genereert een verspilling proportioneel aan $O(x\theta)$ .
Verspilling van Trapezoïden: De iteratieve toepassing van de twee verpakkingsalgoritmen op de trapezoïde $T$ genereert een totale verspilling van $O(h^{3/4})$ .
Optimalisatie: De totale verspilde ruimte wordt begrensd door $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$ . Door de twee termen gelijk te stellen ( $x h^{-1/2} \sim h^{3/4}$ ), is de optimale keuze $h \sim x^{4/5}$ .

Door $h = x^{4/5}$ in de grens in te vullen, volgt:
$W(x) = O(x^{3/5})$

Betekenis en Claims
Het artikel claimt rigoureus te bewijzen dat de verspilde ruimte bij het verpakken van een groot vierkante met eenheden vierkamen begrensd wordt door $O(x^{3/5})$ . Dit resultaat valideert de claim die eerder door Chung en Graham in 2020 werd gemaakt, welke was ingetrokken vanwege een fout. De betekenis ligt in het leveren van een gecorrigeerd bewijs voor deze specifieke asymptotische grens, waarmee de voorheen best bekende grens van $O(x^{(3+\sqrt{2})/7} \log x)$ wordt verbeterd. De auteurs benadrukken dat dit wordt bereikt door een specifiek constructief algoritme dat gebruikmaakt van de interactie tussen twee verpakkingsstrategieën die hoekverschillen en foutaccumulatie binnen trapezoïdale sub-regio's beheren. Het artikel stelt geen verdere toepassingen of toekomstige implicaties voor buiten het vaststellen van deze specifieke bovengrens.