Let \(b\) be the number of blue discs and \(n\) the total number of discs. Drawing two discs without replacement, the probability that both are blue is
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
So the integer pairs we seek satisfy
$$2b(b-1)=n(n-1).$$
The task is to find the first valid arrangement with \(n \gt 10^{12}\). The first such pair is \(b=756872327473\) and \(n=1070379110497\).
A direct search over all totals is far too slow, because valid pairs are extremely sparse. The key is that the quadratic condition above is equivalent to a negative Pell equation, which turns the search into a tiny recurrence loop.
The entire solution comes from replacing a probability statement with an integer equation whose solutions can be generated exactly and in increasing order.
The probability of drawing two blue discs without replacement is
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$$
Setting this equal to \(1/2\) gives
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$$
This is already a Diophantine equation, but not yet in a form that exposes a clean recurrence.
Multiply by \(4\) and complete the squares:
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
Rearranging gives
$$ (2n-1)^2-2(2b-1)^2=-1. $$
Now define
$$x=2n-1,\qquad y=2b-1.$$
Then every valid arrangement corresponds exactly to an integer solution of
$$x^2-2y^2=-1.$$
This is the negative Pell equation for \(D=2\). Because \(x\) and \(y\) are odd, the inverse substitution \(n=(x+1)/2\), \(b=(y+1)/2\) always returns integers.
Write a solution as \(x+y\sqrt{2}\). Multiplying by \(3+2\sqrt{2}\) produces
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
so
$$x'=3x+4y,\qquad y'=2x+3y.$$
The norm \(N(u+v\sqrt{2})=u^2-2v^2\) is multiplicative, and
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
Therefore
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
So the Pell invariant is preserved exactly. Starting from the smallest positive solution \((x,y)=(1,1)\), repeated multiplication by \(3+2\sqrt{2}\) generates the positive solutions in increasing order.
Substitute \(x=2n-1\) and \(y=2b-1\) into the Pell recurrence:
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1).$$
After simplifying, we obtain the recurrence used by the implementations:
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
This affine update preserves the original invariant \(2b(b-1)=n(n-1)\), and every step increases both \(b\) and \(n\), so the first solution exceeding a threshold is found by plain iteration.
A known nontrivial solution is \((b,n)=(15,21)\). Apply one recurrence step:
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
Check the invariant:
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
So \((85,120)\) is another exact solution, and indeed
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
The sequence continues
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
and the first pair with \(n \gt 10^{12}\) is
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
The linear part of the recurrence has dominant growth factor \(3+2\sqrt{2}\approx 5.828\). So the size of the solution is multiplied by roughly \(5.8\) at each step. That means only \(O(\log T)\) steps are needed to pass a threshold \(T\), which is why the \(10^{12}\) target is reached after only a small number of iterations.
The C++, Python, and Java implementations all keep only the current pair \((b,n)\) and the threshold \(10^{12}\). Instead of beginning with the trivial tiny solutions, they seed the process at \((15,21)\), which is already a valid arrangement in the same Pell-generated sequence.
Each loop iteration applies the exact update
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3,$$
then tests whether the new total has crossed the limit. As soon as \(n \gt 10^{12}\), the algorithm outputs the current blue count.
The C++ implementation also includes small checkpoint validations on known solutions and allows the threshold to be changed from the command line, but the mathematical core is identical in all three languages. For this problem the values remain comfortably within signed 64-bit range, so the arithmetic is straightforward in C++ and Java, while Python handles the same recurrence with native integers.
Let \(T\) be the minimum total-disc threshold. Because the recurrence grows by a constant factor \(3+2\sqrt{2}\), the number of loop iterations is \(O(\log T)\). More precisely, it is about \(\log_{3+2\sqrt{2}} T\).
For the specific target \(T=10^{12}\), starting from \((15,21)\), the loop runs only 14 updates before reaching \(n=1070379110497\). Each update uses constant-time integer arithmetic on a fixed number of values, so the practical runtime is negligible. Memory usage is \(O(1)\).
Seien \(b\) die Anzahl der blauen Scheiben und \(n\) die Gesamtzahl der Scheiben. Beim Ziehen ohne Zurücklegen ist die Wahrscheinlichkeit für zwei blaue Scheiben
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
Gesucht sind also ganzzahlige Paare mit
$$2b(b-1)=n(n-1).$$
Gefunden werden soll die erste Anordnung mit \(n \gt 10^{12}\). Das erste passende Paar ist \(b=756872327473\) und \(n=1070379110497\).
Ein direktes Durchprobieren aller möglichen Gesamtzahlen ist unpraktisch, weil gültige Lösungen sehr selten sind. Der entscheidende Schritt ist, die quadratische Bedingung in eine negative Pell-Gleichung umzuschreiben und dann nur noch eine kurze Rekurrenz zu iterieren.
Die komplette Methode besteht darin, eine Wahrscheinlichkeitsbedingung in eine Struktur zu verwandeln, deren ganzzahlige Lösungen sich exakt und in aufsteigender Reihenfolge erzeugen lassen.
Die Wahrscheinlichkeit, ohne Zurücklegen zwei blaue Scheiben zu ziehen, ist
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$$
Die Bedingung aus der Aufgabe lautet daher
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$$
Damit haben wir bereits eine diophantische Gleichung, aber noch keine bequeme Rekurrenz.
Multipliziere mit \(4\) und ergänze zu Quadraten:
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
Nach Umstellen erhält man
$$ (2n-1)^2-2(2b-1)^2=-1. $$
Setze nun
$$x=2n-1,\qquad y=2b-1.$$
Dann entspricht jede gültige Anordnung genau einer ganzzahligen Lösung von
$$x^2-2y^2=-1.$$
Das ist die negative Pell-Gleichung für \(D=2\). Weil \(x\) und \(y\) ungerade sind, liefert die Rücktransformation \(n=(x+1)/2\) und \(b=(y+1)/2\) wieder ganze Zahlen.
Schreibe eine Lösung als \(x+y\sqrt{2}\). Die Multiplikation mit \(3+2\sqrt{2}\) ergibt
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
also
$$x'=3x+4y,\qquad y'=2x+3y.$$
Die Norm \(N(u+v\sqrt{2})=u^2-2v^2\) ist multiplikativ, und
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
Deshalb gilt
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
Das Pell-Invariante bleibt also exakt erhalten. Ausgehend von der kleinsten positiven Lösung \((x,y)=(1,1)\) erzeugt wiederholte Multiplikation mit \(3+2\sqrt{2}\) die positiven Lösungen in wachsender Reihenfolge.
Setzt man \(x=2n-1\) und \(y=2b-1\) in die Pell-Rekurrenz ein, so folgt
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1).$$
Nach Vereinfachung erhält man genau die Rekurrenz, die in den Implementierungen verwendet wird:
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
Diese affine Abbildung erhält die ursprüngliche Bedingung \(2b(b-1)=n(n-1)\). Da beide Werte bei jeder positiven Lösung wachsen, reicht simples Iterieren bis über die Zielschranke hinaus.
Eine bekannte nichttriviale Lösung ist \((b,n)=(15,21)\). Ein Rekurrenzschritt liefert
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
Kontrolle des Invarianten:
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
Damit ist \((85,120)\) wieder eine exakte Lösung, und tatsächlich gilt
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
Die Folge setzt sich fort als
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
und das erste Paar mit \(n \gt 10^{12}\) ist
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
Der dominante Wachstumsfaktor der linearen Komponente ist \(3+2\sqrt{2}\approx 5{,}828\). Damit vergrößert sich die Größenordnung der Lösung in jedem Schritt ungefähr um den Faktor \(5{,}8\). Deshalb werden nur \(O(\log T)\) Schritte benötigt, um eine Schranke \(T\) zu überschreiten.
Die C++-, Python- und Java-Implementierungen speichern nur das aktuelle Paar \((b,n)\) und die Schranke \(10^{12}\). Statt mit den trivialen Kleinstlösungen zu beginnen, starten sie bei \((15,21)\), also bereits in der relevanten nichttrivialen Folge.
Jede Schleifeniteration wendet exakt die Aktualisierung
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3$$
an und prüft danach, ob die Gesamtzahl die Grenze überschritten hat. Sobald \(n \gt 10^{12}\) gilt, wird die aktuelle Anzahl blauer Scheiben ausgegeben.
Die C++-Variante enthält zusätzlich kleine Plausibilitätsprüfungen mit bekannten Lösungen und erlaubt eine veränderbare Schranke, aber mathematisch rechnen alle drei Sprachen identisch. Für diese Aufgabe bleiben die Werte deutlich innerhalb des 64-Bit-Bereichs, sodass C++ und Java mit normalen Ganzzahltypen auskommen, während Python dieselbe Rekurrenz mit nativen Ganzzahlen ausführt.
Sei \(T\) die verlangte Untergrenze für die Gesamtzahl der Scheiben. Wegen des konstanten Wachstumsfaktors \(3+2\sqrt{2}\) benötigt die Schleife \(O(\log T)\) Iterationen, genauer ungefähr \(\log_{3+2\sqrt{2}} T\).
Für \(T=10^{12}\) läuft die Schleife, beginnend bei \((15,21)\), nur 14 Aktualisierungen, bis \(n=1070379110497\) erreicht wird. Jede Aktualisierung verwendet nur eine feste Anzahl elementarer Ganzzahloperationen. Die Laufzeit ist damit praktisch sofortig, und der Speicherbedarf beträgt \(O(1)\).
\(b\) mavi disk sayısı, \(n\) ise toplam disk sayısı olsun. Geri koymadan iki disk çekildiğinde ikisinin de mavi olma olasılığı
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
Dolayısıyla aradığımız tamsayı çiftleri şu denklemi sağlar:
$$2b(b-1)=n(n-1).$$
Amaç, \(n \gt 10^{12}\) koşulunu sağlayan ilk düzeni bulmaktır. İlk uygun çift \(b=756872327473\) ve \(n=1070379110497\) değerleridir.
Toplam disk sayısını tek tek deneyerek arama yapmak pratik değildir; geçerli çözümler çok seyrektir. Kritik fikir, bu ikinci dereceden koşulun negatif Pell denklemiyle aynı yapıya sahip olduğunu fark etmektir. Böylece arama, çok kısa bir yineleme döngüsüne indirgenir.
Bütün çözüm, olasılık ifadesini tam sayı çözümleri artan sırayla üreten bir cebirsel yapıya dönüştürmekten ibarettir.
Geri koymadan iki mavi disk çekme olasılığı
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}$$
olduğuna göre, problem koşulu
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1)$$
şeklindedir. Bu zaten bir Diofant denklemi verir, fakat henüz verimli bir yineleme formu ortaya çıkmış değildir.
Denklemi \(4\) ile çarpıp kare tamamlayalım:
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
Buradan
$$ (2n-1)^2-2(2b-1)^2=-1 $$
elde edilir. Şimdi
$$x=2n-1,\qquad y=2b-1$$
tanımlarını yaparsak, her geçerli düzen tam olarak şu denklemin bir tamsayı çözümüne karşılık gelir:
$$x^2-2y^2=-1.$$
Bu, \(D=2\) için negatif Pell denklemidir. \(x\) ve \(y\) tek olduğu için ters dönüşüm \(n=(x+1)/2\), \(b=(y+1)/2\) her zaman tamsayı verir.
Bir çözümü \(x+y\sqrt{2}\) biçiminde yazalım. Bunu \(3+2\sqrt{2}\) ile çarparsak
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
dolayısıyla
$$x'=3x+4y,\qquad y'=2x+3y$$
olur. \(N(u+v\sqrt{2})=u^2-2v^2\) normu çarpımsaldır ve
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
Bu yüzden
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
Yani Pell invarianti aynen korunur. En küçük pozitif çözüm \((x,y)=(1,1)\) noktasından başlayıp bu çarpımı tekrarlamak, bütün pozitif çözümleri artan sırayla üretir.
\(x=2n-1\) ve \(y=2b-1\) yerine koyunca
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1)$$
olur. Düzenlersek, uygulamaların kullandığı yineleme doğrudan çıkar:
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
Bu affine güncelleme, başlangıçtaki invariant olan \(2b(b-1)=n(n-1)\) eşitliğini korur. Ayrıca pozitif çözümlerde hem \(b\) hem \(n\) büyüdüğü için, eşik değeri aşan ilk çözümü bulmak için yalnızca ileri doğru yinelemek yeterlidir.
Bilinen bir sıfırdan farklı çözüm \((b,n)=(15,21)\) çiftidir. Bir adım uygulayalım:
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
Invariant kontrolü:
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
Demek ki \((85,120)\) de tam çözümdür; gerçekten
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
Dizi şu şekilde devam eder:
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
ve \(n \gt 10^{12}\) koşulunu sağlayan ilk çift
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
Yinelemenin lineer kısmının baskın büyüme katsayısı \(3+2\sqrt{2}\approx 5.828\) değeridir. Yani çözüm büyüklüğü her adımda yaklaşık \(5.8\) kat artar. Bu nedenle \(T\) eşiğini geçmek için gereken adım sayısı yalnızca \(O(\log T)\) mertebesindedir.
C++, Python ve Java uygulamaları yalnızca mevcut \((b,n)\) çiftini ve \(10^{12}\) eşiğini saklar. Önemsiz küçük çözümlerle başlamak yerine, aynı Pell zincirinin içindeki geçerli bir çözüm olan \((15,21)\) çiftinden başlarlar.
Her döngü adımında
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3$$
güncellemesi uygulanır; sonra toplam disk sayısının sınırı geçip geçmediğine bakılır. \(n \gt 10^{12}\) olur olmaz mevcut mavi disk sayısı çıktı verilir.
C++ sürümü ayrıca bilinen çözümler üzerinde küçük doğrulamalar yapar ve eşik değerini değiştirmeye izin verir; fakat üç dilde de çekirdek matematik aynıdır. Bu problemde sayılar 64 bit işaretli tamsayı aralığında rahatça kaldığı için C++ ve Java doğrudan yerleşik tam sayı tipleri kullanır; Python ise aynı yinelemeyi doğal tamsayılarla yürütür.
\(T\) toplam disk sayısı için hedef eşik olsun. Sabit büyüme katsayısı \(3+2\sqrt{2}\) nedeniyle döngü \(O(\log T)\) adım sürer; daha hassas söylersek yaklaşık \(\log_{3+2\sqrt{2}} T\) iterasyon gerekir.
\(T=10^{12}\) için, \((15,21)\) başlangıcından itibaren döngü yalnızca 14 güncelleme sonra \(n=1070379110497\) değerine ulaşır. Her güncelleme sabit sayıda tamsayı işlemi içerir. Dolayısıyla çalışma süresi pratikte ihmal edilebilir, bellek kullanımı ise \(O(1)\)'dir.
Sea \(b\) el número de discos azules y \(n\) el número total de discos. Al extraer dos discos sin reemplazo, la probabilidad de que ambos sean azules es
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
Por tanto, los pares enteros buscados satisfacen
$$2b(b-1)=n(n-1).$$
Hay que encontrar la primera disposición con \(n \gt 10^{12}\). El primer par que cumple esta condición es \(b=756872327473\) y \(n=1070379110497\).
Probar todos los valores de \(n\) sería inútil, porque las soluciones válidas son muy escasas. La estructura correcta aparece al transformar la condición cuadrática en una ecuación de Pell negativa; a partir de ahí, la búsqueda se reduce a una recurrencia muy corta.
La idea completa consiste en convertir una condición de probabilidad en una ecuación diofántica cuyas soluciones se generan exactamente y en orden creciente.
La probabilidad de sacar dos discos azules sin reemplazo es
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$$
Al imponer que sea igual a \(1/2\), obtenemos
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$$
Ya tenemos una ecuación diofántica, pero todavía no una forma cómoda de enumerar sus soluciones.
Multiplicamos por \(4\) y completamos cuadrados:
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
Reordenando, queda
$$ (2n-1)^2-2(2b-1)^2=-1. $$
Definimos entonces
$$x=2n-1,\qquad y=2b-1.$$
Cada disposición válida corresponde exactamente a una solución entera de
$$x^2-2y^2=-1.$$
Esta es la ecuación de Pell negativa para \(D=2\). Como \(x\) e \(y\) son impares, la sustitución inversa \(n=(x+1)/2\), \(b=(y+1)/2\) devuelve enteros.
Escribamos una solución como \(x+y\sqrt{2}\). Al multiplicarla por \(3+2\sqrt{2}\), obtenemos
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
de donde
$$x'=3x+4y,\qquad y'=2x+3y.$$
La norma \(N(u+v\sqrt{2})=u^2-2v^2\) es multiplicativa, y
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
Por eso
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
El invariante de Pell se preserva exactamente. Empezando desde la solución positiva mínima \((x,y)=(1,1)\), la multiplicación repetida por \(3+2\sqrt{2}\) genera las soluciones positivas en orden creciente.
Sustituyendo \(x=2n-1\) y \(y=2b-1\) en la recurrencia anterior, se obtiene
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1).$$
Al simplificar, aparece exactamente la recurrencia usada por las implementaciones:
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
Esta actualización afín conserva la condición original \(2b(b-1)=n(n-1)\). Además, en la rama positiva ambos valores crecen, de modo que basta con iterar hasta rebasar el umbral pedido.
Una solución no trivial conocida es \((b,n)=(15,21)\). Aplicamos una iteración:
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
Comprobación del invariante:
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
Por tanto, \((85,120)\) también es una solución exacta y, en efecto,
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
La sucesión continúa como
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
y el primer par con \(n \gt 10^{12}\) es
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
La parte lineal de la recurrencia tiene factor dominante \(3+2\sqrt{2}\approx 5.828\). Eso significa que el tamaño de la solución se multiplica aproximadamente por \(5.8\) en cada paso. En consecuencia, solo se necesitan \(O(\log T)\) iteraciones para superar un umbral \(T\).
Las implementaciones en C++, Python y Java guardan únicamente el par actual \((b,n)\) y el límite \(10^{12}\). En vez de empezar por las soluciones diminutas, arrancan en \((15,21)\), que ya es una disposición válida dentro de la misma cadena generada por Pell.
En cada vuelta del bucle se aplica la actualización exacta
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3,$$
y después se comprueba si el total ya superó el límite. En cuanto \(n \gt 10^{12}\), se devuelve el valor actual de \(b\).
La implementación en C++ añade además pequeñas comprobaciones con soluciones conocidas y permite variar el umbral, pero el núcleo matemático es el mismo en los tres lenguajes. Para este problema, los valores permanecen dentro del rango de 64 bits con signo, por lo que C++ y Java usan enteros nativos sin dificultad, mientras que Python ejecuta la misma recurrencia con sus enteros incorporados.
Sea \(T\) el umbral mínimo para el número total de discos. Como la recurrencia crece por un factor constante \(3+2\sqrt{2}\), el número de iteraciones es \(O(\log T)\), más precisamente del orden de \(\log_{3+2\sqrt{2}} T\).
Para \(T=10^{12}\), comenzando en \((15,21)\), el bucle ejecuta solo 14 actualizaciones antes de alcanzar \(n=1070379110497\). Cada actualización realiza una cantidad constante de operaciones enteras, de modo que el tiempo real es despreciable. El uso de memoria es \(O(1)\).
设蓝色圆盘数为 \(b\)，圆盘总数为 \(n\)。在不放回地随机抽取两次时，两次都抽到蓝盘的概率为
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
因此我们要求的整数对满足
$$2b(b-1)=n(n-1).$$
题目要求找出第一个满足 \(n \gt 10^{12}\) 的安排。对应的第一个解是 \(b=756872327473\)，\(n=1070379110497\)。
如果直接枚举总数 \(n\)，几乎不可能在合理时间内找到答案，因为满足条件的整数解非常稀疏。真正有用的结构是：上面的二次方程可以改写成一个负 Pell 方程，而所有正整数解都能由一个固定递推逐步生成。
整个解法的核心，是把一个概率条件改写成一个具有严格数论结构的整数方程，然后利用这个结构按大小顺序生成所有可行解。
不放回抽取两个蓝盘的概率也可以写成组合数形式：
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$$
令其等于 \(1/2\)，便得到
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$$
这已经是一个丢番图方程，但此时还看不出如何高效地产生下一组解。
将等式乘以 \(4\)，然后配方：
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
整理后得到
$$ (2n-1)^2-2(2b-1)^2=-1. $$
定义
$$x=2n-1,\qquad y=2b-1.$$
这样一来，每一个满足题意的安排都与如下整数方程的一组解一一对应：
$$x^2-2y^2=-1.$$
这就是 \(D=2\) 的负 Pell 方程。由于 \(x\) 与 \(y\) 都是奇数，反向变换 \(n=(x+1)/2\)、\(b=(y+1)/2\) 一定仍然给出整数。
把一个解写成 \(x+y\sqrt{2}\) 的形式。若乘上 \(3+2\sqrt{2}\)，则有
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
因此
$$x'=3x+4y,\qquad y'=2x+3y.$$
这里使用的关键事实是范数 \(N(u+v\sqrt{2})=u^2-2v^2\) 具有乘法性，而且
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
于是
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
也就是说，负 Pell 不变量被完整保留下来。以最小正解 \((x,y)=(1,1)\) 为起点，不断乘以 \(3+2\sqrt{2}\)，就会按从小到大的顺序生成所有正整数解。
把 \(x=2n-1\)、\(y=2b-1\) 代回去，可得
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1).$$
化简之后，正好得到程序中使用的更新公式：
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
这个仿射递推严格保持原始不变量 \(2b(b-1)=n(n-1)\)。而且在正整数分支上，\(b\) 和 \(n\) 每一步都会增加，所以只需要不断向前迭代，直到总数超过题目要求的阈值。
一个已知的非平凡解是 \((b,n)=(15,21)\)。代入一次递推：
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
检查不变量：
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
因此 \((85,120)\) 仍然是精确解，而且确实满足
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
继续递推可得到
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
最终，第一个满足 \(n \gt 10^{12}\) 的解为
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
递推的线性部分主导增长因子是 \(3+2\sqrt{2}\approx 5.828\)。也就是说，解的规模大约每一步扩大 \(5.8\) 倍，因此越过阈值 \(T\) 所需的步数只有 \(O(\log T)\)。这正是本题能在极短时间内完成的原因。
C++、Python 和 Java 的实现都只维护当前的 \((b,n)\) 以及阈值 \(10^{12}\)。它们没有从最小的平凡解开始，而是直接从同一条 Pell 解链上的非平凡解 \((15,21)\) 出发。
每一轮循环都执行
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3,$$
然后判断新的总数是否已经超过限制。一旦 \(n \gt 10^{12}\)，当前的蓝盘数量就是题目所需答案。
C++ 实现额外加入了几个已知解的检查点，并允许调整阈值，但三种语言的数学核心完全相同。对于本题的数值规模，结果始终落在 64 位有符号整数范围内，所以 C++ 和 Java 直接使用固定宽度整数即可；Python 则用内建整数执行同样的递推。
设总盘数阈值为 \(T\)。由于递推按固定比例 \(3+2\sqrt{2}\) 增长，循环次数为 \(O(\log T)\)，更准确地说，大约是 \(\log_{3+2\sqrt{2}} T\) 次。
对于 \(T=10^{12}\)，若从 \((15,21)\) 开始，循环只需要 14 次更新就会到达 \(n=1070379110497\)。每次更新只涉及常数次整数乘加运算，因此实际运行时间几乎可以忽略，空间复杂度为 \(O(1)\)。
Пусть \(b\) обозначает число синих дисков, а \(n\) — общее число дисков. При извлечении двух дисков без возвращения вероятность того, что оба окажутся синими, равна
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
Следовательно, искомые целочисленные пары удовлетворяют уравнению
$$2b(b-1)=n(n-1).$$
Нужно найти первое допустимое расположение, для которого \(n \gt 10^{12}\). Первая такая пара имеет вид \(b=756872327473\), \(n=1070379110497\).
Прямой перебор по всем возможным значениям \(n\) не годится, потому что подходящие решения встречаются крайне редко. Полезная структура возникает после преобразования этого квадратного условия в отрицательное уравнение Пелля, после чего вся задача сводится к очень короткой рекуррентной последовательности.
Вся идея состоит в том, чтобы заменить вероятностное условие на диофантово уравнение, чьи решения можно порождать точно и в порядке возрастания.
Вероятность вытащить два синих диска без возвращения равна
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$$
Приравнивая её к \(1/2\), получаем
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$$
Это уже диофантово уравнение, но пока не видно, как быстро перечислять все его решения.
Умножим равенство на \(4\) и выделим полные квадраты:
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
После перестановки членов получаем
$$ (2n-1)^2-2(2b-1)^2=-1. $$
Введём обозначения
$$x=2n-1,\qquad y=2b-1.$$
Тогда каждое допустимое расположение в точности соответствует целочисленному решению
$$x^2-2y^2=-1.$$
Это отрицательное уравнение Пелля для \(D=2\). Поскольку \(x\) и \(y\) нечётные, обратная замена \(n=(x+1)/2\), \(b=(y+1)/2\) снова даёт целые числа.
Запишем решение в виде \(x+y\sqrt{2}\). Умножение на \(3+2\sqrt{2}\) даёт
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
то есть
$$x'=3x+4y,\qquad y'=2x+3y.$$
Норма \(N(u+v\sqrt{2})=u^2-2v^2\) мультипликативна, а
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
Следовательно,
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
Инвариант уравнения Пелля сохраняется точно. Начиная с наименьшего положительного решения \((x,y)=(1,1)\), повторное умножение на \(3+2\sqrt{2}\) порождает все положительные решения в возрастающем порядке.
Подставляя \(x=2n-1\) и \(y=2b-1\), получаем
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1).$$
После упрощения выходит именно та рекуррентность, которую используют реализации:
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
Это аффинное преобразование сохраняет исходный инвариант \(2b(b-1)=n(n-1)\). Кроме того, на положительной ветви и \(b\), и \(n\) возрастают, поэтому для поиска первого решения выше порога достаточно просто итерировать вперёд.
Известное нетривиальное решение — \((b,n)=(15,21)\). Один шаг рекуррентности даёт
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
Проверим инвариант:
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
Значит, \((85,120)\) — снова точное решение, и действительно
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
Далее последовательность выглядит так:
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
а первая пара с \(n \gt 10^{12}\) равна
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
Доминирующий коэффициент роста линейной части рекуррентности равен \(3+2\sqrt{2}\approx 5.828\). Это означает, что размер решения примерно умножается на \(5.8\) на каждом шаге. Поэтому для превышения порога \(T\) требуется только \(O(\log T)\) итераций.
Реализации на C++, Python и Java хранят только текущую пару \((b,n)\) и порог \(10^{12}\). Вместо самых маленьких тривиальных решений они стартуют с \((15,21)\), то есть сразу с нетривиального члена той же самой Pell-последовательности.
На каждой итерации цикла выполняется точное обновление
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3,$$
после чего проверяется, превысило ли новое общее число дисков границу. Как только \(n \gt 10^{12}\), текущий \(b\) и есть требуемый ответ.
В варианте на C++ дополнительно есть маленькие проверки на известных решениях и возможность менять порог, но математическое ядро у всех трёх реализаций одинаково. Для данной задачи значения остаются в пределах знакового 64-битного диапазона, поэтому C++ и Java спокойно используют стандартные целые типы, а Python выполняет ту же рекуррентность своими встроенными целыми числами.
Пусть \(T\) — минимальный порог для общего числа дисков. Поскольку рекуррентность растёт с постоянным множителем \(3+2\sqrt{2}\), количество итераций равно \(O(\log T)\), точнее порядка \(\log_{3+2\sqrt{2}} T\).
Для \(T=10^{12}\), если начать с \((15,21)\), цикл делает всего 14 обновлений, прежде чем достигается \(n=1070379110497\). Каждое обновление использует лишь константное число целочисленных операций, так что время работы практически мгновенно. Память — \(O(1)\).
لنرمز إلى عدد الأقراص الزرقاء بـ \(b\)، وإلى العدد الكلي للأقراص بـ \(n\). عند سحب قرصين من دون إرجاع، فإن احتمال أن يكون القرصان أزرقين هو
$$\frac{b}{n}\cdot\frac{b-1}{n-1}=\frac{1}{2}.$$
إذن الأزواج الصحيحة المطلوبة تحقق المعادلة
$$2b(b-1)=n(n-1).$$
المطلوب هو إيجاد أول ترتيب يحقق \(n \gt 10^{12}\). وأول زوج يحقق ذلك هو \(b=756872327473\) و\(n=1070379110497\).
البحث المباشر على جميع القيم الممكنة لـ \(n\) غير عملي، لأن الحلول الصحيحة نادرة جدًا. الفكرة الأساسية هي أن هذا الشرط التربيعي يمكن تحويله إلى معادلة بيل سالبة، وعندها تصبح المسألة كلها مجرد تكرار قصير جدًا.
جوهر الحل هو تحويل شرط احتمالي إلى معادلة ديوفانتية يمكن توليد حلولها الصحيحة بدقة وبترتيب تصاعدي.
احتمال سحب قرصين أزرقين من دون إرجاع يساوي
$$\frac{\binom{b}{2}}{\binom{n}{2}}=\frac{b(b-1)}{n(n-1)}.$$
وبفرض أن هذا الاحتمال يساوي \(1/2\) نحصل على
$$\frac{b(b-1)}{n(n-1)}=\frac{1}{2}\qquad\Longleftrightarrow\qquad 2b(b-1)=n(n-1).$$
هذه بالفعل معادلة ديوفانتية، لكنها ليست بعد في الصورة التي تكشف التكرار المناسب.
نضرب في \(4\) ثم نكمل المربعات:
$$8b^2-8b=4n^2-4n,$$
$$2(2b-1)^2-2=(2n-1)^2-1.$$
وبإعادة الترتيب نحصل على
$$ (2n-1)^2-2(2b-1)^2=-1. $$
لنعرّف الآن
$$x=2n-1,\qquad y=2b-1.$$
عندئذٍ يصبح كل ترتيب صحيح مطابقًا تمامًا لحل صحيح للمعادلة
$$x^2-2y^2=-1.$$
وهذه هي معادلة بيل السالبة عندما \(D=2\). وبما أن \(x\) و\(y\) فرديان، فإن التحويل العكسي \(n=(x+1)/2\) و\(b=(y+1)/2\) يعيد أعدادًا صحيحة.
نكتب الحل على الصورة \(x+y\sqrt{2}\). إذا ضربناه في \(3+2\sqrt{2}\)، فإننا نحصل على
$$x'+y'\sqrt{2}=(3+2\sqrt{2})(x+y\sqrt{2}),$$
ومن ثم
$$x'=3x+4y,\qquad y'=2x+3y.$$
المعيار \(N(u+v\sqrt{2})=u^2-2v^2\) ضربي، كما أن
$$N(3+2\sqrt{2})=3^2-2\cdot 2^2=1.$$
لذلك
$$x'^2-2y'^2=N(x'+y'\sqrt{2})=N(3+2\sqrt{2})N(x+y\sqrt{2})=1\cdot(-1)=-1.$$
أي إن ثابت معادلة بيل يبقى محفوظًا تمامًا. وإذا بدأنا من أصغر حل موجب \((x,y)=(1,1)\)، فإن تكرار الضرب في \(3+2\sqrt{2}\) يولّد جميع الحلول الموجبة بترتيب متزايد.
بالتعويض عن \(x=2n-1\) و\(y=2b-1\) في علاقة بيل السابقة نحصل على
$$2n'-1=3(2n-1)+4(2b-1),$$
$$2b'-1=2(2n-1)+3(2b-1).$$
وبعد التبسيط تظهر صيغة التحديث التي تستخدمها التطبيقات:
$$\boxed{b'=3b+2n-2,\qquad n'=4b+3n-3.}$$
هذا التحويل الخطي المزاح يحافظ على الثابت الأصلي \(2b(b-1)=n(n-1)\). ولأن كلًّا من \(b\) و\(n\) يزدادان على الفرع الموجب، يكفي أن نكرّر إلى الأمام حتى نتجاوز الحد المطلوب.
أحد الحلول غير التافهة المعروفة هو \((b,n)=(15,21)\). بعد خطوة واحدة من التكرار نحصل على
$$b'=3\cdot 15+2\cdot 21-2=85,$$
$$n'=4\cdot 15+3\cdot 21-3=120.$$
وللتحقق من الثابت:
$$2\cdot 85\cdot 84=14280,\qquad 120\cdot 119=14280.$$
إذن \((85,120)\) حل صحيح آخر، وبالفعل
$$\frac{85}{120}\cdot\frac{84}{119}=\frac{1}{2}.$$
وتستمر السلسلة على الصورة
$$ (15,21)\to(85,120)\to(493,697)\to(2871,4060)\to\cdots $$
وأول زوج يحقق \(n \gt 10^{12}\) هو
$$\boxed{(b,n)=(756872327473,\ 1070379110497).}$$
عامل النمو المسيطر في الجزء الخطي من التكرار هو \(3+2\sqrt{2}\approx 5.828\). وهذا يعني أن حجم الحل يكبر تقريبًا بمقدار \(5.8\) مرة في كل خطوة. لذلك فإن عدد الخطوات اللازمة لتجاوز حد \(T\) ليس إلا \(O(\log T)\).
تحتفظ تطبيقات C++ وPython وJava فقط بالزوج الحالي \((b,n)\) وبالحد \(10^{12}\). وهي لا تبدأ من الحلول الصغيرة جدًا، بل تبدأ من \((15,21)\)، وهو حل صحيح غير تافه يقع على السلسلة نفسها الناتجة عن معادلة بيل.
في كل دورة من الحلقة يُطبَّق التحديث
$$b\leftarrow 3b+2n-2,\qquad n\leftarrow 4b+3n-3,$$
ثم يُفحَص ما إذا كان العدد الكلي قد تجاوز الحد. وبمجرد أن يصبح \(n \gt 10^{12}\)، يكون العدد الحالي للأقراص الزرقاء هو الجواب المطلوب.
إصدار C++ يضيف أيضًا بعض فحوصات السلامة على حلول معروفة ويسمح بتغيير العتبة، لكن اللب الرياضي واحد في اللغات الثلاث كلها. وبالنسبة إلى هذه المسألة، تبقى القيم ضمن مجال الأعداد الصحيحة ذات 64 بت بإشارة، لذلك تكفي الأنواع الصحيحة العادية في C++ وJava، بينما ينفّذ Python العلاقة نفسها بأعداده الصحيحة المضمنة.
إذا رمزنا إلى حد العدد الكلي بـ \(T\)، فإن عدد التكرارات يساوي \(O(\log T)\) لأن النمو يتم بعامل ثابت هو \(3+2\sqrt{2}\). وبصورة أدق فهو من رتبة \(\log_{3+2\sqrt{2}} T\).
عند \(T=10^{12}\)، وإذا بدأنا من \((15,21)\)، فإن الحلقة تنفّذ 14 تحديثًا فقط قبل الوصول إلى \(n=1070379110497\). وكل تحديث يحتاج إلى عدد ثابت من عمليات الضرب والجمع الصحيحة، لذا فالزمن العملي ضئيل جدًا، واستهلاك الذاكرة هو \(O(1)\).