Scale every circle so that the radius is 1. Then \(n\) congruent circles sit inside a rectangle of width \(2n\) and height \(2\). In the lower-left corner there is a unit square, and the first circle removes a quarter circle from that square. The remaining corner region is the L-section. The concave triangle is the part of that L-section that lies below the diagonal of the full rectangle.
We must find the smallest positive integer \(n\) such that
$$\frac{A_C(n)}{A_L} \lt 10^{-3}.$$
The geometry becomes manageable because everything reduces to one straight line, one circular arc, and their intersection inside the unit square.
After the radius is normalized to 1, the computation can be written entirely with elementary geometry. The implementations evaluate a closed-form formula for the concave area and then scan upward in \(n\).
Inside the unit square \(0 \le x \le 1\), \(0 \le y \le 1\), the relevant arc comes from the circle centered at \((1,1)\) with radius 1:
$$(x-1)^2 + (y-1)^2 = 1.$$
We need the lower branch of that circle, so
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
The L-section is the unit square minus the quarter circle. Its area does not depend on \(n\):
$$A_L = 1 - \frac{\pi}{4}.$$
The diagonal of the \(2n \times 2\) rectangle runs from \((0,0)\) to \((2n,2)\), so its slope is \(1/n\). In the unit square the line is therefore
$$y_{\mathrm{line}}(x) = \frac{x}{n}.$$
The concave triangle is the part of the L-section below this line. For \(x\) near 0 the line is lower than the arc; after the intersection point, the arc is the lower boundary. That is why the area splits into a line part and an arc part.
Let \(x_\ast\) be the intersection abscissa in \((0,1)\). It satisfies
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$$
Move the square root to the right-hand side and square:
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
Multiplying by \(n^2\) gives the quadratic equation
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
The smaller root is the one that lies inside the unit square:
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
The first piece is the area under the line from 0 to \(x_\ast\):
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
The second piece is the area under the arc from \(x_\ast\) to 1:
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
Set \(u = 1-x\), and write \(\delta = 1-x_\ast\). Since \(2x-x^2 = 1-u^2\), the integral becomes
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$$
Now use the standard antiderivative
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2}.$$
Therefore
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$$
This is exactly the closed form used by the implementation, so no numerical integration is required.
Once the concave area is known, the target ratio is
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$$
Each evaluation needs only a few square roots, one inverse sine, and basic arithmetic. The implementations therefore test \(n=1,2,3,\dots\) in order and stop at the first value for which \(R(n) \lt 10^{-3}\).
For \(n=2\), the intersection simplifies to
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$$
The line contribution is
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$$
The arc contribution is
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$$
So
$$A_C(2) \approx 0.0782494456,$$
while
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366.$$
Hence
$$R(2) \approx 0.364626169291728,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all follow the same plan. They treat the L-section area \(1-\pi/4\) as a constant, because it does not depend on \(n\). For each trial value of \(n\), they compute the intersection point from the quadratic formula above, convert it into \(\delta = 1-x_\ast\), and evaluate the line piece and the arc piece directly in closed form.
After that, the implementation divides by the fixed L-section area to obtain the ratio and scans upward through positive integers until the threshold \(10^{-3}\) is crossed. One implementation also verifies the checkpoints \(R(1)=0.5\), \(R(2)\approx 0.364626169291728\), and that the \(10\%\) threshold is first met at \(n=15\), which confirms that the geometry and the formula are consistent.
Each candidate \(n\) requires only constant-time floating-point work, so the running time is \(O(n_\star)\), where \(n_\star\) is the first integer satisfying the inequality. The memory usage is \(O(1)\), since only a small fixed set of numeric quantities is stored.
Wir skalieren alle Kreise so, dass ihr Radius 1 ist. Dann liegen \(n\) kongruente Kreise in einem Rechteck der Breite \(2n\) und der Höhe \(2\). In der linken unteren Ecke befindet sich ein Einheitsquadrat, aus dem der erste Kreis ein Viertelkreisstück herausschneidet. Der verbleibende Eckbereich ist die L-Sektion. Das konkave Dreieck ist genau der Teil dieser L-Sektion, der unterhalb der Diagonalen des gesamten Rechtecks liegt.
Gesucht ist das kleinste positive \(n\) mit
$$\frac{A_C(n)}{A_L} \lt 10^{-3}.$$
Die Aufgabe wird handhabbar, weil die ganze Geometrie auf eine Gerade, einen Kreisbogen und deren Schnittpunkt im Einheitsquadrat zurückgeführt werden kann.
Nach der Normierung auf Radius 1 lässt sich die Rechnung vollständig mit elementarer Geometrie formulieren. Die Implementierungen werten eine geschlossene Formel für die konkave Fläche aus und erhöhen dann \(n\) schrittweise.
Im Einheitsquadrat \(0 \le x \le 1\), \(0 \le y \le 1\) stammt der relevante Bogen vom Kreis mit Mittelpunkt \((1,1)\) und Radius 1:
$$(x-1)^2 + (y-1)^2 = 1.$$
Benötigt wird der untere Ast dieses Kreises, also
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
Die L-Sektion ist das Einheitsquadrat minus ein Viertelkreis. Deshalb ist ihre Fläche unabhängig von \(n\):
$$A_L = 1 - \frac{\pi}{4}.$$
Die Diagonale des Rechtecks \(2n \times 2\) verläuft von \((0,0)\) nach \((2n,2)\) und hat damit die Steigung \(1/n\). Im Einheitsquadrat gilt daher
$$y_{\mathrm{line}}(x) = \frac{x}{n}.$$
Das konkave Dreieck ist der Teil der L-Sektion unter dieser Geraden. Für kleine \(x\) liegt die Gerade unter dem Bogen; nach dem Schnittpunkt bildet der Bogen die niedrigere Begrenzung. Genau deshalb zerfällt die Fläche in einen Geradenanteil und einen Bogenanteil.
Sei \(x_\ast\) die eindeutige Schnittstelle in \((0,1)\). Dann gilt
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$$
Bringt man die Wurzel auf die andere Seite und quadriert, erhält man
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
Nach Multiplikation mit \(n^2\) folgt die quadratische Gleichung
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
Die geometrisch relevante Lösung im Einheitsquadrat ist die kleinere Wurzel:
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
Der erste Anteil ist die Fläche unter der Geraden von 0 bis \(x_\ast\):
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
Der zweite Anteil ist die Fläche unter dem Bogen von \(x_\ast\) bis 1:
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
Mit der Substitution \(u = 1-x\) und \(\delta = 1-x_\ast\) wird daraus
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$$
Verwendet man die Stammfunktion
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2},$$
so ergibt sich
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$$
Genau diese geschlossene Formel wird in der Implementierung ausgewertet; numerische Integration ist also nicht nötig.
Ist die konkave Fläche bekannt, dann ist das Zielverhältnis
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$$
Jede Auswertung benötigt nur einige Quadratwurzeln, einen Arkussinus und elementare Arithmetik. Deshalb testen die Implementierungen \(n=1,2,3,\dots\) der Reihe nach und stoppen beim ersten \(n\) mit \(R(n) \lt 10^{-3}\).
Für \(n=2\) vereinfacht sich der Schnittpunkt zu
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$$
Der Geradenanteil ist
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$$
Der Bogenanteil ist
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$$
Also gilt
$$A_C(2) \approx 0.0782494456,$$
während
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366.$$
Damit folgt
$$R(2) \approx 0.364626169291728,$$
genau der numerische Kontrollwert aus den Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst behandeln sie die L-Sektionsfläche \(1-\pi/4\) als Konstante, weil sie nicht von \(n\) abhängt. Für jeden Testwert \(n\) berechnen sie den Schnittpunkt mit der quadratischen Formel, bilden daraus \(\delta = 1-x_\ast\) und werten den Geradenanteil und den Bogenanteil direkt in geschlossener Form aus.
Anschließend wird durch die feste L-Sektionsfläche dividiert, um das Verhältnis zu erhalten, und dann wird \(n\) aufsteigend durchsucht, bis die Schranke \(10^{-3}\) unterschritten wird. Eine Implementierung prüft zusätzlich die Kontrollwerte \(R(1)=0.5\), \(R(2)\approx 0.364626169291728\) sowie, dass die \(10\%\)-Schwelle zuerst bei \(n=15\) erreicht wird. Das ist ein guter Konsistenztest für die Herleitung.
Jeder Kandidat \(n\) benötigt nur konstante Gleitkommaarbeit. Daher beträgt die Laufzeit \(O(n_\star)\), wobei \(n_\star\) das erste \(n\) ist, das die Ungleichung erfüllt. Der Speicherverbrauch ist \(O(1)\), weil nur eine feste Anzahl numerischer Größen gehalten wird.
Tüm çemberleri yarıçapı 1 olacak şekilde ölçekleyelim. Böylece \(n\) eş çember, genişliği \(2n\) ve yüksekliği \(2\) olan bir dikdörtgen içine yerleşir. Sol alt köşede birim kare vardır ve ilk çember bu karenin içinden bir çeyrek daire parçası çıkarır. Geriye kalan köşe bölgesi L-bölgesidir. Konkav üçgen ise bu L-bölgesinin, tüm dikdörtgenin köşegeninin altında kalan kısmıdır.
Aradığımız şey,
$$\frac{A_C(n)}{A_L} \lt 10^{-3}$$
koşulunu sağlayan en küçük pozitif \(n\) değeridir. Geometri, bir doğru, bir yay ve bunların birim kare içindeki kesişimi üzerinden kapalı forma indirgenebilir.
Yarıçap 1'e normalize edilince hesap tamamen temel geometriyle yazılabilir. Uygulamalar konkav alan için kapalı formu hesaplar ve sonra \(n\) değerlerini artan sırayla dener.
\(0 \le x \le 1\), \(0 \le y \le 1\) olan birim kare içinde ilgili yay, merkezi \((1,1)\) ve yarıçapı 1 olan çemberden gelir:
$$(x-1)^2 + (y-1)^2 = 1.$$
Birim kare içindeki alt dal gerektiği için
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
L-bölgesi, birim kareden çeyrek dairenin çıkarılmasıdır. Bu yüzden alanı \(n\)'den bağımsız sabittir:
$$A_L = 1 - \frac{\pi}{4}.$$
\(2n \times 2\) dikdörtgeninin köşegeni \((0,0)\) ile \((2n,2)\) arasındadır; eğimi \(1/n\) olur. Birim kare içindeki denklem
$$y_{\mathrm{line}}(x) = \frac{x}{n}$$
şeklindedir. Konkav üçgen, L-bölgesinin bu doğrunun altında kalan kısmıdır. Küçük \(x\) değerlerinde doğru yayın altında kalır; kesişimden sonra alt sınırı yay belirler. Bu nedenle alan iki parçaya ayrılır.
Birim kare içindeki tek kesişimin apsisine \(x_\ast\) diyelim. O zaman
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}$$
olur. Karekök diğer tarafa alınır ve kare alınırsa
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
\(n^2\) ile çarpınca ikinci dereceden denklem elde edilir:
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
Birim kare içinde kalan kök küçüğüdür:
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
İlk parça, 0 ile \(x_\ast\) arasında doğrunun altındaki alandır:
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
İkinci parça, \(x_\ast\) ile 1 arasında yayın altındaki alandır:
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
\(u = 1-x\) ve \(\delta = 1-x_\ast\) yazarsak, \(2x-x^2 = 1-u^2\) olduğundan integral
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du$$
biçimine gelir. Standart asal integral
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2}$$
kullanılırsa
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast$$
elde edilir. Böylece sayısal integral yapmaya gerek kalmaz; uygulamalar doğrudan bu kapalı formu kullanır.
Konkav alan bulunduktan sonra hedef oran
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}$$
olur. Her deneme yalnızca birkaç karekök, bir ters sinüs ve basit aritmetik içerdiğinden uygulamalar \(n=1,2,3,\dots\) diye ilerleyip ilk kez \(R(n) \lt 10^{-3}\) olduğunda durur.
\(n=2\) için kesişim
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}$$
şeklindedir. Doğru parçasının alanı
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04$$
olur. Yay parçası ise
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456$$
değerini verir. Dolayısıyla
$$A_C(2) \approx 0.0782494456,$$
ve
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366$$
olduğundan
$$R(2) \approx 0.364626169291728$$
elde edilir. Bu da uygulamalardaki sayısal kontrolle aynıdır.
C++, Python ve Java uygulamalarının yapısı aynıdır. Önce L-bölgesinin alanı olan \(1-\pi/4\) sabit kabul edilir; çünkü bu değer \(n\)'ye bağlı değildir. Her aday \(n\) için yukarıdaki ikinci dereceden formülden kesişim noktası hesaplanır, sonra \(\delta = 1-x_\ast\) bulunur ve doğru ile yaydan gelen iki alan parçası kapalı formda değerlendirilir.
Daha sonra bu alan sabit L-bölgesi alanına bölünerek oran elde edilir ve eşik \(10^{-3}\) altına düşene kadar \(n\) artan sırayla denenir. Bir uygulama ayrıca \(R(1)=0.5\), \(R(2)\approx 0.364626169291728\) ve \(10\%\) eşiğinin ilk kez \(n=15\) için sağlandığını da doğrular; bu, türetimin sağlam olduğuna dair iyi bir kontrol noktasıdır.
Her aday \(n\) için sabit sayıda kayan noktalı işlem gerekir. Bu yüzden çalışma süresi, eşitsizliği ilk sağlayan değer \(n_\star\) olmak üzere \(O(n_\star)\) olur. Bellek kullanımı ise yalnızca sabit sayıda sayısal büyüklük tutulduğu için \(O(1)\)'dir.
Escalamos todos los círculos para que su radio sea 1. Entonces \(n\) círculos congruentes quedan dentro de un rectángulo de anchura \(2n\) y altura \(2\). En la esquina inferior izquierda aparece un cuadrado unidad, y el primer círculo elimina de ese cuadrado un cuarto de círculo. La región que queda es la sección en L. El triángulo cóncavo es la parte de esa sección en L situada por debajo de la diagonal del rectángulo completo.
Buscamos el menor entero positivo \(n\) tal que
$$\frac{A_C(n)}{A_L} \lt 10^{-3}.$$
La clave es que toda la figura relevante se reduce a una recta, un arco circular y su punto de corte dentro del cuadrado unidad.
Tras normalizar el radio a 1, todo el cálculo puede escribirse con geometría elemental. Las implementaciones evalúan una fórmula cerrada para el área cóncava y luego prueban \(n\) en orden creciente.
En el cuadrado unidad \(0 \le x \le 1\), \(0 \le y \le 1\), el arco relevante pertenece al círculo de centro \((1,1)\) y radio 1:
$$(x-1)^2 + (y-1)^2 = 1.$$
Dentro de ese cuadrado necesitamos la rama inferior, por lo que
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
La sección en L es el cuadrado unidad menos el cuarto de círculo. Por tanto su área es constante, independiente de \(n\):
$$A_L = 1 - \frac{\pi}{4}.$$
La diagonal del rectángulo \(2n \times 2\) va de \((0,0)\) a \((2n,2)\), así que su pendiente es \(1/n\). En el cuadrado unidad la ecuación es
$$y_{\mathrm{line}}(x) = \frac{x}{n}.$$
El triángulo cóncavo es la parte de la sección en L que queda por debajo de esa recta. Para \(x\) pequeño, la recta está por debajo del arco; después del punto de corte, el arco pasa a ser la frontera inferior. Por eso el área se separa de manera natural en dos integrales.
Sea \(x_\ast\) la abscisa única de intersección en \((0,1)\). Satisface
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$$
Si aislamos la raíz y elevamos al cuadrado, obtenemos
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
Multiplicando por \(n^2\) aparece la cuadrática
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
La raíz geométricamente válida, la que queda dentro del cuadrado unidad, es la menor:
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
La primera contribución es el área bajo la recta entre 0 y \(x_\ast\):
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
La segunda contribución es el área bajo el arco entre \(x_\ast\) y 1:
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
Tomemos \(u = 1-x\) y escribamos \(\delta = 1-x_\ast\). Como \(2x-x^2 = 1-u^2\), la integral se convierte en
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$$
Usando la primitiva estándar
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2},$$
se llega a
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$$
Ésta es la misma expresión cerrada que evalúa la implementación, así que no hace falta integración numérica.
Una vez conocida el área cóncava, la razón buscada es
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$$
Cada evaluación sólo requiere unas pocas raíces cuadradas, un arco seno y aritmética elemental. Por eso las implementaciones prueban \(n=1,2,3,\dots\) hasta encontrar el primer valor con \(R(n) \lt 10^{-3}\).
Para \(n=2\), la intersección se simplifica a
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$$
La contribución de la recta es
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$$
La contribución del arco es
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$$
Así,
$$A_C(2) \approx 0.0782494456,$$
mientras que
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366.$$
Por tanto,
$$R(2) \approx 0.364626169291728,$$
en acuerdo con la comprobación numérica usada por las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero tratan \(1-\pi/4\) como una constante, porque el área de la sección en L no depende de \(n\). Para cada valor de prueba de \(n\), calculan el punto de intersección con la fórmula cuadrática anterior, forman \(\delta = 1-x_\ast\) y evalúan directamente la parte bajo la recta y la parte bajo el arco en forma cerrada.
Después dividen por el área fija de la sección en L para obtener la razón y recorren los enteros positivos en orden ascendente hasta cruzar el umbral \(10^{-3}\). Una de las implementaciones también verifica los puntos de control \(R(1)=0.5\), \(R(2)\approx 0.364626169291728\) y que el umbral del \(10\%\) se alcanza por primera vez en \(n=15\), lo cual sirve como comprobación de consistencia.
Cada candidato \(n\) requiere tiempo constante en aritmética de punto flotante, así que el coste total es \(O(n_\star)\), donde \(n_\star\) es el primer entero que satisface la desigualdad. El consumo de memoria es \(O(1)\), porque sólo se almacenan unas pocas cantidades numéricas.
把所有圆统一缩放到半径为 1。这样一来，\(n\) 个全等圆并排放在一个宽 \(2n\)、高 \(2\) 的矩形里。左下角会出现一个单位正方形，而最左边那个圆会从这个单位正方形中切去一个四分之一圆。剩下的角落区域就是题目里的 L-section。所谓 concave triangle，就是这个 L-section 中位于整个大矩形对角线下方的那一块区域。
要求的是满足
$$\frac{A_C(n)}{A_L} \lt 10^{-3}$$
的最小正整数 \(n\)。关键在于，真正需要处理的局部图形只涉及一条直线、一段圆弧，以及它们在单位正方形内部的交点，所以每个 \(n\) 都可以在常数时间内完成判定。
半径归一化以后，所有量都变成无量纲，计算可以完全用初等几何表达。实现采用闭式公式求凹区域面积，然后按顺序测试 \(n\)。
在单位正方形 \(0 \le x \le 1\)、\(0 \le y \le 1\) 内，相关圆弧来自圆心 \((1,1)\)、半径为 1 的圆：
$$(x-1)^2 + (y-1)^2 = 1.$$
由于我们关心的是单位正方形里的下半支，所以圆弧方程写成
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
L-section 就是单位正方形减去一个四分之一圆，因此它的面积与 \(n\) 无关，恒为
$$A_L = 1 - \frac{\pi}{4}.$$
这一步非常重要，因为后面无论 \(n\) 取什么值，分母都不需要重新计算。
整个矩形的左下角是 \((0,0)\)，右上角是 \((2n,2)\)，所以对角线斜率为
$$\frac{2}{2n} = \frac{1}{n}.$$
因此在局部坐标下，对角线在单位正方形中的表达式就是
$$y_{\mathrm{line}}(x) = \frac{x}{n}.$$
凹三角区域正是 L-section 中位于这条直线下方的部分。靠近原点时，直线比圆弧更低，所以边界来自直线；过了交点以后，圆弧反而更低，于是边界改由圆弧给出。这说明面积天然要拆成两段积分。
设单位正方形内唯一的交点横坐标为 \(x_\ast\)。它满足
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$$
先把根号项移项，再平方：
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
乘上 \(n^2\) 以后得到一个标准二次方程：
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
两个根中，真正落在 \((0,1)\) 内的那个较小根是
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
这个闭式表达式正是实现中首先计算的核心量，因为后面的面积公式都依赖于它。
从 \(0\) 到 \(x_\ast\) 的部分由直线控制，其面积为
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
从 \(x_\ast\) 到 1 的部分由圆弧控制，其面积为
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
令 \(u = 1-x\)，再记
$$\delta = 1-x_\ast,$$
则有 \(2x-x^2 = 1-u^2\)，于是上式变成
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$$
这里会用到标准积分公式
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2}.$$
因此可以直接得到闭式结果
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$$
这样就完全避免了数值积分，所有候选 \(n\) 都能通过同一个解析公式快速计算。
有了凹区域面积之后，目标比例就是
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$$
每次计算只包含若干次平方根、一次反正弦和一些基本四则运算，所以实现直接按 \(n=1,2,3,\dots\) 的顺序测试，第一次出现
$$R(n) \lt 10^{-3}$$
时就返回该 \(n\)。由于单次代价极小，这种线性扫描已经足够高效。
当 \(n=2\) 时，交点会简化得很漂亮：
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$$
直线部分面积为
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$$
圆弧部分面积为
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$$
于是
$$A_C(2) \approx 0.0782494456.$$
再结合
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366,$$
得到
$$R(2) \approx 0.364626169291728.$$
这个数值正好对应实现中的校验点，说明推导与程序计算完全一致。
C++、Python 和 Java 三个实现的结构是一致的。首先把 \(1-\pi/4\) 当作常量保存，因为 L-section 的面积不随 \(n\) 改变。对于每个候选 \(n\)，实现先用上面的闭式交点公式求出 \(x_\ast\)，再构造 \(\delta = 1-x_\ast\)，接着分别计算直线贡献和圆弧贡献，并把它们相加得到 \(A_C(n)\)。
随后，程序用 \(A_C(n)\) 除以固定的 L-section 面积得到比例 \(R(n)\)，再按正整数递增的顺序搜索，直到比例第一次低于 \(10^{-3}\) 为止。其中一个实现还额外检查了三个已知数值：\(R(1)=0.5\)、\(R(2)\approx 0.364626169291728\)，以及 \(10\%\) 阈值第一次出现在 \(n=15\)。这些检查可以很好地验证公式没有写错。
每个候选 \(n\) 只需要常数次浮点运算，因此总时间复杂度是 \(O(n_\star)\)，其中 \(n_\star\) 表示满足不等式的第一个整数。整个过程中只保存少量固定的数值，所以空间复杂度是 \(O(1)\)。
Масштабируем все окружности так, чтобы их радиус стал равен 1. Тогда \(n\) одинаковых окружностей лежат внутри прямоугольника ширины \(2n\) и высоты \(2\). В левом нижнем углу находится единичный квадрат, и первая окружность вырезает из него четверть круга. Оставшаяся угловая область и есть L-секция. Вогнутый треугольник представляет собой часть этой L-секции, расположенную ниже диагонали всего прямоугольника.
Нужно найти наименьшее положительное \(n\), для которого
$$\frac{A_C(n)}{A_L} \lt 10^{-3}.$$
Суть решения в том, что вся нужная геометрия сводится к одной прямой, одной дуге окружности и их точке пересечения внутри единичного квадрата.
После нормировки радиуса до 1 вся задача описывается средствами элементарной геометрии. Реализации вычисляют площадь вогнутой области по замкнутой формуле, а затем последовательно перебирают \(n\).
В единичном квадрате \(0 \le x \le 1\), \(0 \le y \le 1\) нужная дуга принадлежит окружности с центром \((1,1)\) и радиусом 1:
$$(x-1)^2 + (y-1)^2 = 1.$$
Нас интересует нижняя ветвь внутри квадрата, поэтому
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
L-секция равна площади единичного квадрата минус площадь четверти круга. Следовательно, её площадь не зависит от \(n\):
$$A_L = 1 - \frac{\pi}{4}.$$
Диагональ прямоугольника \(2n \times 2\) идёт из \((0,0)\) в \((2n,2)\), значит её наклон равен \(1/n\). Внутри единичного квадрата это даёт уравнение
$$y_{\mathrm{line}}(x) = \frac{x}{n}.$$
Вогнутый треугольник — это часть L-секции ниже этой прямой. При малых \(x\) прямая лежит ниже дуги, а после точки пересечения нижней границей становится дуга. Поэтому площадь естественно раскладывается на две части.
Обозначим через \(x_\ast\) абсциссу единственной точки пересечения в интервале \((0,1)\). Она удовлетворяет уравнению
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$$
Перенесём корень в другую часть и возведём в квадрат:
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
После умножения на \(n^2\) получаем квадратное уравнение
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
Подходящий корень, лежащий внутри единичного квадрата, равен
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
Первая часть — площадь под прямой на отрезке от 0 до \(x_\ast\):
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
Вторая часть — площадь под дугой от \(x_\ast\) до 1:
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
Положим \(u = 1-x\) и обозначим \(\delta = 1-x_\ast\). Так как \(2x-x^2 = 1-u^2\), интеграл преобразуется к виду
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$$
Используя стандартную первообразную
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2},$$
получаем
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$$
Именно эту замкнутую формулу используют реализации, поэтому численное интегрирование не требуется.
Когда площадь вогнутой области уже найдена, интересующее отношение равно
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$$
Каждое вычисление использует лишь несколько квадратных корней, один арксинус и базовую арифметику. Поэтому реализации просто проверяют \(n=1,2,3,\dots\) и останавливаются на первом значении, где \(R(n) \lt 10^{-3}\).
При \(n=2\) точка пересечения упрощается до
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$$
Вклад прямой равен
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$$
Вклад дуги равен
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$$
Следовательно,
$$A_C(2) \approx 0.0782494456,$$
а
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366.$$
Поэтому
$$R(2) \approx 0.364626169291728,$$
что совпадает с численной проверкой в реализациях.
Реализации на C++, Python и Java устроены одинаково. Сначала они считают \(1-\pi/4\) постоянной величиной, потому что площадь L-секции не зависит от \(n\). Для каждого пробного значения \(n\) они вычисляют точку пересечения по приведённой выше квадратной формуле, затем получают \(\delta = 1-x_\ast\) и в закрытом виде считают вклад прямой и вклад дуги.
После этого площадь делится на постоянную площадь L-секции, получается отношение, и поиск идёт по положительным целым числам вверх до первого пересечения порога \(10^{-3}\). Одна из реализаций дополнительно проверяет контрольные значения \(R(1)=0.5\), \(R(2)\approx 0.364626169291728\) и тот факт, что порог \(10\%\) впервые достигается при \(n=15\). Это полезная проверка корректности формулы.
На каждое значение \(n\) требуется постоянное количество операций с плавающей точкой. Поэтому суммарное время равно \(O(n_\star)\), где \(n_\star\) — первое целое, удовлетворяющее неравенству. Память равна \(O(1)\), так как хранится только фиксированное число числовых величин.
نقوم أولاً بتطبيع جميع الدوائر بحيث يصبح نصف القطر مساوياً لـ 1. عندئذٍ توضع \(n\) دوائر متطابقة داخل مستطيل عرضه \(2n\) وارتفاعه \(2\). في الزاوية السفلية اليسرى يظهر مربع وحدة، وتزيل الدائرة الأولى ربع دائرة من هذا المربع. المنطقة المتبقية في تلك الزاوية هي مقطع \(L\). أما المثلث المقعّر فهو الجزء من هذا المقطع الواقع أسفل قطر المستطيل الكامل.
المطلوب إيجاد أصغر عدد صحيح موجب \(n\) بحيث
$$\frac{A_C(n)}{A_L} \lt 10^{-3}.$$
جوهر الحل أن الهندسة المحلية المطلوبة تنحصر في خط مستقيم واحد، وقوس دائرة واحد، ونقطة تقاطعهما داخل مربع الوحدة.
بعد جعل نصف القطر مساوياً لـ 1، يمكن كتابة الحل بالكامل باستخدام هندسة ابتدائية. تقوم التطبيقات بحساب مساحة المنطقة المقعّرة بصيغة مغلقة، ثم تفحص قيم \(n\) تصاعدياً.
داخل مربع الوحدة \(0 \le x \le 1\)، \(0 \le y \le 1\)، يأتي القوس المهم من دائرة مركزها \((1,1)\) ونصف قطرها 1:
$$(x-1)^2 + (y-1)^2 = 1.$$
نحتاج إلى الفرع السفلي من هذه الدائرة داخل المربع، ولذلك
$$y_{\mathrm{arc}}(x) = 1 - \sqrt{1-(x-1)^2} = 1 - \sqrt{2x-x^2}.$$
مقطع \(L\) يساوي مساحة مربع الوحدة مطروحاً منها مساحة ربع دائرة، ولهذا تكون مساحته ثابتة لا تعتمد على \(n\):
$$A_L = 1 - \frac{\pi}{4}.$$
يمتد قطر المستطيل \(2n \times 2\) من \((0,0)\) إلى \((2n,2)\)، وبالتالي فميله يساوي \(1/n\). داخل مربع الوحدة تصبح معادلة الخط
$$y_{\mathrm{line}}(x) = \frac{x}{n}.$$
المثلث المقعّر هو الجزء من مقطع \(L\) الموجود أسفل هذا الخط. عندما تكون \(x\) صغيرة يكون الخط أسفل القوس، وبعد نقطة التقاطع يصبح القوس هو الحد الأدنى. لهذا السبب تنقسم المساحة إلى جزأين طبيعيين.
لنرمز إلى إحداثي \(x\) لنقطة التقاطع الوحيدة داخل \((0,1)\) بالرمز \(x_\ast\). عندها تحقق المعادلة
$$\frac{x_\ast}{n} = 1 - \sqrt{2x_\ast-x_\ast^2}.$$
ننقل الجذر إلى الطرف الآخر ثم نربّع:
$$\sqrt{2x_\ast-x_\ast^2} = 1 - \frac{x_\ast}{n},$$
$$2x_\ast - x_\ast^2 = 1 - \frac{2x_\ast}{n} + \frac{x_\ast^2}{n^2}.$$
وبعد الضرب في \(n^2\) نحصل على المعادلة التربيعية
$$\left(n^2+1\right)x_\ast^2 - 2n(n+1)x_\ast + n^2 = 0.$$
الجذر الأصغر هو الجذر الذي يقع فعلاً داخل مربع الوحدة:
$$x_\ast = \frac{n\left(n+1-\sqrt{2n}\right)}{n^2+1}.$$
الجزء الأول هو المساحة تحت الخط من 0 إلى \(x_\ast\):
$$\int_0^{x_\ast}\frac{x}{n}\,dx = \frac{x_\ast^2}{2n}.$$
والجزء الثاني هو المساحة تحت القوس من \(x_\ast\) إلى 1:
$$\int_{x_\ast}^{1}\left(1-\sqrt{2x-x^2}\right)\,dx.$$
لنأخذ \(u = 1-x\)، ولنكتب
$$\delta = 1-x_\ast.$$
بما أن \(2x-x^2 = 1-u^2\)، يتحول التكامل إلى
$$\int_0^{\delta}\left(1-\sqrt{1-u^2}\right)\,du.$$
وباستخدام البدالة القياسية
$$\int \sqrt{1-u^2}\,du = \frac{u\sqrt{1-u^2} + \arcsin(u)}{2},$$
نحصل على الصيغة المغلقة
$$A_C(n) = \frac{x_\ast^2}{2n} + \delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2}, \qquad \delta = 1-x_\ast.$$
وهذه هي الصيغة نفسها التي تعتمدها التطبيقات، ولذلك لا حاجة إلى تكامل عددي.
بعد معرفة مساحة المنطقة المقعّرة تصبح النسبة المطلوبة
$$R(n) = \frac{A_C(n)}{A_L} = \frac{A_C(n)}{1-\pi/4}.$$
كل تقييم يحتاج فقط إلى عدد صغير من الجذور التربيعية، وقيمة عكس الجيب، وبعض الحسابات الأساسية. لذلك تقوم التطبيقات بتجربة \(n=1,2,3,\dots\) بالتتابع وتتوقف عند أول قيمة تحقق
$$R(n) \lt 10^{-3}.$$
عند \(n=2\) تتبسط نقطة التقاطع إلى
$$x_\ast = \frac{2\left(3-\sqrt{4}\right)}{5} = \frac{2}{5}, \qquad \delta = \frac{3}{5}.$$
مساهمة الخط تساوي
$$\frac{x_\ast^2}{2n} = \frac{(2/5)^2}{4} = 0.04.$$
أما مساهمة القوس فتساوي
$$\delta - \frac{\delta\sqrt{1-\delta^2} + \arcsin(\delta)}{2} = 0.6 - \frac{0.6 \cdot 0.8 + \arcsin(0.6)}{2} \approx 0.0382494456.$$
وبالتالي
$$A_C(2) \approx 0.0782494456,$$
بينما
$$A_L = 1 - \frac{\pi}{4} \approx 0.2146018366.$$
ومن ثم
$$R(2) \approx 0.364626169291728,$$
وهو تماماً رقم التحقق العددي المستخدم في التطبيقات.
تتبع تطبيقات ++C وPython وJava الخطة نفسها. فهي تعتبر أولاً أن مساحة مقطع \(L\)، أي \(1-\pi/4\)، ثابتة لأنها لا تعتمد على \(n\). ثم لكل قيمة مرشحة من \(n\)، تحسب نقطة التقاطع من الصيغة التربيعية السابقة، ثم تحسب \(\delta = 1-x_\ast\)، وبعد ذلك تقيم مساحة الجزء الخطي ومساحة الجزء القوسي مباشرة من الصيغ المغلقة.
بعد ذلك تُقسم المساحة المقعّرة على المساحة الثابتة لمقطع \(L\) للحصول على النسبة، ويستمر الفحص تصاعدياً حتى تهبط النسبة تحت العتبة \(10^{-3}\). كما أن أحد التطبيقات يتحقق أيضاً من القيم المرجعية \(R(1)=0.5\) و\(R(2)\approx 0.364626169291728\) وأن عتبة \(10\%\) تتحقق لأول مرة عند \(n=15\)، وهو اختبار جيد لصحة الاشتقاق.
كل قيمة مرشحة لـ \(n\) تحتاج إلى وقت ثابت من العمليات العددية ذات الفاصلة العائمة، لذا فزمن التنفيذ الكلي هو \(O(n_\star)\)، حيث \(n_\star\) هو أول عدد صحيح يحقق المتباينة. أما الذاكرة فهي \(O(1)\) لأن الخوارزمية تحتفظ بعدد ثابت فقط من القيم العددية.