Take three pairwise externally tangent circles with integer radii \(a\), \(b\), and \(c\), where
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$$
Let \(D\) be the circumcenter of the triangle formed by the three tangency points of the original circles, and let \(E\) be the center of the inner Soddy circle tangent to all three of them. For each primitive triple define
$$d(a,b,c)=\operatorname{dist}(D,E).$$
The goal is to average \(d(a,b,c)\) over all primitive triples in the range. The implementation therefore needs an exact constant-time geometric formula for one triple and then a complete enumeration of all admissible triples.
The geometry becomes straightforward once the three original circle centers are placed in coordinates. Every later quantity in the implementation is derived from that coordinate model.
Let \(O_a\), \(O_b\), and \(O_c\) be the centers of the circles of radii \(a\), \(b\), and \(c\). Because the circles are externally tangent, the distances between centers are
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$$
Choose coordinates
$$O_a=(0,0),\qquad O_b=(a+b,0).$$
The third center lies above the \(x\)-axis. By projecting onto the base segment and applying the law of cosines, its coordinates are
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2},$$
so
$$O_c=(x_c,y_c).$$
The tangency point between the circles of radii \(a\) and \(b\) lies on segment \(O_aO_b\), at distance \(a\) from \(O_a\) and \(b\) from \(O_b\). Therefore
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
By the same ratio argument, the other two tangency points are
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$$
Point \(D\) is the circumcenter of triangle \(T_{ab}T_{ac}T_{bc}\). For any non-collinear points \(T_i=(x_i,y_i)\), the circumcenter is given by
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$$
This is the exact formula used in the C++, Python, and Java implementations.
Let the curvatures of the three given circles be
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$$
For the inner tangent circle, Descartes' circle theorem gives the positive fourth curvature
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$$
Hence the inner Soddy radius is
$$r=\frac1{k_4}.$$
If \(E=(x_E,y_E)\) denotes the center of that circle, tangency implies
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$$
Square the three distance conditions. From \(O_a\) we get
$$x_E^2+y_E^2=(a+r)^2.$$
From \(O_b=(a+b,0)\) we get
$$(x_E-(a+b))^2+y_E^2=(b+r)^2.$$
Subtracting these equations cancels the quadratic terms and leaves a linear equation:
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$$
So
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$$
Now use the equation for \(O_c=(x_c,y_c)\):
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2.$$
Subtract the equation for \(O_a\) again to obtain
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2,$$
hence
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$$
The center of the inner Soddy circle is therefore obtained from two linear equations after one square root for \(r\).
The outer search runs over all increasing triples
$$1 \le a \lt b \lt c \le 100$$
and keeps only those with
$$\gcd(a,b,c)=1.$$
This primitive condition removes scaled copies of the same similarity class. Indeed, if every radius is multiplied by a factor \(t\), then every center, every tangency point, the circumcenter \(D\), and the Soddy center \(E\) all scale by \(t\), so
$$d(ta,tb,tc)=t\,d(a,b,c).$$
After summing \(d(a,b,c)\) over all primitive triples, the final result is just the arithmetic mean of those values.
This example is especially clean because the center triangle has side lengths \(3\), \(4\), and \(5\). Therefore
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
The three tangency points are
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$$
The circumcenter of triangle \(T_{ab}T_{ac}T_{bc}\) is
$$D=(1,1).$$
The three curvatures are \(1\), \(1/2\), and \(1/3\), so
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$$
Descartes then yields
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$$
Substituting into the linear formulas gives
$$E=\left(\frac{21}{23},\frac{20}{23}\right).$$
Finally,
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989,$$
which matches the sample value checked by the implementation.
The C++, Python, and Java implementations all follow the same algorithm. They enumerate every increasing triple in the allowed range, discard non-primitive triples with a gcd test, and then evaluate the geometry for each surviving triple. For one triple, the implementation constructs the center triangle, derives the three tangency points, and applies the circumcenter formula to obtain \(D\).
Next it applies Descartes' theorem to find the inner radius \(r\), rewrites the three tangency conditions as two linear equations, and solves them to obtain \(E\). The contribution of that triple is the Euclidean distance between \(D\) and \(E\). After all primitive triples have been processed, the accumulated sum is divided by the number of valid triples. One implementation also verifies several sample cases and checks that the loop count is \(135739\).
The search space consists of all triples with \(1 \le a \lt b \lt c \le 100\), so the total enumeration cost is \(O(100^3)\). For each triple, the program performs only a fixed number of arithmetic operations, square roots, and gcd evaluations, which is constant work. The memory usage is \(O(1)\), since only a small set of coordinates and accumulators is kept at any time.
Betrachtet werden drei paarweise äußerlich tangierende Kreise mit ganzzahligen Radien \(a\), \(b\) und \(c\), wobei
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$$
\(D\) ist der Umkreismittelpunkt des Dreiecks aus den drei Berührpunkten der Ausgangskreise, und \(E\) ist der Mittelpunkt des inneren Soddy-Kreises, der alle drei Kreise berührt. Für jedes primitive Tripel definieren wir
$$d(a,b,c)=\operatorname{dist}(D,E).$$
Gesucht ist der Mittelwert von \(d(a,b,c)\) über alle primitiven Tripel im Bereich. Dafür braucht die Implementierung eine geschlossene geometrische Formel für ein einzelnes Tripel und anschließend eine vollständige Enumeration aller zulässigen Tripel.
Die Geometrie wird übersichtlich, sobald die Mittelpunkte der drei Kreise in ein Koordinatensystem gelegt werden. Alle späteren Größen lassen sich dann direkt aus diesem Modell ableiten.
Seien \(O_a\), \(O_b\) und \(O_c\) die Mittelpunkte der Kreise mit Radien \(a\), \(b\) und \(c\). Wegen der äußeren Tangentialität gelten die Abstände
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$$
Wir wählen
$$O_a=(0,0),\qquad O_b=(a+b,0).$$
Der dritte Mittelpunkt liegt oberhalb der \(x\)-Achse. Mit Projektion auf die Grundseite und dem Kosinussatz erhält man
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2},$$
also
$$O_c=(x_c,y_c).$$
Der Berührpunkt der Kreise mit Radien \(a\) und \(b\) liegt auf der Strecke \(O_aO_b\), im Abstand \(a\) von \(O_a\) und \(b\) von \(O_b\). Daher
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
Ganz analog erhält man die beiden anderen Berührpunkte:
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$$
Der Punkt \(D\) ist der Umkreismittelpunkt des Dreiecks \(T_{ab}T_{ac}T_{bc}\). Für drei nicht kollineare Punkte \(T_i=(x_i,y_i)\) gilt
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$$
Genau diese geschlossene Formel verwenden die Implementierungen.
Die Krümmungen der drei gegebenen Kreise sind
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$$
Für den inneren Tangentialkreis liefert der Satz von Descartes die positive vierte Krümmung
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$$
Damit ist sein Radius
$$r=\frac1{k_4}.$$
Schreibt man den Mittelpunkt dieses Kreises als \(E=(x_E,y_E)\), so folgen aus der Tangentialität die Gleichungen
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$$
Quadratiert man die drei Distanzbedingungen, so erhält man von \(O_a\) aus
$$x_E^2+y_E^2=(a+r)^2.$$
Für \(O_b=(a+b,0)\) gilt
$$(x_E-(a+b))^2+y_E^2=(b+r)^2.$$
Durch Subtraktion verschwinden die quadratischen Terme, und es bleibt die lineare Gleichung
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$$
Also
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$$
Mit \(O_c=(x_c,y_c)\) erhält man weiter
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2.$$
Erneute Subtraktion der Gleichung von \(O_a\) ergibt
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2,$$
und damit
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$$
Der Mittelpunkt des inneren Soddy-Kreises ist also nach einer einzigen Wurzelberechnung direkt aus linearen Gleichungen verfügbar.
Die äußere Schleife betrachtet alle streng wachsenden Tripel
$$1 \le a \lt b \lt c \le 100$$
und behält nur diejenigen mit
$$\gcd(a,b,c)=1.$$
Diese Bedingung entfernt skalierte Kopien derselben Ähnlichkeitsklasse. Werden nämlich alle Radien mit einem Faktor \(t\) multipliziert, dann skalieren auch alle Mittelpunkte, Berührpunkte, der Umkreismittelpunkt \(D\) und der Soddy-Mittelpunkt \(E\) mit \(t\), also
$$d(ta,tb,tc)=t\,d(a,b,c).$$
Nach dem Aufsummieren aller Werte \(d(a,b,c)\) über primitive Tripel ist das Endergebnis einfach deren arithmetisches Mittel.
Dieses Beispiel ist besonders übersichtlich, weil das Dreieck der Mittelpunkte die Seitenlängen \(3\), \(4\) und \(5\) hat. Daher
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
Die drei Berührpunkte sind
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$$
Der Umkreismittelpunkt des Berührdreiecks ist
$$D=(1,1).$$
Die drei Krümmungen lauten \(1\), \(1/2\) und \(1/3\), also
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$$
Mit Descartes folgt
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$$
Einsetzen in die linearen Formeln liefert
$$E=\left(\frac{21}{23},\frac{20}{23}\right).$$
Damit ergibt sich
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989,$$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen folgen alle demselben Ablauf. Zuerst enumerieren sie alle streng wachsenden Tripel im zulässigen Bereich, verwerfen nicht-primitive Tripel per ggT-Test und berechnen dann die Geometrie für jedes verbleibende Tripel. Für ein einzelnes Tripel konstruieren sie das Dreieck der Mittelpunkte, bestimmen daraus die drei Berührpunkte und wenden die Umkreismittelpunkt-Formel an, um \(D\) zu erhalten.
Anschließend verwenden sie den Satz von Descartes für den inneren Radius \(r\), formen die drei Tangentialitätsbedingungen in zwei lineare Gleichungen um und lösen so \(E\). Der Beitrag des Tripels ist dann die euklidische Distanz zwischen \(D\) und \(E\). Nachdem alle primitiven Tripel verarbeitet wurden, wird die aufsummierte Distanz durch die Anzahl der gültigen Tripel geteilt. Eine Implementierung prüft zusätzlich einige Beispielwerte und verifiziert, dass die Schleife genau \(135739\) primitive Tripel enthält.
Der Suchraum besteht aus allen Tripeln mit \(1 \le a \lt b \lt c \le 100\), daher kostet die Enumeration insgesamt \(O(100^3)\). Für jedes Tripel werden nur endlich viele arithmetische Operationen, Wurzeln und ggT-Berechnungen ausgeführt; der Aufwand pro Tripel ist also konstant. Der Speicherverbrauch ist \(O(1)\), weil nur wenige Koordinaten und Summenvariablen gleichzeitig gehalten werden.
Birbirine dıştan teğet üç çemberin yarıçapları \(a\), \(b\) ve \(c\) olsun. Bu yarıçaplar için
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1$$
koşulları verilir. \(D\), bu üç çemberin ikili temas noktalarının oluşturduğu üçgenin çevrel merkezi; \(E\) ise üç çembere de teğet olan iç Soddy çemberinin merkezidir. Her ilkel üçlü için
$$d(a,b,c)=\operatorname{dist}(D,E)$$
tanımlanır. Amaç, bu değerin verilen aralıktaki tüm ilkel üçlüler üzerindeki aritmetik ortalamasını bulmaktır. Bu yüzden çözüm, tek bir üçlü için kapalı bir geometri formülü kurup ardından tüm uygun üçlüleri tarar.
Geometriyi açık hale getirmenin en iyi yolu, üç başlangıç çemberinin merkezlerini koordinat düzlemine yerleştirmektir. Programdaki tüm nicelikler bu koordinat modelinden türetilir.
Yarıçapları \(a\), \(b\) ve \(c\) olan çemberlerin merkezlerini sırasıyla \(O_a\), \(O_b\) ve \(O_c\) ile gösterelim. Çemberler dıştan teğet olduğundan merkezler arası uzaklıklar
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c$$
olur. Koordinatları
$$O_a=(0,0),\qquad O_b=(a+b,0)$$
şeklinde seçelim. Üçüncü merkez \(x\)-ekseninin üstündedir. Taban üzerindeki izdüşüm ve kosinüs teoremi ile
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2}$$
elde edilir; dolayısıyla
$$O_c=(x_c,y_c).$$
\(a\) ve \(b\) yarıçaplı çemberlerin temas noktası, \(O_aO_b\) doğrusu üzerinde, \(O_a\)'dan \(a\) ve \(O_b\)'den \(b\) uzaklıktadır. Bu nedenle
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
Aynı oran mantığıyla diğer iki temas noktası da
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b)$$
olur. \(D\), \(T_{ab}T_{ac}T_{bc}\) üçgeninin çevrel merkezidir. Genel olarak üç doğrusal olmayan nokta \(T_i=(x_i,y_i)\) için çevrel merkez formülü
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}$$
şeklindedir. C++, Python ve Java uygulamaları tam olarak bu kapalı formu kullanır.
Üç verilen çemberin eğrilikleri
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c$$
olsun. İçteki teğet çember için Descartes çember teoremi, pozitif dördüncü eğriliği
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}$$
olarak verir. O halde iç Soddy çemberinin yarıçapı
$$r=\frac1{k_4}$$
olur. Bu çemberin merkezi \(E=(x_E,y_E)\) ise teğetlikten
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r$$
eşitlikleri gelir.
Bu üç uzaklık koşulunun karelerini yazalım. \(O_a\) için
$$x_E^2+y_E^2=(a+r)^2$$
elde edilir. \(O_b=(a+b,0)\) içinse
$$(x_E-(a+b))^2+y_E^2=(b+r)^2$$
vardır. İki denklemi çıkarınca ikinci dereceden terimler yok olur ve
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2$$
kalır. Buradan
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}$$
bulunur. Benzer şekilde \(O_c=(x_c,y_c)\) için
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2$$
eşitliğinden, \(O_a\) denklemi çıkarılınca
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2$$
ve dolayısıyla
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}$$
elde edilir. Böylece iç Soddy merkezini iteratif geometriye gerek kalmadan doğrudan hesaplarız.
Dış döngü tüm artan üçlüleri tarar:
$$1 \le a \lt b \lt c \le 100.$$
Bunların içinden yalnızca
$$\gcd(a,b,c)=1$$
olanlar tutulur. Bu ilkel olma koşulu, aynı benzerlik sınıfının ölçeklenmiş kopyalarını ayıklamış olur. Gerçekten tüm yarıçaplar \(t\) ile çarpılırsa tüm merkezler, tüm temas noktaları, çevrel merkez \(D\) ve Soddy merkezi \(E\) de \(t\) ile ölçeklenir; dolayısıyla
$$d(ta,tb,tc)=t\,d(a,b,c).$$
Tüm ilkel üçlüler için \(d(a,b,c)\) değerleri toplandıktan sonra sonuç, bu toplamın üçlü sayısına bölünmesiyle elde edilen aritmetik ortalamadır.
Bu örnek çok temizdir; çünkü merkez üçgeninin kenarları \(3\), \(4\) ve \(5\)'tir. Bu yüzden
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
Üç temas noktası
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right)$$
olur. Bu üçgenin çevrel merkezi
$$D=(1,1)$$
çıkar. Eğrilikler \(1\), \(1/2\) ve \(1/3\) olduğundan
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1$$
ve Descartes teoreminden
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}$$
gelir. Lineer formüller kullanıldığında
$$E=\left(\frac{21}{23},\frac{20}{23}\right)$$
bulunur. Son olarak
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989$$
elde edilir; bu da uygulamanın kontrol ettiği örnek değerle aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce izin verilen aralıktaki tüm artan üçlüler dolaşılır, EBOB testiyle ilkel olmayanlar atılır, sonra kalan her üçlü için geometri hesaplanır. Tek bir üçlü için uygulama merkez üçgenini kurar, üç temas noktasını türetir ve çevrel merkez formülünü kullanarak \(D\)'yi bulur.
Sonraki adımda Descartes teoremi ile iç yarıçap \(r\) hesaplanır, üç teğetlik koşulu iki lineer denkleme dönüştürülür ve \(E\) çözülür. O üçlünün katkısı, \(D\) ile \(E\) arasındaki Öklid uzaklığıdır. Tüm ilkel üçlüler işlendiğinde toplanan değer geçerli üçlü sayısına bölünür. Uygulamalardan biri ayrıca birkaç örnek üçlüyü doğrular ve döngüde toplam \(135739\) ilkel üçlü bulunduğunu denetler.
Arama uzayı, \(1 \le a \lt b \lt c \le 100\) koşulunu sağlayan tüm üçlülerden oluşur; dolayısıyla toplam tarama maliyeti \(O(100^3)\)'tür. Her üçlü için yalnızca sabit sayıda aritmetik işlem, karekök ve EBOB hesabı yapılır; yani üçlü başına maliyet sabittir. Kullanılan ek bellek \(O(1)\)'dir, çünkü aynı anda yalnızca birkaç koordinat ve toplama değişkeni tutulur.
Se consideran tres circunferencias tangentes exteriormente, con radios enteros \(a\), \(b\) y \(c\), tales que
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$$
Sea \(D\) el circuncentro del triángulo formado por los tres puntos de tangencia de las circunferencias originales, y sea \(E\) el centro de la circunferencia de Soddy interior tangente a las tres. Para cada triple primitivo definimos
$$d(a,b,c)=\operatorname{dist}(D,E).$$
La tarea consiste en promediar \(d(a,b,c)\) sobre todos los triples primitivos del rango. Por eso la solución necesita una fórmula geométrica cerrada para un triple individual y luego una enumeración completa de todos los triples válidos.
La geometría se vuelve manejable en cuanto colocamos en coordenadas los centros de las tres circunferencias originales. Todas las cantidades posteriores salen de ese modelo cartesiano.
Denotemos por \(O_a\), \(O_b\) y \(O_c\) los centros de las circunferencias de radios \(a\), \(b\) y \(c\). Como son tangentes exteriormente dos a dos, sus distancias mutuas son
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$$
Elegimos
$$O_a=(0,0),\qquad O_b=(a+b,0).$$
El tercer centro queda por encima del eje \(x\). Proyectando sobre la base y usando la ley de cosenos obtenemos
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2},$$
de modo que
$$O_c=(x_c,y_c).$$
El punto de tangencia entre las circunferencias de radios \(a\) y \(b\) está sobre el segmento \(O_aO_b\), a distancia \(a\) de \(O_a\) y \(b\) de \(O_b\). Por tanto
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
Con el mismo razonamiento de razón sobre el segmento, los otros dos puntos son
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$$
El punto \(D\) es el circuncentro del triángulo \(T_{ab}T_{ac}T_{bc}\). Para tres puntos no colineales \(T_i=(x_i,y_i)\), se usa la fórmula
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$$
Esa es exactamente la expresión cerrada que evalúa la implementación.
Las curvaturas de las tres circunferencias dadas son
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$$
Para la circunferencia tangente interior, el teorema de Descartes da la cuarta curvatura positiva
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$$
Por tanto, su radio es
$$r=\frac1{k_4}.$$
Si \(E=(x_E,y_E)\) es su centro, entonces la tangencia implica
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$$
Escribimos los cuadrados de las tres condiciones de distancia. Para \(O_a\) se obtiene
$$x_E^2+y_E^2=(a+r)^2.$$
Para \(O_b=(a+b,0)\) se tiene
$$(x_E-(a+b))^2+y_E^2=(b+r)^2.$$
Al restar ambas ecuaciones desaparecen los términos cuadráticos y queda
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$$
Así,
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$$
Con \(O_c=(x_c,y_c)\) también vale
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2.$$
Restando otra vez la ecuación de \(O_a\) se obtiene
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2,$$
y entonces
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$$
Por eso el centro de la circunferencia interior se calcula de forma directa, sin ningún procedimiento iterativo.
El recorrido externo considera todos los triples estrictamente crecientes
$$1 \le a \lt b \lt c \le 100$$
y conserva solo aquellos que satisfacen
$$\gcd(a,b,c)=1.$$
La condición de primitividad elimina copias escaladas de la misma clase de semejanza. En efecto, si todos los radios se multiplican por un factor \(t\), entonces también se multiplican por \(t\) todos los centros, todos los puntos de tangencia, el circuncentro \(D\) y el centro \(E\); por lo tanto
$$d(ta,tb,tc)=t\,d(a,b,c).$$
Después de sumar \(d(a,b,c)\) sobre todos los triples primitivos, el resultado final es simplemente su media aritmética.
Este caso es especialmente limpio porque el triángulo de centros tiene lados \(3\), \(4\) y \(5\). Así,
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
Los tres puntos de tangencia son
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$$
El circuncentro de ese triángulo es
$$D=(1,1).$$
Las tres curvaturas son \(1\), \(1/2\) y \(1/3\), de modo que
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$$
El teorema de Descartes da entonces
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$$
Sustituyendo en las fórmulas lineales se obtiene
$$E=\left(\frac{21}{23},\frac{20}{23}\right).$$
Finalmente,
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989,$$
que coincide con el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Enumeran todos los triples crecientes del rango permitido, descartan los no primitivos mediante una prueba de mcd y evalúan la geometría para cada triple restante. Para un triple concreto, la implementación construye el triángulo de centros, deriva los tres puntos de tangencia y aplica la fórmula del circuncentro para obtener \(D\).
Después usa el teorema de Descartes para hallar el radio interior \(r\), transforma las tres condiciones de tangencia en dos ecuaciones lineales y resuelve el punto \(E\). La contribución del triple es la distancia euclídea entre \(D\) y \(E\). Tras procesar todos los triples primitivos, la suma acumulada se divide por el número de triples válidos. Una de las implementaciones también verifica varios ejemplos y comprueba que el conteo total del bucle es \(135739\).
El espacio de búsqueda está formado por todos los triples con \(1 \le a \lt b \lt c \le 100\), así que el costo total de enumeración es \(O(100^3)\). Para cada triple solo se realizan unas pocas operaciones aritméticas, raíces cuadradas y evaluaciones de mcd, por lo que el trabajo por triple es constante. El uso de memoria es \(O(1)\), ya que solo se guardan unas pocas coordenadas y acumuladores.
考虑三个两两外切的圆，它们的整数半径分别是 \(a\)、\(b\)、\(c\)，并满足
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$$
设 \(D\) 为这三个原始圆两两切点所构成三角形的外心，\(E\) 为同时与这三个圆相切的内 Soddy 圆的圆心。对每个本原三元组定义
$$d(a,b,c)=\operatorname{dist}(D,E).$$
题目要求把所有满足条件的本原三元组上的 \(d(a,b,c)\) 取算术平均值。于是实现的核心分成两部分：先为单个三元组建立直接可算的几何公式，再把所有合法三元组完整枚举一遍。
只要把三个原始圆的圆心放进坐标系，后面的几何量都会变成显式公式。程序中的每一步实际上都是在这个坐标模型上做代数化简。
记半径分别为 \(a\)、\(b\)、\(c\) 的三个圆的圆心为 \(O_a\)、\(O_b\)、\(O_c\)。由于三圆两两外切，圆心之间的距离立刻得到
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$$
不失一般性，可以把前两个圆心放在
$$O_a=(0,0),\qquad O_b=(a+b,0).$$
第三个圆心位于 \(x\) 轴上方。把 \(O_c\) 投影到底边 \(O_aO_b\) 上，并使用余弦定理，可以写出它的横纵坐标：
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2}.$$
因此
$$O_c=(x_c,y_c).$$
到这里为止，三个原始圆的相对位置已经完全确定，不需要任何数值迭代。
半径为 \(a\) 和 \(b\) 的两个圆的切点落在连线 \(O_aO_b\) 上，并且到 \(O_a\) 的距离是 \(a\)，到 \(O_b\) 的距离是 \(b\)。所以该切点是按长度比例分点：
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
同理，其余两个切点也可以直接写成
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$$
题目中的点 \(D\) 就是三角形 \(T_{ab}T_{ac}T_{bc}\) 的外心。若把三个切点一般记为 \(T_i=(x_i,y_i)\)，那么外心坐标满足标准闭式公式
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$$
程序正是直接计算这个行列式形式的外心公式，因此 \(D\) 的求法是完全显式的。
把三个已知圆的曲率写成
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$$
对于与它们都相切的内圆，笛卡儿圆定理给出正的第四曲率
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$$
于是内 Soddy 圆的半径就是
$$r=\frac1{k_4}.$$
若它的圆心记为 \(E=(x_E,y_E)\)，因为这个内圆分别与三个原始圆外切，所以有三个距离条件
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$$
也就是说，\(E\) 同时位于三个以 \(O_a\)、\(O_b\)、\(O_c\) 为圆心、以 \(a+r\)、\(b+r\)、\(c+r\) 为半径的圆上。
如果直接解三个二次方程，会显得有些笨重。但注意到只要把它们两两相减，平方项就会消失。先写出以 \(O_a\) 为圆心的方程：
$$x_E^2+y_E^2=(a+r)^2.$$
再写出以 \(O_b=(a+b,0)\) 为圆心的方程：
$$(x_E-(a+b))^2+y_E^2=(b+r)^2.$$
两式相减后，\(x_E^2\) 和 \(y_E^2\) 消掉，只剩
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$$
因此可以先直接求出
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$$
然后对第三个圆心 \(O_c=(x_c,y_c)\) 写出方程
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2,$$
再减去 \(O_a\) 的方程，就得到
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2.$$
此时 \(x_E\) 已经知道，所以 \(y_E\) 也立刻可得：
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$$
这就是程序里最关键的代数化步骤：把“与三个圆相切”的几何条件转成两个线性方程，因此可以稳定、快速地得到 \(E\)。
外层枚举的是所有满足
$$1 \le a \lt b \lt c \le 100$$
的严格递增三元组，但只保留
$$\gcd(a,b,c)=1$$
的本原三元组。本原条件的意义在于：如果把三条半径同时乘上同一个比例 \(t\)，整套图形都会做相似放大。所有圆心、切点、外心 \(D\)、以及内 Soddy 圆心 \(E\) 都会整体乘以 \(t\)，于是
$$d(ta,tb,tc)=t\,d(a,b,c).$$
因此，非本原三元组本质上只是更小三元组的缩放副本。程序按题意只统计本原三元组，然后把所有对应的 \(d(a,b,c)\) 累加，再除以合法三元组的总数，得到最终平均值。
这个例子非常适合手算，因为三个圆心构成的三角形边长恰好是 \(3\)、\(4\)、\(5\)。于是
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
三个切点分别是
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$$
把它们代入外心公式，可以得到
$$D=(1,1).$$
而三个原始圆的曲率分别为 \(1\)、\(1/2\)、\(1/3\)，所以
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$$
由笛卡儿圆定理可知
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$$
再把这些值代回线性方程，得到
$$E=\left(\frac{21}{23},\frac{20}{23}\right).$$
于是目标距离就是
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989.$$
这与实现中用于校验的示例值完全一致，说明几何推导和代码计算是吻合的。
C++、Python 和 Java 三个实现遵循同一条计算路线。它们先枚举所有范围内的递增三元组，用 gcd 判断并跳过非本原情况，然后对每个保留下来的三元组计算一次完整几何。对单个三元组而言，实现会先构造圆心三角形，再推出三个切点，并用外心公式求出 \(D\)。
接着，实现利用笛卡儿圆定理求出内圆半径 \(r\)，再把三个相切距离条件改写成两个线性方程，从而直接解出 \(E\)。该三元组对总和的贡献就是 \(D\) 与 \(E\) 之间的欧氏距离。处理完全部本原三元组之后，再用总和除以有效三元组个数。其中一个实现还额外检查了几个样例，并确认循环中一共有 \(135739\) 个本原三元组。
搜索空间是所有满足 \(1 \le a \lt b \lt c \le 100\) 的三元组，因此总的枚举代价是 \(O(100^3)\)。对每个三元组，程序只做固定次数的四则运算、平方根和 gcd 计算，所以单个三元组的代价是常数。额外内存消耗为 \(O(1)\)，因为任意时刻只需要保存少量坐标和累加变量。
Рассматриваются три окружности, попарно внешне касающиеся друг друга, с целыми радиусами \(a\), \(b\) и \(c\), причем
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$$
Точка \(D\) определяется как центр описанной окружности треугольника, образованного тремя точками касания исходных окружностей, а точка \(E\) - как центр внутренней окружности Содди, касающейся всех трех. Для каждой примитивной тройки задается величина
$$d(a,b,c)=\operatorname{dist}(D,E).$$
Нужно усреднить \(d(a,b,c)\) по всем примитивным тройкам в заданном диапазоне. Поэтому решение состоит из двух частей: сначала получить точную формулу для одной тройки, а затем перебрать все допустимые тройки.
Вся геометрия становится прозрачной, если сразу разместить центры трех исходных окружностей в координатах. После этого каждая нужная величина выражается явной формулой.
Обозначим через \(O_a\), \(O_b\) и \(O_c\) центры окружностей радиусов \(a\), \(b\) и \(c\). Из попарной внешней касательности следует
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$$
Выберем координаты
$$O_a=(0,0),\qquad O_b=(a+b,0).$$
Третий центр лежит выше оси \(x\). Из проекции на основание и закона косинусов получаем
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2},$$
то есть
$$O_c=(x_c,y_c).$$
Точка касания окружностей радиусов \(a\) и \(b\) лежит на отрезке \(O_aO_b\), на расстоянии \(a\) от \(O_a\) и \(b\) от \(O_b\). Поэтому
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
По той же причине две другие точки касания равны
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$$
Точка \(D\) - это центр описанной окружности треугольника \(T_{ab}T_{ac}T_{bc}\). Для трех неколлинеарных точек \(T_i=(x_i,y_i)\) используется формула
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$$
Именно эта замкнутая формула вычисляется в реализации.
Кривизны трех заданных окружностей равны
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$$
Для внутренней касательной окружности теорема Декарта дает положительную четвертую кривизну
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$$
Следовательно, ее радиус равен
$$r=\frac1{k_4}.$$
Если \(E=(x_E,y_E)\) - центр этой окружности, то из условий касания получаем
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$$
Запишем квадраты расстояний. Для центра \(O_a\) имеем
$$x_E^2+y_E^2=(a+r)^2.$$
Для \(O_b=(a+b,0)\) получаем
$$(x_E-(a+b))^2+y_E^2=(b+r)^2.$$
Если вычесть первое уравнение из второго, квадратичные члены исчезнут, и останется
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$$
Отсюда сразу следует
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$$
Теперь используем центр \(O_c=(x_c,y_c)\):
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2.$$
Снова вычитая уравнение для \(O_a\), получаем
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2,$$
и потому
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$$
Именно поэтому центр внутренней окружности удается найти напрямую: геометрическое условие касания сводится к двум линейным формулам.
Во внешнем переборе рассматриваются все строго возрастающие тройки
$$1 \le a \lt b \lt c \le 100$$
и сохраняются только те, для которых
$$\gcd(a,b,c)=1.$$
Такое ограничение убирает масштабные копии одной и той же фигуры. Если все радиусы умножить на коэффициент \(t\), то все центры, все точки касания, центр описанной окружности \(D\) и центр Содди \(E\) тоже умножатся на \(t\), поэтому
$$d(ta,tb,tc)=t\,d(a,b,c).$$
После суммирования \(d(a,b,c)\) по всем примитивным тройкам остается лишь поделить сумму на число допустимых троек, то есть взять обычное среднее арифметическое.
Этот пример удобен тем, что треугольник центров имеет стороны \(3\), \(4\) и \(5\). Следовательно,
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
Три точки касания равны
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$$
Центр описанной окружности этого треугольника:
$$D=(1,1).$$
Кривизны исходных окружностей равны \(1\), \(1/2\) и \(1/3\), так что
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$$
По теореме Декарта получаем
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$$
Подстановка в линейные формулы дает
$$E=\left(\frac{21}{23},\frac{20}{23}\right).$$
Поэтому
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989,$$
что совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала они перебирают все возрастающие тройки в допустимом диапазоне, отбрасывают непримитивные при помощи проверки gcd, а затем вычисляют геометрию для каждой оставшейся тройки. Для одной тройки программа строит треугольник центров, из него получает три точки касания и по формуле центра описанной окружности находит \(D\).
Далее по теореме Декарта находится внутренний радиус \(r\), три условия касания переписываются как две линейные формулы, и из них извлекается \(E\). Вклад данной тройки - евклидово расстояние между \(D\) и \(E\). После обработки всех примитивных троек накопленная сумма делится на количество допустимых троек. Одна из реализаций дополнительно проверяет несколько примеров и подтверждает, что всего в цикле встречается \(135739\) примитивных троек.
Пространство поиска состоит из всех троек с \(1 \le a \lt b \lt c \le 100\), поэтому полный перебор имеет стоимость \(O(100^3)\). Для каждой тройки выполняется только фиксированное число арифметических операций, извлечений корня и вычислений gcd, то есть работа на одну тройку постоянна. Память имеет порядок \(O(1)\), поскольку одновременно хранятся лишь несколько координат и накопителей.
لدينا ثلاث دوائر متماسة خارجيا اثنتين اثنتين، وأنصاف أقطارها الصحيحة هي \(a\) و\(b\) و\(c\)، مع الشرطين
$$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$$
لتكن \(D\) مركز الدائرة المحيطة بالمثلث الذي تصنعه نقاط التماس الثلاث بين الدوائر الأصلية، ولتكن \(E\) مركز دائرة سودي الداخلية المماسة للدوائر الثلاث جميعا. لكل ثلاثي بدائي نعرّف
$$d(a,b,c)=\operatorname{dist}(D,E).$$
المطلوب هو أخذ المتوسط الحسابي للقيمة \(d(a,b,c)\) على جميع الثلاثيات البدائية ضمن هذا المجال. لذلك يحتاج الحل إلى صيغة هندسية مغلقة لحساب حالة واحدة بسرعة ثابتة، ثم إلى تعداد كامل لجميع الثلاثيات المسموح بها.
تصبح الصورة الهندسية واضحة جدا إذا وضعنا مراكز الدوائر الثلاث في مستوى إحداثي. بعد ذلك تتحول كل الكميات المطلوبة إلى صيغ جبرية مباشرة.
لنرمز إلى مراكز الدوائر ذات أنصاف الأقطار \(a\) و\(b\) و\(c\) بالرموز \(O_a\) و\(O_b\) و\(O_c\). بما أن الدوائر متماسة خارجيا، فإن المسافات بين المراكز هي
$$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$$
نختار الإحداثيات
$$O_a=(0,0),\qquad O_b=(a+b,0).$$
أما المركز الثالث فيقع فوق محور \(x\). ومن إسقاطه على القاعدة واستعمال قانون جيب التمام نحصل على
$$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$$
$$y_c=\sqrt{(a+c)^2-x_c^2},$$
ومن ثم
$$O_c=(x_c,y_c).$$
نقطة التماس بين الدائرتين ذواتي نصفي القطر \(a\) و\(b\) تقع على القطعة \(O_aO_b\)، وتبعد مسافة \(a\) عن \(O_a\) ومسافة \(b\) عن \(O_b\). لذلك
$$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$$
وبنفس منطق القسمة على النسبة نحصل على نقطتي التماس الأخريين:
$$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$$
$$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$$
النقطة \(D\) هي مركز الدائرة المحيطة بالمثلث \(T_{ab}T_{ac}T_{bc}\). وإذا كتبنا ثلاث نقاط غير على استقامة واحدة على الصورة \(T_i=(x_i,y_i)\)، فإن صيغة المركز هي
$$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$$
$$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$$
$$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$$
وهذه هي الصيغة المغلقة التي تستعملها جميع التطبيقات مباشرة.
انحناءات الدوائر الثلاث المعطاة هي
$$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$$
وبحسب مبرهنة ديكارت للدوائر، فإن الانحناء الرابع الموجب للدائرة الداخلية المماسة يساوي
$$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$$
إذن نصف قطرها هو
$$r=\frac1{k_4}.$$
إذا كان مركز هذه الدائرة هو \(E=(x_E,y_E)\)، فإن شروط التماس تعني
$$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$$
نكتب مربعات المسافات الثلاث. من الدائرة ذات المركز \(O_a\) نحصل على
$$x_E^2+y_E^2=(a+r)^2.$$
ومن الدائرة ذات المركز \(O_b=(a+b,0)\) نحصل على
$$(x_E-(a+b))^2+y_E^2=(b+r)^2.$$
بطرح المعادلتين تختفي الحدود التربيعية ويبقى
$$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$$
ومنها
$$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$$
ثم نكتب معادلة المركز \(O_c=(x_c,y_c)\):
$$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2.$$
وبطرح معادلة \(O_a\) مرة أخرى نحصل على
$$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2,$$
وبالتالي
$$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$$
وهكذا يتحول شرط التماس مع ثلاث دوائر إلى معادلتين خطيتين فقط، وهذا هو السبب في أن المركز \(E\) يُحسب مباشرة وبثبات عددي جيد.
يعدّ البرنامج جميع الثلاثيات المتزايدة التي تحقق
$$1 \le a \lt b \lt c \le 100$$
ثم يحتفظ فقط بما يحقق
$$\gcd(a,b,c)=1.$$
هذا الشرط يحذف النسخ المكبرة من الشكل نفسه. فإذا ضربنا أنصاف الأقطار كلها في عامل \(t\)، فإن جميع المراكز ونقاط التماس ومركز الدائرة المحيطة \(D\) ومركز سودي \(E\) تتضاعف كذلك بالعامل نفسه، ومن ثم
$$d(ta,tb,tc)=t\,d(a,b,c).$$
بعد جمع \(d(a,b,c)\) على جميع الثلاثيات البدائية، يكون الناتج النهائي هو المتوسط الحسابي لهذه القيم.
هذا المثال مناسب جدا للحساب اليدوي لأن مثلث المراكز أطوال أضلاعه \(3\) و\(4\) و\(5\). لذلك
$$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$$
أما نقاط التماس الثلاث فهي
$$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$$
ومركز الدائرة المحيطة بهذا المثلث هو
$$D=(1,1).$$
انحناءات الدوائر الأصلية هي \(1\) و\(1/2\) و\(1/3\)، وبالتالي
$$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$$
ومن مبرهنة ديكارت نحصل على
$$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$$
بالتعويض في الصيغ الخطية ينتج
$$E=\left(\frac{21}{23},\frac{20}{23}\right).$$
ومن ثم
$$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989,$$
وهو تماما مقدار التحقق الذي تستخدمه التطبيقات.
تنفذ نسخ C++ وPython وJava الفكرة نفسها خطوة بخطوة. فهي تعدد جميع الثلاثيات المتزايدة ضمن المجال، وتستبعد الثلاثيات غير البدائية باختبار gcd، ثم تحسب التركيب الهندسي لكل ثلاثي باق. بالنسبة إلى ثلاثي واحد، يبني التنفيذ مثلث المراكز، ويستخرج نقاط التماس الثلاث، ثم يطبق صيغة مركز الدائرة المحيطة للحصول على \(D\).
بعد ذلك يستخدم مبرهنة ديكارت لإيجاد نصف القطر الداخلي \(r\)، ويحوّل شروط التماس الثلاثة إلى معادلتين خطيتين ليحل منهما \(E\). مساهمة ذلك الثلاثي هي المسافة الإقليدية بين \(D\) و\(E\). وبعد الانتهاء من جميع الثلاثيات البدائية، تُقسم المحصلة على عدد الثلاثيات الصحيحة. كما أن أحد التطبيقات يتحقق من عدة أمثلة ويؤكد أن عدد الثلاثيات البدائية في الحلقة هو \(135739\).
فضاء البحث هو جميع الثلاثيات التي تحقق \(1 \le a \lt b \lt c \le 100\)، ولذلك تكون كلفة التعداد الكلية \(O(100^3)\). ولكل ثلاثي، يجري البرنامج عددا ثابتا من العمليات الحسابية واستخراج الجذور وفحوص gcd، لذا فالكلفة لكل ثلاثي ثابتة. أما الذاكرة الإضافية فهي \(O(1)\)، لأن البرنامج يحتفظ فقط بعدد صغير من الإحداثيات والمجاميع التراكمية.