There are \(n\) labeled participants and initially two slips carrying each label. The participants act in the order \(1,2,\dots,n-1\). When participant \(k\) acts, every remaining slip labeled \(k\) is forbidden to that participant, and then two admissible slips are drawn uniformly without replacement. The quantity \(q(n)\) is the probability that when the final participant is reached, at least one slip carrying label \(n\) is still present.
A direct history-by-history simulation would branch far too much, because the exact identity of many remaining slips quickly stops mattering. The key idea is to replace the full multiset of labels by a symmetry-reduced state that remembers only the information relevant for future exclusions and for the survival of label \(n\).
Let \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) be the success probability from stage \(k\), where the state variables mean:
\(\rho\): how many slips labeled \(k\) are still present, so they are forbidden at the current stage;
\(\mu\): how many slips labeled \(n\) are still present;
\(\sigma_1\): how many future intermediate labels currently have exactly one self-labeled slip left;
\(\sigma_2\): how many future intermediate labels currently have exactly two self-labeled slips left.
At stage \(k\), the total number of remaining slips is
$$T_k=2(n-k+1).$$
We do not need to remember every label separately. For any future intermediate participant, only the number \(0\), \(1\), or \(2\) of remaining self-labeled slips matters, because that number determines how many slips will be forbidden when that participant later becomes current. All labels in the same class are interchangeable.
The box therefore splits into four groups: the \(\rho\) forbidden slips of the current participant, the \(\mu\) slips of the final participant, the \(\sigma_1\) tracked slips belonging to class-1 future labels, and the \(2\sigma_2\) tracked slips belonging to class-2 future labels. Every other remaining slip can be merged into one generic pool. Its size is forced to be
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$$
This generic pool contains slips whose exact labels no longer matter individually: slips of already processed participants, and also non-critical slips from future labels whose exclusion status is already encoded by \(\sigma_1\) and \(\sigma_2\).
The current participant may draw from all slips except the \(\rho\) forbidden ones, so the admissible total is
$$A=T_k-\rho.$$
The four drawable categories have counts
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
If the first draw uses category \(u\) and the second uses category \(v\), then the ordered probability is
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$$
where \(c_v^{(u)}\) is the updated count after the first draw. Ordered pairs are necessary, because the second draw sees a different box.
The effect of one draw depends only on its category:
$$\begin{aligned} \text{generic draw} &:\quad \gamma\to\gamma-1,\\ \text{final-label draw} &:\quad \mu\to\mu-1,\\ \text{class-1 draw} &:\quad \sigma_1\to\sigma_1-1,\\ \text{class-2 draw} &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
The last line reflects a future label that used to have two self-labeled slips and now has only one. After two draws we obtain updated values \(\mu',\sigma_1',\sigma_2'\), while \(\gamma\) can always be recomputed from the conservation formula.
After stage \(k\), the next current participant is \(k+1\). The compressed state does not record which future label is \(k+1\); it records only how many future labels lie in class \(0\), \(1\), or \(2\). By symmetry, \(k+1\) is uniformly distributed over those future labels.
Let
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
If \(k=n-1\), there is no intermediate participant left, so the continuation is simply success or failure according to whether \(\mu'>0\).
Otherwise the continuation value is
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$$
This is the central symmetry step: instead of tracking identities, we average over the three possible classes of the next participant.
When the process reaches stage \(n\), the only question left is whether at least one slip labeled \(n\) survived. Therefore
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
At the start, participant \(1\) has both self-labeled slips still present, the final participant also has both of theirs, and every intermediate future participant starts in class \(2\). Hence
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
The initial state is \(\mathcal{F}_1(2,2,0,1)\). Participant \(1\) cannot draw the two slips labeled \(1\), so the admissible box contains exactly four slips: two labeled \(2\) and two labeled \(3\).
If both draws remove label \(3\), the probability is
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$$
and the process fails immediately because no slip labeled \(3\) remains.
If one draw removes label \(2\) and the other removes label \(3\), the total probability is
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$$
Then participant \(2\) reaches stage \(2\) with one forbidden self-slip and one surviving slip labeled \(3\). Among the three admissible slips, only one carries label \(3\), so participant \(2\) leaves that slip untouched with probability \(1/3\).
If both draws remove label \(2\), the probability is again \(1/6\). Then participant \(2\) faces four admissible slips, two of which are labeled \(3\); the only failure is drawing both of them, so the continuation probability is \(1-1/6=5/6\).
Combining the three cases gives
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all memoize the same five-parameter dynamic-programming state. The dense versions store values in a flattened table indexed by the stage and the four compressed counters, while the Python version uses a dictionary keyed by the same tuple. In every state, the implementation reconstructs the generic pool size from the conservation equation, computes the admissible total, and then loops over the \(4\times 4\) ordered category pairs for the two draws.
Pairs with zero count are skipped immediately. For each valid pair, the implementation applies the category updates twice, computes the continuation mixture over the three possible classes of the next participant, and adds the weighted contribution to the memoized answer. Because all symmetric labels are merged from the start, the program never needs to enumerate actual names or explicit draw histories.
The stage index contributes \(O(n)\) possibilities, the two slip counters \(\rho\) and \(\mu\) each range over \(\{0,1,2\}\), and the two future-class counters range up to \(n\). Therefore the worst-case state space is \(O(n^4)\). Each state performs at most \(16\) ordered draw transitions and a constant-size continuation mixture, so the running time is \(O(n^4)\) with a moderate constant factor. The dense table versions use \(O(n^4)\) memory, while the memoized dictionary version stores only the reachable subset, though the same worst-case bound still applies.
Es gibt \(n\) beschriftete Teilnehmer, und anfangs liegen von jedem Label genau zwei Zettel vor. Die Teilnehmer handeln in der Reihenfolge \(1,2,\dots,n-1\). Wenn Teilnehmer \(k\) an der Reihe ist, sind alle noch vorhandenen Zettel mit Label \(k\) für ihn verboten; anschließend werden zwei zulässige Zettel gleichverteilt ohne Zurücklegen gezogen. Die gesuchte Größe \(q(n)\) ist die Wahrscheinlichkeit, dass beim Erreichen des letzten Teilnehmers noch mindestens ein Zettel mit Label \(n\) vorhanden ist.
Eine naive Fallunterscheidung über alle möglichen Ziehungsverläufe wäre viel zu groß. Die Lösung speichert deshalb nicht die exakten Label aller verbleibenden Zettel, sondern nur eine symmetrie-reduzierte Zustandsbeschreibung, die für alle zukünftigen Verbote und für das Überleben des Labels \(n\) ausreicht.
Sei \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) die Erfolgswahrscheinlichkeit ab Stufe \(k\). Dabei bedeuten:
\(\rho\): Anzahl der noch vorhandenen Zettel mit Label \(k\), also der momentan verbotenen Zettel;
\(\mu\): Anzahl der noch vorhandenen Zettel mit Label \(n\);
\(\sigma_1\): Anzahl zukünftiger Zwischen-Labels mit genau einem verbleibenden Eigenzettel;
\(\sigma_2\): Anzahl zukünftiger Zwischen-Labels mit genau zwei verbleibenden Eigenzetteln.
In Stufe \(k\) gibt es insgesamt
$$T_k=2(n-k+1)$$
verbleibende Zettel. Für einen zukünftigen Zwischen-Teilnehmer ist nur wichtig, ob von seinem eigenen Label noch \(0\), \(1\) oder \(2\) Zettel übrig sind, denn genau das bestimmt später die Zahl seiner verbotenen Zettel. Alle Labels derselben Klasse sind also austauschbar.
Damit zerfällt die Box in vier Teile: die \(\rho\) verbotenen Zettel des aktuellen Teilnehmers, die \(\mu\) Zettel des letzten Teilnehmers, die \(\sigma_1\) verfolgten Zettel aus Klasse \(1\) und die \(2\sigma_2\) verfolgten Zettel aus Klasse \(2\). Alle übrigen Zettel können zu einem generischen Pool zusammengefasst werden. Seine Größe ist
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$$
In diesem Pool liegen Zettel, deren exakte Identität nicht mehr einzeln relevant ist: Zettel bereits abgearbeiteter Teilnehmer sowie unkritische Zettel zukünftiger Labels, deren Status schon durch \(\sigma_1\) und \(\sigma_2\) codiert ist.
Der aktuelle Teilnehmer darf aus allen Zetteln außer den \(\rho\) verbotenen ziehen. Daher ist die zulässige Gesamtzahl
$$A=T_k-\rho.$$
Die vier ziehbaren Kategorien besitzen die Anzahlen
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
Verwendet die erste Ziehung Kategorie \(u\) und die zweite Kategorie \(v\), dann ist die geordnete Wahrscheinlichkeit
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$$
wobei \(c_v^{(u)}\) die nach der ersten Ziehung aktualisierte Anzahl bezeichnet. Geordnete Paare sind nötig, weil die zweite Ziehung eine veränderte Box sieht.
Eine einzelne Ziehung verändert den Zustand nur entsprechend ihrer Kategorie:
$$\begin{aligned} \text{generische Ziehung} &:\quad \gamma\to\gamma-1,\\ \text{Ziehung von Label } n &:\quad \mu\to\mu-1,\\ \text{Ziehung aus Klasse } 1 &:\quad \sigma_1\to\sigma_1-1,\\ \text{Ziehung aus Klasse } 2 &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
Die letzte Zeile bedeutet: Ein zukünftiges Label mit bisher zwei Eigenzetteln fällt nach einer solchen Ziehung in Klasse \(1\). Nach zwei Ziehungen erhalten wir aktualisierte Werte \(\mu',\sigma_1',\sigma_2'\); \(\gamma\) wird bei Bedarf wieder aus der Erhaltungsgleichung bestimmt.
Nach Stufe \(k\) ist der nächste aktuelle Teilnehmer \(k+1\). Die komprimierte Beschreibung merkt sich nicht, welches konkrete zukünftige Label gleich als Nächstes kommt; sie kennt nur die Anzahl der künftigen Labels in den Klassen \(0\), \(1\) und \(2\). Wegen der Symmetrie ist \(k+1\) unter diesen verbleibenden Labels gleichverteilt.
Setze
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
Falls \(k=n-1\), bleibt kein Zwischen-Teilnehmer mehr übrig, also hängt die Fortsetzung nur noch davon ab, ob \(\mu'>0\) gilt.
Andernfalls lautet der Fortsetzungswert
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$$
Genau hier spart die Symmetrie den exponentiellen Aufwand: Statt Identitäten zu verfolgen, mitteln wir nur über die drei möglichen Klassen des nächsten Teilnehmers.
Beim Erreichen von Stufe \(n\) ist nur noch wichtig, ob wenigstens ein Zettel mit Label \(n\) überlebt hat. Also
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
Zu Beginn besitzt Teilnehmer \(1\) beide Eigenzettel, der letzte Teilnehmer ebenfalls beide, und jeder Zwischen-Teilnehmer startet in Klasse \(2\). Damit gilt
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
Der Anfangszustand ist \(\mathcal{F}_1(2,2,0,1)\). Teilnehmer \(1\) darf die beiden Zettel mit Label \(1\) nicht ziehen, also enthält die zulässige Box genau vier Zettel: zwei mit Label \(2\) und zwei mit Label \(3\).
Werden beide Züge von Label \(3\) getroffen, dann ist die Wahrscheinlichkeit
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$$
und der Erfolg ist sofort unmöglich, weil kein Zettel mit Label \(3\) übrig bleibt.
Fällt eine Ziehung auf Label \(2\) und die andere auf Label \(3\), so ist die Gesamtwahrscheinlichkeit
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$$
Dann erreicht Teilnehmer \(2\) die zweite Stufe mit genau einem verbotenen Eigenzettel und einem verbleibenden Zettel mit Label \(3\). Unter den drei zulässigen Zetteln trägt genau einer das Label \(3\), also bleibt dieser mit Wahrscheinlichkeit \(1/3\) unangetastet.
Werden beide Züge auf Label \(2\) ausgeführt, so ist die Wahrscheinlichkeit ebenfalls \(1/6\). Teilnehmer \(2\) sieht dann vier zulässige Zettel, von denen zwei Label \(3\) tragen; nur wenn er beide zieht, scheitert der Prozess. Daher ist die Fortsetzung \(1-1/6=5/6\).
Somit folgt
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
genau der Kontrollwert aus der Implementierung.
Die Implementierungen in C++, Python und Java memoizieren denselben DP-Zustand mit fünf Parametern. Die dichten Varianten speichern Werte in einer abgeflachten Tabelle, die über Stufe und Zähler adressiert wird; die Python-Version verwendet ein Wörterbuch mit demselben Schlüssel-Tupel. In jedem Zustand rekonstruiert die Implementierung zunächst den generischen Pool aus der Erhaltungsgleichung, bestimmt die Zahl zulässiger Zettel und durchläuft dann die \(4\times 4\) geordneten Kategorienpaare der beiden Ziehungen.
Kategorien mit Anzahl \(0\) werden sofort übersprungen. Für jedes gültige Paar werden die Zustandszähler zweimal aktualisiert, danach die symmetrische Mischung über die drei möglichen Klassen des nächsten Teilnehmers gebildet, und der gewichtete Beitrag wird zur memoisierten Antwort addiert. Gerade weil symmetrische Labels von Beginn an zusammengelegt werden, muss das Programm nie explizite Namensverläufe enumerieren.
Der Stufenindex liefert \(O(n)\) Möglichkeiten, die Zähler \(\rho\) und \(\mu\) haben jeweils nur die Werte \(0,1,2\), und die beiden Klassenzähler reichen bis \(n\). Daraus ergibt sich im Worst Case ein Zustandsraum von \(O(n^4)\). Pro Zustand werden höchstens \(16\) geordnete Ziehungsübergänge und eine Fortsetzung konstanter Größe ausgewertet. Somit beträgt die Laufzeit \(O(n^4)\) mit moderatem konstanten Faktor. Die dichten Tabellenvarianten benötigen \(O(n^4)\) Speicher; die Wörterbuch-Variante speichert nur den erreichbaren Teil, besitzt aber dieselbe Worst-Case-Schranke.
\(n\) adet etiketli katılımcı vardır ve başlangıçta her etiketten iki kağıt bulunur. Katılımcılar \(1,2,\dots,n-1\) sırasıyla işlem yapar. Katılımcı \(k\) sırasında, üzerinde \(k\) etiketi olan tüm kalan kağıtlar o kişi için yasaktır; ardından uygun kağıtlardan yerine koymadan rastgele iki tane çekilir. \(q(n)\), son katılımcının sırası geldiğinde üzerinde \(n\) etiketi bulunan en az bir kağıdın hala kutuda kalmış olma olasılığıdır.
Olası tüm çekiliş geçmişlerini tek tek izlemek çok pahalıdır. Çözüm bunun yerine kalan kağıtların tam kimliğini tutmaz; gelecekteki yasakları ve \(n\) etiketinin hayatta kalmasını belirleyen bilgiyi koruyan simetri azaltılmış bir durum kullanır.
\(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\), \(k\). aşamadaki başarı olasılığı olsun. Burada:
\(\rho\): üzerinde \(k\) etiketi bulunan ve bu aşamada yasak olan kağıt sayısı;
\(\mu\): üzerinde \(n\) etiketi bulunan kalan kağıt sayısı;
\(\sigma_1\): gelecekteki ara etiketlerden kendi etiketinden tam bir kağıdı kalmış olanların sayısı;
\(\sigma_2\): gelecekteki ara etiketlerden kendi etiketinden tam iki kağıdı kalmış olanların sayısı.
\(k\). aşamada toplam kalan kağıt sayısı
$$T_k=2(n-k+1)$$
olur. Gelecekteki bir ara katılımcı için önemli olan tek şey, kendi etiketinden \(0\), \(1\) ya da \(2\) kağıt kalıp kalmadığıdır; çünkü daha sonra yasak olacak kağıt sayısını belirleyen şey tam olarak budur. Aynı sınıftaki etiketler bu yüzden birbirinden ayırt edilmek zorunda değildir.
Böylece kutu dört parçaya ayrılır: mevcut katılımcının \(\rho\) yasak kağıdı, son katılımcının \(\mu\) kağıdı, sınıf \(1\) içindeki gelecekteki etiketlere ait \(\sigma_1\) izlenen kağıt ve sınıf \(2\) içindeki gelecekteki etiketlere ait \(2\sigma_2\) izlenen kağıt. Geri kalan her şey tek bir genel havuzda birleştirilebilir. Bu havuzun büyüklüğü zorunlu olarak
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2$$
olur. Bu genel havuz, artık tek tek kimliği önemli olmayan kağıtları içerir: sırası geçmiş katılımcılara ait kağıtlar ile, durumu zaten \(\sigma_1\) ve \(\sigma_2\) tarafından temsil edilen gelecekteki etiketlerin kritik olmayan kağıtları.
Mevcut katılımcı, yalnızca \(\rho\) yasak kağıt dışındaki kağıtlardan çekebilir. Dolayısıyla uygun toplam
$$A=T_k-\rho$$
olur. Çekilebilen dört kategori şu adetlere sahiptir:
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
İlk çekiliş kategori \(u\), ikinci çekiliş kategori \(v\) ise sıralı olasılık
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1}$$
şeklindedir. Burada \(c_v^{(u)}\), ilk çekilişten sonraki güncellenmiş sayıdır. Çekilişler sıralı değerlendirilmelidir; çünkü ikinci çekiliş farklı bir kutudan yapılır.
Tek bir çekilişin etkisi sadece hangi kategoriye düştüğüne bağlıdır:
$$\begin{aligned} \text{genel havuz çekilişi} &:\quad \gamma\to\gamma-1,\\ \text{son etiket çekilişi} &:\quad \mu\to\mu-1,\\ \text{sınıf } 1 \text{ çekilişi} &:\quad \sigma_1\to\sigma_1-1,\\ \text{sınıf } 2 \text{ çekilişi} &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
Son satırın anlamı şudur: Kendi etiketinden iki kağıdı kalan bir gelecekteki etiket, bunlardan biri çekilince sınıf \(1\)'e düşer. İki çekiliş sonunda \(\mu',\sigma_1',\sigma_2'\) değerleri elde edilir; \(\gamma\) ise korunma eşitliğinden her zaman yeniden hesaplanabilir.
\(k\). aşamadan sonra sıradaki mevcut katılımcı \(k+1\) olur. Ancak sıkıştırılmış durumda hangi somut etiketin \(k+1\) olduğu tutulmaz; yalnızca kalan gelecek etiketlerin kaç tanesinin sınıf \(0\), \(1\) ve \(2\) içinde olduğu bilinir. Simetri nedeniyle \(k+1\), bu etiketler arasında düzgün dağılmış gibi ortalanabilir.
Şunları yazalım:
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
Eğer \(k=n-1\) ise arada başka katılımcı kalmaz; bu durumda devam değeri yalnızca \(\mu'>0\) olup olmadığına bağlıdır.
Aksi halde devam terimi
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1)$$
olur. Kimlikleri tek tek takip etmek yerine yalnızca bir sonraki katılımcının hangi sınıftan geleceği üzerinden ortalama almak, patlayan durum sayısını kontrol altında tutar.
Süreç \(n\). aşamaya ulaştığında geriye kalan tek soru, üzerinde \(n\) etiketi bulunan en az bir kağıdın hayatta kalıp kalmadığıdır. Bu yüzden
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
Başlangıçta birinci katılımcının iki öz kağıdı da durur, son katılımcının da iki kağıdı vardır ve aradaki tüm katılımcılar sınıf \(2\)'dedir. Dolayısıyla
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
Başlangıç durumu \(\mathcal{F}_1(2,2,0,1)\)'dir. Katılımcı \(1\), üzerinde \(1\) etiketi olan iki kağıdı çekemez; uygun kutuda yalnızca dört kağıt kalır: iki tane \(2\), iki tane \(3\).
Eğer iki çekiliş de \(3\) etiketine giderse olasılık
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6}$$
olur ve artık \(3\) etiketi kalmadığı için süreç hemen başarısızdır.
Biri \(2\), diğeri \(3\) gelirse toplam olasılık
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}$$
olur. Bu durumda katılımcı \(2\), bir yasak öz kağıt ve bir adet yaşayan \(3\) etiketiyle ikinci aşamaya gelir. Uygun üç kağıttan yalnızca biri \(3\) olduğundan, onu dokunmadan bırakma olasılığı \(1/3\)'tür.
İki çekiliş de \(2\) olursa olasılık yine \(1/6\)'dır. O zaman katılımcı \(2\), dördü de uygun olan dört kağıt görür; bunların ikisi \(3\) etiketlidir. Tek başarısızlık her iki \(3\)'ü de çekmesidir, dolayısıyla devam olasılığı \(1-1/6=5/6\) olur.
Sonuç olarak
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
ve bu değer uygulamadaki kontrol sonucu ile aynıdır.
C++, Python ve Java implementasyonları aynı beş parametreli dinamik programlama durumunu memoize eder. Yoğun tablo kullanan sürümler, aşama ve sayaçları tek boyutlu bir depolama alanına düzleyerek saklar; Python sürümü ise aynı bilgiyi bir sözlük anahtarı olarak tutar. Her durumda önce korunma eşitliğinden genel havuz büyüklüğü çıkarılır, sonra uygun toplam hesaplanır ve iki çekiliş için \(4\times 4\) sıralı kategori çifti dolaşılır.
Adedi sıfır olan çiftler anında atlanır. Geçerli her çift için sayaçlar iki kez güncellenir, ardından bir sonraki katılımcının üç olası sınıfı üzerinden devam karışımı hesaplanır ve ağırlıklı katkı kayıtlı cevaba eklenir. Simetrik etiketler en baştan birleştirildiği için gerçek isimleri ya da açık çekiliş geçmişlerini tek tek üretmeye hiç gerek kalmaz.
Aşama indeksi \(O(n)\) değer alır; \(\rho\) ve \(\mu\) sayaçları yalnızca \(0,1,2\) olabilir; iki sınıf sayacı da \(n\)'e kadar çıkar. Bu nedenle en kötü durumda durum uzayı \(O(n^4)\) büyüklüğündedir. Her durumda en fazla \(16\) sıralı çekiliş geçişi ve sabit boyutlu bir devam karışımı hesaplanır; dolayısıyla zaman karmaşıklığı \(O(n^4)\) olur. Yoğun tablo kullanan sürümler \(O(n^4)\) bellek tüketir; sözlük tabanlı sürüm yalnızca erişilen durumları saklasa da en kötü durum sınırı yine aynıdır.
Hay \(n\) participantes etiquetados y al principio existen dos papeletas con cada etiqueta. Los participantes actúan en el orden \(1,2,\dots,n-1\). Cuando le toca al participante \(k\), todas las papeletas restantes con etiqueta \(k\) le están prohibidas, y luego se extraen dos papeletas admisibles de manera uniforme y sin reemplazo. La cantidad \(q(n)\) es la probabilidad de que, cuando llegue el turno del participante final, todavía quede al menos una papeleta con la etiqueta \(n\).
Seguir todas las historias posibles una por una sería demasiado costoso. La solución sustituye el multiconjunto completo por un estado comprimido por simetría que conserva solo la información que realmente influye en las restricciones futuras y en la supervivencia de la etiqueta \(n\).
Sea \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) la probabilidad de éxito desde la etapa \(k\). Los parámetros significan:
\(\rho\): cuántas papeletas con etiqueta \(k\) siguen presentes y por tanto están prohibidas ahora;
\(\mu\): cuántas papeletas con etiqueta \(n\) siguen presentes;
\(\sigma_1\): cuántas etiquetas futuras intermedias conservan exactamente una papeleta propia;
\(\sigma_2\): cuántas etiquetas futuras intermedias conservan exactamente dos papeletas propias.
En la etapa \(k\), el número total de papeletas restantes es
$$T_k=2(n-k+1).$$
Para un participante futuro intermedio, lo único importante es si de su propia etiqueta quedan \(0\), \(1\) o \(2\) papeletas, porque eso determina cuántas papeletas le estarán prohibidas cuando llegue su turno. Las etiquetas que pertenecen a la misma clase son intercambiables.
Por eso la caja se divide en cuatro partes: las \(\rho\) papeletas prohibidas del participante actual, las \(\mu\) papeletas del participante final, las \(\sigma_1\) papeletas rastreadas de las etiquetas futuras de clase \(1\), y las \(2\sigma_2\) papeletas rastreadas de las etiquetas futuras de clase \(2\). Todo lo demás se puede fusionar en un único grupo genérico. Su tamaño viene dado por
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$$
Ese grupo genérico contiene papeletas cuya identidad exacta ya no importa por separado: papeletas de participantes ya procesados y también papeletas no críticas de etiquetas futuras cuyo estado ya está resumido por \(\sigma_1\) y \(\sigma_2\).
El participante actual puede extraer cualquier papeleta salvo las \(\rho\) prohibidas, así que el total admisible es
$$A=T_k-\rho.$$
Las cuatro categorías extraíbles tienen tamaños
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
Si la primera extracción usa la categoría \(u\) y la segunda la categoría \(v\), entonces la probabilidad ordenada es
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$$
donde \(c_v^{(u)}\) es el recuento actualizado tras la primera extracción. Hay que trabajar con pares ordenados porque la segunda extracción ve una caja distinta.
El efecto de una sola extracción depende únicamente de la categoría elegida:
$$\begin{aligned} \text{extracción genérica} &:\quad \gamma\to\gamma-1,\\ \text{extracción de la etiqueta final} &:\quad \mu\to\mu-1,\\ \text{extracción de clase } 1 &:\quad \sigma_1\to\sigma_1-1,\\ \text{extracción de clase } 2 &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
La última línea significa que una etiqueta futura que antes conservaba dos papeletas propias pasa a la clase \(1\) después de perder una de ellas. Tras dos extracciones obtenemos \(\mu',\sigma_1',\sigma_2'\), mientras que \(\gamma\) siempre puede reconstruirse a partir de la ecuación de conservación.
Después de la etapa \(k\), el siguiente participante actual es \(k+1\). El estado comprimido no guarda cuál es exactamente esa etiqueta futura; solo guarda cuántas etiquetas futuras quedan en las clases \(0\), \(1\) y \(2\). Por simetría, \(k+1\) puede tratarse como una etiqueta uniformemente distribuida entre esas futuras etiquetas.
Definimos
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
Si \(k=n-1\), ya no queda ningún participante intermedio y la continuación se reduce simplemente a comprobar si \(\mu'>0\).
En caso contrario, el valor de continuación es
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$$
Este promedio es el paso decisivo que evita seguir identidades concretas: solo importa la clase del siguiente participante.
Cuando el proceso llega a la etapa \(n\), la única pregunta que queda es si sobrevive al menos una papeleta con etiqueta \(n\). Por lo tanto,
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
Al comienzo, el participante \(1\) conserva sus dos papeletas propias, el participante final también conserva las suyas, y todos los participantes intermedios están en la clase \(2\). Así,
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
El estado inicial es \(\mathcal{F}_1(2,2,0,1)\). El participante \(1\) no puede tomar las dos papeletas con etiqueta \(1\), de modo que la caja admisible contiene exactamente cuatro papeletas: dos con etiqueta \(2\) y dos con etiqueta \(3\).
Si ambas extracciones eliminan la etiqueta \(3\), la probabilidad es
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$$
y el proceso fracasa inmediatamente porque ya no queda ninguna papeleta con etiqueta \(3\).
Si una extracción elimina una etiqueta \(2\) y la otra una etiqueta \(3\), la probabilidad total es
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$$
Entonces el participante \(2\) llega a la etapa siguiente con una sola papeleta propia prohibida y con una única papeleta superviviente de etiqueta \(3\). Entre sus tres papeletas admisibles, solo una tiene etiqueta \(3\), así que deja intacta esa papeleta con probabilidad \(1/3\).
Si ambas extracciones eliminan la etiqueta \(2\), la probabilidad vuelve a ser \(1/6\). Entonces el participante \(2\) ve cuatro papeletas admisibles, dos de ellas con etiqueta \(3\); la única forma de fracasar es retirar las dos, así que la continuación vale \(1-1/6=5/6\).
En consecuencia,
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
exactamente el valor de control usado por la implementación.
Las implementaciones en C++, Python y Java memorizan el mismo estado de programación dinámica con cinco parámetros. Las versiones densas almacenan los valores en una tabla aplanada indexada por la etapa y por los cuatro contadores comprimidos, mientras que la versión en Python usa un diccionario con la misma tupla como clave. En cada estado, la implementación reconstruye el tamaño del grupo genérico a partir de la ecuación de conservación, calcula el total admisible y recorre los \(4\times 4\) pares ordenados de categorías para las dos extracciones.
Las categorías con recuento nulo se descartan enseguida. Para cada par válido se aplican dos actualizaciones de estado, se calcula la mezcla de continuación sobre las tres clases posibles del siguiente participante y se acumula la contribución ponderada. Gracias a la compresión por simetría, nunca hace falta enumerar identidades concretas ni historias explícitas de extracción.
El índice de etapa aporta \(O(n)\) posibilidades; los contadores \(\rho\) y \(\mu\) solo pueden valer \(0\), \(1\) o \(2\); y los dos contadores de clases futuras llegan hasta \(n\). Por tanto, el número de estados es \(O(n^4)\) en el peor caso. Cada estado evalúa como máximo \(16\) transiciones ordenadas de extracción y una mezcla de continuación de tamaño constante, de modo que el tiempo total es \(O(n^4)\). Las versiones con tabla densa usan \(O(n^4)\) memoria; la versión con diccionario guarda solo el subconjunto alcanzable, aunque conserva la misma cota asintótica máxima.
共有 \(n\) 个带标签的参与者，初始时每个标签各有两张纸条。参与者按 \(1,2,\dots,n-1\) 的顺序行动。轮到第 \(k\) 个参与者时，所有仍然带有标签 \(k\) 的纸条都不能被他抽到；然后他会从其余可抽取的纸条中等概率地不放回抽取两张。题目中的 \(q(n)\) 就是这样一个概率：当轮到最后一位参与者时，盒子里是否还至少剩下一张标签为 \(n\) 的纸条。
如果直接记录所有可能的抽签历史，状态数会迅速爆炸。真正可行的办法是利用对称性，不再关心每一张剩余纸条的具体身份，而只保留那些会影响未来“禁止抽到自己”规则以及标签 \(n\) 是否存活的信息。
记 \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) 为从第 \(k\) 阶段开始最终成功的概率，其中：
\(\rho\)：当前参与者自己的标签 \(k\) 还剩多少张，因此这些纸条在本阶段是禁止的；
\(\mu\)：标签 \(n\) 还剩多少张；
\(\sigma_1\)：未来中间参与者里，有多少个标签还恰好剩下一张“自己的标签”纸条；
\(\sigma_2\)：未来中间参与者里，有多少个标签还恰好剩下两张“自己的标签”纸条。
在第 \(k\) 阶段，剩余纸条总数为
$$T_k=2(n-k+1).$$
对于未来某个尚未出场的中间参与者来说，真正重要的不是它的具体编号，而是“它自己的标签还剩 \(0\)、\(1\) 还是 \(2\) 张”。因为等到那个参与者出场时，被禁止的纸条数量正是由这个数决定的。同一类里的标签彼此完全等价，可以合并统计。
因此，盒子里的纸条可以分成四部分：当前参与者的 \(\rho\) 张禁抽纸条、最后一位参与者标签对应的 \(\mu\) 张纸条、未来 class-1 标签贡献的 \(\sigma_1\) 张被跟踪纸条，以及未来 class-2 标签贡献的 \(2\sigma_2\) 张被跟踪纸条。除此之外的所有纸条都可以并入一个“普通池”。它的大小必然是
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$$
这个普通池包括两类对象：已经处理过的参与者所对应的纸条，以及未来标签中那些虽然还在盒子里、但其是否属于“自己的标签”这一关键信息已经被 \(\sigma_1\) 和 \(\sigma_2\) 统计掉的非关键纸条。
当前参与者只能从除去 \(\rho\) 张禁抽纸条之外的纸条中选择，因此可抽总数为
$$A=T_k-\rho.$$
四种可抽类别的数量分别是
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
如果第一次抽到的是类别 \(u\)，第二次抽到的是类别 \(v\)，那么这个有序结果的概率为
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$$
其中 \(c_v^{(u)}\) 表示在第一次抽取完成之后，第二次抽取所面对的更新后数量。之所以必须按有序对处理，是因为第二次抽取看到的盒子已经发生了变化。
一次抽取的影响只与它来自哪一类有关：
$$\begin{aligned} \text{普通池抽取} &:\quad \gamma\to\gamma-1,\\ \text{抽到标签 } n &:\quad \mu\to\mu-1,\\ \text{抽到 class-1} &:\quad \sigma_1\to\sigma_1-1,\\ \text{抽到 class-2} &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
最后一行的含义是：某个未来标签原本还有两张“自己的标签”纸条，抽走其中一张之后，它就从 class-2 变成了 class-1。两次抽取结束后，我们得到新的 \(\mu',\sigma_1',\sigma_2'\)；而 \(\gamma\) 仍然可以随时用守恒公式重新算出。
完成第 \(k\) 阶段后，下一位当前参与者是 \(k+1\)。压缩状态并不知道未来哪一个具体标签就是 \(k+1\)，它只知道未来标签中有多少个属于 class-0、class-1、class-2。由于这些未来标签在压缩后是对称的，所以可以把 \(k+1\) 看成在这些未来标签中均匀抽到的一个。
记
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
若 \(k=n-1\)，说明中间参与者已经全部处理完，接下来只需要判断 \(\mu'>0\) 是否成立。
否则，后继期望为
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$$
这一步是整个做法最关键的地方：我们不追踪“下一位究竟是谁”，而是只追踪“下一位属于哪一类”，于是状态空间从按身份爆炸变成按计数聚合。
当过程推进到第 \(n\) 阶段时，唯一剩下的问题就是：标签 \(n\) 是否至少还活着一张纸条。因此
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
初始时，第 \(1\) 位参与者自己的两张纸条都在，最后一位参与者的两张纸条也都在，而中间的每个未来参与者都属于 class-2，所以
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
初始状态是 \(\mathcal{F}_1(2,2,0,1)\)。第 \(1\) 位参与者不能抽到两张标签为 \(1\) 的纸条，因此可抽盒子里恰好只有四张：两张标签为 \(2\)，两张标签为 \(3\)。
如果两次都抽到标签 \(3\)，概率为
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$$
这时标签 \(3\) 已经全部消失，过程立刻失败。
如果一次抽到标签 \(2\)，一次抽到标签 \(3\)，总概率为
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$$
此时到第 \(2\) 阶段时，参与者 \(2\) 还有一张自己的禁抽纸条，而标签 \(3\) 也只剩一张。在他可抽的三张纸条中，只有一张是标签 \(3\)，所以把它保留下来的概率是 \(1/3\)。
如果两次都抽到标签 \(2\)，概率同样是 \(1/6\)。这时参与者 \(2\) 面前有四张都可抽的纸条，其中两张是标签 \(3\)。唯一失败的情况是把两张 \(3\) 都抽走，所以后继成功概率是 \(1-1/6=5/6\)。
因此
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
这正好与实现中的校验值一致。
C++、Python 和 Java 的实现都记忆化了同一个五参数动态规划状态。C++ 与 Java 使用扁平化后的连续表来存储由阶段和四个压缩计数确定的值；Python 则使用以同一状态元组为键的字典。对每个状态，程序先根据守恒关系重建普通池大小，再算出当前可抽总数，然后遍历两次抽取对应的 \(4\times 4\) 个有序类别组合。
数量为零的类别会被立即跳过。对每个有效组合，程序执行两次状态更新，随后按照下一位参与者可能属于的三种类别计算后继加权平均，并把这一贡献累加到记忆化结果中。因为对称标签从一开始就被合并了，所以实现完全不需要枚举真实姓名或显式抽签路径。
阶段编号有 \(O(n)\) 种可能，\(\rho\) 和 \(\mu\) 都只可能取 \(0,1,2\)，而两个未来类别计数最多增长到 \(n\)。因此最坏情况下状态数为 \(O(n^4)\)。每个状态最多考察 \(16\) 个有序抽取转移以及一个常数规模的后继混合，所以总时间复杂度为 \(O(n^4)\)。使用稠密表的版本需要 \(O(n^4)\) 内存；字典记忆化版本虽然通常只保存可达状态，但最坏情况下的渐近上界仍然相同。
Есть \(n\) участников с метками, и изначально для каждой метки лежат две бумажки. Участники действуют в порядке \(1,2,\dots,n-1\). Когда ходит участник \(k\), все оставшиеся бумажки с меткой \(k\) запрещены для него, а затем из допустимых бумажек равновероятно вытягиваются две без возвращения. Величина \(q(n)\) означает вероятность того, что к моменту хода последнего участника в коробке останется хотя бы одна бумажка с меткой \(n\).
Перебирать все истории вытягиваний напрямую слишком дорого. Поэтому решение не хранит точный набор оставшихся меток, а использует сжатое состояние, где сохраняется только информация, влияющая на будущие запреты и на выживание метки \(n\).
Обозначим через \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) вероятность успеха, начиная с шага \(k\). Здесь:
\(\rho\): сколько бумажек с меткой \(k\) еще осталось, то есть сколько бумажек сейчас запрещено;
\(\mu\): сколько бумажек с меткой \(n\) еще осталось;
\(\sigma_1\): сколько будущих промежуточных меток имеют ровно одну оставшуюся собственную бумажку;
\(\sigma_2\): сколько будущих промежуточных меток имеют ровно две оставшиеся собственные бумажки.
На шаге \(k\) общее число оставшихся бумажек равно
$$T_k=2(n-k+1).$$
Для любого будущего промежуточного участника важно только то, сколько его собственных бумажек осталось: \(0\), \(1\) или \(2\). Именно это число определит, сколько бумажек будет запрещено, когда до него дойдет очередь. Метки из одного и того же класса можно считать неразличимыми.
Значит, коробка распадается на четыре части: \(\rho\) запрещенных бумажек текущего участника, \(\mu\) бумажек последнего участника, \(\sigma_1\) отслеживаемых бумажек будущих меток класса \(1\) и \(2\sigma_2\) отслеживаемых бумажек будущих меток класса \(2\). Все остальные бумажки можно объединить в один общий пул. Его размер равен
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$$
В общий пул попадают бумажки уже обработанных участников, а также несущественные по отдельности бумажки будущих меток, для которых критический статус уже полностью описан числами \(\sigma_1\) и \(\sigma_2\).
Текущий участник может тянуть любые бумажки, кроме \(\rho\) запрещенных, поэтому число допустимых бумажек равно
$$A=T_k-\rho.$$
Размеры четырех извлекаемых категорий таковы:
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
Если первая вытянутая бумажка относится к категории \(u\), а вторая к категории \(v\), то вероятность упорядоченной пары равна
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$$
где \(c_v^{(u)}\) означает обновленное количество перед второй вытяжкой. Упорядоченность важна, потому что после первой вытяжки содержимое коробки меняется.
Эффект одной вытяжки зависит только от категории:
$$\begin{aligned} \text{обычная вытяжка} &:\quad \gamma\to\gamma-1,\\ \text{вытяжка метки } n &:\quad \mu\to\mu-1,\\ \text{вытяжка из класса } 1 &:\quad \sigma_1\to\sigma_1-1,\\ \text{вытяжка из класса } 2 &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
Последняя строка означает, что будущая метка, у которой раньше оставались две собственные бумажки, после потери одной переходит в класс \(1\). После двух вытяжек мы получаем обновленные \(\mu',\sigma_1',\sigma_2'\), а \(\gamma\) всегда можно восстановить из закона сохранения.
После шага \(k\) следующим текущим участником станет \(k+1\). Сжатое состояние не хранит, какая именно будущая метка соответствует \(k+1\); оно знает только, сколько будущих меток находится в классах \(0\), \(1\) и \(2\). По симметрии \(k+1\) можно считать равномерно выбранным из этих будущих меток.
Положим
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
Если \(k=n-1\), то промежуточных участников больше нет, и продолжение определяется только условием \(\mu'>0\).
Иначе значение продолжения равно
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$$
Это и есть главный прием: вместо отслеживания конкретных личностей мы усредняем только по трем возможным классам следующего участника.
Когда процесс доходит до шага \(n\), остается единственный вопрос: выжила ли хотя бы одна бумажка с меткой \(n\). Поэтому
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
В начальный момент у участника \(1\) есть обе собственные бумажки, у последнего участника тоже обе, а каждый промежуточный будущий участник находится в классе \(2\). Следовательно,
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
Начальное состояние равно \(\mathcal{F}_1(2,2,0,1)\). Участник \(1\) не может вытянуть две бумажки с меткой \(1\), поэтому допустимая коробка состоит ровно из четырех бумажек: двух с меткой \(2\) и двух с меткой \(3\).
Если обе вытяжки убирают метку \(3\), то вероятность равна
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$$
и успех невозможен сразу, потому что метка \(3\) полностью исчезает.
Если одна вытяжка убирает метку \(2\), а другая метку \(3\), суммарная вероятность равна
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$$
Тогда на шаге \(2\) у участника \(2\) остается одна запрещенная собственная бумажка и одна выжившая бумажка с меткой \(3\). Среди трех допустимых бумажек только одна несет метку \(3\), значит, вероятность оставить ее нетронутой равна \(1/3\).
Если обе вытяжки убирают метку \(2\), вероятность снова равна \(1/6\). Тогда участник \(2\) видит четыре допустимые бумажки, из которых две имеют метку \(3\); единственный способ проиграть состоит в том, чтобы вытянуть их обе, поэтому продолжение равно \(1-1/6=5/6\).
Итак,
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java мемоизируют одно и то же состояние динамического программирования с пятью параметрами. В версиях с плотным хранением значения размещаются в одномерной таблице, индексируемой этапом и четырьмя сжатыми счетчиками; версия на Python использует словарь с тем же кортежем в качестве ключа. Для каждого состояния сначала восстанавливается размер общего пула по формуле сохранения, затем считается число допустимых бумажек, после чего перебираются все \(4\times 4\) упорядоченные пары категорий для двух вытягиваний.
Категории с нулевым количеством сразу пропускаются. Для каждой допустимой пары код дважды обновляет состояние, затем вычисляет смесь продолжения по трем возможным классам следующего участника и прибавляет взвешенный вклад к мемоизированному ответу. Благодаря объединению симметричных меток программа нигде не перечисляет реальные имена и не строит явные деревья историй.
Индекс этапа дает \(O(n)\) вариантов, счетчики \(\rho\) и \(\mu\) принимают только значения \(0\), \(1\), \(2\), а два счетчика будущих классов доходят до \(n\). Поэтому в худшем случае число состояний равно \(O(n^4)\). Каждое состояние рассматривает не более \(16\) упорядоченных переходов вытягивания и продолжение постоянного размера, так что время работы равно \(O(n^4)\). Версии с плотными таблицами используют \(O(n^4)\) памяти; версия со словарем хранит только достижимые состояния, но асимптотическая верхняя граница остается той же.
لدينا \(n\) مشاركين ذوي تسميات، وفي البداية توجد ورقتان لكل تسمية. يعمل المشاركون بالترتيب \(1,2,\dots,n-1\). عندما يأتي دور المشارك \(k\)، فإن كل ورقة متبقية تحمل التسمية \(k\) تكون ممنوعة عليه، ثم يسحب ورقتين مسموحتين بشكل منتظم ومن دون إرجاع. الكمية \(q(n)\) هي احتمال أن تبقى ورقة واحدة على الأقل تحمل التسمية \(n\) عندما يصل الدور إلى المشارك الأخير.
تتبع جميع تواريخ السحب الممكنة مباشرة يؤدي إلى انفجار كبير في عدد الحالات. لذلك لا يحتفظ الحل بهوية كل ورقة متبقية، بل يستعمل حالة مضغوطة بالتماثل تحفظ فقط المعلومات التي تؤثر في القيود اللاحقة وفي بقاء التسمية \(n\).
لتكن \(\mathcal{F}_k(\rho,\mu,\sigma_1,\sigma_2)\) هي احتمالية النجاح ابتداء من المرحلة \(k\). ومعاني المتغيرات هي:
\(\rho\): عدد الأوراق التي تحمل التسمية \(k\) وما زالت موجودة، ولذلك فهي ممنوعة في هذه المرحلة؛
\(\mu\): عدد الأوراق التي تحمل التسمية \(n\) وما زالت موجودة؛
\(\sigma_1\): عدد التسميات المستقبلية الوسيطة التي بقي لها بالضبط ورقة واحدة من تسميتها الخاصة؛
\(\sigma_2\): عدد التسميات المستقبلية الوسيطة التي بقي لها بالضبط ورقتان من تسميتها الخاصة.
في المرحلة \(k\)، يكون العدد الكلي للأوراق المتبقية هو
$$T_k=2(n-k+1).$$
بالنسبة إلى أي مشارك وسيط في المستقبل، فإن المهم ليس هويته الدقيقة، بل فقط هل بقي من تسميته الخاصة \(0\) أو \(1\) أو \(2\) من الأوراق. هذا هو الذي يحدد لاحقا عدد الأوراق الممنوعة عليه. لذلك يمكن اعتبار جميع التسميات داخل الفئة نفسها متماثلة.
بالتالي ينقسم الصندوق إلى أربعة أجزاء: \(\rho\) ورقة ممنوعة تخص المشارك الحالي، و\(\mu\) ورقة تخص المشارك الأخير، و\(\sigma_1\) ورقة متعقبة قادمة من تسميات مستقبلية من الفئة \(1\)، و\(2\sigma_2\) ورقة متعقبة قادمة من تسميات مستقبلية من الفئة \(2\). أما بقية الأوراق فيمكن جمعها في حوض عام واحد، وحجمه هو
$$\gamma=T_k-\rho-\mu-\sigma_1-2\sigma_2.$$
هذا الحوض العام يحتوي على أوراق لم تعد هويتها الفردية مهمة: أوراق المشاركين الذين مر دورهم بالفعل، وكذلك الأوراق غير الحرجة للتسميات المستقبلية التي صار وضعها موصوفا بالكامل بواسطة \(\sigma_1\) و\(\sigma_2\).
يمكن للمشارك الحالي أن يسحب من كل الأوراق ما عدا \(\rho\) الأوراق الممنوعة، ولذلك يكون العدد المسموح هو
$$A=T_k-\rho.$$
أعداد الفئات الأربع القابلة للسحب هي
$$c_0=\gamma,\qquad c_1=\mu,\qquad c_2=\sigma_1,\qquad c_3=2\sigma_2.$$
إذا كانت السحبة الأولى من الفئة \(u\) والثانية من الفئة \(v\)، فإن الاحتمال المرتب يساوي
$$\Pr(u,v)=\frac{c_u}{A}\cdot\frac{c_v^{(u)}}{A-1},$$
حيث \(c_v^{(u)}\) هو العدد بعد تحديث الصندوق إثر السحبة الأولى. ويجب التعامل مع الأزواج المرتبة لأن السحبة الثانية ترى صندوقا مختلفا عن السحبة الأولى.
أثر سحب ورقة واحدة يعتمد فقط على فئتها:
$$\begin{aligned} \text{generic} &:\quad \gamma\to\gamma-1,\\ \text{final} &:\quad \mu\to\mu-1,\\ \text{class 1} &:\quad \sigma_1\to\sigma_1-1,\\ \text{class 2} &:\quad \sigma_2\to\sigma_2-1,\qquad \sigma_1\to\sigma_1+1. \end{aligned}$$
السطر الأخير يعني أن تسمية مستقبلية كانت تملك ورقتين من تسميتها الخاصة، وبعد سحب واحدة منهما تهبط إلى الفئة \(1\). بعد سحبتين نحصل على القيم الجديدة \(\mu',\sigma_1',\sigma_2'\)، بينما يمكن إعادة حساب \(\gamma\) دائما من معادلة الحفظ.
بعد إنهاء المرحلة \(k\)، يصبح المشارك الحالي التالي هو \(k+1\). الحالة المضغوطة لا تخزن أي تسمية مستقبلية بعينها على أنها \(k+1\)، بل تخزن فقط عدد التسميات المستقبلية الموجودة في الفئات \(0\) و\(1\) و\(2\). وبسبب التماثل يمكن اعتبار \(k+1\) تسمية موزعة بانتظام على تلك التسميات المستقبلية.
لنكتب
$$N_f=n-k-1,\qquad \tau_1=\sigma_1',\qquad \tau_2=\sigma_2',\qquad \tau_0=N_f-\tau_1-\tau_2.$$
إذا كان \(k=n-1\)، فلن يبقى أي مشارك وسيط، وعندها تتحدد الاستمرارية فقط بحسب ما إذا كان \(\mu'>0\) أم لا.
وفي غير ذلك تكون قيمة الاستمرار
$$\frac{\tau_0}{N_f}\mathcal{F}_{k+1}(0,\mu',\tau_1,\tau_2)+\frac{\tau_1}{N_f}\mathcal{F}_{k+1}(1,\mu',\tau_1-1,\tau_2)+\frac{\tau_2}{N_f}\mathcal{F}_{k+1}(2,\mu',\tau_1,\tau_2-1).$$
هذه هي الخطوة الجوهرية في الحل: بدلا من تتبع هوية الشخص التالي بدقة، نأخذ المتوسط فقط على الفئة التي ينتمي إليها.
عندما تصل العملية إلى المرحلة \(n\)، يبقى سؤال واحد فقط: هل نجت ورقة واحدة على الأقل تحمل التسمية \(n\)؟ لذلك
$$\mathcal{F}_n(\rho,\mu,\sigma_1,\sigma_2)= \begin{cases} 1,& \mu>0,\\ 0,& \mu=0. \end{cases}$$
في البداية تكون ورقتا المشارك \(1\) موجودتين، وكذلك ورقتا المشارك الأخير، وكل المشاركين الوسطيين المستقبليين ينتمون إلى الفئة \(2\). ومن ثم
$$q(n)=\mathcal{F}_1(2,2,0,n-2).$$
الحالة الابتدائية هي \(\mathcal{F}_1(2,2,0,1)\). لا يستطيع المشارك \(1\) سحب الورقتين اللتين تحملان التسمية \(1\)، ولذلك يحتوي الصندوق المسموح بالضبط على أربع أوراق: ورقتان بالتسمية \(2\) وورقتان بالتسمية \(3\).
إذا أزالت السحبتان كلتا ورقتي التسمية \(3\)، فإن الاحتمال يساوي
$$\frac{2}{4}\cdot\frac{1}{3}=\frac{1}{6},$$
ويحدث الفشل مباشرة لأن التسمية \(3\) تختفي بالكامل.
إذا أزالت إحدى السحبتين ورقة من التسمية \(2\) والأخرى ورقة من التسمية \(3\)، فإن الاحتمال الكلي يساوي
$$2\cdot\frac{2}{4}\cdot\frac{2}{3}=\frac{2}{3}.$$
عندئذ يصل المشارك \(2\) إلى المرحلة التالية ومعه ورقة ذاتية واحدة ممنوعة، ومع بقاء ورقة واحدة فقط من التسمية \(3\). ومن بين أوراقه الثلاث المسموحة توجد ورقة واحدة فقط بالتسمية \(3\)، لذلك يكون احتمال تركها دون سحب هو \(1/3\).
إذا كانت السحبتان كلتاهما من التسمية \(2\)، فالاحتمال مرة أخرى هو \(1/6\). في هذه الحالة يرى المشارك \(2\) أربع أوراق مسموحة، اثنتان منها بالتسمية \(3\)، والطريقة الوحيدة للفشل هي سحب كلتيهما، ولذلك يكون احتمال الاستمرار \(1-1/6=5/6\).
إذن
$$q(3)=\frac{1}{6}\cdot 0+\frac{2}{3}\cdot\frac{1}{3}+\frac{1}{6}\cdot\frac{5}{6}=\frac{13}{36}=0.361111\ldots,$$
وهو تماما مقدار التحقق المستخدم في التنفيذ.
تقوم تطبيقات C++ وPython وJava جميعها بعمل memoization لنفس حالة البرمجة الديناميكية ذات المعاملات الخمسة. النسخ الكثيفة تخزن القيم في جدول مسطح مفهرس بالمرحلة وبالعدادات الأربع المضغوطة، أما نسخة Python فتستعمل قاموسا بالمفتاح نفسه. في كل حالة تعيد الشيفرة بناء حجم الحوض العام من معادلة الحفظ، ثم تحسب عدد الأوراق المسموحة، وبعد ذلك تمر على جميع الأزواج المرتبة \(4\times 4\) لفئات السحبتين.
تتجاوز الشيفرة مباشرة أي فئة عددها صفر. ولكل زوج صالح تطبق تحديث الحالة مرتين، ثم تحسب مزيج الاستمرار عبر الفئات الثلاث الممكنة للمشارك التالي، وتضيف المساهمة الموزونة إلى الجواب المخزن. وبما أن التسميات المتماثلة دُمجت منذ البداية، فلا توجد حاجة إلى تعداد الأسماء الفعلية أو مسارات السحب الصريحة.
يعطي فهرس المرحلة \(O(n)\) احتمالات، أما \(\rho\) و\(\mu\) فلا يأخذان إلا القيم \(0\) و\(1\) و\(2\)، بينما قد يصل عدادا الفئتين المستقبليتين إلى \(n\). لذلك يكون حجم فضاء الحالات في أسوأ الأحوال هو \(O(n^4)\). وكل حالة تفحص في الحد الأقصى \(16\) انتقالا مرتبا للسحب مع مزيج استمرار ذي حجم ثابت، ومن ثم يكون زمن التنفيذ \(O(n^4)\). النسخ التي تستخدم جداول كثيفة تحتاج إلى \(O(n^4)\) من الذاكرة، أما النسخة المعتمدة على القاموس فتخزن فقط الحالات القابلة للوصول، مع بقاء الحد الأعلى الأسوأ كما هو.