In the original problem we observe random three-digit licence plates from 000 to 999. We stop as soon as two observed plates sum to \(1000\). The local solvers generalize the setting to any odd maximum \(M\), so the available values are \(\{0,1,\dots,M\}\) and the target sum is \(M+1\). For the Project Euler input \(M=999\), the program computes the expected stopping time and prints it to eight decimal places.
Let
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
Then the numbers split into three types. For each \(1\le i\le m\) we have one complementary pair
$$P_i=\{i,N-i\}.$$
There are \(m\) such pairs, one self-complementary value \(s\) because \(s+s=N\), and the singleton \(0\), whose complement \(N\) lies outside the range. When \(M=999\), this means \(499\) ordinary pairs, the special value \(500\), and the harmless value \(000\).
Before the game ends, an ordinary pair can only be in two relevant conditions: unopened, meaning neither side has appeared yet, or half-open, meaning exactly one side has appeared. A fully completed pair would already end the process, so it never appears inside the recurrence.
Therefore the detailed identity of the opened pairs does not matter. We only need:
\(k\): the number of half-open pairs, and a binary flag telling us whether \(s\) has already appeared once.
Define \(E_0[k]\) as the expected remaining number of draws when \(k\) ordinary pairs are half-open and \(s\) has not been seen. Define \(E_1[k]\) as the same expectation when \(s\) has been seen exactly once. This is the exact meaning of the arrays e0 and e1 in the C++, Python, and Java solutions.
Assume we are in state \(E_1[k]\). Then:
The draw \(0\) keeps the state unchanged. For each of the \(k\) half-open pairs, drawing the already seen side also keeps the state unchanged. So there are \(k+1\) same-state outcomes.
Drawing \(s\) again wins immediately. For each of the \(k\) half-open pairs, drawing the missing complement also wins immediately. So there are \(k+1\) winning outcomes.
The remaining \(m-k\) pairs are unopened. Any one of their \(2(m-k)\) numbers opens a new pair, so the process moves to \(E_1[k+1]\).
First-step analysis therefore gives
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$$
Moving the same-state term to the left yields the recurrence implemented in the code:
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
The denominator \(N-(k+1)\) is exactly the variable den in the source files. It appears because we subtract the probability of staying in the same state from the left-hand side.
Now assume \(s\) has not appeared yet. The same-state outcomes are still \(0\) plus the already seen sides of the \(k\) half-open pairs, so again there are \(k+1\) of them.
Drawing the missing complement of one of the \(k\) half-open pairs wins immediately. Drawing \(s\) does not win yet; it changes the state from \(E_0[k]\) to \(E_1[k]\). Finally, any number from one of the \(m-k\) unopened pairs moves the process to \(E_0[k+1]\).
Hence
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
so
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
When \(k=m\), every ordinary pair is already half-open, so there is no transition to \(k+1\). The recurrence becomes
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$$
From there we sweep backward for \(k=m-1,m-2,\dots,0\). The required expectation is
$$\boxed{E_0[0]}. $$
This is the exact case hard-coded in the C++ verification. Here \(N=4\), there is one ordinary pair \(\{1,3\}\), the special value \(2\), and the inert value \(0\). The backward recurrence gives
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$$
This matches the checkpoint in Euler371.cpp. For the real input \(M=999\), the same recurrence with \(m=499\) gives
$$E_0[0]\approx 40.66368097.$$
All three solution files implement the same compressed dynamic program. They compute pairCount = (maxNumber - 1) / 2, set totalNumbers = 2 * pairCount + 2, allocate arrays e0 and e1, and iterate \(k\) downward from pairCount to \(0\).
The helper quantities are
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$$
Here grow counts the numbers that belong to still unopened pairs and therefore increase \(k\) by one. Then the code applies the two boxed recurrences above. The final formatted result is e0[0].
The C++ file also contains an explicit-state verifier for tiny instances. In that checker, every pair has three microstates: unseen, left side seen, or right side seen. Together with the flag for whether \(s\) has been seen, this creates \(2\cdot 3^m\) states. The program builds the linear system for those exact Markov expectations, solves it by Gaussian elimination, and confirms that the compressed recurrence agrees for \(m=2\) and \(m=3\).
Let \(m=(M-1)/2\). The implemented recurrence evaluates each \(k\) once, so the running time is \(O(m)\). The current implementations store two arrays of length \(m+1\), hence \(O(m)\) memory. The explicit-state verifier is exponential in \(m\) and is only used for very small checkpoint cases.
Im Originalproblem beobachtet man zufällige dreistellige Kennzeichen von 000 bis 999. Der Prozess endet, sobald zwei beobachtete Kennzeichen die Summe \(1000\) ergeben. Die lokalen Solver formulieren das allgemeiner für ein ungerades Maximum \(M\): gezogen wird aus \(\{0,1,\dots,M\}\), und die Zielsumme ist \(M+1\). Für den Euler-Fall \(M=999\) berechnet das Programm die erwartete Stoppzeit mit acht Nachkommastellen.
Setze
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
Dann zerfallen die Zahlen in drei Klassen. Für jedes \(1\le i\le m\) gibt es ein Komplementärpaar
$$P_i=\{i,N-i\}.$$
Insgesamt entstehen also \(m\) gewöhnliche Paare, der selbstkomplementäre Wert \(s\) mit \(s+s=N\), und die Einzelzahl \(0\), deren Komplement \(N\) außerhalb des Bereichs liegt. Für \(M=999\) sind das \(499\) normale Paare, der Spezialwert \(500\) und der harmlose Wert 000.
Vor dem Spielende kann ein gewöhnliches Paar nur in zwei relevanten Zuständen sein: ungeöffnet, wenn noch keine Seite gesehen wurde, oder halb geöffnet, wenn genau eine Seite gesehen wurde. Ein vollständig getroffenes Paar wäre bereits ein Gewinnzustand und taucht deshalb in der Rekurrenz nicht auf.
Darum ist die genaue Identität der geöffneten Paare unwichtig. Es genügt,
\(k\): die Anzahl halb geöffneter Paare, und ein Bit dafür zu speichern, ob \(s\) bereits einmal erschienen ist.
Sei \(E_0[k]\) die erwartete Restanzahl von Ziehungen, wenn \(k\) gewöhnliche Paare halb geöffnet sind und \(s\) noch nicht gesehen wurde. Sei \(E_1[k]\) dieselbe Erwartung, wenn \(s\) bereits genau einmal aufgetreten ist. Genau diese Bedeutung haben die Arrays e0 und e1 in C++, Python und Java.
Betrachte den Zustand \(E_1[k]\). Dann gilt:
Die Ziehung von \(0\) lässt den Zustand unverändert. Für jedes der \(k\) halb geöffneten Paare lässt auch die bereits gesehene Seite den Zustand unverändert. Es gibt also \(k+1\) Übergänge ohne Zustandswechsel.
Eine weitere Ziehung von \(s\) beendet den Prozess sofort. Ebenso beendet bei jedem der \(k\) halb geöffneten Paare das fehlende Komplement den Prozess. Das sind also \(k+1\) sofortige Gewinnfälle.
Die verbleibenden \(m-k\) Paare sind noch ungeöffnet. Jede ihrer \(2(m-k)\) Zahlen öffnet ein neues Paar und führt nach \(E_1[k+1]\).
Mit First-Step-Analyse folgt
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$$
Nach Umstellen erhält man genau die im Code verwendete Form:
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
Der Nenner \(N-(k+1)\) ist identisch zur Variablen den im Quelltext. Er entsteht dadurch, dass die Wahrscheinlichkeit des Verbleibs im selben Zustand auf die linke Seite gebracht wird.
Wenn \(s\) noch nicht gesehen wurde, bleiben die gleichen \(k+1\) Zustands-Schleifen erhalten: \(0\) sowie die bereits bekannten Seiten der \(k\) halb geöffneten Paare.
Das fehlende Komplement eines halb geöffneten Paares gewinnt sofort. Die Ziehung von \(s\) gewinnt noch nicht, sondern wechselt von \(E_0[k]\) nach \(E_1[k]\). Und jede Zahl aus einem noch ungeöffneten Paar führt nach \(E_0[k+1]\).
Daraus folgt
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
also
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
Für \(k=m\) sind bereits alle gewöhnlichen Paare halb geöffnet, daher gibt es keinen Übergang mehr nach \(k+1\). Dann gilt
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$$
Von dort iteriert man rückwärts für \(k=m-1,m-2,\dots,0\). Gesucht ist
$$\boxed{E_0[0]}. $$
Genau dieser Fall ist als Checkpoint in der C++-Datei hinterlegt. Hier sind \(N=4\), ein gewöhnliches Paar \(\{1,3\}\), der Spezialwert \(2\) und die inerte Zahl \(0\) vorhanden. Die Rückwärtsrekurrenz liefert
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$$
Das stimmt exakt mit dem Prüfwert aus Euler371.cpp überein. Für den echten Eingabewert \(M=999\) ergibt dieselbe Rekurrenz mit \(m=499\)
$$E_0[0]\approx 40.66368097.$$
Alle drei Lösungsdateien implementieren denselben komprimierten dynamischen Ansatz. Zuerst wird pairCount = (maxNumber - 1) / 2 berechnet, dann totalNumbers = 2 * pairCount + 2, anschließend werden die Arrays e0 und e1 angelegt, und schließlich läuft eine Schleife rückwärts über \(k\) von pairCount bis \(0\).
Die Hilfsgrößen sind
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$$
Dabei zählt grow genau die Zahlen, die zu noch ungeöffneten Paaren gehören und deshalb den Zustand nach \(k+1\) verschieben. Danach wendet der Code direkt die beiden eingerahmten Rekurrenzen an. Die finale Ausgabe ist e0[0].
Die C++-Datei enthält zusätzlich einen expliziten Verifizierer für sehr kleine Fälle. Dort besitzt jedes Paar drei Mikrozustände: nichts gesehen, linke Seite gesehen oder rechte Seite gesehen. Zusammen mit dem Bit für \(s\) entstehen \(2\cdot 3^m\) Zustände. Das Programm stellt das lineare Gleichungssystem für diese exakten Markov-Erwartungen auf, löst es per Gauß-Elimination und prüft so die komprimierte Formel für \(m=2\) und \(m=3\).
Mit \(m=(M-1)/2\) wird jeder Wert \(k\) genau einmal berechnet, also beträgt die Laufzeit \(O(m)\). Die aktuelle Implementierung speichert zwei Arrays der Länge \(m+1\) und benötigt daher \(O(m)\) Speicher. Der explizite Zustandsprüfer wächst exponentiell in \(m\) und wird bewusst nur für winzige Testfälle verwendet.
Orijinal soruda 000 ile 999 arasındaki üç basamaklı plakalar rastgele görülür. Süreç, görülen iki plakanın toplamı \(1000\) olduğunda durur. Yerel çözümler bunu tek bir örneğe sabitlemek yerine herhangi bir tek \(M\) için geneller: çekilen değerler \(\{0,1,\dots,M\}\) kümesindendir ve hedef toplam \(M+1\)'dir. Euler girdisi olan \(M=999\) için program beklenen durma süresini sekiz ondalık basamakla yazar.
Şöyle tanımlayalım:
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
Böylece her \(1\le i\le m\) için bir tamamlayıcı çift vardır:
$$P_i=\{i,N-i\}.$$
Toplamda \(m\) adet normal çift, \(s+s=N\) olduğu için kendisiyle eşleşen özel değer \(s\), bir de tümleyeni aralık dışında kalan \(0\) vardır. \(M=999\) durumunda bunlar \(499\) normal çift, özel değer \(500\) ve etkisiz değer 000 olur.
Süreç bitmeden önce normal bir çift yalnızca iki anlamlı durumda olabilir: henüz hiç görülmemiş olması ya da tam bir kez açılmış olması. Bir çiftin iki tarafı da görülmüş olsaydı oyun zaten biterdi; bu yüzden o durum reküransta yer almaz.
Bu nedenle hangi çiftlerin açıldığını tek tek tutmak gerekmez. Yalnızca şu bilgiler yeterlidir:
\(k\): tam bir kez açılmış normal çift sayısı, ve \(s\) değerinin daha önce bir kez görülüp görülmediğini söyleyen bir bayrak.
\(E_0[k]\), \(k\) çift açıkken ve \(s\) henüz görülmemişken kalan beklenen çekiliş sayısı olsun. \(E_1[k]\) ise \(s\) tam bir kez görüldüğündeki aynı beklenti olsun. C++, Python ve Java dosyalarındaki e0 ve e1 dizileri tam olarak bunu temsil eder.
\(E_1[k]\) durumunda olduğumuzu düşünelim.
\(0\) gelirse durum değişmez. Ayrıca açık olan \(k\) çiftin her biri için daha önce görülen taraf tekrar gelirse durum yine değişmez. Dolayısıyla aynı durumda kalmaya yol açan \(k+1\) sonuç vardır.
\(s\) yeniden gelirse anında kazanırız. Benzer biçimde açık olan \(k\) çiftin eksik tümleyenlerinden biri gelirse de süreç hemen biter. Yani kazandıran \(k+1\) sonuç vardır.
Kalan \(m-k\) çift henüz kapalıdır. Bu çiftlerden birine ait \(2(m-k)\) sayıdan biri gelirse yeni bir çift açılır ve süreç \(E_1[k+1]\) durumuna geçer.
İlk adım analizi ile
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1]$$
elde edilir. Aynı durumda kalma terimini sola atarsak kodda kullanılan form ortaya çıkar:
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
Buradaki \(N-(k+1)\) paydası kaynak dosyalardaki den değişkenidir. Bu ifade, aynı durumda kalma olasılığını sol tarafa taşımaktan gelir.
\(s\) henüz görülmemişken de aynı durumda bırakan sonuçlar yine \(k+1\) tanedir: \(0\) ve açık çiftlerdeki daha önce görülmüş taraflar.
Açık bir çiftin eksik tümleyeni gelirse hemen kazanırız. \(s\) gelirse henüz oyun bitmez; yalnızca \(E_0[k]\) durumundan \(E_1[k]\) durumuna geçilir. Kapalı çiftlerden gelen her sayı ise \(E_0[k+1]\) durumuna taşır.
Dolayısıyla
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
yani
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
\(k=m\) olduğunda tüm normal çiftler bir kez açılmıştır; artık \(k+1\)'e giden geçiş yoktur. Bu durumda
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}$$
olur. Sonra \(k=m-1,m-2,\dots,0\) için geriye doğru hesap yapılır. Aranan değer
$$\boxed{E_0[0]}. $$
Bu küçük örnek C++ çözümünde açıkça sınama olarak bulunur. Burada \(N=4\), tek normal çift \(\{1,3\}\), özel değer \(2\) ve etkisiz değer \(0\) vardır. Geriye doğru çözüm
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}$$
sonucunu verir. Bu, Euler371.cpp içindeki kesin kontrol değeriyle aynıdır. Gerçek girdi \(M=999\) için aynı rekürans \(m=499\) ile
$$E_0[0]\approx 40.66368097$$
değerini üretir.
Üç çözüm dosyasının da çekirdeği aynı sıkıştırılmış dinamik programdır. Önce pairCount = (maxNumber - 1) / 2 ve totalNumbers = 2 * pairCount + 2 hesaplanır, ardından e0 ve e1 dizileri oluşturulur ve \(k\) değeri pairCount'tan \(0\)'a doğru azaltılır.
Yardımcı büyüklükler
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1)$$
şeklindedir. grow, henüz açılmamış çiftlere ait ve bu yüzden \(k\) değerini bir artıran sayıların sayısıdır. Kod daha sonra yukarıdaki iki kutulu reküransı doğrudan uygular ve son olarak e0[0] değerini biçimlendirerek döndürür.
C++ dosyasında ayrıca küçük örnekler için açık durumlu bir doğrulama da vardır. Orada her normal çift üç mikrodurumdan birindedir: hiç görülmedi, sol taraf görüldü, sağ taraf görüldü. \(s\) değerinin görülüp görülmediği bitiyle birlikte toplam durum sayısı \(2\cdot 3^m\) olur. Program bu tam Markov sisteminin lineer denklemlerini kurar, Gauss elemesiyle çözer ve sıkıştırılmış formülün \(m=2\) ve \(m=3\) için aynı sonucu verdiğini doğrular.
\(m=(M-1)/2\) olsun. Rekürans her \(k\) değerini yalnızca bir kez hesapladığı için çalışma süresi \(O(m)\)'dir. Mevcut implementasyon iki adet \(m+1\) uzunluklu dizi tuttuğundan bellek kullanımı \(O(m)\)'dir. Açık durumlu doğrulayıcı ise üstel büyür ve bu yüzden sadece çok küçük testlerde kullanılır.
En el enunciado original observamos matrículas aleatorias de tres cifras desde 000 hasta 999. El proceso termina cuando dos matrículas observadas suman \(1000\). Los solucionadores locales lo escriben de forma general para cualquier máximo impar \(M\): los valores posibles son \(\{0,1,\dots,M\}\) y la suma objetivo es \(M+1\). Para el caso de Euler, \(M=999\), el programa calcula el tiempo de espera esperado y lo imprime con ocho decimales.
Definimos
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
Entonces, para cada \(1\le i\le m\), aparece un par complementario
$$P_i=\{i,N-i\}.$$
Hay \(m\) pares ordinarios, un valor especial \(s\) que se complementa consigo mismo porque \(s+s=N\), y el valor aislado \(0\), cuyo complemento \(N\) queda fuera del rango. Cuando \(M=999\), esto significa \(499\) pares normales, el valor especial \(500\) y el valor inofensivo 000.
Antes de detenernos, un par ordinario solo puede estar en dos situaciones relevantes: cerrado, si todavía no se ha visto ningún elemento, o semiabierto, si ya apareció exactamente uno. El estado “los dos lados ya aparecieron” sería absorbente y por eso no participa en la recurrencia.
Así, no importa qué pares concretos estén abiertos; solo importa cuántos hay. Guardamos:
\(k\): número de pares ordinarios semiabiertos, y un indicador binario de si \(s\) ya apareció una vez.
Definimos \(E_0[k]\) como la esperanza del número de extracciones restantes cuando hay \(k\) pares semiabiertos y \(s\) aún no ha aparecido. Definimos \(E_1[k]\) de la misma manera cuando \(s\) ya apareció exactamente una vez. Ese es el significado preciso de los arreglos e0 y e1 en las tres implementaciones.
Supongamos que estamos en el estado \(E_1[k]\).
Si sale \(0\), el estado no cambia. Para cada uno de los \(k\) pares semiabiertos, volver a sacar el lado ya visto tampoco cambia nada. En total hay \(k+1\) resultados que nos dejan en el mismo estado.
Si sale \(s\) otra vez, ganamos inmediatamente. También ganamos si sale el complemento faltante de cualquiera de los \(k\) pares semiabiertos. Por tanto hay \(k+1\) resultados ganadores.
Los otros \(m-k\) pares siguen cerrados. Cualquiera de sus \(2(m-k)\) valores abre un nuevo par y nos lleva a \(E_1[k+1]\).
Por análisis del primer paso,
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$$
Reordenando obtenemos exactamente la fórmula del código:
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
El denominador \(N-(k+1)\) coincide con la variable den del código. Aparece al mover al lado izquierdo la probabilidad de permanecer en el mismo estado.
Si \(s\) todavía no ha aparecido, los bucles al mismo estado siguen siendo \(k+1\): el valor \(0\) y los lados ya vistos de los \(k\) pares semiabiertos.
El complemento faltante de uno de esos pares produce victoria inmediata. Sacar \(s\) todavía no gana; solo cambia el estado de \(E_0[k]\) a \(E_1[k]\). Sacar un número de un par aún cerrado mueve el proceso a \(E_0[k+1]\).
Así,
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
y por tanto
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
Cuando \(k=m\), todos los pares ordinarios ya están semiabiertos y no existe transición a \(k+1\). La recurrencia se reduce a
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$$
Después solo queda iterar hacia atrás para \(k=m-1,m-2,\dots,0\). La respuesta buscada es
$$\boxed{E_0[0]}. $$
Este es el caso pequeño que verifica el archivo C++. Aquí \(N=4\), hay un único par ordinario \(\{1,3\}\), el valor especial \(2\) y el valor inerte \(0\). La recurrencia hacia atrás produce
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$$
Esto coincide exactamente con el punto de control de Euler371.cpp. Para la entrada real \(M=999\), la misma recurrencia con \(m=499\) da
$$E_0[0]\approx 40.66368097.$$
Los archivos en C++, Python y Java implementan el mismo programa dinámico comprimido. Calculan pairCount = (maxNumber - 1) / 2, luego totalNumbers = 2 * pairCount + 2, reservan los arreglos e0 y e1, y recorren \(k\) desde pairCount hasta \(0\).
Las cantidades auxiliares son
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$$
Aquí grow cuenta cuántos números pertenecen a pares todavía cerrados y, por tanto, incrementan \(k\) en uno. Después se aplican directamente las dos recurrencias anteriores. El valor final formateado es e0[0].
Además, el archivo C++ incluye una verificación con estados explícitos para instancias diminutas. Cada par puede estar en tres microestados: no visto, lado izquierdo visto o lado derecho visto. Junto con el bit que indica si \(s\) ya apareció, eso produce \(2\cdot 3^m\) estados. El programa construye el sistema lineal exacto para esos tiempos esperados de Markov, lo resuelve por eliminación gaussiana y comprueba así que la compresión es correcta para \(m=2\) y \(m=3\).
Sea \(m=(M-1)/2\). La recurrencia implementada procesa cada valor de \(k\) una sola vez, así que el tiempo total es \(O(m)\). Como el código guarda dos arreglos de longitud \(m+1\), el uso de memoria es \(O(m)\). El verificador con estados explícitos es exponencial en \(m\) y solo se usa para comprobaciones pequeñas.
原题观察的是从 000 到 999 的三位车牌。只要已经看到的两个车牌之和等于 \(1000\)，过程就停止。仓库中的本地解法把它推广到了任意奇数上界 \(M\)：可见数值为 \(\{0,1,\dots,M\}\)，目标和为 \(M+1\)。对 Project Euler 的实际输入 \(M=999\)，程序输出停止前抽取次数的期望，保留八位小数。
记
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
对于每个 \(1\le i\le m\)，都有一个互补对
$$P_i=\{i,N-i\}.$$
因此一共存在 \(m\) 个普通互补对，一个特殊值 \(s\)，因为 \(s+s=N\)，以及单独的 \(0\)，它的互补值 \(N\) 不在允许范围内。对于 \(M=999\)，这意味着 \(499\) 个普通配对、特殊值 \(500\) 和无害的 000。
在游戏尚未结束时，普通配对只会处于两种相关状态之一：未开启，即两边都没出现；半开启，即只有一边出现过。如果某一对的两边都已出现，过程已经结束，所以这种状态不会进入递推。
因此不需要记录“具体是哪几对被打开了”，只需要记录：
\(k\)：当前半开启的普通配对数量，以及一个二元标志，表示特殊值 \(s\) 是否已经出现过一次。
设 \(E_0[k]\) 为“有 \(k\) 个普通配对半开启，且 \(s\) 尚未出现”时，从当前状态到结束所需抽取次数的期望；设 \(E_1[k]\) 为“\(s\) 已经恰好出现一次”时对应的期望。这正是三个实现中数组 e0 和 e1 的含义。
先看状态 \(E_1[k]\)。
抽到 \(0\) 时状态不变。对每个半开启配对而言，再次抽到已经见过的那一侧，状态也不变。所以一共有 \(k+1\) 个“停留在原状态”的结果。
再次抽到 \(s\) 会立即结束。对每个半开启配对，抽到缺失的互补数也会立即结束。因此一共有 \(k+1\) 个直接获胜结果。
其余 \(m-k\) 个配对仍未开启。只要抽到这些配对中的任意一个数，共 \(2(m-k)\) 个可能，就会新打开一个配对，转移到 \(E_1[k+1]\)。
由一步分析可得
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$$
把原状态项移到左边，得到代码中的公式：
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
这里的分母 \(N-(k+1)\) 就是源码中的 den。它来自把“留在当前状态”的概率从左侧提取出来，而不是简单地数非获胜结果。
若 \(s\) 还没出现，那么不改变状态的结果仍然是 \(k+1\) 个：抽到 \(0\)，或者在某个半开启配对中抽到已经出现过的一侧。
若抽到某个半开启配对缺失的互补数，则立即结束。若抽到 \(s\)，还不会结束，而是从 \(E_0[k]\) 转移到 \(E_1[k]\)。若抽到某个未开启配对中的数，则转移到 \(E_0[k+1]\)。
因此
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
也就是
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
当 \(k=m\) 时，所有普通配对都已经半开启，不再存在通向 \(k+1\) 的转移。此时
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$$
然后从 \(k=m-1\) 逆推到 \(0\)。所求答案就是
$$\boxed{E_0[0]}. $$
这正是 C++ 文件中写死的检查点。此时 \(N=4\)，只有一个普通配对 \(\{1,3\}\)，特殊值是 \(2\)，另外还有惰性的 \(0\)。逆推可得
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$$
这与 Euler371.cpp 中的精确检查完全一致。对真实输入 \(M=999\)，也就是 \(m=499\)，同一递推会得到
$$E_0[0]\approx 40.66368097.$$
C++、Python 和 Java 三个解法实现的是同一个压缩动态规划。它们先计算 pairCount = (maxNumber - 1) / 2，再设 totalNumbers = 2 * pairCount + 2，创建数组 e0 和 e1，然后让 \(k\) 从 pairCount 递减到 \(0\)。
辅助量为
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$$
其中 grow 统计的是仍属于未开启配对的数字个数，因此它们会让 \(k\) 增加一。之后代码直接套用上面的两个盒装递推式，最终输出 e0[0]。
C++ 版本还包含一个小规模显式状态验证器。那里每个普通配对有三个微状态：两边都没见过、只见过左边、只见过右边；再乘上“\(s\) 是否已出现”的一位标志，总状态数为 \(2\cdot 3^m\)。程序为这些精确的马尔可夫期望建立线性方程组，用高斯消元求解，并据此验证压缩递推在 \(m=2\) 和 \(m=3\) 上的正确性。
令 \(m=(M-1)/2\)。压缩递推对每个 \(k\) 只计算一次，因此时间复杂度为 \(O(m)\)。当前实现保存两个长度为 \(m+1\) 的数组，所以空间复杂度为 \(O(m)\)。显式状态验证器则随 \(m\) 指数增长，只适用于很小的检查样例。
В исходной задаче наблюдаются случайные трёхзначные номера от 000 до 999. Процесс останавливается, как только сумма двух увиденных номеров становится равной \(1000\). Локальные решения формулируют ту же модель для любого нечётного максимума \(M\): возможные значения равномерно берутся из \(\{0,1,\dots,M\}\), а целевая сумма равна \(M+1\). Для входа Euler \(M=999\) программа вычисляет математическое ожидание момента остановки и выводит его с точностью до восьми знаков после запятой.
Обозначим
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
Для каждого \(1\le i\le m\) получаем комплементарную пару
$$P_i=\{i,N-i\}.$$
Итак, имеется \(m\) обычных пар, одно специальное число \(s\), которое дополняет само себя, поскольку \(s+s=N\), и отдельное значение \(0\), чьё дополнение \(N\) лежит вне диапазона. При \(M=999\) это \(499\) обычных пар, специальное число \(500\) и безвредное значение 000.
Пока процесс не завершён, обычная пара может находиться только в двух существенных состояниях: не открыта, если ещё не встретилась ни одна её сторона, или полуоткрыта, если встретилась ровно одна сторона. Состояние «обе стороны уже встречены» было бы поглощающим и потому не появляется внутри рекурсии.
Поэтому не нужно помнить, какие именно пары уже открыты. Достаточно знать:
\(k\): число полуоткрытых обычных пар, и бинарный флаг того, появлялось ли число \(s\) ровно один раз.
Пусть \(E_0[k]\) обозначает ожидаемое число оставшихся наблюдений, если полуоткрыто \(k\) обычных пар и \(s\) ещё не встречалось. Пусть \(E_1[k]\) обозначает ту же величину, если \(s\) уже встретилось один раз. Именно так интерпретируются массивы e0 и e1 во всех трёх языковых версиях.
Рассмотрим состояние \(E_1[k]\).
Если выпадает \(0\), состояние не меняется. Для каждой из \(k\) полуоткрытых пар повторное выпадение уже увиденной стороны тоже не меняет состояние. Значит, имеется \(k+1\) исходов, оставляющих нас в том же состоянии.
Если снова выпадает \(s\), процесс немедленно завершается. То же самое происходит, если для одной из \(k\) полуоткрытых пар выпадает недостающий комплемент. Следовательно, есть ещё \(k+1\) мгновенно завершающих исходов.
Оставшиеся \(m-k\) пар ещё не открыты. Любое из их \(2(m-k)\) чисел открывает новую пару и переводит процесс в состояние \(E_1[k+1]\).
По анализу первого шага получаем
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$$
После переноса петли влево имеем формулу из кода:
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
Знаменатель \(N-(k+1)\) совпадает с переменной den в исходниках. Он появляется потому, что вероятность остаться в том же состоянии выносится в левую часть уравнения.
Если \(s\) ещё не встречалось, количество самопереходов остаётся равным \(k+1\): это число \(0\) и уже виденные стороны у \(k\) полуоткрытых пар.
Недостающий комплемент одной из полуоткрытых пар немедленно завершает процесс. Появление \(s\) ещё не даёт победы, а только переводит нас из \(E_0[k]\) в \(E_1[k]\). Любое число из ещё закрытой пары переводит процесс в \(E_0[k+1]\).
Следовательно,
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
то есть
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
Когда \(k=m\), все обычные пары уже полуоткрыты, и перехода к \(k+1\) больше нет. Тогда
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$$
Далее выполняется обратный проход по \(k=m-1,m-2,\dots,0\). Искомое ожидание равно
$$\boxed{E_0[0]}. $$
Именно этот случай используется как контроль в C++-файле. Здесь \(N=4\), одна обычная пара \(\{1,3\}\), специальное число \(2\) и инертный ноль. Обратная рекурсия даёт
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$$
Это в точности совпадает с контрольным значением из Euler371.cpp. Для реального входа \(M=999\), то есть \(m=499\), та же рекурсия даёт
$$E_0[0]\approx 40.66368097.$$
Все три файла решений реализуют один и тот же сжатый динамический алгоритм. Сначала вычисляется pairCount = (maxNumber - 1) / 2, затем totalNumbers = 2 * pairCount + 2, выделяются массивы e0 и e1, после чего выполняется проход по \(k\) от pairCount вниз до \(0\).
Вспомогательные величины равны
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$$
Здесь grow считает числа, принадлежащие ещё не открытым парам и поэтому увеличивающие \(k\) на единицу. Затем код напрямую применяет две приведённые выше рекуррентные формулы и в конце форматирует значение e0[0].
В C++ есть ещё явный проверяющий решатель для маленьких случаев. В нём каждая пара имеет три микросостояния: ничего не видели, видели левую сторону, видели правую сторону. Вместе с битом появления \(s\) это даёт \(2\cdot 3^m\) состояний. Программа строит точную систему линейных уравнений для этих марковских ожиданий, решает её методом Гаусса и тем самым подтверждает корректность сжатой модели для \(m=2\) и \(m=3\).
Пусть \(m=(M-1)/2\). Сжатая рекурсия вычисляет каждое значение \(k\) ровно один раз, поэтому время работы равно \(O(m)\). Текущая реализация хранит два массива длины \(m+1\), так что затраты памяти составляют \(O(m)\). Явный проверяющий решатель имеет экспоненциальную сложность по \(m\) и используется только на крошечных тестах.
في الصياغة الأصلية نراقب لوحات سيارات عشوائية من 000 إلى 999. تتوقف العملية بمجرد أن يصبح مجموع لوحتين شوهدتا من قبل مساويًا لـ \(1000\). الحلول المحلية تعمم هذا إلى أي حد أعلى فردي \(M\): القيم الممكنة هي \(\{0,1,\dots,M\}\)، والمجموع المطلوب هو \(M+1\). بالنسبة إلى إدخال Project Euler حيث \(M=999\)، يحسب البرنامج التوقع الرياضي لزمن التوقف ويطبعه حتى ثماني خانات عشرية.
نعرّف
$$N=M+1,\qquad m=\frac{M-1}{2},\qquad s=\frac{M+1}{2}.$$
ولكل \(1\le i\le m\) يوجد زوج مكمّل
$$P_i=\{i,N-i\}.$$
إذن لدينا \(m\) أزواج عادية، وقيمة خاصة \(s\) تحقق \(s+s=N\)، وكذلك القيمة المنفردة \(0\) لأن مكمّلها \(N\) خارج المجال. عندما \(M=999\) نحصل على \(499\) زوجًا عاديًا، والقيمة الخاصة \(500\)، والقيمة غير المؤثرة 000.
قبل انتهاء العملية لا يمكن للزوج العادي إلا أن يكون في واحدة من حالتين مهمتين: مغلقًا إذا لم يظهر أي عنصر منه بعد، أو نصف مفتوح إذا ظهر عنصر واحد فقط. أما الحالة التي يظهر فيها الطرفان فهي حالة امتصاص وينتهي عندها اللعب، لذلك لا تدخل في معادلات التكرار.
لهذا لا نحتاج إلى معرفة أي الأزواج بالضبط قد فُتحت. يكفي أن نحتفظ بما يلي:
\(k\): عدد الأزواج العادية نصف المفتوحة، ومعه راية ثنائية تخبرنا هل ظهرت القيمة \(s\) مرة واحدة أم لا.
لنرمز بـ \(E_0[k]\) إلى التوقع لبقية السحوبات عندما يكون لدينا \(k\) أزواج نصف مفتوحة ولم تظهر \(s\) بعد. ولنرمز بـ \(E_1[k]\) إلى التوقع نفسه عندما تكون \(s\) قد ظهرت مرة واحدة بالضبط. هذا هو المعنى الدقيق للمصفوفتين e0 وe1 في حلول C++ وPython وJava.
نفترض أننا في الحالة \(E_1[k]\).
إذا سحبنا \(0\) فلا يتغير شيء. ولكل واحد من الأزواج نصف المفتوحة وعددها \(k\)، فإن إعادة سحب الطرف الذي سبق أن ظهر تترك الحالة كما هي. لذلك يوجد \(k+1\) نواتج تعيدنا إلى الحالة نفسها.
إذا ظهرت \(s\) مرة أخرى فإن العملية تنتهي فورًا. وكذلك إذا ظهر المكمّل الناقص لأحد الأزواج نصف المفتوحة. إذن هناك أيضًا \(k+1\) نواتج رابحة مباشرة.
أما الأزواج الباقية وعددها \(m-k\) فما زالت مغلقة. أي عدد من أعدادها البالغ عددها \(2(m-k)\) يفتح زوجًا جديدًا وينقل العملية إلى \(E_1[k+1]\).
ومن تحليل الخطوة الأولى نحصل على
$$E_1[k]=1+\frac{k+1}{N}E_1[k]+\frac{2(m-k)}{N}E_1[k+1].$$
وبنقل حد البقاء في الحالة نفسها إلى الطرف الأيسر نحصل على الصيغة المستخدمة في الكود:
$$\boxed{E_1[k]=\frac{N+2(m-k)E_1[k+1]}{N-(k+1)}}.$$
المقام \(N-(k+1)\) هو نفسه المتغير den في الشيفرة. وهو يظهر لأننا نطرح احتمال البقاء في الحالة نفسها من الطرف الأيسر.
إذا كانت \(s\) لم تظهر بعد، فإن عدد النواتج التي تبقي الحالة دون تغيير يبقى مساويًا لـ \(k+1\): وهي \(0\) والأطراف التي سبق ظهورها في الأزواج نصف المفتوحة.
ظهور المكمّل الناقص لأحد هذه الأزواج يحقق الفوز فورًا. أما ظهور \(s\) فلا يكفي للفوز بعد، بل ينقلنا من \(E_0[k]\) إلى \(E_1[k]\). وأي عدد من زوج مغلق ينقلنا إلى \(E_0[k+1]\).
إذًا
$$E_0[k]=1+\frac{k+1}{N}E_0[k]+\frac{1}{N}E_1[k]+\frac{2(m-k)}{N}E_0[k+1],$$
ومنها
$$\boxed{E_0[k]=\frac{N+2(m-k)E_0[k+1]+E_1[k]}{N-(k+1)}}.$$
عندما \(k=m\) تكون كل الأزواج العادية قد أصبحت نصف مفتوحة، وبالتالي لا يوجد انتقال إلى \(k+1\). عندها نحصل على
$$E_1[m]=\frac{N}{N-(m+1)}=\frac{2m+2}{m+1}=2,$$
$$E_0[m]=\frac{N+E_1[m]}{N-(m+1)}=\frac{2m+4}{m+1}.$$
بعد ذلك نحسب القيم عكسيًا من \(k=m-1\) حتى \(0\). والكمية المطلوبة هي
$$\boxed{E_0[0]}. $$
هذه هي الحالة الصغيرة المستخدمة صراحةً في ملف C++. هنا \(N=4\)، ولدينا زوج عادي واحد هو \(\{1,3\}\)، والقيمة الخاصة \(2\)، والقيمة الخاملة \(0\). يعطي الحل العكسي
$$E_1[1]=2,\qquad E_0[1]=3,$$
$$E_1[0]=\frac{4+2E_1[1]}{3}=\frac{8}{3},$$
$$E_0[0]=\frac{4+2E_0[1]+E_1[0]}{3}=\frac{38}{9}.$$
وهذا يطابق تمامًا قيمة الفحص الموجودة في Euler371.cpp. أما في الإدخال الحقيقي \(M=999\)، أي \(m=499\)، فإن التكرار نفسه يعطي
$$E_0[0]\approx 40.66368097.$$
الملفات الثلاثة تنفذ البرمجة الديناميكية المضغوطة نفسها. أولًا يُحسب pairCount = (maxNumber - 1) / 2، ثم totalNumbers = 2 * pairCount + 2، ثم تُنشأ المصفوفتان e0 وe1، وبعد ذلك تسير الحلقة على \(k\) من pairCount نزولًا حتى \(0\).
والكميتان المساعدتان هما
$$\texttt{grow}=2(\texttt{pairCount}-k),\qquad \texttt{den}=\texttt{totalNumbers}-(k+1).$$
تمثل grow عدد القيم التي ما زالت تنتمي إلى أزواج غير مفتوحة، ولذلك فهي تزيد \(k\) بمقدار واحد. بعد ذلك يطبق الكود المعادلتين المؤطرتين مباشرةً، وفي النهاية يطبع e0[0].
ملف C++ يحتوي أيضًا على محقق صريح للحالات الصغيرة. في ذلك التحقق يكون لكل زوج ثلاثة ميكرو-حالات: لم يظهر شيء، ظهر الطرف الأيسر، ظهر الطرف الأيمن. ومع بت يحدد هل ظهرت \(s\) من قبل، يصبح عدد الحالات الكلي \(2\cdot 3^m\). يبني البرنامج نظام المعادلات الخطي لهذه التوقعات الماركوفيّة الدقيقة، ثم يحله بحذف غاوسي، ويؤكد بذلك أن الصيغة المضغوطة صحيحة عند \(m=2\) و\(m=3\).
إذا كان \(m=(M-1)/2\)، فإن التكرار المضغوط يحسب كل قيمة من قيم \(k\) مرة واحدة فقط، ولذلك يكون الزمن \(O(m)\). وبما أن التنفيذ الحالي يخزّن مصفوفتين بطول \(m+1\)، فإن الذاكرة المطلوبة هي \(O(m)\). أما المحقق ذو الحالات الصريحة فتعقيده أُسّي في \(m\)، ولهذا يُستخدم فقط في حالات تحقق صغيرة جدًا.