🔢 mathematics

Optimally Packing a Large Square by Unit Squares

L'article démontre qu'un grand carré de côté $x$ peut être rempli de carrés unitaires de telle sorte que l'espace perdu résultant soit borné par $O(x^{3/5})$ .

Auteurs originaux : Rory McClenagan

Publié 2026-02-03

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Rory McClenagan

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous ayez une pièce carrée géante (appelons-la Pièce X) et un énorme tas de carreaux de sol identiques de 30 cm sur 30 cm (un pied par un pied). Votre objectif est de couvrir la plus grande surface possible du sol avec ces carreaux sans qu'ils ne se chevauchent.

Si la pièce fait exactement 10 pieds de large, vous pouvez poser 10 rangées de 10 carreaux parfaitement. Sans aucun écart. Mais que se passe-t-il si la pièce fait 10,3 pieds de large ?

Le Problème : L'écart « Naïf »

Si vous essayez de poser les carreaux bien droit (parallèlement aux murs), vous rencontrez un problème. Vous pouvez placer 10 carreaux entiers, mais il reste une mince bande de 0,3 pied d'espace vide qui court sur toute la longueur de la pièce.

Si la pièce fait 1 000 pieds de large, cette bande mesure 1 000 pieds de long.
L'espace « perdu » (la zone vide que vous ne pouvez pas couvrir) est immense.

Pendant des décennies, des mathématiciens ont cherché un meilleur moyen de carreler ces pièces pour minimiser cet espace perdu. La meilleure méthode précédente consistait à incliner légèrement les carreaux, ce qui réduisait le gaspillage, mais celui-ci restait encore important.

La Solution : Un « Escalier » d'Angles

Cet article, de Rory McClenagan, introduit une nouvelle façon ingénieuse de disposer les carreaux qui réduit considérablement l'espace perdu. Au lieu de simplement incliner les carreaux une seule fois, l'auteur utilise une « danse » de deux angles qui permet d'annuler les erreurs.

Voici l'analogie de son fonctionnement :

Étape 1 : Les « Empilements Inclinés »

Imaginez que vous ne posiez pas les carreaux en rangées droites. Au lieu de cela, vous les construisez en empilements diagonaux.

Vous penchez les empilements légèrement contre le mur.
Parce qu'ils sont inclinés, ils s'emboîtent de manière à créer un motif dentelé, en escalier, le long des bords.
Cela laisse quelques petits espaces triangulaires tout en haut et tout en bas de la pièce, mais cela remplit le milieu très efficacement.

Étape 2 : La « Correction d'Angle » (Les deux algorithmes)

C'est ici que cela devient délicat. Si vous continuez à incliner les empilements de la même manière sur toute la longueur de la pièce, l'aspect « dentelé » s'aggrave de plus en plus, créant un grand vide à l'extrémité.

La percée de l'auteur est d'utiliser deux motifs de rangement différents qui travaillent ensemble comme une paire de ciseaux ou une fermeture éclair :

Le Premier Motif : Vous remplissez une section de la pièce en penchant les carreaux d'un côté. Cela crée un angle de « gaspillage » spécifique au sommet de cette section.
Le Second Motif : Immédiatement après, vous passez à un second motif qui incline les carreaux dans la direction opposée (ou ajuste l'angle juste assez) pour « annuler » l'erreur commise par le premier motif.

Imaginez que vous montez une colline, puis que vous redescendez immédiatement une pente de la même inclinaison exacte. Vous revenez au niveau initial, ayant parcouru la distance sans gagner ni perdre de hauteur.

En alternant ces deux motifs encore et encore, l'auteur s'assure que l'espace « perdu » (les écarts) reste minuscule et ne croît pas à mesure que la pièce devient plus grande.

Le Résultat : Un Tour de Magie Mathématique

L'article prouve qu'en utilisant cette méthode spécifique d'« empilement incliné » avec la « danse de correction d'angle » :

La quantité d'espace perdu n'est plus proportionnelle à la longueur de la pièce.
Au lieu de cela, l'espace perdu croît beaucoup, beaucoup plus lentement.

Mathématiquement, si la pièce a une longueur de côté $x$ , l'espace perdu est approximativement de $x^{3/5}$ .

Ancienne méthode : l'espace perdu était approximativement de $x$ (une ligne droite).
Nouvelle méthode : l'espace perdu est approximativement de $x^{0,6}$ (une courbe qui s'aplatit).

Pour une pièce massive, cette différence est énorme. Cela signifie que vous pouvez couvrir un immense carré avec des carreaux unitaires et ne laisser derrière vous qu'une infime fraction d'espace vide par rapport aux méthodes précédentes.

Résumé

L'article ne se contente pas de dire « inclinez les carreaux ». Il fournit une recette précise de combien il faut les incliner et quand changer la direction de l'inclinaison afin que les erreurs s'annulent mutuellement. Cela nous permet de remplir un grand carré avec des carrés unitaires de manière plus efficace que jamais, en laissant derrière nous la plus petite fraction d'espace de sol « perdu » mathématiquement possible avec cette approche.

Résumé Technique : Empilement Optimal d'un Grand Carré par des Carrés Unitaires

Énoncé du Problème
L'article traite du problème de l'empilement d'un grand carré $S(x)$ de côté $x$ avec des carrés unitaires ayant des intérieurs disjoints. L'objectif est de minimiser l'espace perdu $W(x)$ , défini comme l'aire de $S(x)$ non couverte par les carrés unitaires. Bien que $W(x) = 0$ lorsque $x$ est un entier, le problème devient non trivial lorsque $x$ n'est pas un entier. Un alignement naïf de carrés unitaires parallèles aux côtés de $S(x)$ produit un espace perdu de $W(x) = O(x\{x\})$ , ce qui se simplifie en $O(x)$ si la partie fractionnaire $\{x\}$ est éloignée de zéro. Le défi central consiste à déterminer le taux de croissance asymptotique optimal de $W(x)$ en permettant aux carrés unitaires d'être orientés selon de légers angles.

Contexte Historique et Bornes Précédentes
L'article situe sa contribution dans une chronologie de bornes établies :

Borne Inférieure : Roth et Vaughan (1978) ont prouvé que $W(x) > 10^{-100}\sqrt{x - \lfloor x \rfloor}$ , établissant que la borne ne peut être meilleure que $\Omega(x^{1/2})$ .
Bornes Supérieures :
- Erdős et Graham (1975) ont montré que $W(x) = O(x^{7/11})$ .
- Montgomery a amélioré cela à $O(x^{(3-\sqrt{3})/2})$ .
- Chung et Graham (2009) ont affiné davantage la borne à $O(x^{(3+\sqrt{2})/7} \log x)$ .
- En 2020, Chung et Graham ont revendiqué une borne de $O(x^{3/5})$ , mais l'article note que ce résultat contenait une erreur, ramenant la meilleure borne connue à celle de 2009 jusqu'à l'œuvre actuelle.

Méthodologie
L'article propose un nouvel algorithme pour atteindre la borne $O(x^{3/5})$ , corrigeant l'erreur de la revendication de 2020. La preuve se déroule en quatre étapes distinctes :

Empilement Trivial Initial : Le carré $S(x)$ est d'abord empilé trivialement avec des carrés unitaires parallèles aux côtés, laissant deux régions rectangulaires étroites de largeur $h$ . Une telle région rectangulaire, $R$ , est sélectionnée pour un traitement ultérieur.
Empilement avec Inclinaison : Le rectangle $R$ est empilé à l'aide de « piles » de $n$ carrés unitaires inclinées selon un angle $\theta$ . Ces piles touchent à la fois les parois verticales et les parois inclinées du rectangle. Ce processus laisse derrière lui une région trapézoïdale $T$ aux extrémités. L'angle $\theta$ est choisi de telle sorte que $\theta \asymp h^{-1/2}$ .
Empilement Trapézoïdal à Deux Étapes : Le cœur de l'algorithme consiste à remplir le trapèze $T$ $T$ en utilisant deux sous-algorithmes complémentaires :
- Algorithme 1 : Empile le $T$ en utilisant des piles presque horizontales et verticales de longueurs décroissantes ( $m, m-1, \dots$ ). Cet algorithme introduit un décalage angulaire spécifique, changeant l'inclinaison de $\psi$ au bas à $\phi$ au sommet, où la différence $\phi - \psi \approx \theta$ .
- Algorithme 2 : Conçu pour « annuler » le décalage angulaire introduit par l'Algorithme 1. Il commence là où l'Algorithme 1 s'arrête, empilant des piles de longueur $m+1$ et $m$ pour restaurer la géométrie requise pour redémarrer l'Algorithme 1.
- Application Itérative : Ces deux algorithmes sont appliqués l'un après l'autre dans un cycle. L'article démontre que les paramètres ( $\phi, \psi, \theta, m$ ) peuvent être fixés ou ajustés de telle sorte que les termes d'erreur ( $\epsilon, \epsilon'$ ) ne s'accumulent pas de manière destructive au cours des itérations.
Optimisation des Paramètres : La largeur $w$ du trapèze $T$ et le nombre d'itérations sont optimisés. L'algorithme est appliqué environ $\approx \sqrt{h}$ fois pour couvrir le trapèze.

Résultats Clés et Analyse
L'article dérive l'espace perdu total $W(x)$ en sommant le gaspillage des piles verticales et le gaspillage généré dans les régions trapézoïdales :

Gaspillage des Piles : L'empilement des $O(x)$ piles verticales avec une inclinaison $\theta$ génère un gaspillage proportionnel à $O(x\theta)$ .
Gaspillage des Trapèzes : L'application itérative des deux algorithmes d'empilement sur le trapèze $T$ génère un gaspillage total de $O(h^{3/4})$ .
Optimisation : Le gaspillage total est borné par $W(x) \ll \frac{x}{\sqrt{h}} + h^{3/4}$ . En égalisant les deux termes ( $x h^{-1/2} \sim h^{3/4}$ ), le choix optimal est $h \sim x^{4/5}$ .

En substituant $h = x^{4/5}$ dans la borne, on obtient :
$W(x) = O(x^{3/5})$

Signification et Revendications
L'article affirme prouver rigoureusement que l'espace perdu dans l'empilement d'un grand carré par des carrés unitaires est borné par $O(x^{3/5})$ . Ce résultat valide la revendication précédemment faite par Chung et Graham en 2020, qui avait été rétractée en raison d'une erreur. La signification réside dans le fait de fournir une preuve corrigée pour cette borne asymptotique spécifique, améliorant la meilleure borne connue précédemment de $O(x^{(3+\sqrt{2})/7} \log x)$ . Les auteurs soulignent que cela est réalisé grâce à un algorithme constructif spécifique impliquant l'interaction de deux stratégies d'empilement qui gèrent les écarts angulaires et l'accumulation d'erreurs au sein de sous-régions trapézoïdales. L'article ne propose pas d'autres applications ou implications futures au-delà de l'établissement de cette borne supérieure spécifique.