A unit circle contains three equal circles, each tangent to the other two and also tangent to the outer circle. The curved triangular gaps that remain are then filled recursively: in every gap bounded by three mutually tangent circles, insert the unique new circle tangent to all three boundary circles, and repeat this for a fixed number of generations. The problem asks for the fraction of the unit disk that is still uncovered after 10 iterations.
The geometry looks two-dimensional, but the implementations never need explicit coordinates. The entire computation can be driven by curvatures alone, which turns the packing into a clean recursive area sum.
The key idea is to represent every circle by its signed curvature \(k=1/r\). Inner circles have positive curvature, while the enclosing unit circle is treated as a circle of curvature \(-1\). With that convention, every local configuration is governed by Descartes' circle theorem.
For four mutually tangent circles with curvatures \(k_1,k_2,k_3,k_4\), Descartes' theorem says
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$$
If we fix the outer circle as \(k_1=-1\) and the three equal inner circles as \(k_2=k_3=k_4=k\), then
$$2(1+3k^2)=(-1+3k)^2,$$
which simplifies to
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$$
This is the only positive solution, so each initial inner circle has radius
$$r=\frac{1}{k}.$$
Its area is therefore \(\pi/k^2\), and the three original circles already cover \(3\pi/k^2\) of the unit disk.
Suppose a gap is bounded by three mutually tangent circles with curvatures \(a,b,c\). Solving Descartes' theorem for the fourth curvature gives
$$x=a+b+c\pm2\sqrt{ab+ac+bc}.$$
The minus sign recovers the already existing fourth circle of the Descartes configuration, while the plus sign gives the new smaller circle that fits inside the open gap. So the inserted circle has curvature
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
and area
$$\frac{\pi}{x^2}.$$
After that insertion, the original gap is split into exactly three smaller gaps bounded by the triples \((a,b,x)\), \((a,c,x)\), and \((b,c,x)\). This is why a depth-\(d\) computation has a ternary recursive structure.
The starting picture has only two geometric gap types. There is one central gap enclosed by the three equal circles, and there are three congruent boundary gaps, each enclosed by the outer circle and two adjacent inner circles. If \(G_d(a,b,c)\) denotes the total area added inside a gap with boundary curvatures \(a,b,c\) over \(d\) generations, then
$$G_0(a,b,c)=0,$$
and for \(d\ge1\),
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
where
$$x=a+b+c+2\sqrt{ab+ac+bc}.$$
Therefore the total covered area after \(d\) iterations is
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$$
and the required uncovered ratio is
$$R_d=1-\frac{C_d}{\pi}.$$
The first recursive step already shows every ingredient of the full solution. In the central gap we use \((k,k,k)\), so the new curvature is
$$k_{\text{center}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3.$$
In a boundary gap we use \((-1,k,k)\), so
$$k_{\text{edge}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3.$$
Thus depth 1 adds one central circle and three congruent edge circles, giving
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{center}}^2}+\frac{3}{k_{\text{edge}}^2}\right)\approx0.198133880558.$$
This matches the checkpoint used in the C++ implementation, so the recurrence is not just plausible geometry; it reproduces the numeric behavior exactly.
Nothing is being approximated except the final floating-point evaluation. Every gap in the packing is determined completely by the three circles that bound it, and Descartes' theorem gives the unique circle that can be inserted next. Because each new circle partitions its parent gap into three disjoint child gaps, summing the recursively generated areas counts every inserted circle once and only once.
The C++, Python, and Java implementations all follow the formula above literally. They first compute \(k=1+2/\sqrt3\), evaluate the area of the three original equal circles, and then make one recursive call for the central gap and one recursive call for a boundary gap, multiplying the latter by 3 because of symmetry.
Each recursive call receives the three boundary curvatures and the remaining depth. If the depth is zero, it contributes no new area. Otherwise it computes the Descartes curvature \(x\), adds the area \(\pi/x^2\), and recurses on the three child gaps. After the recursion returns, the implementation divides the total covered area by \(\pi\) and subtracts from 1 to obtain the uncovered fraction.
The three languages differ only in presentation details. The C++ version keeps the arithmetic in extended precision, optionally accepts a different depth from the command line, and checks the depth-0 and depth-1 values before printing the final result. The Python and Java versions use the same recurrence with standard floating-point arithmetic and print the depth-10 value directly.
One starting gap produces a ternary recursion tree. The number of inserted circles inside a single gap up to depth \(d\) is
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}.$$
There are four starting gaps in total, so the full computation inserts
$$4\cdot\frac{3^d-1}{2}=2(3^d-1)$$
circles beyond the initial three. Hence the running time is \(\Theta(3^d)\), and the recursion stack uses \(\Theta(d)\) memory. For the actual input \(d=10\), this is only 118096 inserted circles, which is easily manageable.
In einem Einheitskreis liegen drei gleich große Kreise, die sich paarweise berühren und außerdem den Außenkreis tangieren. Die verbleibenden krummlinigen Dreieckslücken werden dann rekursiv gefüllt: In jede von drei tangentialen Kreisen begrenzte Lücke wird der eindeutig bestimmte neue Tangentialkreis eingesetzt, und dieser Schritt wird über eine feste Anzahl von Generationen wiederholt. Gesucht ist der Anteil der Einheitskreisscheibe, der nach 10 Iterationen unbedeckt bleibt.
Obwohl das Bild stark geometrisch aussieht, braucht der Algorithmus keine expliziten Koordinaten. Alles lässt sich allein über Krümmungen formulieren, sodass die Aufgabe zu einer sauberen rekursiven Flächensumme wird.
Jeder Kreis wird durch seine vorzeichenbehaftete Krümmung \(k=1/r\) beschrieben. Innere Kreise haben positive Krümmung, der umschließende Einheitskreis wird mit Krümmung \(-1\) behandelt. Mit dieser Konvention genügt in jeder lokalen Konfiguration der Satz von Descartes.
Für vier paarweise tangentiale Kreise mit Krümmungen \(k_1,k_2,k_3,k_4\) gilt
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$$
Setzt man den Außenkreis als \(k_1=-1\) und die drei gleichen Innenkreise als \(k_2=k_3=k_4=k\), so erhält man
$$2(1+3k^2)=(-1+3k)^2,$$
also
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$$
Das ist die einzige positive Lösung. Deshalb hat jeder der drei Startkreise Radius
$$r=\frac{1}{k},$$
und zusammen bedecken sie bereits die Fläche \(3\pi/k^2\).
Sei eine Lücke von drei tangentialen Kreisen mit Krümmungen \(a,b,c\) begrenzt. Löst man den Descartes-Zusammenhang nach der vierten Krümmung auf, ergibt sich
$$x=a+b+c\pm2\sqrt{ab+ac+bc}.$$
Das Minuszeichen liefert den bereits vorhandenen vierten Kreis derselben Konfiguration zurück, während das Pluszeichen den neuen kleineren Kreis in der offenen Lücke erzeugt. Für den einzusetzenden Kreis gilt also
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
mit Fläche
$$\frac{\pi}{x^2}.$$
Nach dem Einsetzen zerfällt die ursprüngliche Lücke in genau drei kleinere Lücken mit Randkrümmungen \((a,b,x)\), \((a,c,x)\) und \((b,c,x)\). Daher entsteht natürlich eine ternäre Rekursion.
Im Startbild gibt es nur zwei Lückentypen. Es gibt eine zentrale Lücke zwischen den drei gleichen Innenkreisen und drei kongruente Randlücken zwischen Außenkreis und je zwei benachbarten Innenkreisen. Bezeichne mit \(G_d(a,b,c)\) die gesamte in einer Lücke mit Randkrümmungen \(a,b,c\) während \(d\) Generationen hinzugefügte Fläche. Dann gilt
$$G_0(a,b,c)=0,$$
und für \(d\ge1\)
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
wobei
$$x=a+b+c+2\sqrt{ab+ac+bc}.$$
Damit ist die gesamte bedeckte Fläche nach \(d\) Iterationen
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$$
und der gesuchte unbedeckte Anteil lautet
$$R_d=1-\frac{C_d}{\pi}.$$
Schon der erste Rekursionsschritt enthält alle wesentlichen Ideen. In der zentralen Lücke mit \((k,k,k)\) ist die neue Krümmung
$$k_{\text{Zentrum}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3.$$
In einer Randlücke mit \((-1,k,k)\) erhält man
$$k_{\text{Rand}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3.$$
Für Tiefe 1 kommt also ein Kreis in der Mitte und drei kongruente Kreise am Rand hinzu. Der unbedeckte Anteil ist dann
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{Zentrum}}^2}+\frac{3}{k_{\text{Rand}}^2}\right)\approx0.198133880558.$$
Genau dieser Wert erscheint als Kontrollpunkt in der C++-Implementierung. Die Rekursion beschreibt die Geometrie also exakt.
Abgesehen von der abschließenden Gleitkommaauswertung wird nichts angenähert. Jede Lücke ist vollständig durch ihre drei Randkreise bestimmt, und der Satz von Descartes liefert genau den einen Kreis, der als Nächstes eingesetzt werden kann. Da jeder neue Kreis seine Elternlücke in drei disjunkte Teilstücke zerlegt, wird jede eingefügte Kreisfläche in der rekursiven Summe genau einmal erfasst.
Die C++-, Python- und Java-Implementierungen setzen die obigen Formeln unmittelbar um. Zuerst wird \(k=1+2/\sqrt3\) berechnet, dann die Fläche der drei Startkreise bestimmt, anschließend ein rekursiver Aufruf für die zentrale Lücke und ein rekursiver Aufruf für eine Randlücke durchgeführt; letzterer wird wegen der Symmetrie mit 3 multipliziert.
Jeder rekursive Aufruf erhält drei Randkrümmungen und die verbleibende Tiefe. Bei Tiefe 0 wird keine weitere Fläche hinzugefügt. Andernfalls wird die Descartes-Krümmung \(x\) berechnet, die Fläche \(\pi/x^2\) addiert und auf die drei Kindlücken weiterverzweigt. Nach Abschluss der Rekursion wird die gesamte bedeckte Fläche durch \(\pi\) geteilt und von 1 abgezogen.
Die Unterschiede zwischen den Sprachen betreffen nur die Ausführung. Die C++-Version rechnet intern mit erweiterter Präzision, akzeptiert optional eine andere Tiefe über die Kommandozeile und prüft die Werte für Tiefe 0 und 1. Die Python- und Java-Versionen benutzen dieselbe Rekursion mit gewöhnlicher Gleitkommaarithmetik und geben direkt den Wert für Tiefe 10 aus.
Eine Startlücke erzeugt einen ternären Rekursionsbaum. Die Anzahl der innerhalb einer einzigen Lücke bis Tiefe \(d\) eingefügten Kreise ist
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}.$$
Da es insgesamt vier Startlücken gibt, werden zusätzlich zu den ursprünglichen drei Kreisen insgesamt
$$4\cdot\frac{3^d-1}{2}=2(3^d-1)$$
Kreise eingefügt. Die Laufzeit ist also \(\Theta(3^d)\), der Rekursionsspeicher \(\Theta(d)\). Für den tatsächlichen Fall \(d=10\) sind das nur 118096 zusätzliche Kreise und damit rechnerisch völlig unproblematisch.
Birim çemberin içine, birbirine ve dış çembere teğet üç eş çember yerleştiriliyor. Daha sonra geride kalan eğrisel üçgen boşlukların her birine, o boşluğu sınırlayan üç çembere de teğet olan tek yeni çember yerleştiriliyor ve bu işlem sabit sayıda nesil boyunca tekrarlanıyor. Sorulan şey, 10 iterasyon sonunda birim disk alanının ne kadarının hâlâ boş kaldığıdır.
Şekil iki boyutlu geometri problemi gibi görünse de çözüm açık koordinatlar gerektirmez. Tüm hesap, yalnızca eğrilikler üzerinden yürütülür; böylece paketleme problemi temiz bir özyinelemeli alan toplamına dönüşür.
Her çemberi işaretli eğrilik \(k=1/r\) ile temsil ediyoruz. İç çemberlerin eğriliği pozitiftir; dıştaki birim çember ise \(-1\) eğrilikli bir çember gibi ele alınır. Bu işaret seçimi sayesinde her yerel yapı Descartes çember teoremiyle çözülebilir.
Dört karşılıklı teğet çemberin eğrilikleri \(k_1,k_2,k_3,k_4\) ise
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2$$
eşitliği geçerlidir. Dış çemberi \(k_1=-1\), üç eş iç çemberi de \(k_2=k_3=k_4=k\) alırsak
$$2(1+3k^2)=(-1+3k)^2$$
elde edilir. Buradan
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}$$
çıkar. Pozitif tek kök bu olduğu için başlangıçtaki her iç çemberin yarıçapı
$$r=\frac{1}{k}$$
olur. Dolayısıyla bu üç çember daha en başta toplam \(3\pi/k^2\) alan kaplar.
Sınırını eğrilikleri \(a,b,c\) olan üç teğet çemberin oluşturduğu bir boşluk düşünelim. Descartes bağıntısı dördüncü eğrilik için
$$x=a+b+c\pm2\sqrt{ab+ac+bc}$$
verir. Eksi işaret aynı Descartes dörtlüsündeki zaten mevcut olan öteki çemberi geri verir; artı işaret ise açık boşluğu dolduran yeni ve daha küçük çemberi üretir. Bu yüzden yerleştirilecek çemberin eğriliği
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
ve alanı
$$\frac{\pi}{x^2}$$
olur. Yeni çember eklendikten sonra ana boşluk tam olarak üç alt boşluğa ayrılır: \((a,b,x)\), \((a,c,x)\) ve \((b,c,x)\). Özyinelemenin dallanma yapısı buradan gelir.
Başlangıç resminde aslında sadece iki tür boşluk vardır. Üç eş iç çemberin ortasında bir merkez boşluğu bulunur. Ayrıca dış çember ile komşu iki iç çember arasında üç eş kenar boşluğu vardır. Sınır eğrilikleri \(a,b,c\) olan bir boşlukta \(d\) nesil boyunca eklenen toplam alanı \(G_d(a,b,c)\) ile gösterelim. O zaman
$$G_0(a,b,c)=0,$$
ve \(d\ge1\) için
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
burada
$$x=a+b+c+2\sqrt{ab+ac+bc}.$$
Böylece \(d\) iterasyon sonundaki toplam kaplı alan
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k)$$
olur ve istenen boş oran
$$R_d=1-\frac{C_d}{\pi}$$
şeklindedir.
İlk özyineleme adımı, tüm çözümün özünü gösterir. Merkez boşluğunda \((k,k,k)\) kullanıldığı için yeni eğrilik
$$k_{\text{merkez}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3$$
olur. Bir kenar boşluğunda ise \((-1,k,k)\) kullanılır ve
$$k_{\text{kenar}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3$$
elde edilir. Demek ki derinlik 1'de bir merkez çemberi ve üç eş kenar çemberi eklenir. Sonuçta boş oran
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{merkez}}^2}+\frac{3}{k_{\text{kenar}}^2}\right)\approx0.198133880558$$
çıkar. Bu sayı C++ uygulamasındaki kontrol noktasıyla tam uyuşur; yani kurulan bağıntı yalnızca sezgisel değil, doğrudan sayısal olarak da doğrulanır.
Son aşamadaki kayan nokta değerlendirmesi dışında hiçbir yaklaşık geometri yapılmaz. Her boşluk, onu sınırlayan üç çember tarafından tamamen belirlenir ve Descartes teoremi sıradaki tek teğet çemberi verir. Yeni çember, ebeveyn boşluğu üç ayrık alt boşluğa böldüğü için özyinelemeli toplam her eklenen çember alanını bir kez ve yalnızca bir kez sayar.
C++, Python ve Java uygulamaları bu formülleri doğrudan uygular. Önce \(k=1+2/\sqrt3\) hesaplanır, üç başlangıç çemberinin alanı toplanır, sonra merkez boşluğu için bir özyinelemeli çağrı ve kenar boşluğu için bir özyinelemeli çağrı yapılır; kenar boşluğu simetriden dolayı 3 ile çarpılır.
Her özyinelemeli çağrı üç sınır eğriliği ile kalan derinliği alır. Derinlik sıfırsa yeni alan eklemez. Aksi halde Descartes eğriliği \(x\) bulunur, \(\pi/x^2\) alanı eklenir ve üç alt boşluk için yeniden çağrı yapılır. Bütün katkılar toplandıktan sonra toplam kaplı alan \(\pi\)'ye bölünür ve 1'den çıkarılarak boş oran elde edilir.
Diller arasındaki farklar yalnızca uygulama ayrıntılarıdır. C++ sürümü hesabı genişletilmiş duyarlıkla yürütür, isteğe bağlı farklı derinlik alabilir ve derinlik 0 ile 1 değerlerini doğrular. Python ve Java sürümleri aynı özyinelemeyi standart kayan nokta aritmetiğiyle kullanır ve doğrudan derinlik 10 sonucunu yazar.
Tek bir başlangıç boşluğu üç dallı bir özyineleme ağacı üretir. Tek bir boşluk içine derinlik \(d\)'ye kadar eklenen çember sayısı
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}$$
olur. Toplam dört başlangıç boşluğu bulunduğu için, ilk üç çembere ek olarak yerleştirilen çember sayısı
$$4\cdot\frac{3^d-1}{2}=2(3^d-1)$$
kadardır. Bu nedenle zaman karmaşıklığı \(\Theta(3^d)\), çağrı yığını belleği ise \(\Theta(d)\) olur. Gerçek giriş olan \(d=10\) için bu yalnızca 118096 ek çember demektir; hesap rahatlıkla yapılır.
Dentro del círculo unidad se colocan tres círculos iguales, tangentes entre sí y también tangentes al círculo exterior. Los huecos curvilíneos restantes se rellenan de forma recursiva: en cada hueco limitado por tres círculos mutuamente tangentes se inserta el único círculo nuevo tangente a los tres, y el proceso se repite durante un número fijo de generaciones. Se pide la fracción del disco unidad que sigue sin cubrirse después de 10 iteraciones.
Aunque el dibujo parece exigir geometría con coordenadas, las implementaciones no necesitan posiciones explícitas. Toda la cuenta puede hacerse usando solo curvaturas, lo que convierte el empaquetamiento en una suma recursiva de áreas.
Representamos cada círculo mediante su curvatura con signo \(k=1/r\). Los círculos interiores tienen curvatura positiva, mientras que el círculo unidad envolvente se trata como un círculo de curvatura \(-1\). Con esa convención, cada configuración local queda descrita por el teorema de Descartes.
Si cuatro círculos mutuamente tangentes tienen curvaturas \(k_1,k_2,k_3,k_4\), entonces
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$$
Tomando el círculo exterior como \(k_1=-1\) y los tres círculos iguales como \(k_2=k_3=k_4=k\), obtenemos
$$2(1+3k^2)=(-1+3k)^2,$$
de donde sale
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$$
Es la única raíz positiva, así que cada círculo inicial tiene radio
$$r=\frac{1}{k}$$
y área \(\pi/k^2\). Los tres juntos cubren desde el principio \(3\pi/k^2\).
Consideremos un hueco limitado por tres círculos tangentes con curvaturas \(a,b,c\). Al despejar la cuarta curvatura en la relación de Descartes se obtiene
$$x=a+b+c\pm2\sqrt{ab+ac+bc}.$$
El signo menos devuelve el cuarto círculo ya existente en esa configuración, mientras que el signo más produce el nuevo círculo pequeño que cabe en el hueco abierto. Por tanto, la curvatura del círculo insertado es
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
y su área vale
$$\frac{\pi}{x^2}.$$
Una vez insertado, el hueco original se divide exactamente en tres subhuecos con ternas de curvaturas \((a,b,x)\), \((a,c,x)\) y \((b,c,x)\). Ahí nace la recurrencia ternaria.
La figura inicial solo tiene dos tipos geométricos de hueco. Hay un hueco central encerrado por los tres círculos iguales y tres huecos de borde congruentes, cada uno limitado por el círculo exterior y dos círculos interiores contiguos. Si \(G_d(a,b,c)\) es el área total añadida dentro de un hueco con curvaturas de borde \(a,b,c\) durante \(d\) generaciones, entonces
$$G_0(a,b,c)=0,$$
y para \(d\ge1\)
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
donde
$$x=a+b+c+2\sqrt{ab+ac+bc}.$$
Así, el área total cubierta tras \(d\) iteraciones es
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$$
y la fracción pedida de área no cubierta es
$$R_d=1-\frac{C_d}{\pi}.$$
La primera iteración ya muestra toda la mecánica del problema. En el hueco central usamos \((k,k,k)\), así que la nueva curvatura es
$$k_{\text{centro}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3.$$
En un hueco de borde usamos \((-1,k,k)\), por lo que
$$k_{\text{borde}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3.$$
En profundidad 1 se añaden entonces un círculo central y tres círculos de borde congruentes, y queda
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{centro}}^2}+\frac{3}{k_{\text{borde}}^2}\right)\approx0.198133880558.$$
Ese valor coincide con la comprobación usada en C++, de modo que la recurrencia reproduce exactamente el comportamiento numérico de la figura.
No hay aproximación geométrica en el modelo, aparte de la evaluación final en coma flotante. Cada hueco queda determinado por los tres círculos que lo limitan, y el teorema de Descartes da el único círculo que puede insertarse a continuación. Como cada nuevo círculo parte su hueco padre en tres huecos disjuntos, la suma recursiva cuenta cada círculo añadido una sola vez.
Las implementaciones en C++, Python y Java siguen estas fórmulas de forma literal. Primero calculan \(k=1+2/\sqrt3\), suman el área de los tres círculos iniciales y luego hacen una llamada recursiva para el hueco central y otra para un hueco de borde, multiplicando esta última por 3 gracias a la simetría.
Cada llamada recursiva recibe las tres curvaturas del borde y la profundidad restante. Si la profundidad es cero, no añade área. En otro caso calcula la curvatura de Descartes \(x\), suma \(\pi/x^2\) y continúa sobre los tres subhuecos. Cuando termina la recursión, el área cubierta total se divide por \(\pi\) y se resta de 1 para obtener la fracción no cubierta.
Las diferencias entre lenguajes son menores. La versión en C++ usa precisión extendida, permite fijar otra profundidad por línea de comandos y verifica los casos de profundidad 0 y 1. Las versiones en Python y Java usan la misma recurrencia con aritmética estándar de punto flotante y escriben directamente el resultado de profundidad 10.
Un hueco inicial genera un árbol recursivo ternario. El número de círculos añadidos dentro de un solo hueco hasta profundidad \(d\) es
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}.$$
Como hay cuatro huecos iniciales, el número total de círculos añadidos, aparte de los tres originales, es
$$4\cdot\frac{3^d-1}{2}=2(3^d-1).$$
Por tanto, el tiempo es \(\Theta(3^d)\) y la memoria de pila es \(\Theta(d)\). Para el valor real \(d=10\), eso significa solo 118096 círculos insertados, perfectamente manejables.
在单位圆内部先放入三个大小相同的圆，它们两两相切，并且都与外侧的单位圆相切。这样会留下若干弯曲三角形状的空隙。接下来对每一个由三条相切圆弧围成的空隙，都放入一个同时与这三个边界圆相切的新圆，然后继续对新产生的空隙重复同样的操作。题目要求的是：经过 10 次迭代之后，单位圆盘中仍然没有被覆盖的面积比例是多少。
这道题看起来像是坐标几何题，但实现时完全不需要追踪圆心坐标。只要使用曲率，就能把整个圆填充过程写成一个严格的递归面积求和问题。
把每个圆记为带符号的曲率 \(k=1/r\)。内部圆的曲率为正，包住它们的单位圆则记作曲率 \(-1\)。采用这个约定后，所有局部构型都可以直接套用 Descartes 圆定理。
若四个圆两两相切，曲率分别为 \(k_1,k_2,k_3,k_4\)，则有
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$$
把外圆取为 \(k_1=-1\)，三个相同的内圆取为 \(k_2=k_3=k_4=k\)，可得
$$2(1+3k^2)=(-1+3k)^2,$$
整理后得到
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$$
这是唯一的正根，因此初始三个内圆的半径都是
$$r=\frac{1}{k}$$
每个圆的面积为 \(\pi/k^2\)，所以初始三圆总共已经覆盖了 \(3\pi/k^2\) 的面积。
设某个空隙由三个互相相切的边界圆围成，它们的曲率分别为 \(a,b,c\)。把 Descartes 关系看成关于第四个圆曲率的方程，可以写成
$$x=a+b+c\pm2\sqrt{ab+ac+bc}$$
减号对应的是这个 Descartes 四元组中原本就存在的那个“另一侧”的圆，真正填入当前空隙的新圆必须取加号，因此
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
就是新圆的曲率，而它的面积是
$$\frac{\pi}{x^2}$$
放入这个新圆以后，原来的空隙会被准确地分裂成三个更小的空隙，边界曲率三元组分别是 \((a,b,x)\)、\((a,c,x)\) 和 \((b,c,x)\)。这正是递归式出现三叉分支的原因。
整个初始图形其实只有两种不同类型的空隙。第一种是三个相同内圆围出的中心空隙，只有 1 个。第二种是外圆和两个相邻内圆围出的边缘空隙，这种空隙一共有 3 个，而且彼此全等。设 \(G_d(a,b,c)\) 表示在边界曲率为 \(a,b,c\) 的空隙中继续填充 \(d\) 代所新增的总面积，那么
$$G_0(a,b,c)=0,$$
并且对 \(d\ge1\)，有
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
其中
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
于是，迭代 \(d\) 次后的总覆盖面积为
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$$
题目要求的未覆盖比例就是
$$R_d=1-\frac{C_d}{\pi}$$
只看第一代就能把整个数学结构看清楚。中心空隙对应 \((k,k,k)\)，因此新圆曲率是
$$k_{\text{center}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3$$
边缘空隙对应 \((-1,k,k)\)，因此新圆曲率是
$$k_{\text{edge}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3$$
也就是说，深度 1 时一共新增 4 个圆：中心 1 个，边缘 3 个。此时未覆盖比例为
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{center}}^2}+\frac{3}{k_{\text{edge}}^2}\right)\approx0.198133880558$$
这个数值正好与 C++ 实现中的检查值一致，说明递推公式不仅形式正确，而且与程序行为完全吻合。
除了最后用浮点数求值之外，这个模型本身没有任何几何近似。每个空隙都由恰好三个边界圆完全决定，而 Descartes 定理给出唯一能够继续放入该空隙的圆。每插入一个新圆，父空隙就被分成三个互不重叠的子空隙，因此递归面积和恰好把每一个新增圆算一次，不会漏算，也不会重算。
C++、Python 和 Java 三份实现都在直接执行上面的公式。它们先计算 \(k=1+2/\sqrt3\)，求出最初三个相同圆的面积，然后对中心空隙做一次递归，对边缘空隙做一次递归，再把边缘结果乘以 3，因为三块边缘区域完全对称。
每次递归调用都接收三个边界曲率以及剩余深度。若深度为 0，就不再新增面积；否则先计算 Descartes 曲率 \(x\)，累加 \(\pi/x^2\)，再继续处理三个子空隙。全部返回之后，把总覆盖面积除以 \(\pi\)，再用 1 减去这个比例，就得到题目要求的未覆盖面积比。
三种语言之间只有实现层面的细微差别。C++ 版本用扩展精度计算，并且可以从命令行改深度，还会先验证深度 0 和深度 1 的结果。Python 和 Java 版本使用同样的递归结构，只是采用标准双精度浮点并直接输出深度 10 的答案。
单个初始空隙会生成一棵三叉递归树。在一个空隙内部，深度到 \(d\) 为止新增的圆个数为
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}$$
整个问题共有 4 个初始空隙，所以除去最开始的 3 个圆之后，总新增圆数是
$$4\cdot\frac{3^d-1}{2}=2(3^d-1)$$
因此时间复杂度为 \(\Theta(3^d)\)，递归栈空间为 \(\Theta(d)\)。对实际输入 \(d=10\) 来说，总共只需要处理 118096 个新增圆，规模非常小。
Внутри единичного круга расположены три одинаковые окружности, каждая из которых касается двух остальных и внешней окружности. Оставшиеся криволинейные треугольные зазоры затем заполняются рекурсивно: в каждый зазор, ограниченный тремя взаимно касающимися окружностями, вставляется единственная новая окружность, касающаяся всех трёх, после чего тот же процесс повторяется заданное число поколений. Требуется найти долю площади единичного диска, которая остаётся непокрытой после 10 итераций.
Хотя рисунок выглядит как задача на координатную геометрию, в коде координаты вообще не нужны. Достаточно работать только с кривизнами, и тогда вся задача сводится к рекурсивному суммированию площадей.
Каждую окружность удобно описывать знаковой кривизной \(k=1/r\). Внутренние окружности имеют положительную кривизну, а внешняя единичная окружность рассматривается как окружность кривизны \(-1\). При таком соглашении все локальные конфигурации подчиняются теореме Декарта о четырёх касающихся окружностях.
Если четыре окружности с кривизнами \(k_1,k_2,k_3,k_4\) попарно касаются, то
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$$
Пусть внешняя окружность имеет кривизну \(k_1=-1\), а три одинаковые внутренние окружности имеют кривизну \(k_2=k_3=k_4=k\). Тогда
$$2(1+3k^2)=(-1+3k)^2,$$
откуда следует
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$$
Это единственный положительный корень, значит радиус каждой исходной внутренней окружности равен
$$r=\frac{1}{k}.$$
Площадь одной такой окружности равна \(\pi/k^2\), а три исходные окружности сразу покрывают площадь \(3\pi/k^2\).
Пусть некоторый зазор ограничен тремя взаимно касающимися окружностями с кривизнами \(a,b,c\). Решая формулу Декарта относительно четвёртой кривизны, получаем
$$x=a+b+c\pm2\sqrt{ab+ac+bc}.$$
Знак минус возвращает уже существующую четвёртую окружность той же конфигурации, а знак плюс даёт новую меньшую окружность, которая действительно заполняет открытый зазор. Поэтому кривизна вставляемой окружности равна
$$x=a+b+c+2\sqrt{ab+ac+bc},$$
а её площадь равна
$$\frac{\pi}{x^2}.$$
После вставки исходный зазор распадается ровно на три меньших зазора с тройками граничных кривизн \((a,b,x)\), \((a,c,x)\) и \((b,c,x)\). Именно поэтому рекурсия имеет троичную ветвистость.
В начальной картинке есть только два типа зазоров. Один центральный зазор ограничен тремя одинаковыми внутренними окружностями, а ещё три конгруэнтных краевых зазора ограничены внешней окружностью и двумя соседними внутренними. Обозначим через \(G_d(a,b,c)\) суммарную площадь, добавляемую внутри зазора с граничными кривизнами \(a,b,c\) за \(d\) поколений. Тогда
$$G_0(a,b,c)=0,$$
а при \(d\ge1\)
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
где
$$x=a+b+c+2\sqrt{ab+ac+bc}.$$
Следовательно, полная покрытая площадь после \(d\) итераций равна
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$$
а искомая доля незаполненной площади равна
$$R_d=1-\frac{C_d}{\pi}.$$
Уже на первом шаге видна вся структура решения. Для центрального зазора \((k,k,k)\) новая кривизна равна
$$k_{\text{центр}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3.$$
Для краевого зазора \((-1,k,k)\) получаем
$$k_{\text{край}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3.$$
Значит, на глубине 1 добавляется одна центральная окружность и три одинаковые краевые, и доля незаполненной площади становится
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{центр}}^2}+\frac{3}{k_{\text{край}}^2}\right)\approx0.198133880558.$$
Именно это число используется как контрольное в реализации на C++, так что рекуррентная формула полностью согласована с вычислениями.
Кроме финального вычисления в плавающей точке, здесь нет никакого приближения. Каждый зазор полностью задаётся тремя ограничивающими его окружностями, и теорема Декарта однозначно определяет следующий вставляемый круг. Поскольку новый круг разбивает родительский зазор на три неперекрывающихся дочерних, рекурсивная сумма считает площадь каждого добавленного круга ровно один раз.
Реализации на C++, Python и Java буквально следуют этим формулам. Сначала вычисляется \(k=1+2/\sqrt3\), затем суммируется площадь трёх исходных окружностей, после чего выполняется один рекурсивный вызов для центрального зазора и один рекурсивный вызов для краевого зазора; краевой вклад умножается на 3 по симметрии.
Каждый рекурсивный вызов получает три граничные кривизны и оставшуюся глубину. Если глубина равна нулю, ничего не добавляется. Иначе вычисляется кривизна Декарта \(x\), к сумме прибавляется \(\pi/x^2\), а затем обрабатываются три дочерних зазора. После возврата из рекурсии полная покрытая площадь делится на \(\pi\), и из 1 вычитается покрытая доля.
Различия между версиями минимальны. C++ использует расширенную точность, может принимать глубину из командной строки и проверяет значения для глубин 0 и 1. Python и Java используют ту же самую рекурсию со стандартной вещественной арифметикой и сразу печатают результат для глубины 10.
Один стартовый зазор порождает троичное рекурсивное дерево. Число окружностей, вставленных в один зазор до глубины \(d\), равно
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}.$$
Стартовых зазоров четыре, поэтому общее число добавленных окружностей, не считая исходных трёх, равно
$$4\cdot\frac{3^d-1}{2}=2(3^d-1).$$
Отсюда время работы \(\Theta(3^d)\), а глубина стека рекурсии \(\Theta(d)\). Для реального значения \(d=10\) это всего 118096 добавленных окружностей, то есть вычисление очень лёгкое.
داخل دائرة الوحدة توجد ثلاث دوائر متساوية، كل دائرة منها مماسة للدائرتين الأخريين ومماسة أيضاً للدائرة الخارجية. بعد ذلك نملأ الفجوات المنحنية المتبقية بشكل تكراري: في كل فجوة يحدها ثلاث دوائر متماسة نضع الدائرة الوحيدة الجديدة المماسة لها جميعاً، ثم نكرر العملية على الفجوات الأصغر الناتجة لعدد ثابت من الأجيال. المطلوب هو نسبة المساحة غير المغطاة من قرص الوحدة بعد 10 تكرارات.
رغم أن المسألة تبدو هندسية بحتة، فإن التنفيذ لا يحتاج إلى إحداثيات المراكز إطلاقاً. يكفي العمل بالانحناءات، وعندها تتحول التعبئة كلها إلى مجموع مساحات تكراري دقيق.
نمثل كل دائرة بانحنائها ذي الإشارة \(k=1/r\). الدوائر الداخلية لها انحناء موجب، أما دائرة الوحدة الحاوية فنتعامل معها كدائرة انحناؤها \(-1\). بهذا الاصطلاح تصبح كل البنى المحلية خاضعة مباشرة لمبرهنة ديكارت للدوائر المتماسة.
إذا كانت لدينا أربع دوائر متماسة بانحناءات \(k_1,k_2,k_3,k_4\)، فإن
$$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$$
نأخذ الدائرة الخارجية بحيث \(k_1=-1\)، والدوائر الداخلية الثلاث المتساوية بحيث \(k_2=k_3=k_4=k\). عندئذ نحصل على
$$2(1+3k^2)=(-1+3k)^2,$$
ومنها
$$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$$
وهذا هو الجذر الموجب الوحيد، لذا فإن نصف قطر كل دائرة ابتدائية يساوي
$$r=\frac{1}{k}.$$
ومساحة كل واحدة منها هي \(\pi/k^2\)، أي إن الدوائر الثلاث الأولى تغطي منذ البداية مساحة مقدارها \(3\pi/k^2\).
لنفرض أن فجوة ما محاطة بثلاث دوائر متماسة انحناءاتها \(a,b,c\). عند حل علاقة ديكارت بالنسبة إلى الانحناء الرابع نحصل على
$$x=a+b+c\pm2\sqrt{ab+ac+bc}.$$
الإشارة السالبة تعيد الدائرة الرابعة الموجودة أصلاً في الترتيب نفسه، أما الإشارة الموجبة فتعطي الدائرة الجديدة الأصغر التي تملأ الفجوة المفتوحة. لذلك يكون انحناء الدائرة المدخلة هو
$$x=a+b+c+2\sqrt{ab+ac+bc}$$
ومساحتها
$$\frac{\pi}{x^2}.$$
بعد إدخال هذه الدائرة تنقسم الفجوة الأصلية تماماً إلى ثلاث فجوات أصغر حدودها \((a,b,x)\) و\((a,c,x)\) و\((b,c,x)\). ومن هنا يأتي التفرع الثلاثي في العلاقة التكرارية.
الشكل الابتدائي لا يحتوي إلا على نوعين هندسيين من الفجوات. هناك فجوة مركزية واحدة محاطة بالدوائر الداخلية الثلاث المتساوية، وهناك ثلاث فجوات حدودية متطابقة يحد كل واحدة منها الدائرة الخارجية ودائرتان داخليتان متجاورتان. إذا رمزنا بـ \(G_d(a,b,c)\) إلى مجموع المساحة المضافة داخل فجوة حدودها ذات انحناءات \(a,b,c\) خلال \(d\) أجيال، فإن
$$G_0(a,b,c)=0,$$
ولـ \(d\ge1\) يكون
$$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$$
حيث
$$x=a+b+c+2\sqrt{ab+ac+bc}.$$
إذن المساحة المغطاة بعد \(d\) تكرارات تساوي
$$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$$
والنسبة المطلوبة للمساحة غير المغطاة هي
$$R_d=1-\frac{C_d}{\pi}.$$
الجيل الأول وحده يكشف كل أفكار الحل. في الفجوة المركزية نستخدم \((k,k,k)\)، ولذلك يكون الانحناء الجديد
$$k_{\text{center}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3.$$
وفي فجوة حدودية نستخدم \((-1,k,k)\)، فنحصل على
$$k_{\text{edge}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3.$$
أي إن العمق 1 يضيف دائرة مركزية واحدة وثلاث دوائر حدودية متطابقة، وبذلك تصبح نسبة المساحة غير المغطاة
$$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{center}}^2}+\frac{3}{k_{\text{edge}}^2}\right)\approx0.198133880558.$$
هذا هو نفس المقدار الذي تتحقق منه نسخة C++، وهو تأكيد مباشر على أن العلاقة التكرارية تطابق السلوك العددي الفعلي.
لا يوجد هنا تقريب هندسي، باستثناء تقييم الأعداد الحقيقية في النهاية باستخدام الفاصلة العائمة. كل فجوة يحددها بالكامل الثلاثي الذي يحدها من الدوائر، ومبرهنة ديكارت تعطي الدائرة الوحيدة التي يمكن إدخالها بعد ذلك. ولأن كل دائرة جديدة تقسم فجوتها الأم إلى ثلاث فجوات منفصلة، فإن مجموع المساحات التكراري يحسب كل دائرة مضافة مرة واحدة فقط.
تنفذ تطبيقات C++ وPython وJava الصيغ السابقة كما هي. تبدأ بحساب \(k=1+2/\sqrt3\)، ثم تجمع مساحة الدوائر الثلاث الابتدائية، وبعد ذلك تجري استدعاءً تكرارياً واحداً للفجوة المركزية واستدعاءً آخر لفجوة حدودية، ثم تضرب مساهمة الفجوة الحدودية في 3 بسبب التناظر.
كل استدعاء تكراري يستقبل انحناءات الدوائر الثلاث المحددة للفجوة مع العمق المتبقي. إذا كان العمق صفراً فلا يضيف أي مساحة. وإلا فإنه يحسب انحناء ديكارت \(x\)، ويضيف \(\pi/x^2\)، ثم يعاود الاستدعاء على الفجوات الفرعية الثلاث. وبعد اكتمال جميع المساهمات تقسم المساحة المغطاة الكلية على \(\pi\) ثم تطرح من 1 للحصول على النسبة غير المغطاة.
الفروق بين اللغات طفيفة فقط. نسخة C++ تستخدم دقة موسعة، ويمكنها استقبال عمق مختلف من سطر الأوامر، كما تتحقق أولاً من قيمتي العمق 0 والعمق 1. أما نسختا Python وJava فتستخدمان العلاقة نفسها بدقة عائمة قياسية وتطبعان مباشرة نتيجة العمق 10.
كل فجوة ابتدائية تولد شجرة تكرارية ثلاثية الفروع. عدد الدوائر المضافة داخل فجوة واحدة حتى العمق \(d\) يساوي
$$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}.$$
وبما أن لدينا أربع فجوات ابتدائية، فإن العدد الكلي للدوائر المضافة فوق الدوائر الثلاث الأصلية هو
$$4\cdot\frac{3^d-1}{2}=2(3^d-1).$$
لذلك يكون الزمن \(\Theta(3^d)\)، بينما يساوي استهلاك الذاكرة على المكدس \(\Theta(d)\). وعند القيمة الفعلية \(d=10\) لا نحتاج إلا إلى معالجة 118096 دائرة مضافة، وهو حجم صغير جداً.