We begin with two flocks, one white and one black, each containing \(n\) sheep. Every sheep is equally likely to bleat next. If a white sheep bleats, one black sheep crosses over and becomes white, so \((w,b)\mapsto (w+1,b-1)\). If a black sheep bleats, one white sheep crosses over and becomes black, so \((w,b)\mapsto (w-1,b+1)\). After this colour change, Peredur may remove any number of white sheep. The goal is to maximize the expected final number of black sheep, denoted \(E(n)\), starting from the balanced position \((n,n)\).
The published solver computes this expectation to fixed decimal precision but, as elsewhere on the site, intentionally does not reveal the final Project Euler value.
Let \(V(w,b)\) be the optimal expected final number of black sheep when the current state contains \(w\) white and \(b\) black sheep and Peredur is allowed to prune white sheep immediately.
If no white sheep remain, the process is over and all remaining sheep are black, so
$$V(0,b)=b.$$
If no black sheep remain, the terminal payoff is zero:
$$V(w,0)=0.$$
These boundary values anchor the entire dynamic program.
Suppose Peredur keeps exactly \(k\) white sheep, with \(1\le k\le w\). The next bleat is white with probability \(\frac{k}{k+b}\), leading to \((k+1,b-1)\), and black with probability \(\frac{b}{k+b}\), leading to \((k-1,b+1)\). Hence the one-step continuation value is
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
If he removes all white sheep (\(k=0\)), the game stops immediately and the payoff is simply \(b\). Therefore the Bellman optimization is
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
This is a stochastic control problem: the decision is how many white sheep to keep, and the randomness comes from the next bleat.
The fast solver relies on the policy
$$k^*(w,b)=\min(w,b-1),$$
which is independently checked by the exact solver on all small states used in the C++ checkpoints. In words, once white sheep are at least as numerous as black sheep, it is never beneficial to keep them above \(b-1\).
The intuition is straightforward: only black sheep contribute to the final payoff, while extra white sheep increase the chance of a white bleat, and a white bleat converts one black sheep into a white sheep. So excess white sheep are pure risk and can be removed without sacrificing upside.
Between bleats no sheep are created; colours only swap. This makes the total
$$s=w+b$$
a natural layer index. Define
$$U_s(w)=V(w,s-w).$$
If \(w\le b-1\), equivalently \(1\le w\le t\) with
$$t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
then no immediate pruning occurs, and the Bellman equation reduces to the continuation recurrence
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
If \(w\ge b\), the optimal policy removes white sheep until the state leaves that region. One immediate pruning step gives
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$$
Applying this relation repeatedly is exactly the same as capping white sheep to \(b-1\).
For a fixed layer \(s\), the unknown continuation values are \(U_s(1),U_s(2),\dots,U_s(t)\). Rearranging the recurrence gives
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
The left boundary is known exactly:
$$U_s(0)=V(0,s)=s.$$
The right boundary is inherited from the pruning region:
$$U_s(t+1)=U_{s-1}(t).$$
So each layer becomes a tridiagonal linear system, which the code solves in \(O(s)\) time by forward elimination and back substitution.
The initial position is \((n,n)\), but Peredur may prune only after the first bleat and crossover. By symmetry, the first bleat is white or black with probability \(\frac12\). Thus
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
This is why the implementation computes the full layer \(s=2n\) and then averages the two neighboring states around the diagonal start.
With one white and one black sheep, the first bleat already determines the outcome. If the white sheep bleats, the state becomes \((2,0)\), so the final number of black sheep is \(0\). If the black sheep bleats, the state becomes \((0,2)\), so the final number of black sheep is \(2\). Therefore
$$E(1)=\frac{0+2}{2}=1.$$
The code also checks the published benchmark \(E(5)=6.871346\) (rounded to six decimals) as a checkpoint for the fast recurrence.
The arrays prev and cur store the values of \(U_{s-1}\) and \(U_s\). For each layer \(s\), the cap region \(w\ge t+1\) is filled immediately by cur[w] = prev[w-1], implementing the pruning rule.
The continuation region \(1\le w\le t\) is then solved as a tridiagonal system using temporary arrays for the diagonal, superdiagonal, and right-hand side coefficients. After the final layer \(s=2n\) is built, the answer is returned as
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}.$$
In the C++ version, an exact small-state solver is additionally used to verify the cap policy and to compare the fast method against exact values on sample inputs.
Layer \(s\) contains \(O(s)\) relevant states and is solved in \(O(s)\) time. Summing over \(s=1,2,\dots,2n\) gives
$$O(1+2+\cdots+2n)=O(n^2).$$
Only the current layer, the previous layer, and a few temporary tridiagonal arrays are stored, so the memory usage is \(O(n)\).
Zu Beginn gibt es zwei Herden, eine weiße und eine schwarze, mit jeweils \(n\) Schafen. Jedes einzelne Schaf ist mit gleicher Wahrscheinlichkeit das nächste, das blökt. Blökt ein weißes Schaf, so wechselt ein schwarzes Schaf die Seite und wird weiß; damit gilt \((w,b)\mapsto (w+1,b-1)\). Blökt ein schwarzes Schaf, so wechselt ein weißes Schaf die Seite und wird schwarz; damit gilt \((w,b)\mapsto (w-1,b+1)\). Nach diesem Farbwechsel darf Peredur beliebig viele weiße Schafe entfernen. Gesucht ist die maximale erwartete Endzahl schwarzer Schafe, bezeichnet mit \(E(n)\), ausgehend vom symmetrischen Startzustand \((n,n)\).
Der veröffentlichte Solver berechnet diesen Erwartungswert auf feste Dezimalgenauigkeit, verrät aber wie auf den übrigen Seiten den finalen Project-Euler-Wert nicht.
Sei \(V(w,b)\) die optimale erwartete Endzahl schwarzer Schafe, wenn der aktuelle Zustand \(w\) weiße und \(b\) schwarze Schafe enthält und Peredur sofort weiße Schafe wegnehmen darf.
Wenn keine weißen Schafe mehr vorhanden sind, ist der Prozess beendet und alle verbleibenden Schafe sind schwarz. Also
$$V(0,b)=b.$$
Wenn keine schwarzen Schafe mehr vorhanden sind, ist der Endwert null:
$$V(w,0)=0.$$
Diese beiden Randwerte tragen die gesamte dynamische Programmierung.
Angenommen, Peredur behält genau \(k\) weiße Schafe, mit \(1\le k\le w\). Dann blökt als Nächstes mit Wahrscheinlichkeit \(\frac{k}{k+b}\) ein weißes Schaf, was zu \((k+1,b-1)\) führt, und mit Wahrscheinlichkeit \(\frac{b}{k+b}\) ein schwarzes Schaf, was zu \((k-1,b+1)\) führt. Der Erwartungswert eines Fortsetzungsschritts ist daher
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
Entfernt er alle weißen Schafe (\(k=0\)), endet das Spiel sofort mit Auszahlung \(b\). Damit lautet die Bellman-Optimierung
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
Das ist ein stochastisches Kontrollproblem: Die Entscheidung ist, wie viele weiße Schafe man behält, und die Zufälligkeit kommt vom nächsten Blöken.
Der schnelle Solver basiert auf der Regel
$$k^*(w,b)=\min(w,b-1),$$
die durch den exakten Solver auf allen kleinen Zuständen der C++-Checkpoints unabhängig überprüft wird. Mit anderen Worten: Sobald es mindestens so viele weiße wie schwarze Schafe gibt, lohnt es sich nie, mehr als \(b-1\) weiße Schafe stehen zu lassen.
Die Intuition ist klar: Nur schwarze Schafe tragen zum Endwert bei. Zusätzliche weiße Schafe erhöhen aber die Wahrscheinlichkeit eines weißen Blökens, und genau dann wird ein schwarzes Schaf weiß. Überschüssige weiße Schafe sind also reines Risiko und können ohne Verlust an Nutzen entfernt werden.
Zwischen zwei Blökvorgängen entstehen keine neuen Schafe; nur die Farbe wechselt. Deshalb ist die Gesamtzahl
$$s=w+b$$
ein natürlicher Schichtindex. Definiere
$$U_s(w)=V(w,s-w).$$
Falls \(w\le b-1\), äquivalent \(1\le w\le t\) mit
$$t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
ist kein sofortiges Beschneiden nötig, und die Bellman-Gleichung reduziert sich auf die Fortsetzungsrekursion
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
Falls \(w\ge b\), entfernt die optimale Regel weiße Schafe so lange, bis der Zustand diese Region verlässt. Ein einzelner Beschneidungsschritt ergibt
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$$
Wendet man diese Relation wiederholt an, ist das genau dasselbe wie das Kappen auf \(b-1\) weiße Schafe.
Für eine feste Schicht \(s\) sind die unbekannten Fortsetzungswerte \(U_s(1),U_s(2),\dots,U_s(t)\). Umgestellt ergibt die Rekursion
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
Die linke Randbedingung ist exakt bekannt:
$$U_s(0)=V(0,s)=s.$$
Die rechte Randbedingung kommt aus der Beschneidungsregion:
$$U_s(t+1)=U_{s-1}(t).$$
Damit wird jede Schicht zu einem tridiagonalen LGS, das der Code in \(O(s)\) mit Vorwärtselfimination und Rückwärtseinsetzen löst.
Der Anfangszustand ist \((n,n)\), aber Peredur darf erst nach dem ersten Blöken und Seitenwechsel eingreifen. Wegen der Symmetrie ist das erste blökende Schaf mit Wahrscheinlichkeit \(\frac12\) weiß oder schwarz. Also gilt
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
Deshalb berechnet die Implementierung die ganze Schicht \(s=2n\) und mittelt anschließend die beiden Nachbarzustände um den diagonalen Start.
Bei einem weißen und einem schwarzen Schaf entscheidet schon das erste Blöken über das Ergebnis. Blökt das weiße Schaf, entsteht \((2,0)\), also ist die Endzahl schwarzer Schafe \(0\). Blökt das schwarze Schaf, entsteht \((0,2)\), also ist die Endzahl schwarzer Schafe \(2\). Somit
$$E(1)=\frac{0+2}{2}=1.$$
Zusätzlich prüft der Code den veröffentlichten Benchmark \(E(5)=6.871346\) (auf sechs Nachkommastellen gerundet) als Kontrollwert für die schnelle Rekursion.
Die Arrays prev und cur speichern die Werte von \(U_{s-1}\) beziehungsweise \(U_s\). Für jede Schicht \(s\) wird die Beschneidungsregion \(w\ge t+1\) sofort über cur[w] = prev[w-1] gefüllt; genau das implementiert die Kappungsregel.
Die Fortsetzungsregion \(1\le w\le t\) wird anschließend als tridiagonales System mit temporären Arrays für Diagonale, Nebendiagonale und rechte Seite gelöst. Nachdem die Endschicht \(s=2n\) aufgebaut ist, liefert
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}$$
die gesuchte Antwort. In der C++-Version wird außerdem ein exakter Solver für kleine Zustände verwendet, um die Kappungspolitik zu verifizieren und die schnelle Methode mit exakten Werten zu vergleichen.
Die Schicht \(s\) enthält \(O(s)\) relevante Zustände und wird in \(O(s)\) Zeit gelöst. Über \(s=1,2,\dots,2n\) summiert ergibt das
$$O(1+2+\cdots+2n)=O(n^2).$$
Gespeichert werden nur die aktuelle Schicht, die vorherige Schicht und einige temporäre Arrays für das tridiagonale System. Der Speicherbedarf ist also \(O(n)\).
Başlangıçta biri beyaz, biri siyah olmak üzere iki sürü vardır ve her birinde \(n\) koyun bulunur. Sıradaki melemenin hangi koyundan geleceği tüm koyunlar arasında eşit olasılıkla seçilir. Beyaz bir koyun melediğinde bir siyah koyun karşı tarafa geçip beyaza dönüşür; yani \((w,b)\mapsto (w+1,b-1)\). Siyah bir koyun melediğinde bir beyaz koyun karşıya geçip siyaha dönüşür; yani \((w,b)\mapsto (w-1,b+1)\). Bu renk değişiminden sonra Peredur istediği kadar beyaz koyunu oyundan çıkarabilir. Amaç, dengeli başlangıç durumu \((n,n)\)'den yola çıkıldığında elde edilebilecek son siyah koyun sayısının beklenen değerini, yani \(E(n)\)'i, en büyüklemektir.
Yayınlanan çözücü bu beklentiyi sabit ondalık hassasiyetle hesaplar; ancak sitedeki diğer sayfalarda olduğu gibi nihai Project Euler değeri açıkça verilmez.
\(V(w,b)\), mevcut durumda \(w\) beyaz ve \(b\) siyah koyun varken ve Peredur hemen beyaz koyun azaltma hakkına sahipken elde edilebilecek en iyi son siyah koyun beklentisi olsun.
Hiç beyaz koyun kalmazsa süreç biter ve elde kalan tüm koyunlar siyahtır. Dolayısıyla
$$V(0,b)=b.$$
Hiç siyah koyun kalmazsa nihai getiri sıfırdır:
$$V(w,0)=0.$$
Bu iki sınır değeri tüm dinamik programlamanın temelini oluşturur.
Peredur'un tam olarak \(k\) beyaz koyun bıraktığını varsayalım; burada \(1\le k\le w\). Sonraki meleme \(\frac{k}{k+b}\) olasılıkla beyazdan gelir ve durum \((k+1,b-1)\)'e gider; \(\frac{b}{k+b}\) olasılıkla siyahtan gelir ve durum \((k-1,b+1)\)'e gider. Bu yüzden tek adımlık devam beklentisi
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
Eğer tüm beyaz koyunları kaldırırsa (\(k=0\)), oyun anında biter ve getiri doğrudan \(b\) olur. O halde Bellman optimizasyonu
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
Buradaki karar değişkeni tutulacak beyaz koyun sayısıdır; rastgelelik ise bir sonraki melemeden gelir.
Hızlı çözücü şu politikaya dayanır:
$$k^*(w,b)=\min(w,b-1).$$
Bu kural, C++ içindeki tam çözücü tarafından küçük durumların tamamında bağımsız olarak doğrulanır. Başka bir deyişle, beyaz koyun sayısı siyah koyun sayısına yetiştiğinde veya onu geçtiğinde, \(b-1\)'den fazla beyaz koyun bırakmak hiçbir zaman avantaj sağlamaz.
Sezgi şudur: Nihai ödüle yalnızca siyah koyunlar katkı yapar. Buna karşılık fazladan beyaz koyunlar, beyaz koyun melemesi olasılığını artırır; beyaz melemesi de bir siyah koyunu beyaza çevirir. Yani fazla beyaz koyunlar getirisi olmayan ek risktir.
Melemeler arasında yeni koyun oluşmaz; yalnızca renk dağılımı değişir. Bu yüzden toplam sayı
$$s=w+b$$
doğal bir katman indisi olur. Şöyle tanımlayalım:
$$U_s(w)=V(w,s-w).$$
Eğer \(w\le b-1\) ise, yani eşdeğer olarak
$$1\le w\le t,\qquad t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
hemen budama gerekmez ve Bellman denklemi şu devam bağıntısına iner:
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
Eğer \(w\ge b\) ise optimal politika beyaz koyunları bu bölgeden çıkana kadar azaltır. Tek bir budama adımı
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1$$
verir. Bu ilişki art arda uygulandığında, beyaz koyunları tam olarak \(b-1\)'e kadar indirmekle aynı şey olur.
Sabit bir \(s\) katmanı için bilinmeyen devam değerleri \(U_s(1),U_s(2),\dots,U_s(t)\)'dir. Bağıntıyı yeniden düzenlersek
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
Sol sınır tam olarak bilinir:
$$U_s(0)=V(0,s)=s.$$
Sağ sınır ise budama bölgesinden gelir:
$$U_s(t+1)=U_{s-1}(t).$$
Böylece her katman bir tridiagonal lineer sisteme dönüşür ve kod bunu ileri eleme ile geri yerine koyma kullanarak \(O(s)\) zamanda çözer.
Başlangıç durumu \((n,n)\)'dir; fakat Peredur ilk budamayı ancak ilk melemeden ve renk değişiminden sonra yapabilir. Simetri gereği ilk meleyen koyun \(\frac12\) olasılıkla beyaz, \(\frac12\) olasılıkla siyahtır. Bu yüzden
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
Uygulamanın \(s=2n\) katmanını tamamen hesaplayıp sonra köşegen başlangıcın iki komşusunu ortalamasının sebebi budur.
Bir beyaz ve bir siyah koyun varken sonucu ilk melemenin kendisi belirler. Beyaz koyun melediğinde durum \((2,0)\) olur; yani son siyah koyun sayısı \(0\)'dır. Siyah koyun melediğinde durum \((0,2)\) olur; yani son siyah koyun sayısı \(2\)'dir. Dolayısıyla
$$E(1)=\frac{0+2}{2}=1.$$
Kod ayrıca hızlı bağıntının doğru kurulduğunu görmek için verilen referans değeri \(E(5)=6.871346\)'yı da (6 ondalığa yuvarlanmış biçimde) kontrol eder.
prev ve cur dizileri sırasıyla \(U_{s-1}\) ve \(U_s\) katmanlarını tutar. Her \(s\) katmanında budama bölgesi \(w\ge t+1\), doğrudan cur[w] = prev[w-1] atanarak doldurulur; bu satır tam olarak budama kuralını uygular.
Daha sonra devam bölgesi \(1\le w\le t\), köşegen, üst köşegen ve sağ taraf katsayılarını tutan geçici dizilerle tridiagonal sistem olarak çözülür. Son katman \(s=2n\) tamamlandığında cevap
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}$$
şeklinde döndürülür. C++ sürümünde buna ek olarak küçük durumlar için tam bir çözücü çalıştırılır; böylece budama politikası doğrulanır ve hızlı yöntem örnek girdilerde tam değerlerle karşılaştırılır.
\(s\) katmanında \(O(s)\) ilgili durum vardır ve çözüm maliyeti \(O(s)\)'dir. \(s=1,2,\dots,2n\) için toplandığında
$$O(1+2+\cdots+2n)=O(n^2)$$
elde edilir. Bellekte yalnızca mevcut katman, önceki katman ve birkaç yardımcı tridiagonal dizi tutulduğu için toplam bellek kullanımı \(O(n)\)'dir.
Al comienzo hay dos rebaños, uno blanco y otro negro, cada uno con \(n\) ovejas. Cualquier oveja es igual de probable de balar a continuación. Si bala una oveja blanca, una oveja negra cruza y se vuelve blanca, así que \((w,b)\mapsto (w+1,b-1)\). Si bala una oveja negra, una oveja blanca cruza y se vuelve negra, así que \((w,b)\mapsto (w-1,b+1)\). Después de ese cambio de color, Peredur puede retirar cualquier cantidad de ovejas blancas. El objetivo es maximizar el número esperado final de ovejas negras, denotado \(E(n)\), partiendo del estado equilibrado \((n,n)\).
El solver publicado calcula esa esperanza con precisión decimal fija, pero, igual que en el resto del sitio, omite deliberadamente el valor final de Project Euler.
Sea \(V(w,b)\) el número esperado óptimo de ovejas negras al final cuando el estado actual tiene \(w\) ovejas blancas y \(b\) ovejas negras, y Peredur puede eliminar ovejas blancas de inmediato.
Si no queda ninguna oveja blanca, el proceso termina y todas las ovejas restantes son negras. Por tanto,
$$V(0,b)=b.$$
Si no queda ninguna oveja negra, el pago final es cero:
$$V(w,0)=0.$$
Estas condiciones de frontera sostienen toda la programación dinámica.
Supongamos que Peredur conserva exactamente \(k\) ovejas blancas, con \(1\le k\le w\). El siguiente balido es blanco con probabilidad \(\frac{k}{k+b}\), lo que lleva a \((k+1,b-1)\), y negro con probabilidad \(\frac{b}{k+b}\), lo que lleva a \((k-1,b+1)\). Por ello, el valor esperado de continuación en un paso es
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
Si elimina todas las ovejas blancas (\(k=0\)), el juego termina inmediatamente y el pago es simplemente \(b\). Por consiguiente, la optimización de Bellman es
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
Es un problema de control estocástico: la decisión es cuántas ovejas blancas dejar, y el azar proviene del siguiente balido.
El solver rápido se apoya en la política
$$k^*(w,b)=\min(w,b-1),$$
que el solver exacto comprueba de manera independiente en todos los estados pequeños usados como checkpoints en C++. En palabras: cuando las ovejas blancas ya son al menos tantas como las negras, nunca conviene dejar más de \(b-1\) blancas.
La intuición es simple: solo las ovejas negras cuentan para la recompensa final, mientras que las ovejas blancas extra aumentan la probabilidad de un balido blanco, y un balido blanco convierte una oveja negra en blanca. Por tanto, las blancas sobrantes son riesgo puro.
Entre balidos no se crean ovejas; únicamente cambia el color. Por eso la cantidad total
$$s=w+b$$
es un índice natural de capa. Definimos
$$U_s(w)=V(w,s-w).$$
Si \(w\le b-1\), equivalentemente
$$1\le w\le t,\qquad t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
no hace falta recortar de inmediato y la ecuación de Bellman se reduce a la recurrencia de continuación
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
Si \(w\ge b\), la política óptima elimina blancas hasta salir de esa región. Un solo paso de recorte da
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$$
Aplicar esta relación repetidamente equivale exactamente a capar el número de blancas en \(b-1\).
Para una capa fija \(s\), los valores desconocidos de continuación son \(U_s(1),U_s(2),\dots,U_s(t)\). Reordenando la recurrencia obtenemos
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
La frontera izquierda es conocida exactamente:
$$U_s(0)=V(0,s)=s.$$
La frontera derecha proviene de la región de recorte:
$$U_s(t+1)=U_{s-1}(t).$$
Así, cada capa se convierte en un sistema lineal tridiagonal, que el código resuelve en \(O(s)\) mediante eliminación hacia adelante y sustitución hacia atrás.
La posición inicial es \((n,n)\), pero Peredur solo puede recortar después del primer balido y del cruce. Por simetría, el primer balido es blanco o negro con probabilidad \(\frac12\). Por tanto,
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
Por eso la implementación calcula toda la capa \(s=2n\) y luego promedia los dos estados vecinos alrededor del arranque diagonal.
Con una oveja blanca y una negra, el primer balido ya decide el resultado. Si bala la blanca, el estado pasa a \((2,0)\), de modo que el número final de ovejas negras es \(0\). Si bala la negra, el estado pasa a \((0,2)\), de modo que el número final de ovejas negras es \(2\). En consecuencia,
$$E(1)=\frac{0+2}{2}=1.$$
El código también verifica el valor de referencia publicado \(E(5)=6.871346\) (redondeado a seis decimales) como checkpoint de la recurrencia rápida.
Los arreglos prev y cur almacenan los valores de \(U_{s-1}\) y \(U_s\). En cada capa \(s\), la región recortada \(w\ge t+1\) se rellena de inmediato mediante cur[w] = prev[w-1], que implementa exactamente la regla de poda.
Luego la región de continuación \(1\le w\le t\) se resuelve como un sistema tridiagonal usando arreglos temporales para la diagonal, la superdiagonal y el lado derecho. Una vez construida la capa final \(s=2n\), la respuesta devuelta es
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}.$$
En la versión en C++, además se usa un solver exacto para estados pequeños con el fin de verificar la política de recorte y comparar el método rápido con valores exactos en entradas de prueba.
La capa \(s\) contiene \(O(s)\) estados relevantes y se resuelve en \(O(s)\) tiempo. Sumando para \(s=1,2,\dots,2n\) se obtiene
$$O(1+2+\cdots+2n)=O(n^2).$$
Solo se guardan la capa actual, la capa anterior y unos pocos arreglos temporales del sistema tridiagonal, así que la memoria total es \(O(n)\).
初始时有两群羊，一群白羊、一群黑羊，每群各有 \(n\) 只。下一次叫的是哪一只羊，在所有羊之间等概率选择。若白羊叫，则有一只黑羊过河并变成白羊，因此 \((w,b)\mapsto (w+1,b-1)\)。若黑羊叫，则有一只白羊过河并变成黑羊，因此 \((w,b)\mapsto (w-1,b+1)\)。完成这次颜色变化之后，Peredur 可以移除任意数量的白羊。目标是从平衡初态 \((n,n)\) 出发，使最终黑羊数量的期望值最大，这个最优期望记为 \(E(n)\)。
页面中的程序会把这个期望计算到固定小数精度，但与站内其他页面一样，不直接公开最终的 Project Euler 数值。
设 \(V(w,b)\) 表示当前状态有 \(w\) 只白羊、\(b\) 只黑羊，并且 Peredur 此刻可以立刻删去部分白羊时，最终黑羊数量的最优期望。
如果已经没有白羊，那么过程立刻结束，剩下的全是黑羊，因此
$$V(0,b)=b.$$
如果已经没有黑羊，那么最终收益就是零：
$$V(w,0)=0.$$
这两个边界值构成了整个动态规划的基础。
假设 Peredur 保留恰好 \(k\) 只白羊，其中 \(1\le k\le w\)。下一次叫的是白羊的概率为 \(\frac{k}{k+b}\)，对应新状态 \((k+1,b-1)\)；叫的是黑羊的概率为 \(\frac{b}{k+b}\)，对应新状态 \((k-1,b+1)\)。因此一步继续后的期望值为
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
如果他把白羊全部移除（\(k=0\)），游戏会立刻结束，收益就是当前的 \(b\)。所以 Bellman 优化写成
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
这是一个随机控制问题：控制变量是保留多少白羊，随机性来自下一次叫声。
快速解法依赖如下策略：
$$k^*(w,b)=\min(w,b-1).$$
C++ 程序中的精确求解器会在所有小规模 checkpoint 状态上独立验证这条规则。它的含义是：一旦白羊数量已经不少于黑羊数量，就永远没有必要把白羊保留在 \(b-1\) 之上。
直观原因并不复杂：最终收益只和黑羊数量有关；额外的白羊只会提高“白羊叫”的概率，而白羊一叫，就会把一只黑羊转成白羊。因此，多余的白羊只增加风险，不增加收益。
在叫声之间不会产生新羊；变化的只是颜色分布。因此总数
$$s=w+b$$
是最自然的分层指标。定义
$$U_s(w)=V(w,s-w).$$
若 \(w\le b-1\)，也就是
$$1\le w\le t,\qquad t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
则当前不需要立刻删羊，Bellman 方程退化为继续区间上的递推
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
若 \(w\ge b\)，最优策略会持续删白羊直到离开该区域。一次删去一只白羊对应
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$$
重复使用这个关系，正好等价于把白羊数量截到 \(b-1\)。
对固定层 \(s\)，未知的继续值是 \(U_s(1),U_s(2),\dots,U_s(t)\)。把递推式移项可得
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
左边界可以直接写出：
$$U_s(0)=V(0,s)=s.$$
右边界来自删减区：
$$U_s(t+1)=U_{s-1}(t).$$
因此每一层都会变成一个三对角线性方程组，代码用前向消元和回代在 \(O(s)\) 时间内求解。
初始状态是 \((n,n)\)，但题目规定 Peredur 只有在第一次叫声和过河发生之后才能开始删白羊。由对称性，第一次叫的是白羊或黑羊的概率都是 \(\frac12\)。于是
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
这也解释了为什么程序要先完整算出 \(s=2n\) 这一层，然后对对角线起点两侧的状态取平均。
当只有一只白羊和一只黑羊时，第一次叫声就完全决定结果。若白羊先叫，状态变成 \((2,0)\)，最终黑羊数为 \(0\)。若黑羊先叫，状态变成 \((0,2)\)，最终黑羊数为 \(2\)。因此
$$E(1)=\frac{0+2}{2}=1.$$
代码还会检查题目给出的参考值 \(E(5)=6.871346\)（四舍五入到小数点后六位），作为快速递推的校验点。
prev 与 cur 分别存储 \(U_{s-1}\) 和 \(U_s\) 这一层的值。对每个 \(s\)，删减区 \(w\ge t+1\) 先通过 cur[w] = prev[w-1] 直接填好，这一步正是在执行最优删减规则。
随后继续区 \(1\le w\le t\) 被写成三对角系统，用若干临时数组保存主对角线、上对角线和右端项系数。最终层 \(s=2n\) 构造完成后，答案返回为
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}.$$
在 C++ 版本中，还额外有一个小规模精确求解器，用来验证截断策略，并把快速算法与若干样例上的精确值逐一比对。
第 \(s\) 层有 \(O(s)\) 个相关状态，求解这一层需要 \(O(s)\) 时间。对 \(s=1,2,\dots,2n\) 求和得到
$$O(1+2+\cdots+2n)=O(n^2).$$
程序只保留当前层、上一层以及少量三对角系统辅助数组，所以空间复杂度为 \(O(n)\)。
Изначально есть два стада, белое и чёрное, по \(n\) овец в каждом. Следующей может заблеять любая овца с одинаковой вероятностью. Если блеет белая овца, одна чёрная переходит на другую сторону и становится белой, то есть \((w,b)\mapsto (w+1,b-1)\). Если блеет чёрная овца, одна белая переходит и становится чёрной, то есть \((w,b)\mapsto (w-1,b+1)\). После этой смены цвета Передур может удалить любое количество белых овец. Требуется максимизировать ожидаемое конечное число чёрных овец, обозначаемое \(E(n)\), начиная из симметричного состояния \((n,n)\).
Опубликованный решатель вычисляет это ожидание с фиксированной десятичной точностью, но, как и на остальных страницах сайта, не раскрывает итоговый числовой ответ Project Euler.
Пусть \(V(w,b)\) обозначает оптимальное ожидаемое конечное число чёрных овец, если в текущем состоянии есть \(w\) белых и \(b\) чёрных овец и Передур может немедленно убрать часть белых.
Если белых овец не осталось, процесс завершён, и все оставшиеся овцы чёрные. Поэтому
$$V(0,b)=b.$$
Если чёрных овец не осталось, конечный выигрыш равен нулю:
$$V(w,0)=0.$$
Именно эти граничные значения задают основу всей динамики.
Предположим, что Передур оставляет ровно \(k\) белых овец, где \(1\le k\le w\). Следующей с вероятностью \(\frac{k}{k+b}\) блеет белая овца, что даёт состояние \((k+1,b-1)\), а с вероятностью \(\frac{b}{k+b}\) блеет чёрная, что даёт состояние \((k-1,b+1)\). Поэтому математическое ожидание одного шага продолжения равно
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
Если убрать всех белых овец (\(k=0\)), игра заканчивается немедленно, и выигрыш равен просто \(b\). Следовательно, оптимизация Беллмана имеет вид
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
Это стохастическая задача управления: решение состоит в выборе числа сохраняемых белых овец, а случайность приходит от следующего блеяния.
Быстрый решатель опирается на политику
$$k^*(w,b)=\min(w,b-1),$$
которая независимо проверяется точным решателем на всех малых состояниях, входящих в C++-checkpoint'ы. Иными словами, как только белых овец становится не меньше, чем чёрных, никогда не выгодно держать их больше \(b-1\).
Интуиция проста: в конечную награду входят только чёрные овцы. Лишние белые овцы лишь повышают вероятность того, что заблеет белая овца, а это превращает одну чёрную овцу в белую. Значит, избыточные белые овцы создают риск, но не добавляют выгоды.
Между блеяниями новые овцы не появляются; меняется только раскраска. Поэтому общая численность
$$s=w+b$$
естественно используется как индекс слоя. Введём обозначение
$$U_s(w)=V(w,s-w).$$
Если \(w\le b-1\), то есть эквивалентно
$$1\le w\le t,\qquad t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
немедленная обрезка не нужна, и уравнение Беллмана сводится к рекуррентному соотношению продолжения
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
Если \(w\ge b\), оптимальная политика удаляет белых овец, пока состояние не выйдет из этой области. Один шаг обрезки даёт
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$$
Многократное применение этого равенства в точности эквивалентно ограничению числа белых овец значением \(b-1\).
Для фиксированного слоя \(s\) неизвестными значениями продолжения являются \(U_s(1),U_s(2),\dots,U_s(t)\). Перенеся члены, получаем
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
Левая граница известна точно:
$$U_s(0)=V(0,s)=s.$$
Правая граница наследуется из области обрезки:
$$U_s(t+1)=U_{s-1}(t).$$
Значит, каждый слой превращается в трёхдиагональную систему линейных уравнений, которую код решает за \(O(s)\) при помощи прямого хода и обратной подстановки.
Начальное состояние равно \((n,n)\), но Передур имеет право удалять белых овец только после первого блеяния и перехода. По симметрии первое блеяние белое или чёрное с вероятностью \(\frac12\). Поэтому
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
Именно поэтому реализация вычисляет весь слой \(s=2n\), а затем усредняет два соседних состояния вокруг диагонального старта.
Если есть одна белая и одна чёрная овца, то первое блеяние уже полностью определяет исход. Если сначала блеет белая овца, получается состояние \((2,0)\), и конечное число чёрных овец равно \(0\). Если сначала блеет чёрная овца, получается \((0,2)\), и конечное число чёрных овец равно \(2\). Следовательно,
$$E(1)=\frac{0+2}{2}=1.$$
Код также проверяет опубликованный контрольный ориентир \(E(5)=6.871346\) (округление до шести знаков после запятой) как checkpoint для быстрой рекурсии.
Массивы prev и cur хранят значения \(U_{s-1}\) и \(U_s\) соответственно. Для каждого слоя \(s\) область обрезки \(w\ge t+1\) сразу заполняется присваиванием cur[w] = prev[w-1]; именно это реализует правило удаления лишних белых овец.
Затем область продолжения \(1\le w\le t\) решается как трёхдиагональная система с временными массивами для диагонали, наддиагонали и правой части. После построения финального слоя \(s=2n\) ответ возвращается в виде
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}.$$
В версии на C++ дополнительно используется точный решатель для малых состояний, чтобы проверить политику обрезки и сравнить быстрый метод с точными значениями на тестовых входах.
Слой \(s\) содержит \(O(s)\) существенных состояний и решается за \(O(s)\) времени. Суммирование по \(s=1,2,\dots,2n\) даёт
$$O(1+2+\cdots+2n)=O(n^2).$$
Хранятся только текущий слой, предыдущий слой и несколько временных массивов для трёхдиагональной системы, поэтому память составляет \(O(n)\).
في البداية توجد قطيعان، أحدهما أبيض والآخر أسود، وفي كل واحد منهما \(n\) خراف. كل خروف له الاحتمال نفسه لأن يكون هو التالي الذي يثغو. إذا ثغى خروف أبيض فإن خروفًا أسود يعبر ويصبح أبيض، أي إن الحالة تتحول من \((w,b)\) إلى \((w+1,b-1)\). وإذا ثغى خروف أسود فإن خروفًا أبيض يعبر ويصبح أسود، أي \((w,b)\mapsto (w-1,b+1)\). بعد هذا التبدل في اللون، يستطيع Peredur أن يزيل أي عدد يشاء من الخراف البيضاء. الهدف هو تعظيم العدد المتوقع النهائي للخراف السوداء، والذي نرمز له بـ \(E(n)\)، انطلاقًا من الحالة المتوازنة \((n,n)\).
البرنامج المنشور يحسب هذا التوقع بدقة عشرية ثابتة، لكنه لا يكشف القيمة النهائية الخاصة بـ Project Euler كما هو الحال في بقية صفحات الموقع.
لتكن \(V(w,b)\) القيمة المثلى المتوقعة لعدد الخراف السوداء في النهاية عندما تحتوي الحالة الحالية على \(w\) خراف بيضاء و\(b\) خراف سوداء، ويكون مسموحًا لـ Peredur أن يقلص عدد البيضاء فورًا.
إذا لم تبق أي خراف بيضاء، تنتهي العملية فورًا وتكون كل الخراف المتبقية سوداء، ولذلك
$$V(0,b)=b.$$
أما إذا لم تبق أي خراف سوداء، فالعائد النهائي يساوي صفرًا:
$$V(w,0)=0.$$
هاتان القيمتان الحدّيتان هما الأساس الذي تُبنى عليه البرمجة الديناميكية كلها.
افترض أن Peredur أبقى بالضبط \(k\) خراف بيضاء، حيث \(1\le k\le w\). تكون الثغوة التالية بيضاء باحتمال \(\frac{k}{k+b}\)، فنصل إلى الحالة \((k+1,b-1)\)، وتكون سوداء باحتمال \(\frac{b}{k+b}\)، فنصل إلى \((k-1,b+1)\). لذلك فإن قيمة الاستمرار لخطوة واحدة هي
$$C(k,b)=\frac{k}{k+b}V(k+1,b-1)+\frac{b}{k+b}V(k-1,b+1).$$
وإذا أزال جميع الخراف البيضاء (\(k=0\)) فإن اللعبة تنتهي مباشرة ويكون العائد ببساطة هو \(b\). ومن ثم تصبح صيغة بيلمان
$$V(w,b)=\max\!\left(b,\ \max_{1\le k\le w} C(k,b)\right).$$
هذه إذن مسألة تحكم احتمالي: القرار هو عدد الخراف البيضاء التي سنحتفظ بها، والعشوائية تأتي من الثغوة التالية.
الحل السريع يعتمد على السياسة التالية:
$$k^*(w,b)=\min(w,b-1).$$
ويجري التحقق من هذه القاعدة بشكل مستقل بواسطة محلل دقيق على جميع الحالات الصغيرة المستخدمة كنقاط فحص في نسخة C++. ومعناها أنه ما إن يصبح عدد الخراف البيضاء مساويًا لعدد السوداء أو أكبر منه، فلا توجد أي فائدة في إبقاء البيضاء فوق \(b-1\).
الحدس هنا مباشر: العائد النهائي يعتمد فقط على الخراف السوداء، بينما زيادة البيضاء ترفع احتمال أن تكون الثغوة التالية من خروف أبيض، وعندها تتحول إحدى الخراف السوداء إلى بيضاء. لذا فالبيضاء الزائدة تمثل خطرًا صرفًا من دون مكسب مقابل.
بين الثغوات لا تُخلق خراف جديدة؛ الذي يتغير فقط هو اللون. لذلك يكون المجموع
$$s=w+b$$
فهرسًا طبيعيًا للطبقات. نعرّف
$$U_s(w)=V(w,s-w).$$
إذا كان \(w\le b-1\)، أو بصورة مكافئة
$$1\le w\le t,\qquad t=\left\lfloor\frac{s-1}{2}\right\rfloor,$$
فلا حاجة إلى تقليص فوري، وتتحول معادلة بيلمان إلى علاقة استمرار:
$$U_s(w)=\frac{w}{s}U_s(w+1)+\frac{s-w}{s}U_s(w-1).$$
أما إذا كان \(w\ge b\)، فإن السياسة المثلى تزيل البيضاء حتى تخرج الحالة من هذه المنطقة. خطوة تقليص واحدة تعطي
$$U_s(w)=U_{s-1}(w-1),\qquad w\ge t+1.$$
وتكرار هذه العلاقة يعادل تمامًا وضع حد أعلى لعدد الخراف البيضاء عند \(b-1\).
عند تثبيت الطبقة \(s\)، تكون القيم المجهولة في منطقة الاستمرار هي \(U_s(1),U_s(2),\dots,U_s(t)\). وبإعادة ترتيب العلاقة نحصل على
$$-\frac{s-w}{s}U_s(w-1)+U_s(w)-\frac{w}{s}U_s(w+1)=0,\qquad 1\le w\le t.$$
الحد الأيسر معلوم تمامًا:
$$U_s(0)=V(0,s)=s.$$
أما الحد الأيمن فيأتي من منطقة التقليص:
$$U_s(t+1)=U_{s-1}(t).$$
وبذلك تتحول كل طبقة إلى نظام خطي ثلاثي القطريات، ويحلّه الكود في \(O(s)\) باستخدام الحذف الأمامي ثم التعويض الخلفي.
الحالة الابتدائية هي \((n,n)\)، لكن Peredur لا يستطيع حذف البيضاء إلا بعد أول ثغوة وأول انتقال. وبسبب التناظر، تكون الثغوة الأولى بيضاء أو سوداء باحتمال \(\frac12\) لكل منهما. لذلك
$$E(n)=\frac{V(n+1,n-1)+V(n-1,n+1)}{2}=\frac{U_{2n}(n+1)+U_{2n}(n-1)}{2}.$$
ولهذا السبب يحسب التنفيذ الطبقة الكاملة \(s=2n\) ثم يأخذ متوسط الحالتين المجاورتين حول نقطة البداية القطرية.
عندما يكون لدينا خروف أبيض واحد وخروف أسود واحد، فإن الثغوة الأولى وحدها تحسم النتيجة. إذا ثغى الخروف الأبيض أولًا أصبحت الحالة \((2,0)\)، ومن ثم يكون العدد النهائي للخراف السوداء هو \(0\). وإذا ثغى الخروف الأسود أولًا أصبحت الحالة \((0,2)\)، ومن ثم يكون العدد النهائي للخراف السوداء هو \(2\). وعليه
$$E(1)=\frac{0+2}{2}=1.$$
ويتحقق الكود أيضًا من القيمة المرجعية المنشورة \(E(5)=6.871346\) بعد التقريب إلى ستة منازل عشرية، بوصفها نقطة فحص للعلاقة السريعة.
المصفوفتان prev وcur تخزنان قيم \(U_{s-1}\) و\(U_s\) على الترتيب. في كل طبقة \(s\)، تُملأ منطقة التقليص \(w\ge t+1\) مباشرة عبر السطر cur[w] = prev[w-1]، وهذا يطبق قاعدة الحذف المثلى حرفيًا.
بعد ذلك تُحل منطقة الاستمرار \(1\le w\le t\) على أنها نظام ثلاثي القطريات باستخدام مصفوفات مؤقتة لمعاملات القطر الرئيسي والقطر العلوي والطرف الأيمن. وبعد بناء الطبقة الأخيرة \(s=2n\)، تكون الإجابة
$$\frac{\texttt{prev}[n-1]+\texttt{prev}[n+1]}{2}.$$
وفي نسخة C++ يوجد أيضًا محلل دقيق للحالات الصغيرة من أجل التحقق من سياسة التقليص ومقارنة الطريقة السريعة بقيم دقيقة على بعض المدخلات النموذجية.
الطبقة \(s\) تحتوي على \(O(s)\) من الحالات المهمة، وحلها يحتاج \(O(s)\) زمنًا. وعند الجمع على \(s=1,2,\dots,2n\) نحصل على
$$O(1+2+\cdots+2n)=O(n^2).$$
ولا يُخزَّن في الذاكرة إلا الطبقة الحالية والطبقة السابقة وعدد قليل من المصفوفات المؤقتة الخاصة بالنظام الثلاثي، لذلك يكون استهلاك الذاكرة \(O(n)\).