Expérience · Géométrie

Friedman Packing Center : des empilements de cercles exacts et certifiés

Cette expérience porte sur deux pages du Packing Center d’Erich Friedman, qui recensent, pour chaque nombre n de cercles, l’empilement de somme des rayons la plus grande connue, dans un rectangle de périmètre 4 et dans un cercle de rayon 1. Résultat : 16 des 20 entrées de la page « rectangle » pour n de 31 à 50, et l’entrée n = 50 de la page « cercle », sont créditées à l’expérience. Chaque empilement est exact, accompagné d’un certificat en arithmétique rationnelle que n’importe qui revérifie.

1. La question

Pour un nombre n de cercles, quelle somme maximale de rayons peut-on atteindre en les plaçant, sans chevauchement, dans un contenant fixé ? Les rayons sont libres. Les deux contenants de l’expérience sont le disque de rayon 1 et le rectangle de périmètre 4 : les côtés W et H vérifient W + H = 2, et la forme du rectangle est libre elle aussi. Aucune formule ne donne la réponse, hors quelques petits cas.

2. Protocole et page de référence

Erich Friedman tient les pages de son Packing Center : pour chaque n, une image de l’empilement, la valeur de Σ r tronquée à cinq décimales (le signe « + » indique une borne inférieure), le nom de l’auteur et le mois. Chaque résultat est un empilement dont les coordonnées sont contrôlées en arithmétique rationnelle exacte par un programme de quelques lignes (section 5).

3. Résultats

Au relevé du 1^er octobre 2026, la page « rectangle » s’arrêtait à n = 30 et la page « cercle » indiquait 6,53814+ pour n = 50. Au relevé du 11 octobre 2026, la page « rectangle » compte 50 entrées et la page « cercle » indique 6,53881+ pour n = 50. Le tableau donne, pour n de 31 à 50, la somme exacte des rayons de l’empilement déposé, la valeur affichée par la page et le crédit qu’elle porte.

Pour les 16 entrées créditées à l’expérience, la valeur affichée par la page est la somme exacte tronquée à cinq décimales. Pour n = 50 dans le cercle, l’empilement déposé a pour somme exacte 6,538814832 ; la valeur précédente de la page était 6,53814+.

Les empilements, tracés à partir des coordonnées exactes : le centre et le rayon de chaque cercle. La couleur suit le rayon, du violet (petit) au cyan (grand). Les cercles de la figure animée apparaissent de gauche à droite : c’est un balayage d’affichage. Les données de chaque figure sont téléchargeables en JSON.

Les 20 rectangles de n = 31 à 50 sont tracés à la même échelle. Le rectangle est libre : sa largeur W est un paramètre de l’empilement, avec W + H = 2.

4. Théorème et certificat

Le certificat est le contrôle exact des n lignes d’un fichier. Il n’utilise ni racine carrée ni tolérance : les valeurs décimales sont lues comme des nombres rationnels, et toutes les comparaisons se font sur ces rationnels.

Énoncé de validité

Proposition. Soit (x_i, y_i, r_i), i = 1…n, des nombres rationnels avec r_i > 0, et un contenant C égal soit au rectangle [0, W] × [0, H] (W rationnel, 0 < W < 2, H = 2 − W), soit au disque fermé de rayon 1 centré en l’origine. Si

1. pour le rectangle : r_i ≤ x_i ≤ W − r_i et r_i ≤ y_i ≤ H − r_i ; pour le disque : r_i < 1 et x_i² + y_i² ≤ (1 − r_i)² ;
2. pour tout i < j : (x_i − x_j)² + (y_i − y_j)² ≥ (r_i + r_j)² ;

alors (a) chaque disque fermé D_i de centre (x_i, y_i) et de rayon r_i est contenu dans C ; (b) les intérieurs de deux disques distincts sont disjoints ; (c) la somme des rayons vaut exactement Σ r_i, un nombre rationnel calculé sans arrondi.

Démonstration

(a) Rectangle : si (X, Y) est dans D_i, alors |X − x_i| ≤ r_i, donc X ∈ [x_i − r_i, x_i + r_i] ⊂ [0, W] ; de même pour Y. Disque : si P est dans D_i, alors |P| ≤ |c_i| + r_i ≤ (1 − r_i) + r_i = 1, où |c_i| ≤ 1 − r_i vient de la condition 1 par passage à la racine carrée, 1 − r_i étant positif.

(b) Si un point P était dans l’intérieur de D_i et de D_j, l’inégalité triangulaire donnerait |c_i − c_j| < r_i + r_j, donc |c_i − c_j|² < (r_i + r_j)², ce qui contredit la condition 2.

(c) C’est une somme finie de rationnels.

Ce que le certificat garantit

• que les n cercles tiennent dans le contenant, sans en sortir, même d’une quantité infime ;
• qu’aucun couple de cercles ne se chevauche : au plus, deux cercles se touchent ;
• la valeur exacte de la somme des rayons du fichier déposé ;
• que n cercles sont bien présents, ni plus ni moins.

Une borne démontrée, et le rapport de chaque entrée

Une borne supérieure donne une règle fixe, indépendante des autres entrées de la page.

Proposition. Pour tout empilement de n cercles deux à deux disjoints : (i) dans un rectangle de périmètre 4, Σ r_i ≤ √(n/π) ; (ii) dans le disque de rayon 1, Σ r_i ≤ √n.

Preuve. (i) Les disques sont disjoints et contenus dans le rectangle, dont l’aire WH est au plus 1 puisque W + H = 2 (WH ≤ ((W + H)/2)² = 1). Donc Σ π r_i² ≤ 1. Par Cauchy–Schwarz sur (r₁, …, r_n) et (1, …, 1), (Σ r_i)² ≤ n · Σ r_i² ≤ n/π. (ii) Même raisonnement avec l’aire π du disque : Σ π r_i² ≤ π, donc (Σ r_i)² ≤ n · Σ r_i² ≤ n. ∎

Cette borne est élémentaire : elle tient en quelques lignes (aire et Cauchy–Schwarz) et sert ici de règle de mesure.

Le contrôle de la borne (distinct du certificat de validité) vérifie π·(Σ r)² ≤ n pour le rectangle et (Σ r)² ≤ n pour le disque, en arithmétique rationnelle exacte (π est encadré par deux rationnels à 30 décimales, et c’est sa borne supérieure qui sert au test). Le 11/10/2026, il déclare conformes les 20 empilements du rectangle et celui du cercle. Les 16 entrées du rectangle créditées à l’expérience atteignent de 92,2 % (n = 32) à 92,7 % (n = 49) de la borne ; pour le cercle n = 50, 92,5 %. Ce rapport ne change pas quand une valeur de la page est battue.

5. Revérifier soi-même

Télécharger le fichier JSON d’un empilement, puis exécuter ce court programme Python (bibliothèque standard seule). Il lit les coordonnées en rationnels exacts, teste les conditions 1 et 2 pour toutes les paires (n(n − 1)/2 paires, soit 1 225 pour n = 50) et affiche le résultat. Pour le cercle, seule la condition de contenance change :

import json
from fractions import Fraction as F

d = json.load(open("friedman_rect_50.json"))
W = F(d["W"]); H = 2 - W                              # rectangle [0, W] x [0, H], périmètre 2(W + H) = 4
P = [tuple(F(v) for v in c) for c in d["circles"]]     # (x, y, r) en rationnels exacts
dedans = all(r > 0 and r <= x and x + r <= W and r <= y and y + r <= H for x, y, r in P)
disjoints = all((a[0]-b[0])**2 + (a[1]-b[1])**2 >= (a[2]+b[2])**2
                for i, a in enumerate(P) for b in P[i+1:])
print(len(P), dedans and disjoints, float(sum(r for _, _, r in P)))

d = json.load(open("friedman_cercle_50.json"))
P = [tuple(F(v) for v in c) for c in d["circles"]]
dedans = all(0 < r < 1 and x*x + y*y <= (1 - r)**2 for x, y, r in P)     # le disque est dans le disque unité
# (la condition de disjonction est la même que ci-dessus)

Résultat attendu pour le rectangle n = 50 : 50 True 3.6953181299845124. Les fichiers JSON contiennent aussi l'empreinte sha256 du fichier déposé.

6. La carte du défi

Les 50 entrées de chacune des deux pages, rangées par lignes de 25 (n = 1 à 25, puis 26 à 50). Cyan : créditée à l'expérience ; or : créditée à un autre contributeur pour n de 31 à 50 sur la page « rectangle » ; violet pâle : les autres entrées. Pages relevées le 11 octobre 2026.

7. Ce que modélise cette question

Ce type de question modélise des problèmes de placement qui se posent dans la découpe et l'emballage (disposer des pièces rondes de tailles différentes dans une plaque ou une boîte), le placement de capteurs ou d'antennes à zone de couverture circulaire et l'étude des matériaux granulaires. Les pages de Friedman servent de référence commune pour comparer des empilements ; ceux présentés ici sont exacts, certifiés et revérifiables par n'importe qui.

Mon projet d'IA au service de ma recherche

Ce défi n'est pas un but en soi : c'est un banc d'essai de ma recherche sur une IA embarquée certifiable. Mon projet d'IA, dont le fonctionnement reste confidentiel, me permet d'atteindre 16 des 20 entrées du rectangle et l'entrée du cercle, chacune revérifiée en arithmétique exacte. Le certificat et l'arbitre en font foi : ce n'est pas mon explication qu'il faut croire, c'est le résultat qui se revérifie. Il s'agit du meilleur résultat connu à la date indiquée, pas d'un optimum démontré.