We want to simulate a fair \(n\)-sided outcome by rolling only fair 5-sided and 6-sided dice. After each roll we may choose again which source die to use, so the strategy is adaptive rather than fixed in advance.
For each target size \(n\), let \(R(n)\) be the minimum expected number of source-die rolls needed to finish the simulation. The quantity required by the problem is
$$S(N)=\sum_{n=2}^{N} R(n),$$
and the implementation evaluates this sum at \(N=1000\).
The key observation is that the full roll history is unnecessary. After every partial sequence, all that matters is how many equally likely unresolved branches remain.
Suppose we are trying to simulate one of \(n\) equally likely outcomes. After some rolls, part of the sample space may already be assignable to the final outcomes, while a leftover part is still unresolved. If that leftover contains \(r\) equally likely branches, then the future depends only on \(r\), not on the exact path that produced it.
Thus the process can be modeled by states
$$r\in\{0,1,\dots,n-1\}.$$
State \(r=0\) means the simulation has already finished. The initial state is \(r=1\), because before any roll there is exactly one unresolved branch.
From a live state \(r\), choose a die with \(m\) faces, where \(m\in\{5,6\}\). Each unresolved branch splits into \(m\) equally likely subbranches, so the unresolved pool temporarily contains \(mr\) equiprobable cases.
Now divide \(mr\) by \(n\):
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
The first \(qn\) cases can be partitioned into \(q\) complete sets of size \(n\), and each complete set can be assigned evenly to the \(n\) target outcomes. Only the leftover \(r'\) cases remain unresolved.
Therefore, after choosing die \(m\), the process continues with probability
$$\Pr(\text{continue}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
and, conditional on continuation, the next state is exactly \(r'\).
Let \(V_n(r)\) be the minimum expected number of additional rolls needed from state \(r\). Then the absorbing state satisfies
$$V_n(0)=0.$$
For every live state \(1\le r\le n-1\), one roll is spent immediately, and then we continue only if the leftover remainder is nonzero. Hence
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
This is the Bellman optimality equation for the finite decision process. The quantity asked for one target size is
$$R(n)=V_n(1).$$
Two partial roll histories with the same leftover count \(r\) are strategically identical. In both cases there are \(r\) unresolved branches, all equally likely, and the next choice only depends on how a new 5-way or 6-way split interacts with the target size \(n\).
This symmetry collapses a potentially huge decision tree into only \(n\) states and two available actions per live state. After computing \(R(n)\) for each target size, the outer problem is simply
$$S(N)=\sum_{n=2}^{N} R(n).$$
The checkpoint \(R(8)\) can be derived directly from the recurrence. Start with some useful intermediate states.
From \(r=4\), choosing the 6-sided die gives
$$6\cdot 4=24=3\cdot 8+0,$$
so the process certainly ends after one more roll. Therefore
$$V_8(4)=1.$$
From \(r=6\), choosing the 6-sided die gives remainder \(4\), so
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
At \(r=5\), the 5-sided die gives remainder \(1\), hence
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
The 6-sided die would instead give
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$$
From the initial state \(r=1\), choosing the 5-sided die sends us to \(r=5\) with certainty, so
$$V_8(1)=1+V_8(5).$$
Combining the two 5-die equations gives
$$V_8(1)=2+\frac{1}{25}V_8(1),$$
which solves to
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
Substituting back shows \(V_8(5)=13/12\), which is indeed smaller than \(11/9\), so the chosen actions are self-consistent. This matches the checkpoint used by the C++, Python, and Java implementations.
The C++, Python, and Java implementations all follow the same numerical plan. For a fixed \(n\), they first precompute, for every live state \(r\), the two possible next remainders and the two continuation factors corresponding to choosing the 5-sided or 6-sided die.
They then keep two value arrays and repeatedly apply the Bellman update
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right),$$
where \(r_5,r_6\) are the next remainders and \(\rho_5(r),\rho_6(r)\) are the corresponding continuation probabilities. Iteration stops when the largest absolute change across all states falls below \(10^{-18}\), or when the fixed safety cap of 2000 sweeps is reached.
The value at the initial state \(r=1\) is recorded as \(R(n)\). An outer loop evaluates every \(n\) from \(2\) through \(1000\) and accumulates their sum.
For one target size \(n\), building the transition data costs \(O(n)\) time and \(O(n)\) memory. Each relaxation sweep also costs \(O(n)\), because each live state compares exactly two actions.
If \(I_n\) sweeps are needed before the stopping rule is met, then computing \(R(n)\) costs \(O(nI_n)\) time and \(O(n)\) memory. Therefore the full sum up to \(N\) costs
$$\sum_{n=2}^{N} O(nI_n).$$
Because the implementation also imposes a fixed cap of 2000 sweeps, the worst-case growth is quadratic in \(N\) up to that constant factor. In practice the numerical updates stabilize much earlier.
Wir wollen ein faires \(n\)-seitiges Ergebnis simulieren, obwohl nur faire 5-seitige und 6-seitige Würfel zur Verfügung stehen. Nach jedem Wurf darf erneut entschieden werden, welchen Ausgangswürfel man als Nächstes benutzt, also ist die Strategie adaptiv.
Für jede Zielgröße \(n\) sei \(R(n)\) die minimale erwartete Anzahl von Würfen mit den Ausgangswürfeln. Gesucht ist
$$S(N)=\sum_{n=2}^{N} R(n),$$
und die Implementierung berechnet diese Summe für \(N=1000\).
Der entscheidende Punkt ist, dass die vollständige Wurfhistorie nicht gebraucht wird. Nach jeder Teilsequenz zählt nur noch, wie viele gleichwahrscheinliche, noch nicht entschiedene Zweige übrig sind.
Angenommen, wir wollen eines von \(n\) gleichwahrscheinlichen Ergebnissen erzeugen. Nach einigen Würfen kann ein Teil des Ergebnisraums bereits den Zielausgängen zugeordnet werden; nur ein Rest bleibt offen. Hat dieser Rest \(r\) gleichwahrscheinliche Zweige, dann hängt die Zukunft nur von \(r\) ab und nicht mehr vom genauen Entstehungsweg.
Damit lässt sich der Prozess durch Zustände
$$r\in\{0,1,\dots,n-1\}$$
beschreiben. \(r=0\) bedeutet, dass die Simulation bereits abgeschlossen ist. Der Anfangszustand ist \(r=1\), weil vor dem ersten Wurf genau ein unaufgelöster Zweig existiert.
Aus einem aktiven Zustand \(r\) wählen wir einen Würfel mit \(m\) Seiten, wobei \(m\in\{5,6\}\). Jeder unaufgelöste Zweig spaltet sich dann in \(m\) gleichwahrscheinliche Unterzweige, also entstehen vorübergehend \(mr\) Fälle.
Nun teilen wir \(mr\) durch \(n\):
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
Die ersten \(qn\) Fälle lassen sich in \(q\) vollständige Mengen der Größe \(n\) zerlegen, und jede dieser Mengen kann gleichmäßig auf die \(n\) Zielausgänge abgebildet werden. Nur die restlichen \(r'\) Fälle bleiben unentschieden.
Deshalb ist die Fortsetzungswahrscheinlichkeit nach Wahl des \(m\)-seitigen Würfels
$$\Pr(\text{Fortsetzung}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
und bedingt auf Fortsetzung ist der nächste Zustand genau \(r'\).
Sei \(V_n(r)\) die minimale erwartete zusätzliche Wurfzahl aus Zustand \(r\). Für den absorbierenden Zustand gilt
$$V_n(0)=0.$$
Für jeden aktiven Zustand \(1\le r\le n-1\) wird zunächst sicher ein Wurf verbraucht; nur falls der Rest nicht verschwindet, geht der Prozess weiter. Daher
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
Das ist die Bellman-Optimalitätsgleichung dieses endlichen Entscheidungsprozesses. Gesucht für eine feste Zielgröße ist
$$R(n)=V_n(1).$$
Zwei partielle Wurfgeschichten mit demselben Restwert \(r\) sind strategisch äquivalent. In beiden Fällen gibt es \(r\) unaufgelöste Zweige mit identischer Wahrscheinlichkeit, und die nächste Entscheidung hängt nur davon ab, wie eine neue 5er- oder 6er-Aufspaltung mit der Zielgröße \(n\) zusammenspielt.
Diese Symmetrie reduziert einen potenziell riesigen Entscheidungsbaum auf nur \(n\) Zustände und zwei mögliche Aktionen pro aktivem Zustand. Sobald \(R(n)\) für jedes \(n\) bestimmt ist, bleibt außen nur
$$S(N)=\sum_{n=2}^{N} R(n).$$
Der Kontrollwert \(R(8)\) lässt sich direkt aus der Rekursion herleiten. Wir beginnen mit einigen Zwischenzuständen.
Aus \(r=4\) liefert die Wahl des 6-seitigen Würfels
$$6\cdot 4=24=3\cdot 8+0,$$
also endet der Prozess sicher nach genau einem weiteren Wurf. Damit ist
$$V_8(4)=1.$$
Aus \(r=6\) führt der 6-seitige Würfel auf Rest \(4\), also
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
Für \(r=5\) erzeugt der 5-seitige Würfel den Rest \(1\), also
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
Der 6-seitige Würfel ergäbe stattdessen
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$$
Vom Anfangszustand \(r=1\) aus führt die Wahl des 5-seitigen Würfels sicher zu \(r=5\), also
$$V_8(1)=1+V_8(5).$$
Die beiden 5er-Gleichungen zusammen ergeben
$$V_8(1)=2+\frac{1}{25}V_8(1),$$
und daraus folgt
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
Rückeinsetzen liefert \(V_8(5)=13/12\), was tatsächlich kleiner ist als \(11/9\). Die gewählten Aktionen sind also konsistent optimal. Genau dieser Wert erscheint auch als Kontrollpunkt in den C++-, Python- und Java-Implementierungen.
Die C++-, Python- und Java-Implementierungen verwenden denselben numerischen Plan. Für ein festes \(n\) werden zunächst für jeden aktiven Zustand \(r\) die beiden möglichen Folgereste und die beiden zugehörigen Fortsetzungsfaktoren für die Wahl des 5-seitigen bzw. 6-seitigen Würfels vorab berechnet.
Anschließend halten die Programme zwei Wertefelder und wenden wiederholt das Bellman-Update an:
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right).$$
Die Iteration endet, sobald sich der größte absolute Unterschied über alle Zustände auf weniger als \(10^{-18}\) reduziert, oder sobald die feste Sicherheitsgrenze von 2000 Durchläufen erreicht ist.
Der Wert im Anfangszustand \(r=1\) ist dann \(R(n)\). Eine äußere Schleife berechnet dies für alle \(n\) von \(2\) bis \(1000\) und summiert die Ergebnisse.
Für eine einzelne Zielgröße \(n\) kostet der Aufbau der Übergangsdaten \(O(n)\) Zeit und \(O(n)\) Speicher. Ein Relaxationsdurchlauf kostet ebenfalls \(O(n)\), weil jeder aktive Zustand genau zwei Aktionen vergleicht.
Werden bis zum Abbruchkriterium \(I_n\) Durchläufe benötigt, dann kostet die Berechnung von \(R(n)\) also \(O(nI_n)\) Zeit bei \(O(n)\) Speicher. Für die Gesamtsumme bis \(N\) ergibt sich
$$\sum_{n=2}^{N} O(nI_n).$$
Da die Implementierung zusätzlich eine feste Obergrenze von 2000 Durchläufen setzt, wächst die Laufzeit im schlechtesten Fall quadratisch in \(N\), bis auf diesen konstanten Faktor. In der Praxis stabilisieren sich die numerischen Updates deutlich früher.
Amacımız, yalnızca adil 5 yüzlü ve 6 yüzlü zarlar kullanarak adil bir \(n\)-sonuçlu dağılım üretmektir. Her atıştan sonra hangi kaynağı kullanacağımıza yeniden karar verebildiğimiz için strateji sabit değil, uyarlanabilirdir.
Her hedef boyut \(n\) için \(R(n)\), simülasyonu tamamlamak için gereken en küçük beklenen kaynak-zar atışı sayısını göstersin. Problemde istenen toplam
$$S(N)=\sum_{n=2}^{N} R(n),$$
olup uygulama bu toplamı \(N=1000\) için hesaplar.
Temel gözlem şudur: Atış geçmişinin tamamını taşımaya gerek yoktur. Her ara aşamada yalnızca eşit olasılıklı çözülmemiş dalların kaç tane kaldığı önemlidir.
\(n\) eşit olasılıklı sonuçtan birini üretmeye çalıştığımızı düşünelim. Birkaç atıştan sonra örnek uzayın bir kısmı hedef sonuçlara zaten atanabilir; yalnızca bir artık bölüm çözümsüz kalır. Bu bölüm \(r\) tane eşit olasılıklı daldan oluşuyorsa, bundan sonraki kararlar sadece \(r\)'ye bağlıdır.
Böylece süreç şu durumlarla modellenebilir:
$$r\in\{0,1,\dots,n-1\}.$$
\(r=0\) durumu simülasyonun bittiği soğurucu durumdur. Başlangıçta tam bir çözümsüz dal bulunduğu için ilk durum \(r=1\)'dir.
Canlı bir \(r\) durumundan, \(m\in\{5,6\}\) olmak üzere \(m\) yüzlü bir zar seçelim. Her çözümsüz dal \(m\) eşit olasılıklı alt dala ayrılır; dolayısıyla geçici olarak \(mr\) tane eşit olasılıklı durum oluşur.
Şimdi \(mr\)'yi \(n\)'e bölelim:
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
İlk \(qn\) durum, büyüklüğü \(n\) olan \(q\) tam kümeye ayrılabilir ve bu tam kümelerin her biri \(n\) hedef sonuca eşit biçimde dağıtılabilir. Yalnızca \(r'\) tane artık durum çözümsüz kalır.
Bu nedenle \(m\) yüzlü zar seçildikten sonra devam etme olasılığı
$$\Pr(\text{devam}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
olur; devam edilirse yeni durum tam olarak \(r'\)'dir.
\(V_n(r)\), \(r\) durumundan itibaren gereken en küçük ek atış sayısının beklentisi olsun. Soğurucu durum için
$$V_n(0)=0$$
yazılır. Her canlı durum \(1\le r\le n-1\) için bir atış kesin olarak şimdi harcanır; yalnızca artık sıfır değilse süreç sürer. Bu yüzden
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
Bu, sonlu karar sürecinin Bellman eniyilik denklemidir. Tek bir hedef boyut için aranan değer
$$R(n)=V_n(1)$$
olur.
Aynı artık sayısı \(r\)'ye sahip iki farklı atış geçmişi stratejik olarak eşdeğerdir. Her iki durumda da \(r\) tane eşit olasılıklı çözümsüz dal vardır ve bir sonraki karar yalnızca yeni 5'li veya 6'lı bölmenin hedef boyut \(n\) ile nasıl etkileştiğine bağlıdır.
Bu simetri, üstel büyüyebilecek karar ağacını yalnızca \(n\) durumlu ve her canlı durumda iki eylemli sonlu bir dinamik programa indirger. Her \(n\) için \(R(n)\) bulunduktan sonra dış problem basitçe
$$S(N)=\sum_{n=2}^{N} R(n)$$
haline gelir.
\(R(8)\) kontrol değeri doğrudan yineleme denkleminden çıkarılabilir. Önce bazı ara durumlara bakalım.
\(r=4\) durumunda 6 yüzlü zar seçilirse
$$6\cdot 4=24=3\cdot 8+0$$
olur; yani süreç bir sonraki atışta kesin biter. Dolayısıyla
$$V_8(4)=1.$$
\(r=6\) durumunda 6 yüzlü zar, kalan olarak \(4\) verir:
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
\(r=5\) için 5 yüzlü zar, kalanı \(1\) yapar; bu yüzden
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
6 yüzlü zar seçilseydi maliyet
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}$$
olacaktı. Başlangıç durumu \(r=1\)'de 5 yüzlü zar seçmek bizi kesin olarak \(r=5\)'e götürür; yani
$$V_8(1)=1+V_8(5).$$
Bu iki 5-zar denkleminden
$$V_8(1)=2+\frac{1}{25}V_8(1)$$
elde edilir ve buradan
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
çıkar. Geri yerine koyunca \(V_8(5)=13/12\) bulunur; bu değer gerçekten de \(11/9\)'dan küçüktür. Böylece seçilen eylemlerin kendi içinde tutarlı biçimde optimal olduğu görülür. Bu sonuç C++, Python ve Java uygulamalarındaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamalarının hepsi aynı sayısal planı izler. Sabit bir \(n\) için önce her canlı \(r\) durumu adına iki olası sonraki kalan ve 5 yüzlü ya da 6 yüzlü zar seçimine karşılık gelen iki devam katsayısı önceden hesaplanır.
Daha sonra iki değer dizisi tutulur ve şu Bellman güncellemesi tekrar tekrar uygulanır:
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right).$$
Tüm durumlar üzerindeki en büyük mutlak değişim \(10^{-18}\)'in altına düştüğünde ya da sabit güvenlik sınırı olan 2000 tarama tamamlandığında iterasyon durur.
Başlangıç durumu \(r=1\)'deki değer \(R(n)\) olarak alınır. Dıştaki döngü \(2\) ile \(1000\) arasındaki tüm \(n\) değerleri için bunu hesaplar ve toplamı biriktirir.
Tek bir hedef boyut \(n\) için geçiş verisini kurmak \(O(n)\) zaman ve \(O(n)\) bellek ister. Her gevşetme turu da \(O(n)\) sürer, çünkü her canlı durumda yalnızca iki eylem karşılaştırılır.
Durdurma kuralına kadar \(I_n\) tur gerekiyorsa, \(R(n)\) hesabının maliyeti \(O(nI_n)\) zaman ve \(O(n)\) bellektir. Dolayısıyla \(N\)'e kadar tam toplamın maliyeti
$$\sum_{n=2}^{N} O(nI_n)$$
olur. Uygulama ayrıca 2000 turluk sabit bir üst sınır kullandığı için en kötü durumda büyüme bu sabit çarpana kadar \(N\) cinsinden kareseldir. Pratikte güncellemeler çok daha erken dengelenir.
Queremos simular un resultado uniforme de \(n\) posibilidades usando solo dados justos de 5 caras y de 6 caras. Despues de cada tirada podemos volver a elegir que dado usar, asi que la estrategia es adaptativa.
Para cada tamano objetivo \(n\), sea \(R(n)\) el numero esperado minimo de tiradas del dado fuente necesarias para terminar la simulacion. La cantidad pedida por el problema es
$$S(N)=\sum_{n=2}^{N} R(n),$$
y la implementacion evalua esta suma en \(N=1000\).
La idea central es que no hace falta conservar toda la historia de tiradas. En cada etapa parcial solo importa cuantas ramas equiprobables sin resolver siguen vivas.
Supongamos que queremos producir uno de \(n\) resultados igualmente probables. Tras varias tiradas, parte del espacio muestral ya puede asignarse a los resultados finales y solo queda una parte residual sin resolver. Si esa parte residual contiene \(r\) ramas equiprobables, entonces el futuro depende solo de \(r\), no del camino exacto que nos llevo hasta alli.
Por tanto, el proceso se modela con estados
$$r\in\{0,1,\dots,n-1\}.$$
El estado \(r=0\) significa que la simulacion ya termino. El estado inicial es \(r=1\), porque antes de la primera tirada existe exactamente una rama no resuelta.
Desde un estado activo \(r\), elegimos un dado con \(m\) caras, donde \(m\in\{5,6\}\). Cada rama no resuelta se divide en \(m\) subramas equiprobables, asi que temporalmente aparecen \(mr\) casos equiprobables.
Ahora dividimos \(mr\) por \(n\):
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
Los primeros \(qn\) casos pueden agruparse en \(q\) bloques completos de tamano \(n\), y cada bloque completo puede asignarse de manera uniforme a los \(n\) resultados objetivo. Solo los \(r'\) casos restantes permanecen sin resolver.
Por eso, despues de elegir el dado de \(m\) caras, la probabilidad de continuar es
$$\Pr(\text{continuar}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
y, condicionado a continuar, el siguiente estado es precisamente \(r'\).
Sea \(V_n(r)\) el numero esperado minimo de tiradas adicionales necesarias desde el estado \(r\). Para el estado absorbente se tiene
$$V_n(0)=0.$$
Para cada estado activo \(1\le r\le n-1\), una tirada se gasta inmediatamente y solo seguimos si el resto no se anula. Por lo tanto,
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
Esta es la ecuacion de optimalidad de Bellman para el proceso finito de decisiones. El valor pedido para un objetivo fijo es
$$R(n)=V_n(1).$$
Dos historias parciales con el mismo residuo \(r\) son estrategicamente equivalentes. En ambos casos hay \(r\) ramas equiprobables sin resolver, y la siguiente decision solo depende de como una nueva particion en 5 o en 6 interactua con el tamano objetivo \(n\).
Esa simetria reduce un arbol de decisiones potencialmente enorme a solo \(n\) estados y dos acciones por cada estado activo. Una vez calculado \(R(n)\) para cada tamano objetivo, el problema exterior se convierte simplemente en
$$S(N)=\sum_{n=2}^{N} R(n).$$
El valor de control \(R(8)\) se obtiene directamente de la recurrencia. Empecemos con algunos estados intermedios utiles.
Desde \(r=4\), elegir el dado de 6 caras produce
$$6\cdot 4=24=3\cdot 8+0,$$
de modo que el proceso termina con certeza tras una tirada mas. Luego
$$V_8(4)=1.$$
Desde \(r=6\), el dado de 6 caras deja resto \(4\), asi que
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
En \(r=5\), el dado de 5 caras deja resto \(1\), por lo que
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
Si en cambio eligieramos el dado de 6 caras, obtendriamos
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$$
Desde el estado inicial \(r=1\), elegir el dado de 5 caras nos lleva con certeza a \(r=5\), asi que
$$V_8(1)=1+V_8(5).$$
Al combinar las dos ecuaciones con dado de 5 caras se obtiene
$$V_8(1)=2+\frac{1}{25}V_8(1),$$
y por tanto
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
Al sustituir hacia atras se ve que \(V_8(5)=13/12\), que efectivamente es menor que \(11/9\). Por eso las acciones elegidas son coherentemente optimas. Este valor coincide con el punto de control usado por las implementaciones en C++, Python y Java.
Las implementaciones en C++, Python y Java siguen el mismo esquema numerico. Para un \(n\) fijo, primero precalculan, para cada estado activo \(r\), los dos restos siguientes posibles y los dos factores de continuacion asociados a elegir el dado de 5 caras o el de 6 caras.
Despues mantienen dos arreglos de valores y aplican repetidamente la actualizacion de Bellman
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right).$$
La iteracion se detiene cuando el mayor cambio absoluto entre todos los estados cae por debajo de \(10^{-18}\), o cuando se alcanza el limite fijo de seguridad de 2000 barridos.
El valor en el estado inicial \(r=1\) se toma como \(R(n)\). Un bucle exterior calcula esto para todos los \(n\) entre \(2\) y \(1000\) y va acumulando la suma.
Para un solo tamano objetivo \(n\), construir los datos de transicion cuesta \(O(n)\) tiempo y \(O(n)\) memoria. Cada barrido de relajacion tambien cuesta \(O(n)\), porque cada estado activo compara exactamente dos acciones.
Si hacen falta \(I_n\) barridos hasta satisfacer la condicion de parada, entonces calcular \(R(n)\) cuesta \(O(nI_n)\) tiempo y \(O(n)\) memoria. Por consiguiente, la suma completa hasta \(N\) cuesta
$$\sum_{n=2}^{N} O(nI_n).$$
Como la implementacion ademas impone un limite fijo de 2000 barridos, el peor crecimiento es cuadratico en \(N\) salvo por ese factor constante. En la practica, las actualizaciones se estabilizan mucho antes.
题目的目标是：只能使用公平的 5 面骰和 6 面骰，却要模拟出一个公平的 \(n\) 种结果的分布。并且在每次掷完之后，我们都可以根据当前进展再次决定下一次使用哪一种骰子，因此策略是自适应的，而不是预先固定的。
对每个目标规模 \(n\)，记 \(R(n)\) 为完成这次公平模拟所需的最小期望掷骰次数。题目要求计算
$$S(N)=\sum_{n=2}^{N} R(n),$$
而实现最终求的是 \(N=1000\) 时的这个总和。
核心观察是：并不需要保存完整的掷骰历史。对于任意一个中间阶段，真正重要的只有“还剩下多少个等概率、但尚未分配到最终答案的分支”。
设我们要模拟的是 \(n\) 个等概率结果中的一个。经过若干次掷骰后，样本空间中的一部分情况已经可以平均分配给这 \(n\) 个目标结果，而另一部分情况仍然无法均匀分配，需要继续细分。
如果这部分尚未解决的情况一共还剩下 \(r\) 个等概率分支，那么后续决策只取决于这个 \(r\)，而不再取决于之前具体掷出了什么。于是整个过程可以压缩为状态
$$r\in\{0,1,\dots,n-1\}.$$
其中 \(r=0\) 表示已经完全结束，不需要再掷；初始状态是 \(r=1\)，因为在第一次掷骰之前，只有一个尚未展开的分支。
从某个活动状态 \(r\) 出发，选择一个 \(m\) 面骰，其中 \(m\in\{5,6\}\)。由于每个未解决分支都会再分裂成 \(m\) 个等概率子分支，所以这一轮之后暂时总共有 \(mr\) 个等概率情况。
把 \(mr\) 除以 \(n\)：
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
这里 \(qn\) 个情况可以被拆成 \(q\) 个完整的大小为 \(n\) 的块。每一个完整块都可以一一平均映射到 \(n\) 个目标结果上，因此这部分已经成功“消费”掉了。真正还需要继续处理的，只剩下余下的 \(r'\) 个情况。
所以，若当前在状态 \(r\) 并选择 \(m\) 面骰，则继续掷下去的概率是
$$\Pr(\text{继续}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
而一旦继续，新的状态就是 \(r'\)。
设 \(V_n(r)\) 表示：当目标规模固定为 \(n\) 时，从状态 \(r\) 出发，完成模拟所需的最小期望额外掷骰次数。那么吸收态满足
$$V_n(0)=0.$$
对每个活动状态 \(1\le r\le n-1\)，当前这一轮一定要先掷一次；只有在余量不为零时才会继续。因此有
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
这就是该有限决策过程的 Bellman 最优性方程。题目对单个 \(n\) 真正需要的量正是
$$R(n)=V_n(1).$$
如果两段不同的掷骰历史在某一时刻都留下了同样的余量 \(r\)，那么从策略角度看它们完全等价。原因是这两种情况下都只剩下 \(r\) 个等概率未解决分支，而下一步选择 5 面骰还是 6 面骰，只取决于新的 \(5\) 路或 \(6\) 路细分与目标规模 \(n\) 的整除关系。
这条对称性非常重要，因为它把一个可能指数增长的决策树，压缩成了只有 \(n\) 个状态、每个活动状态只有两个动作的有限动态规划。对每个 \(n\) 求出 \(R(n)\) 后，外层总任务就只是
$$S(N)=\sum_{n=2}^{N} R(n).$$
\(R(8)\) 可以直接由递推式算出来，这也是实现里使用的一个数值检查点。先看几个关键状态。
当 \(r=4\) 时，如果选择 6 面骰，那么
$$6\cdot 4=24=3\cdot 8+0,$$
也就是说这一掷之后一定结束，因此
$$V_8(4)=1.$$
当 \(r=6\) 时，若选择 6 面骰，余量会变成 \(4\)，于是
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
当 \(r=5\) 时，若选择 5 面骰，余量变成 \(1\)，所以
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
如果改选 6 面骰，则代价是
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$$
从初始状态 \(r=1\) 出发，选择 5 面骰会以概率 1 转到 \(r=5\)，因此
$$V_8(1)=1+V_8(5).$$
把两条“选择 5 面骰”的关系联立即得
$$V_8(1)=2+\frac{1}{25}V_8(1),$$
从而
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
再代回去可得 \(V_8(5)=13/12\)，确实小于备用方案的 \(11/9\)，因此上述动作选择前后一致并且最优。这个值与 C++、Python 和 Java 实现中的检查点完全一致。
C++、Python 和 Java 实现采用完全相同的数值流程。对固定的 \(n\)，它们先为每个活动状态 \(r\) 预计算两种选择对应的数据：如果选 5 面骰，下一余量是多少、继续概率是多少；如果选 6 面骰，对应的数据又是多少。
然后程序维护两个值数组，不断执行 Bellman 更新：
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right).$$
当所有状态上的最大绝对改变量小于 \(10^{-18}\) 时，迭代停止；如果还未满足，则最多做 2000 次扫描后强制停止。
初始状态 \(r=1\) 上的值就是 \(R(n)\)。最外层循环把 \(n=2,3,\dots,1000\) 全部算一遍，并把它们累加起来。
对单个目标规模 \(n\)，构造转移数据需要 \(O(n)\) 时间和 \(O(n)\) 空间。每一轮松弛更新同样是 \(O(n)\)，因为每个活动状态只比较两个动作。
如果为了满足停止条件需要 \(I_n\) 轮，那么计算 \(R(n)\) 的代价就是 \(O(nI_n)\) 时间和 \(O(n)\) 空间。因此计算到 \(N\) 为止的总复杂度为
$$\sum_{n=2}^{N} O(nI_n).$$
由于实现里还加了 2000 轮的固定上限，所以最坏情况下关于 \(N\) 的增长是二次的，只是前面带着这个常数因子。实际运行时，数值更新通常会在远早于上限的时候稳定下来。
Нужно смоделировать равновероятный результат с \(n\) исходами, используя только честные 5-гранный и 6-гранный кубики. После каждого броска можно заново выбирать, какой из двух кубиков бросать дальше, то есть стратегия допускает адаптацию по ходу процесса.
Для каждого размера цели \(n\) обозначим через \(R(n)\) минимальное математическое ожидание числа бросков исходных кубиков, необходимое для завершения симуляции. Требуется вычислить
$$S(N)=\sum_{n=2}^{N} R(n),$$
а реализация считает эту сумму при \(N=1000\).
Главная идея состоит в том, что хранить полную историю бросков не нужно. В любой промежуточный момент важно только то, сколько равновероятных, но еще не распределенных ветвей остается.
Предположим, что мы хотим получить один из \(n\) равновероятных итогов. После нескольких бросков часть пространства исходов уже можно равномерно сопоставить этим \(n\) итогам, а часть остается неразрешенной. Если неразрешенная часть содержит \(r\) равновероятных ветвей, то дальнейшие решения зависят только от \(r\), а не от того, каким именно путем мы пришли в это состояние.
Поэтому процесс описывается состояниями
$$r\in\{0,1,\dots,n-1\}.$$
Состояние \(r=0\) означает, что симуляция уже завершена. Начальное состояние равно \(r=1\), потому что до первого броска имеется ровно одна неразвернутая ветвь.
Из активного состояния \(r\) выбирается кубик с \(m\) гранями, где \(m\in\{5,6\}\). Каждая неразрешенная ветвь распадается на \(m\) равновероятных подветвей, так что временно возникает \(mr\) равновероятных случаев.
Разделим \(mr\) на \(n\):
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
Первые \(qn\) случаев можно разбить на \(q\) полных блоков размера \(n\), и каждый такой блок равномерно сопоставить \(n\) целевым исходам. Неразрешенными остаются только \(r'\) случаев.
Следовательно, если в состоянии \(r\) выбран кубик с \(m\) гранями, то вероятность продолжения равна
$$\Pr(\text{продолжить}\mid r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
а при условии продолжения следующим состоянием становится именно \(r'\).
Пусть \(V_n(r)\) обозначает минимальное ожидаемое число дополнительных бросков, необходимых из состояния \(r\). Для поглощающего состояния имеем
$$V_n(0)=0.$$
Для любого активного состояния \(1\le r\le n-1\) один бросок тратится сразу, а далее процесс продолжается только тогда, когда остаток не стал нулем. Поэтому
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
Это и есть уравнение оптимальности Беллмана для данного конечного процесса принятия решений. Нужная величина для фиксированного \(n\) равна
$$R(n)=V_n(1).$$
Две частичные истории бросков, приводящие к одному и тому же остатку \(r\), стратегически эквивалентны. В обоих случаях имеется \(r\) равновероятных неразрешенных ветвей, а следующий выбор зависит только от того, как новое разбиение на 5 или 6 частей взаимодействует с целевым размером \(n\).
Эта симметрия превращает потенциально огромный деревообразный процесс в конечную динамическую программу всего с \(n\) состояниями и двумя действиями в каждом активном состоянии. После вычисления \(R(n)\) для каждого \(n\) внешняя задача сводится к сумме
$$S(N)=\sum_{n=2}^{N} R(n).$$
Контрольное значение \(R(8)\) удобно получить прямо из рекуррентных соотношений. Начнем с нескольких промежуточных состояний.
Из состояния \(r=4\) выбор 6-гранного кубика дает
$$6\cdot 4=24=3\cdot 8+0,$$
то есть процесс гарантированно заканчивается после еще одного броска. Следовательно,
$$V_8(4)=1.$$
Из состояния \(r=6\) выбор 6-гранного кубика оставляет остаток \(4\), поэтому
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
В состоянии \(r=5\) выбор 5-гранного кубика дает остаток \(1\), так что
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
Если же выбрать 6-гранный кубик, получится
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$$
Из начального состояния \(r=1\) выбор 5-гранного кубика с вероятностью 1 переводит в \(r=5\), значит
$$V_8(1)=1+V_8(5).$$
Комбинируя два равенства для выбора 5-гранного кубика, получаем
$$V_8(1)=2+\frac{1}{25}V_8(1),$$
откуда
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
Обратная подстановка дает \(V_8(5)=13/12\), и это действительно меньше, чем альтернативное \(11/9\). Значит, выбранные действия согласованно оптимальны. Это значение совпадает с контрольной точкой, используемой в реализациях на C++, Python и Java.
Реализации на C++, Python и Java используют один и тот же численный план. Для фиксированного \(n\) они сначала предвычисляют для каждого активного состояния \(r\) два возможных следующих остатка и два коэффициента продолжения, соответствующие выбору 5-гранного или 6-гранного кубика.
Затем поддерживаются два массива значений, и многократно применяется обновление Беллмана
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right).$$
Итерации останавливаются, когда максимальное абсолютное изменение по всем состояниям становится меньше \(10^{-18}\), либо когда достигается фиксированный защитный предел в 2000 проходов.
Значение в начальном состоянии \(r=1\) принимается за \(R(n)\). Внешний цикл выполняет это вычисление для всех \(n\) от \(2\) до \(1000\) и суммирует результаты.
Для одного целевого размера \(n\) построение переходных данных требует \(O(n)\) времени и \(O(n)\) памяти. Один проход релаксации тоже стоит \(O(n)\), поскольку в каждом активном состоянии сравниваются ровно два действия.
Если до выполнения критерия остановки требуется \(I_n\) проходов, то вычисление \(R(n)\) стоит \(O(nI_n)\) времени и \(O(n)\) памяти. Поэтому полная сумма до \(N\) имеет стоимость
$$\sum_{n=2}^{N} O(nI_n).$$
Поскольку реализация дополнительно задает жесткий верхний предел в 2000 проходов, худший рост по \(N\) является квадратичным с точностью до этого постоянного множителя. На практике значения стабилизируются заметно раньше.
نريد محاكاة نتيجة عادلة لها \(n\) مخرجات ممكنة باستخدام نرد عادل ذي 5 أوجه ونرد عادل ذي 6 أوجه فقط. وبعد كل رمية يحق لنا أن نختار من جديد أي النردين سنستخدمه لاحقا، لذلك فالاستراتيجية تكيفية وليست ثابتة مسبقا.
لكل قيمة هدف \(n\)، نرمز بـ \(R(n)\) إلى أقل قيمة ممكنة للتوقع الرياضي لعدد الرميات المطلوبة من نرد المصدر حتى تكتمل المحاكاة. والكمية المطلوبة في المسألة هي
$$S(N)=\sum_{n=2}^{N} R(n),$$
وتقوم الخوارزمية بحساب هذا المجموع عند \(N=1000\).
الفكرة الرئيسية هي أننا لا نحتاج إلى الاحتفاظ بكل تاريخ الرميات. في أي مرحلة جزئية، الشيء المهم الوحيد هو عدد الفروع المتساوية الاحتمال التي ما زالت غير محسومة.
افترض أننا نريد إنتاج واحد من \(n\) نواتج متساوية الاحتمال. بعد عدة رميات قد يصبح جزء من فضاء الحالات قابلا للتوزيع مباشرة على النواتج النهائية، بينما يبقى جزء آخر غير محسوم. إذا كان هذا الجزء غير المحسوم يحتوي على \(r\) فروع متساوية الاحتمال، فإن القرارات اللاحقة تعتمد على \(r\) فقط، ولا تعتمد على المسار التفصيلي الذي أوصلنا إلى هذه النقطة.
لذلك يمكن تمثيل العملية بالحالات
$$r\in\{0,1,\dots,n-1\}.$$
الحالة \(r=0\) تعني أن المحاكاة انتهت تماما. أما الحالة الابتدائية فهي \(r=1\)، لأنه قبل أول رمية يوجد فرع واحد فقط غير مفصول بعد.
من حالة فعالة \(r\)، نختار نردا له \(m\) أوجه حيث \(m\in\{5,6\}\). كل فرع غير محسوم ينقسم عندئذ إلى \(m\) فروع فرعية متساوية الاحتمال، فيصبح لدينا مؤقتا \(mr\) حالة متساوية الاحتمال.
نقسم الآن \(mr\) على \(n\):
$$mr=qn+r',\qquad q=\left\lfloor\frac{mr}{n}\right\rfloor,\qquad r'=mr\bmod n.$$
يمكن تفكيك أول \(qn\) حالة إلى \(q\) كتل كاملة، كل كتلة حجمها \(n\)، ثم يمكن توزيع كل كتلة كاملة بالتساوي على النواتج النهائية \(n\). أما الحالات المتبقية وعددها \(r'\) فهي التي تظل غير محسومة.
إذن إذا اخترنا نردا ذا \(m\) أوجه من الحالة \(r\)، فإن احتمال الاستمرار يساوي
$$P_{\mathrm{cont}}(r,m)=\frac{r'}{mr}=\frac{mr\bmod n}{mr},$$
ومتى استمرت العملية فإن الحالة التالية تكون هي نفسها \(r'\).
لتكن \(V_n(r)\) هي أقل قيمة ممكنة للتوقع الرياضي لعدد الرميات الإضافية اللازمة ابتداء من الحالة \(r\). بالنسبة إلى الحالة الماصة لدينا
$$V_n(0)=0.$$
ولكل حالة فعالة \(1\le r\le n-1\)، لا بد من إنفاق رمية واحدة فورا، ثم لا نستمر إلا إذا كان الباقي الجديد غير صفري. لذلك
$$V_n(r)=\min_{m\in\{5,6\}}\left(1+\frac{mr\bmod n}{mr}\,V_n(mr\bmod n)\right).$$
وهذه هي معادلة بيلمان للمثالية في عملية القرار المحدودة هذه. أما القيمة المطلوبة لمسألة ذات \(n\) ثابت فهي
$$R(n)=V_n(1).$$
إذا وصل تاريخان مختلفان من الرميات إلى العدد نفسه \(r\) من الفروع غير المحسومة، فهما متكافئان استراتيجيا. ففي الحالتين يوجد \(r\) فروع متساوية الاحتمال، والقرار التالي يعتمد فقط على كيفية تفاعل تقسيم جديد إلى 5 أو 6 فروع مع الحجم الهدف \(n\).
هذه المماثلة تضغط شجرة قرارات قد تكون ضخمة جدا إلى برنامج ديناميكي محدود فيه \(n\) حالة فقط، ولكل حالة فعالة خياران. وبعد حساب \(R(n)\) لكل قيمة \(n\)، تصبح المسألة الخارجية ببساطة
$$S(N)=\sum_{n=2}^{N} R(n).$$
يمكن استخراج قيمة الفحص \(R(8)\) مباشرة من العلاقة التكرارية. لنبدأ ببعض الحالات الوسيطة المفيدة.
من الحالة \(r=4\)، إذا اخترنا النرد ذي 6 أوجه فإننا نحصل على
$$6\cdot 4=24=3\cdot 8+0,$$
أي إن العملية تنتهي يقينا بعد رمية إضافية واحدة. ومن ثم
$$V_8(4)=1.$$
ومن الحالة \(r=6\)، يؤدي اختيار النرد ذي 6 أوجه إلى باقي يساوي \(4\)، وبالتالي
$$V_8(6)=1+\frac{4}{36}V_8(4)=1+\frac{1}{9}=\frac{10}{9}.$$
أما عند \(r=5\)، فإن اختيار النرد ذي 5 أوجه يعطي باقيًا يساوي \(1\)، ولذلك
$$V_8(5)=1+\frac{1}{25}V_8(1).$$
ولو اخترنا النرد ذي 6 أوجه بدلا من ذلك لحصلنا على
$$1+\frac{6}{30}V_8(6)=1+\frac{1}{5}\cdot\frac{10}{9}=\frac{11}{9}.$$
ومن الحالة الابتدائية \(r=1\)، فإن اختيار النرد ذي 5 أوجه ينقلنا يقينا إلى \(r=5\)، لذلك
$$V_8(1)=1+V_8(5).$$
وبدمج معادلتي الاختيار ذي 5 أوجه نحصل على
$$V_8(1)=2+\frac{1}{25}V_8(1),$$
ومنها
$$R(8)=V_8(1)=\frac{25}{12}=2.083333333333\ldots$$
وعند التعويض العكسي نجد أن \(V_8(5)=13/12\)، وهي بالفعل أصغر من البديل \(11/9\). إذن فالاختيارات المذكورة متسقة وأمثلية في آن واحد. وهذه القيمة تطابق نقطة الفحص المستخدمة في تطبيقات C++ وPython وJava.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. فعند تثبيت \(n\)، تقوم أولا بحساب حالتي الانتقال الممكنتين لكل حالة فعالة \(r\)، إلى جانب معاملي الاستمرار الموافقين لاختيار النرد ذي 5 أوجه أو ذي 6 أوجه.
بعد ذلك تحتفظ الخوارزمية بمصفوفتين للقيم وتكرر تحديث بيلمان التالي:
$$V_{\text{new}}(r)=\min\left(1+\rho_5(r)V_{\text{old}}(r_5),\ 1+\rho_6(r)V_{\text{old}}(r_6)\right).$$
ويتوقف التكرار عندما يصبح أكبر تغير مطلق بين جميع الحالات أصغر من \(10^{-18}\)، أو عندما يصل عدد المسحات إلى الحد الوقائي الثابت وهو 2000.
ثم تؤخذ القيمة عند الحالة الابتدائية \(r=1\) على أنها \(R(n)\). وتقوم حلقة خارجية بحساب ذلك لكل \(n\) من \(2\) إلى \(1000\) ثم تجمع القيم كلها.
من أجل قيمة هدف واحدة \(n\)، فإن بناء بيانات الانتقال يكلف \(O(n)\) زمنا و\(O(n)\) ذاكرة. وكل مسحة استرخاء تكلف أيضا \(O(n)\)، لأن كل حالة فعالة تقارن خيارين فقط.
إذا احتاجت الخوارزمية إلى \(I_n\) مسحات قبل تحقيق شرط التوقف، فإن حساب \(R(n)\) يكلف \(O(nI_n)\) زمنا و\(O(n)\) ذاكرة. ولذلك فإن الكلفة الكلية حتى \(N\) تساوي
$$\sum_{n=2}^{N} O(nI_n).$$
وبما أن التطبيق يفرض أيضا سقفا ثابتا مقداره 2000 مسحة، فإن أسوأ نمو بالنسبة إلى \(N\) يكون تربيعيا حتى هذا العامل الثابت. أما عمليا فتستقر القيم العددية قبل ذلك بكثير.