The weekly process begins with a single \(A1\) sheet, but after the first cut-and-use operation the envelope already contains exactly one sheet of each size \(A2,A3,A4,A5\). That is why the implementations start from the state \(s_0=(1,1,1,1)\): from that point onward, every job consists of drawing one sheet uniformly from the envelope, cutting it down if necessary, using one \(A5\), and returning the leftover smaller sheets.
The goal is to find the expected number of later occasions on which the envelope contains exactly one sheet. The state with a lone \(A5\) is excluded from the count, because it is the terminal last-job situation rather than an additional nontrivial single-sheet event.
This is an exact finite-state expectation problem. Once the right state variables are chosen, the whole solution is a short Markov-style recurrence evaluated with memoization.
Let
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
where \(a_k\) is the number of \(A_k\)-sheets currently in the envelope. Only the sizes \(A2,A3,A4,A5\) can appear after the first job, so these four integers describe the process completely. The starting state is
$$s_0=(1,1,1,1).$$
The random choice at each step is uniform over sheets, not over sizes, so the probability of drawing size \(A_k\) is \(a_k/T(s)\).
If a chosen sheet is larger than \(A5\), it is halved repeatedly until one \(A5\) is used. The leftovers are precisely one copy of every intermediate smaller size. Therefore the four possible successors are
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
These formulas are exactly what the implementations build when they remove one selected sheet and then add back all smaller leftovers created by the cutting chain.
A convenient way to see that the recursion must terminate is to measure the remaining paper in \(A5\)-equivalents:
$$W(s)=8a_2+4a_3+2a_4+a_5.$$
One \(A2\) contains the area of eight \(A5\) sheets, one \(A3\) contains four, and one \(A4\) contains two. Under any transition above, exactly one \(A5\)-worth of paper is consumed, so
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{for every available }k\in\{2,3,4,5\}.$$
Starting from \(s_0=(1,1,1,1)\), we have \(W(s_0)=15\). Hence the process can never cycle: every step moves to a strictly smaller value of \(W\), and after 15 jobs the envelope is empty. This turns the state graph into a small directed acyclic graph.
Let \(E(s)\) be the expected number of future single-sheet occasions starting from state \(s\). The only single-sheet states that count are
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$$
because the terminal state \((0,0,0,1)\) must be excluded. Define the indicator
$$I(s)=\begin{cases} 1, & T(s)=1\text{ and }a_5=0,\\ 0, & \text{otherwise.} \end{cases}$$
Then the empty-envelope base case is
$$E(0,0,0,0)=0,$$
and for every nonempty state, the law of total expectation gives
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$$
where terms with \(a_k=0\) are simply absent. This formula already solves the problem: the desired answer is \(E(1,1,1,1)\).
Take the state \(s=(0,0,1,0)\), meaning that the envelope contains only one \(A4\). This state counts once immediately, and the only possible next state is \((0,0,0,1)\). Therefore
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
The initial state illustrates the probabilistic branching. Since \(T(1,1,1,1)=4\), each size is chosen with probability \(1/4\), so
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$$
Every later expectation is obtained by repeating exactly the same recurrence on smaller states.
Because \(W(s)\) decreases by 1 at every step, \(E(s)\) only depends on states with smaller \(W\). There is no need for simulation, sampling, or solving a large linear system. Caching the value of each reached state once is sufficient to evaluate the entire recurrence exactly up to floating-point output formatting.
The C++, Python, and Java implementations all store the four sheet counts as the complete state description and cache already computed expectations in a hash table. The C++ and Java versions pack the four counts into an integer-style key, while the Python version uses the tuple itself as the key, but mathematically they memoize the same function \(E(s)\).
For each state, the implementation first computes the total number of sheets \(T(s)\). If the envelope is empty, it returns 0. Otherwise it adds 1 exactly when the state is a counted single-sheet state, then loops over the available sizes, constructs the corresponding successor state, multiplies the recursive value by the probability \(a_k/T(s)\), and accumulates the result. Finally it starts from \((1,1,1,1)\) and prints the expectation rounded to six decimal places.
Let \(S\) be the number of reachable states from \((1,1,1,1)\). Each state examines at most four outgoing transitions, so the running time is \(O(S)\) and the memory usage is also \(O(S)\).
For this problem \(S\) is tiny, because every state satisfies \(W(s)\le 15\) and every move decreases \(W\) by 1. The recursion depth is therefore at most 15, and the memo table remains small. The algorithm is fast because it replaces an exponentially branching random process by one evaluation of a compact acyclic state graph.
Der Wochenablauf beginnt zwar mit einem einzelnen \(A1\)-Bogen, aber nach dem ersten Schneide-und-Verbrauch-Schritt liegen im Umschlag bereits genau ein \(A2\)-, ein \(A3\)-, ein \(A4\)- und ein \(A5\)-Bogen. Deshalb starten die Implementierungen mit dem Zustand \(s_0=(1,1,1,1)\): Von dort an besteht jeder Auftrag darin, einen Bogen gleichverteilt aus dem Umschlag zu ziehen, ihn falls nötig bis zu \(A5\) herunterzuschneiden, einen \(A5\)-Bogen zu verbrauchen und die übrigen kleineren Bögen zurückzulegen.
Gesucht ist der Erwartungswert der späteren Zeitpunkte, an denen sich genau ein Bogen im Umschlag befindet. Der Zustand mit genau einem \(A5\) wird nicht mitgezählt, weil er nur die triviale Endsituation des letzten Auftrags darstellt.
Das Problem lässt sich exakt als endlicher Zustandsprozess lösen. Sobald man die richtigen Zustandsgrößen wählt, bleibt nur eine kurze Erwartungswert-Rekurrenz, die per Memoisierung ausgewertet wird.
Wir schreiben
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
wobei \(a_k\) die aktuelle Anzahl der \(A_k\)-Bögen im Umschlag ist. Nach dem ersten Auftrag können nur noch die Größen \(A2,A3,A4,A5\) auftreten; diese vier Zahlen beschreiben den Zustand also vollständig. Der Startzustand ist
$$s_0=(1,1,1,1).$$
Wichtig ist, dass gleichverteilt über einzelne Bögen gezogen wird, nicht über Papiergrößen. Die Wahrscheinlichkeit für \(A_k\) ist deshalb \(a_k/T(s)\).
Wird ein größerer Bogen gewählt, dann wird er so oft halbiert, bis ein \(A5\) verbraucht werden kann. Die Rückstände sind genau je ein Exemplar aller dazwischenliegenden kleineren Größen. Damit ergeben sich die vier Nachfolger
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
Genau diese Übergänge setzen die Implementierungen um: ein ausgewähltes Blatt entfernen und anschließend alle bei der Schneidekette entstehenden kleineren Restblätter hinzufügen.
Für die Terminierung ist die Größe
$$W(s)=8a_2+4a_3+2a_4+a_5$$
entscheidend. Ein \(A2\)-Bogen entspricht acht \(A5\)-Flächen, ein \(A3\)-Bogen vier und ein \(A4\)-Bogen zwei. Bei jedem Übergang wird genau eine \(A5\)-Flächeneinheit verbraucht, also gilt
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{für jedes verfügbare }k\in\{2,3,4,5\}.$$
Aus \(s_0=(1,1,1,1)\) folgt \(W(s_0)=15\). Damit sind Zyklen ausgeschlossen: Jeder Schritt senkt \(W\) strikt, und nach 15 Aufträgen ist der Umschlag leer. Der Zustandsgraph ist also ein kleiner gerichteter azyklischer Graph.
Sei \(E(s)\) die erwartete Anzahl zukünftiger Einblatt-Zeitpunkte ab Zustand \(s\). Gezählt werden nur die drei Zustände
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$$
denn \((0,0,0,1)\) ist der ausgeschlossene Endfall. Wir definieren den Indikator
$$I(s)=\begin{cases} 1, & T(s)=1\text{ und }a_5=0,\\ 0, & \text{sonst.} \end{cases}$$
Für den leeren Umschlag gilt
$$E(0,0,0,0)=0,$$
und für jeden nichtleeren Zustand liefert das Gesetz der totalen Erwartung
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$$
wobei Terme mit \(a_k=0\) entfallen. Damit ist das Problem bereits gelöst: Gesucht ist \(E(1,1,1,1)\).
Betrachte zunächst \(s=(0,0,1,0)\), also genau einen \(A4\)-Bogen im Umschlag. Dieser Zustand zählt sofort einmal, und der einzige Nachfolger ist \((0,0,0,1)\). Also
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
Der Startzustand zeigt die Verzweigung nach Wahrscheinlichkeiten. Weil \(T(1,1,1,1)=4\) ist, wird jede Größe mit Wahrscheinlichkeit \(1/4\) gezogen, also
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$$
Alle weiteren Werte entstehen durch dieselbe Rekurrenz auf Zuständen mit kleinerem \(W\).
Da \(W(s)\) in jedem Schritt um 1 sinkt, hängt \(E(s)\) nur von Zuständen mit kleinerem \(W\) ab. Weder Simulation noch ein großes lineares Gleichungssystem sind nötig. Es reicht, jeden erreichten Zustand einmal zu berechnen und anschließend aus dem Cache zu lesen.
Die C++-, Python- und Java-Implementierungen speichern die vier Blattzahlen als vollständige Zustandsbeschreibung und legen bereits berechnete Erwartungswerte in einer Hashtabelle ab. C++ und Java packen die vier Zähler in einen ganzzahligen Schlüssel, Python verwendet das Tupel selbst als Schlüssel; mathematisch memoisiert jedoch jede Version dieselbe Funktion \(E(s)\).
Für jeden Zustand berechnet die Implementierung zuerst die Gesamtzahl \(T(s)\). Ist der Umschlag leer, wird 0 zurückgegeben. Andernfalls wird genau dann 1 addiert, wenn ein zählbarer Einblatt-Zustand vorliegt; danach werden alle verfügbaren Papiergrößen durchlaufen, die passenden Nachfolgezustände konstruiert, mit den Wahrscheinlichkeiten \(a_k/T(s)\) gewichtet und aufaddiert. Am Ende startet alles bei \((1,1,1,1)\), und der Erwartungswert wird auf sechs Nachkommastellen ausgegeben.
Sei \(S\) die Anzahl der von \((1,1,1,1)\) aus erreichbaren Zustände. Jeder Zustand betrachtet höchstens vier ausgehende Übergänge, daher betragen Laufzeit und Speicher jeweils \(O(S)\).
In diesem Problem ist \(S\) sehr klein, weil jeder Zustand die Schranke \(W(s)\le 15\) erfüllt und jeder Schritt \(W\) um 1 verringert. Die Rekursionstiefe ist also höchstens 15, und die Memoisierungstabelle bleibt klein. Die Effizienz entsteht dadurch, dass ein zufälliger Prozess mit vielen Verzweigungen auf eine einmalige Auswertung eines kompakten azyklischen Zustandsgraphen reduziert wird.
Haftalık süreç aslında tek bir \(A1\) kâğıdıyla başlar; fakat ilk kesme ve kullanım adımından sonra zarfta zaten tam olarak birer tane \(A2,A3,A4,A5\) bulunur. Bu yüzden uygulamalar başlangıç durumu olarak \(s_0=(1,1,1,1)\) vektörünü alır: bundan sonraki her işte zarftan mevcut yapraklar arasından eşit olasılıkla bir kâğıt seçilir, gerekiyorsa \(A5\)'e kadar kesilir, bir \(A5\) kullanılır ve artan küçük parçalar tekrar zarfa konur.
Aranan nicelik, daha sonraki adımlarda zarfın tam olarak bir yaprak içerdiği anların beklenen sayısıdır. Tek başına kalan \(A5\) durumu sayılmaz; çünkü o durum, sayılması gereken ek bir olaydan çok sürecin son işini temsil eder.
Bu problem tam olarak çözülebilen sonlu bir durum sürecidir. Doğru durum değişkenleri seçildiğinde tüm çözüm, memoization ile hesaplanan kısa bir beklenti bağıntısına indirgenir.
Durumu
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
şeklinde yazalım. Burada \(a_k\), zarftaki \(A_k\) boyutlu kâğıt sayısını gösterir. İlk işten sonra yalnızca \(A2,A3,A4,A5\) boyutları görülebileceği için bu dört sayı süreci tamamen tanımlar. Başlangıç durumu
$$s_0=(1,1,1,1)$$
olur. Her adımda seçim boyutlar arasında değil, tek tek yapraklar arasında eşit olasılıkla yapıldığı için \(A_k\) seçilme olasılığı \(a_k/T(s)\) olur.
Büyük bir yaprak seçildiğinde, bir \(A5\) kullanılıncaya kadar ardışık biçimde ikiye bölünür. Zarfa geri dönen artıklar, aradaki bütün daha küçük boyutlardan birer adettir. Bu nedenle dört olası ardıl durum şunlardır:
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
Uygulamalar tam olarak bu işlemi yapar: seçilen bir kâğıdı çıkarır ve kesme zincirinden doğan daha küçük artık yaprakları ekler.
Özyinelemenin neden mutlaka biteceğini görmek için
$$W(s)=8a_2+4a_3+2a_4+a_5$$
büyüklüğünü tanımlayalım. Bir \(A2\), sekiz \(A5\)'lik alana; bir \(A3\), dört \(A5\)'lik alana; bir \(A4\) ise iki \(A5\)'lik alana eşittir. Yukarıdaki her geçişte tam bir \(A5\)'lik alan tüketildiğinden
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{her uygun }k\in\{2,3,4,5\}\text{ için}$$
olur. Başlangıçta \(W(s_0)=15\) olduğu için süreç döngü yapamaz; her adımda \(W\) kesin olarak azalır ve 15 iş sonra zarf boşalır. Böylece durum grafiği küçük bir yönlü çevrimsiz grafa dönüşür.
\(E(s)\), durum \(s\)'den itibaren gelecekte görülecek tek-yaprak anlarının beklenen sayısı olsun. Sayılan tek-yaprak durumları yalnızca
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0)$$
durumlarıdır; çünkü \((0,0,0,1)\) terminal tek \(A5\) halidir ve dışarıda bırakılır. Şimdi
$$I(s)=\begin{cases} 1, & T(s)=1\text{ ve }a_5=0,\\ 0, & \text{aksi halde} \end{cases}$$
göstergesini tanımlayalım. Boş zarf için
$$E(0,0,0,0)=0$$
olur. Boş olmayan her durumda toplam beklenti yasası
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right)$$
bağıntısını verir; burada \(a_k=0\) olan terimler doğal olarak yoktur. İstenen sonuç tam olarak \(E(1,1,1,1)\)'dir.
Önce \(s=(0,0,1,0)\) durumunu alalım; yani zarfta yalnızca tek bir \(A4\) vardır. Bu durum hemen bir kez sayılır ve tek olası sonraki durum \((0,0,0,1)\)'dir. Dolayısıyla
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
Başlangıç durumu ise olasılıklı dallanmayı gösterir. \(T(1,1,1,1)=4\) olduğundan her boyut \(1/4\) olasılıkla seçilir ve
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0)$$
elde edilir. Sonraki bütün beklenti değerleri, aynı formülün daha küçük \(W\) değerli durumlara uygulanmasıyla çıkar.
\(W(s)\) her adımda 1 azaldığı için \(E(s)\) yalnızca daha küçük \(W\) değerine sahip durumlara bağlıdır. Bu nedenle Monte Carlo benzetimine ya da büyük bir lineer denklem sistemine ihtiyaç yoktur. Her erişilen durumun değeri bir kez hesaplanıp saklanırsa tüm problem çözülür.
C++, Python ve Java uygulamalarının üçü de durumu dört kâğıt sayısıyla temsil eder ve daha önce hesaplanmış beklentileri bir hash tablosunda tutar. C++ ve Java sürümleri bu dört sayıyı tamsayı benzeri bir anahtara paketler; Python sürümü ise doğrudan demeti anahtar olarak kullanır. Matematiksel olarak hepsi aynı \(E(s)\) fonksiyonunu önbelleğe alır.
Her durumda önce toplam yaprak sayısı \(T(s)\) hesaplanır. Zarf boşsa sonuç 0'dır. Aksi halde, durum sayılan bir tek-yaprak durumuysa sonuca 1 eklenir; ardından mevcut boyutlar üzerinden geçilir, uygun ardıl durum oluşturulur, özyinelemeli değer \(a_k/T(s)\) olasılığıyla çarpılır ve toplam beklentiye eklenir. Son olarak süreç \((1,1,1,1)\) durumundan başlatılır ve sonuç altı ondalık basamakla yazdırılır.
\((1,1,1,1)\) başlangıcından erişilebilen durum sayısına \(S\) diyelim. Her durum en fazla dört giden geçiş inceler; bu yüzden zaman karmaşıklığı \(O(S)\), bellek karmaşıklığı da \(O(S)\) olur.
Bu problemde \(S\) çok küçüktür; çünkü her durum için \(W(s)\le 15\) ve her adımda \(W\) bir azalır. Böylece özyineleme derinliği en fazla 15 olur ve memo tablosu rahatça küçük kalır. Yöntemin verimliliği, çok dallı rastgele süreci küçük bir çevrimsiz durum grafiğinin tek seferlik değerlendirmesine indirmesinden gelir.
El proceso semanal empieza con una sola hoja \(A1\), pero después del primer paso de cortar y usar ya quedan en el sobre exactamente una \(A2\), una \(A3\), una \(A4\) y una \(A5\). Por eso las implementaciones comienzan en el estado \(s_0=(1,1,1,1)\): a partir de allí, cada trabajo consiste en elegir una hoja uniformemente entre todas las que hay en el sobre, cortarla si hace falta hasta obtener una \(A5\), usar una \(A5\) y devolver las hojas sobrantes.
Lo que se pide es el número esperado de ocasiones posteriores en las que el sobre contiene exactamente una hoja. El estado con una única \(A5\) no se cuenta, porque representa el último trabajo terminal y no un evento adicional interesante.
Se trata de un problema exacto de esperanza sobre un espacio finito de estados. Una vez elegido el estado correcto, toda la solución se reduce a una recurrencia de tipo Markov evaluada con memoización.
Definimos
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
donde \(a_k\) es la cantidad de hojas \(A_k\) presentes en el sobre. Después del primer trabajo solo pueden aparecer tamaños \(A2,A3,A4,A5\), así que estas cuatro cifras describen completamente el proceso. El estado inicial es
$$s_0=(1,1,1,1).$$
La elección aleatoria es uniforme entre hojas individuales, no entre tamaños. Por tanto, la probabilidad de extraer un \(A_k\) es \(a_k/T(s)\).
Si se elige una hoja mayor que \(A5\), se va cortando por mitades hasta usar una \(A5\). Los sobrantes son exactamente una copia de cada tamaño menor intermedio. Por eso los cuatro sucesores posibles son
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
Esto coincide exactamente con lo que hacen las implementaciones: quitar una hoja elegida y luego añadir todas las hojas menores que reaparecen en la cadena de cortes.
Para ver por qué la recursión termina, conviene medir el papel restante en equivalentes de \(A5\):
$$W(s)=8a_2+4a_3+2a_4+a_5.$$
Una hoja \(A2\) contiene el área de ocho \(A5\), una \(A3\) equivale a cuatro \(A5\) y una \(A4\) equivale a dos. En cualquiera de las transiciones anteriores se consume exactamente un equivalente de \(A5\), de modo que
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{para todo }k\in\{2,3,4,5\}\text{ disponible}.$$
Como \(W(1,1,1,1)=15\), el proceso no puede formar ciclos: cada paso disminuye estrictamente \(W\) y tras 15 trabajos el sobre queda vacío. Eso convierte el grafo de estados en un pequeño DAG.
Sea \(E(s)\) el número esperado de futuras ocasiones con una sola hoja a partir del estado \(s\). Los únicos estados unitarios que sí cuentan son
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$$
porque \((0,0,0,1)\) es el caso terminal excluido. Definimos el indicador
$$I(s)=\begin{cases} 1, & T(s)=1\text{ y }a_5=0,\\ 0, & \text{en otro caso.} \end{cases}$$
La condición base es
$$E(0,0,0,0)=0,$$
y para cualquier estado no vacío la ley de la esperanza total da
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$$
donde simplemente se omiten los términos con \(a_k=0\). Por tanto, la cantidad buscada es \(E(1,1,1,1)\).
Consideremos primero \(s=(0,0,1,0)\), es decir, un único \(A4\) en el sobre. Ese estado se cuenta inmediatamente una vez, y el único sucesor posible es \((0,0,0,1)\). Luego
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
El estado inicial muestra cómo aparece la ramificación probabilística. Como \(T(1,1,1,1)=4\), cada tamaño se elige con probabilidad \(1/4\), y entonces
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$$
Todos los valores posteriores se obtienen repitiendo la misma fórmula sobre estados con menor valor de \(W\).
Como \(W(s)\) disminuye en 1 en cada paso, \(E(s)\) solo depende de estados con un \(W\) menor. No hace falta simulación ni un gran sistema lineal. Basta con calcular cada estado alcanzable una sola vez y guardar el resultado.
Las implementaciones en C++, Python y Java guardan las cuatro cantidades de hojas como descripción completa del estado y almacenan las esperanzas ya calculadas en una tabla hash. Las versiones en C++ y Java empaquetan las cuatro cuentas en una clave entera; la versión en Python usa directamente la tupla como clave. Desde el punto de vista matemático, las tres memoizan la misma función \(E(s)\).
Para cada estado, la implementación calcula primero el total de hojas \(T(s)\). Si el sobre está vacío, devuelve 0. En caso contrario, suma 1 exactamente cuando el estado es un caso contado de una sola hoja; después recorre los tamaños disponibles, construye el sucesor correspondiente, multiplica el valor recursivo por la probabilidad \(a_k/T(s)\) y acumula la contribución. Finalmente arranca en \((1,1,1,1)\) y muestra la esperanza redondeada a seis decimales.
Sea \(S\) el número de estados alcanzables desde \((1,1,1,1)\). Cada estado examina como máximo cuatro transiciones salientes, así que el tiempo total es \(O(S)\) y la memoria también es \(O(S)\).
Aquí \(S\) es muy pequeño, porque todo estado cumple \(W(s)\le 15\) y cada movimiento reduce \(W\) en una unidad. La profundidad de la recursión es, por tanto, como mucho 15, y la caché sigue siendo diminuta. La eficiencia viene de reemplazar un proceso aleatorio con muchas ramificaciones por una sola evaluación de un grafo acíclico compacto.
每周流程最初从一张 \(A1\) 纸开始，但第一次裁切并使用之后，信封里已经恰好剩下一张 \(A2\)、一张 \(A3\)、一张 \(A4\) 和一张 \(A5\)。因此实现并不是从 \(A1\) 开始递推，而是从状态 \(s_0=(1,1,1,1)\) 开始：从这一刻起，每次任务都等概率地从信封中的所有纸张里抽出一张，若尺寸大于 \(A5\) 就继续裁切到能够用掉一张 \(A5\)，再把剩下的较小纸张放回信封。
题目要求的是之后“信封中恰好只剩一张纸”这一事件出现的期望次数。不过只剩一张 \(A5\) 的终止状态不计入答案，因为那只是最后一次任务开始前的必然结束情形，而不是题目想统计的额外孤张事件。
这是一个可以精确求解的有限状态期望问题。选对状态表示之后，核心就是一个很小的马尔可夫型递推，再配合记忆化即可。
记
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
其中 \(a_k\) 表示信封中当前 \(A_k\) 纸张的张数。第一次任务之后，只可能出现 \(A2,A3,A4,A5\) 这四种尺寸，因此这四个整数已经足以完整描述整个过程。起始状态就是
$$s_0=(1,1,1,1).$$
随机选择是对“纸张”均匀，而不是对“尺寸”均匀，所以抽到 \(A_k\) 的概率是 \(a_k/T(s)\)。
如果抽到的纸张比 \(A5\) 大，就不断对半裁切，直到能够用掉一张 \(A5\)。返回信封的剩余部分，恰好是中间所有更小尺寸各一张。因此四种可能的后继状态为
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
这正是实现里的真实更新规则：先移除被抽中的一张纸，再把裁切链上产生的所有较小剩余纸张加回去。
为了说明递归一定终止，可以把剩余总面积改写成 \(A5\) 张数的等价形式：
$$W(s)=8a_2+4a_3+2a_4+a_5.$$
一张 \(A2\) 相当于八张 \(A5\) 的面积，一张 \(A3\) 相当于四张 \(A5\)，一张 \(A4\) 相当于两张 \(A5\)。无论发生哪一种转移，都会恰好消耗掉一个 \(A5\) 面积单位，因此
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{对每个可选的 }k\in\{2,3,4,5\}\text{都成立。}$$
起始状态满足 \(W(1,1,1,1)=15\)。这说明过程不可能出现环：每一步都会把 \(W\) 严格减一，15 次任务之后信封必为空。于是整个状态图实际上是一个很小的有向无环图。
设 \(E(s)\) 为从状态 \(s\) 出发，未来还会看到多少次“信封里恰好一张纸”的期望值。真正计数的单张状态只有
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$$
因为 \((0,0,0,1)\) 是题目明确排除的终止单 \(A5\) 状态。定义指示函数
$$I(s)=\begin{cases} 1, & T(s)=1\text{ 且 }a_5=0,\\ 0, & \text{其他情况。} \end{cases}$$
空信封的边界条件是
$$E(0,0,0,0)=0.$$
对于任意非空状态，由全期望公式可得
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$$
其中 \(a_k=0\) 的项自然不存在。这样一来，题目所求就是 \(E(1,1,1,1)\)。
先看状态 \(s=(0,0,1,0)\)，也就是信封里只剩一张 \(A4\)。这个状态会立刻贡献一次计数，而且唯一可能的下一状态是 \((0,0,0,1)\)。因此
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
起始状态则展示了概率分支如何出现。因为 \(T(1,1,1,1)=4\)，四种尺寸都以 \(1/4\) 的概率被抽到，所以
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$$
后面的所有值都继续用同样的递推式，在更小的状态上反复展开即可。
由于 \(W(s)\) 每一步都会减少 1，\(E(s)\) 只会依赖于 \(W\) 更小的状态。这意味着既不需要蒙特卡洛模拟，也不需要求解大型线性方程组。只要把每个到达过的状态算一次并缓存起来，就能把整个递推精确地求完。
C++、Python 和 Java 实现都把四个纸张计数作为完整状态，并把已经算出的期望存入哈希表。C++ 和 Java 版本把四个计数打包成一个整数风格的键；Python 版本则直接把四元组作为键。虽然编码方式不同，但三者缓存的都是同一个数学函数 \(E(s)\)。
对于每个状态，实现先计算总纸张数 \(T(s)\)。如果信封为空，就返回 0。否则，当且仅当当前状态是需要计数的单张状态时加上 1；接着遍历所有仍然存在的尺寸，构造对应后继状态，用概率 \(a_k/T(s)\) 乘上递归值并累加。最后从 \((1,1,1,1)\) 开始计算，并输出保留六位小数的结果。
设从 \((1,1,1,1)\) 可达的状态数为 \(S\)。每个状态最多只会查看四条出边，所以总时间复杂度为 \(O(S)\)，空间复杂度也为 \(O(S)\)。
在本题中，\(S\) 非常小，因为所有状态都满足 \(W(s)\le 15\)，而每一步都会把 \(W\) 降低 1。因此递归深度最多只有 15，缓存表也很小。算法之所以高效，是因为它把一个看似会不断随机分叉的过程，压缩成了对一个小型有向无环状态图的一次性求值。
Недельный процесс формально начинается с одного листа \(A1\), но после первого шага разрезания и использования в конверте уже лежат ровно по одному листу \(A2,A3,A4,A5\). Именно поэтому реализации стартуют из состояния \(s_0=(1,1,1,1)\): дальше каждый заказ означает, что из конверта равновероятно выбирают один из имеющихся листов, при необходимости режут его до \(A5\), используют один \(A5\) и возвращают оставшиеся более мелкие листы.
Нужно найти математическое ожидание числа последующих моментов, когда в конверте остается ровно один лист. Состояние с единственным \(A5\) не учитывается, потому что это просто терминальная ситуация последнего заказа, а не отдельное нетривиальное событие.
Это точная задача на ожидание в конечном пространстве состояний. После удачного выбора состояния все сводится к короткой рекуррентной формуле типа цепи Маркова, которую удобно считать с мемоизацией.
Обозначим
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
где \(a_k\) означает текущее количество листов формата \(A_k\) в конверте. После первого заказа могут встречаться только размеры \(A2,A3,A4,A5\), так что эти четыре числа полностью задают процесс. Начальное состояние равно
$$s_0=(1,1,1,1).$$
Выбор происходит равновероятно по отдельным листам, а не по форматам, поэтому вероятность вытянуть \(A_k\) равна \(a_k/T(s)\).
Если выбран лист крупнее \(A5\), его режут пополам столько раз, сколько нужно, чтобы использовать один \(A5\). В конверт возвращаются ровно по одному экземпляру всех промежуточных более мелких форматов. Поэтому возможные следующие состояния таковы:
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
Именно эти переходы реализованы в коде: убрать выбранный лист и добавить все более мелкие остатки, появившиеся в цепочке разрезаний.
Чтобы понять, почему рекурсия обязана закончиться, удобно ввести величину
$$W(s)=8a_2+4a_3+2a_4+a_5.$$
Один лист \(A2\) содержит площадь восьми листов \(A5\), лист \(A3\) соответствует четырем \(A5\), а лист \(A4\) двум. При любом переходе выше расходуется ровно одна единица площади \(A5\), поэтому
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{для любого доступного }k\in\{2,3,4,5\}.$$
В начальном состоянии \(W(1,1,1,1)=15\). Значит, циклов быть не может: каждый шаг строго уменьшает \(W\), и через 15 заказов конверт опустеет. Следовательно, граф состояний является маленьким ориентированным ациклическим графом.
Пусть \(E(s)\) обозначает ожидаемое число будущих моментов с одним листом, начиная из состояния \(s\). Засчитываются только три одно-листовых состояния
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$$
потому что \((0,0,0,1)\) есть исключенный терминальный случай. Введем индикатор
$$I(s)=\begin{cases} 1, & T(s)=1\text{ и }a_5=0,\\ 0, & \text{иначе.} \end{cases}$$
Для пустого конверта имеем
$$E(0,0,0,0)=0,$$
а для любого непустого состояния закон полной вероятности дает
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$$
где слагаемые с \(a_k=0\) просто отсутствуют. Отсюда искомая величина есть \(E(1,1,1,1)\).
Рассмотрим состояние \(s=(0,0,1,0)\), то есть в конверте лежит только один лист \(A4\). Это состояние сразу дает один засчитанный момент, а единственный следующий шаг ведет в \((0,0,0,1)\). Поэтому
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
Начальное состояние показывает вероятностное ветвление. Поскольку \(T(1,1,1,1)=4\), каждый формат выбирается с вероятностью \(1/4\), и потому
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$$
Все остальные значения строятся той же формулой на состояниях с меньшим \(W\).
Так как \(W(s)\) на каждом шаге уменьшается на 1, значение \(E(s)\) зависит только от состояний с меньшим \(W\). Поэтому здесь не нужна ни имитация Монте-Карло, ни решение большой системы линейных уравнений. Достаточно один раз вычислить каждое достижимое состояние и сохранить результат.
Реализации на C++, Python и Java используют четыре счетчика листов как полное описание состояния и хранят уже найденные ожидания в хеш-таблице. Версии на C++ и Java упаковывают четыре числа в целочисленный ключ, а версия на Python использует сам кортеж как ключ. С математической точки зрения все три реализации мемоизируют одну и ту же функцию \(E(s)\).
Для каждого состояния программа сначала находит общее число листов \(T(s)\). Если конверт пуст, возвращается 0. Иначе прибавляется 1 тогда и только тогда, когда текущее состояние является засчитываемым одно-листовым случаем; затем перебираются все доступные форматы, строится соответствующее следующее состояние, рекурсивное значение умножается на вероятность \(a_k/T(s)\), и все вклады суммируются. После этого вычисление запускается из \((1,1,1,1)\), а результат выводится с точностью до шести знаков после запятой.
Пусть \(S\) обозначает число состояний, достижимых из \((1,1,1,1)\). Каждое состояние рассматривает не более четырех исходящих переходов, так что время работы равно \(O(S)\), а память тоже \(O(S)\).
В этой задаче \(S\) очень мало, поскольку для любого состояния выполняется \(W(s)\le 15\), а каждый шаг уменьшает \(W\) на единицу. Значит, глубина рекурсии не превосходит 15, и таблица мемоизации остается маленькой. Эффективность появляется потому, что случайный процесс с ветвлением заменяется однократным проходом по компактному ациклическому графу состояний.
تبدأ العملية الأسبوعية رسميًا بورقة \(A1\) واحدة، لكن بعد أول خطوة قصّ واستخدام يصبح الظرف محتويًا بالفعل على ورقة واحدة من كل من \(A2,A3,A4,A5\). لهذا السبب تبدأ التطبيقات من الحالة \(s_0=(1,1,1,1)\): ومن هذه اللحظة فصاعدًا تعني كل مهمة اختيار ورقة عشوائيًا وباحتمال متساوٍ من بين جميع الأوراق الموجودة، ثم قصّها إذا لزم الأمر حتى يمكن استخدام ورقة \(A5\)، وبعد ذلك تعاد القصاصات الأصغر المتبقية إلى الظرف.
المطلوب هو القيمة المتوقعة لعدد المرات اللاحقة التي يحتوي فيها الظرف على ورقة واحدة فقط. أمّا الحالة التي تبقى فيها ورقة \(A5\) وحيدة فلا تُحسب، لأنها تمثل وضع النهاية الخاص بآخر مهمة وليست حدثًا إضافيًا غير تافه من نوع "ورقة واحدة".
هذه مسألة توقع دقيقة على فضاء حالات منتهٍ. وبعد اختيار تمثيل الحالة المناسب، ينحصر الحل كله في علاقة تكرارية قصيرة من نوع ماركوف تُقيَّم باستخدام الحفظ في الذاكرة.
نكتب
$$s=(a_2,a_3,a_4,a_5),\qquad T(s)=a_2+a_3+a_4+a_5,$$
حيث تمثل \(a_k\) عدد أوراق \(A_k\) الموجودة حاليًا في الظرف. بعد المهمة الأولى لا يمكن أن تظهر إلا الأحجام \(A2,A3,A4,A5\)، ولذلك فإن هذه الأعداد الأربعة تصف العملية بالكامل. حالة البداية هي
$$s_0=(1,1,1,1).$$
الاختيار العشوائي يكون موزعًا بالتساوي على الأوراق الفردية لا على الأحجام، ولذلك فإن احتمال اختيار \(A_k\) يساوي \(a_k/T(s)\).
إذا اختيرت ورقة أكبر من \(A5\)، فإنها تُقصّ إلى أنصاف متتالية حتى يمكن استخدام ورقة \(A5\). أما البواقي المعادة إلى الظرف فهي بالضبط نسخة واحدة من كل حجم أصغر متوسط في سلسلة القص. لذلك تكون الحالات اللاحقة الممكنة هي
$$\begin{aligned} s^{(2)}&=(a_2-1,\ a_3+1,\ a_4+1,\ a_5+1),\\ s^{(3)}&=(a_2,\ a_3-1,\ a_4+1,\ a_5+1),\\ s^{(4)}&=(a_2,\ a_3,\ a_4-1,\ a_5+1),\\ s^{(5)}&=(a_2,\ a_3,\ a_4,\ a_5-1). \end{aligned}$$
وهذا يطابق تمامًا ما تنفذه التطبيقات: إزالة الورقة المختارة أولًا، ثم إضافة جميع الأوراق الأصغر التي تنتج عن سلسلة القص.
لرؤية سبب انتهاء العودية دائمًا، من المفيد قياس كمية الورق المتبقية بوحدات مكافئة لـ \(A5\):
$$W(s)=8a_2+4a_3+2a_4+a_5.$$
فورقة \(A2\) تعادل مساحة ثماني أوراق \(A5\)، وورقة \(A3\) تعادل أربع أوراق \(A5\)، وورقة \(A4\) تعادل ورقتين \(A5\). وفي أي انتقال من الانتقالات السابقة تُستهلك بالضبط وحدة مساحة واحدة من نوع \(A5\)، ولذلك
$$W\!\left(s^{(k)}\right)=W(s)-1\qquad\text{لكل }k\in\{2,3,4,5\}\text{ متاح.}$$
وبما أن \(W(1,1,1,1)=15\)، فلا يمكن أن تظهر دورات في العملية: كل خطوة تُنقص \(W\) إنقاصًا صارمًا، وبعد 15 مهمة يصبح الظرف فارغًا. وهكذا يتحول فضاء الحالات إلى رسم بياني موجه لا دوري صغير.
لتكن \(E(s)\) هي القيمة المتوقعة لعدد المرات المستقبلية التي يظهر فيها ظرف يحتوي على ورقة واحدة فقط ابتداءً من الحالة \(s\). الحالات الوحيدة ذات الورقة الواحدة التي تُحسب فعلًا هي
$$(1,0,0,0),\qquad(0,1,0,0),\qquad(0,0,1,0),$$
لأن الحالة \((0,0,0,1)\) هي حالة النهاية المستثناة. نعرّف مؤشر العدّ
$$I(s)=\begin{cases} 1, & T(s)=1\text{ و }a_5=0,\\ 0, & \text{في غير ذلك.} \end{cases}$$
أما حالة الظرف الفارغ فهي
$$E(0,0,0,0)=0.$$
ولكل حالة غير فارغة يعطي قانون التوقع الكلي العلاقة
$$E(s)=I(s)+\sum_{k=2}^{5}\frac{a_k}{T(s)}\,E\!\left(s^{(k)}\right),$$
مع حذف الحدود التي يكون فيها \(a_k=0\). ومن ثم فالقيمة المطلوبة في المسألة هي \(E(1,1,1,1)\).
لنأخذ أولًا الحالة \(s=(0,0,1,0)\)، أي إن الظرف يحتوي على ورقة \(A4\) واحدة فقط. هذه الحالة تُحسب مرة واحدة فورًا، والحالة التالية الوحيدة الممكنة هي \((0,0,0,1)\). إذًا
$$E(0,0,1,0)=1+E(0,0,0,1)=1.$$
أما حالة البداية فتُظهر التشعب الاحتمالي. بما أن \(T(1,1,1,1)=4\)، فإن كل حجم يُختار باحتمال \(1/4\)، ولذلك
$$E(1,1,1,1)=\frac14E(0,2,2,2)+\frac14E(1,0,2,2)+\frac14E(1,1,0,2)+\frac14E(1,1,1,0).$$
وجميع القيم اللاحقة تُستخرج بتكرار الصيغة نفسها على حالات أصغر في قيمة \(W\).
بما أن \(W(s)\) ينخفض بمقدار 1 في كل خطوة، فإن \(E(s)\) لا يعتمد إلا على حالات ذات \(W\) أصغر. لذلك لا حاجة إلى محاكاة مونت كارلو ولا إلى حل نظام خطي كبير. يكفي حساب كل حالة قابلة للوصول مرة واحدة وتخزين نتيجتها.
تستخدم تطبيقات C++ وPython وJava أعداد الأوراق الأربعة بوصفها التمثيل الكامل للحالة، ثم تحفظ قيم التوقع المحسوبة مسبقًا في جدول تجزئة. نسختا C++ وJava تضغطان العدادات الأربعة داخل مفتاح عددي، أما نسخة Python فتستخدم الرباعية نفسها كمفتاح. لكن من الناحية الرياضية فإن النسخ الثلاث كلها تحفظ الدالة نفسها \(E(s)\).
في كل حالة تحسب التطبيقات أولًا العدد الكلي للأوراق \(T(s)\). فإذا كان الظرف فارغًا تُعاد القيمة 0. وإلا تُضاف \(1\) فقط عندما تكون الحالة الحالية من حالات الورقة الواحدة التي يجب عدّها، ثم تُفحَص الأحجام المتاحة، ويُبنى الانتقال الموافق، وتُضرب القيمة العودية في الاحتمال \(a_k/T(s)\)، ثم تُجمَع المساهمات كلها. وفي النهاية يبدأ الحساب من \((1,1,1,1)\) وتُطبع النتيجة حتى ست منازل عشرية.
إذا رمزنا بعدد الحالات القابلة للوصول من \((1,1,1,1)\) بالرمز \(S\)، فإن كل حالة تفحص في الأكثر أربع انتقالات خارجة، لذا يكون الزمن الكلي \(O(S)\) وتكون الذاكرة أيضًا \(O(S)\).
في هذه المسألة تكون \(S\) صغيرة جدًا، لأن كل حالة تحقق \(W(s)\le 15\) وكل خطوة تُنقص \(W\) بمقدار واحد. لذلك لا يتجاوز عمق العودية 15، ويبقى جدول التخزين المؤقت صغيرًا. مصدر الكفاءة هنا هو تحويل عملية عشوائية كثيرة التشعب إلى تقييم واحد لرسم بياني صغير لا دوري للحالات.