There are \(n\) distinct values, and each value appears exactly four times in a shuffled deck of \(4n\) cards. As cards are revealed one by one, a value-group is called open if it has appeared at least once but fewer than four times. If \(M\) denotes the largest number of open groups seen at any moment, the goal is to compute \(\mathbb{E}[M]\) exactly for \(n=60\), then round the result to eight decimal places.
A direct simulation would only produce an approximation. The implementation instead performs an exact probability dynamic program over aggregated deck states, using symmetry to ignore the actual labels and track only how many values are in each partial-completion stage.
The essential simplification is exchangeability: once we know how many values have been seen \(0\), \(1\), \(2\), or \(3\) times, the precise identities of those values no longer matter for future probabilities.
Let \(c_0,c_1,c_2,c_3\) be the numbers of values for which exactly \(0,1,2,3\) copies have already been revealed. Values with four revealed copies are closed, so they do not need their own tracked bucket.
The number of currently open groups is therefore
$$p=c_1+c_2+c_3.$$
The number of already closed values is
$$c_4=n-(c_0+c_1+c_2+c_3).$$
This compressed description is exact. Two partial decks with the same quadruple \((c_0,c_1,c_2,c_3)\) have the same number of hidden cards of every type, hence the same transition probabilities.
From state \((c_0,c_1,c_2,c_3)\), the number of cards still hidden is
$$r=4c_0+3c_1+2c_2+c_3.$$
Exactly four kinds of next draw can occur:
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{with probability } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{with probability } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{with probability } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{with probability } \frac{c_3}{r}. \end{aligned}$$
The first copy of a value opens a new group, the second and third copies keep that group open, and the fourth copy closes it.
For a fixed integer threshold \(t\), define
$$Q_t=\mathbb{P}(M<t).$$
Instead of computing the full distribution of \(M\) directly, the dynamic program keeps only those paths for which the open-group count always remains strictly below \(t\). If a transition would produce a new open count \(p'\ge t\), that transition is discarded immediately.
After all \(4n\) cards have been processed, the surviving probability mass is exactly \(Q_t\).
Since \(M\) is an integer between \(1\) and \(n\), the tail-sum identity gives
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right).$$
So the exact answer is obtained by running the thresholded DP for every \(t=1,2,\dots,n\), then summing the complements \(1-Q_t\).
No future probability depends on whether a particular value is, say, the number \(7\) or the number \(43\). What matters is only how many values contribute four unseen cards, three unseen cards, two unseen cards, or one unseen card. That symmetry turns the original deck process into a finite Markov process on aggregated count states.
With only two values, the maximum \(M\) can be either \(1\) or \(2\). Therefore
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2).$$
To keep \(M<2\), the second value must not appear before the first value has already been completed. Starting from \((2,0,0,0)\), the only safe chain of states is
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0), $$
because opening the second value any earlier would create two open groups. The corresponding probability is
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35}. $$
Hence
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
This is the same checkpoint value used by the implementations before the full \(n=60\) computation.
The C++, Python, and Java implementations all follow the same structure. For one threshold \(t\), they keep a probability map for the current draw depth and another for the next depth. Each compressed state is encoded into a compact integer key so that hash-based containers can merge probability contributions efficiently.
At each step, the implementation decodes one state, computes the remaining-card count \(r\), applies the four transitions above, and drops every successor whose open-group count would reach or exceed the threshold. After \(4n\) layers, the probability attached to the terminal empty state is exactly \(Q_t=\mathbb{P}(M<t)\). An outer loop repeats this for all thresholds from \(1\) to \(n\), accumulates \(1-Q_t\), and finally rounds the result to eight decimal places.
For a fixed threshold \(t\), the DP has \(4n\) layers and stores only states with fewer than \(t\) open groups. At a fixed layer, the draw depth determines one linear relation among the state counts, so the remaining feasible configurations are described by \(O(t^3)\) possibilities. This yields \(O(nt^3)\) time for one threshold and \(O(t^3)\) memory for the two active layers. Summing over \(t=1,\dots,n\) gives an overall worst-case bound of \(O(n^5)\) time and \(O(n^3)\) memory. In practice the active frontier is much smaller, because unreachable states never enter the hash maps and the threshold pruning is strong.
Es gibt \(n\) verschiedene Werte, und jeder Wert kommt in einem gemischten Stapel von \(4n\) Karten genau viermal vor. Beim schrittweisen Aufdecken heißt eine Wertgruppe offen, wenn sie schon mindestens einmal, aber noch nicht viermal erschienen ist. Bezeichnet \(M\) die größte Anzahl gleichzeitig offener Gruppen, dann soll \(\mathbb{E}[M]\) für \(n=60\) exakt berechnet und anschließend auf acht Nachkommastellen gerundet werden.
Eine bloße Simulation wäre nur näherungsweise. Deshalb verwendet die Lösung ein exaktes Wahrscheinlichkeits-DP über aggregierte Zustände und nutzt die Symmetrie aus, dass die konkreten Werte selbst keine Rolle mehr spielen.
Die entscheidende Vereinfachung ist Austauschbarkeit: Sobald bekannt ist, wie viele Werte bereits \(0\), \(1\), \(2\) oder \(3\) Mal gesehen wurden, sind alle zukünftigen Übergangswahrscheinlichkeiten festgelegt.
Seien \(c_0,c_1,c_2,c_3\) die Anzahlen der Werte, von denen bisher genau \(0,1,2,3\) Kopien aufgedeckt wurden. Werte mit vier aufgedeckten Kopien sind abgeschlossen und brauchen kein eigenes Fach mehr.
Damit ist die aktuelle Zahl offener Gruppen
$$p=c_1+c_2+c_3.$$
Die Zahl bereits abgeschlossener Werte lautet
$$c_4=n-(c_0+c_1+c_2+c_3).$$
Diese Beschreibung ist exakt: Zwei partielle Stapel mit demselben Viererzustand \((c_0,c_1,c_2,c_3)\) haben genau dieselbe Verteilung möglicher nächster Züge.
Aus dem Zustand \((c_0,c_1,c_2,c_3)\) sind noch
$$r=4c_0+3c_1+2c_2+c_3$$
Karten verdeckt. Der nächste Zug kann genau vier Typen haben:
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{mit Wahrscheinlichkeit } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{mit Wahrscheinlichkeit } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{mit Wahrscheinlichkeit } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{mit Wahrscheinlichkeit } \frac{c_3}{r}. \end{aligned}$$
Die erste Kopie eines Werts öffnet also eine neue Gruppe, die zweite und dritte lassen sie offen, und die vierte schließt sie.
Für einen festen ganzzahligen Schwellwert \(t\) definieren wir
$$Q_t=\mathbb{P}(M<t).$$
Statt die gesamte Verteilung von \(M\) direkt zu bestimmen, propagiert das DP nur solche Pfade, auf denen die Zahl offener Gruppen immer strikt kleiner als \(t\) bleibt. Jeder Übergang, der zu einem neuen offenen Gruppenstand \(p'\ge t\) führen würde, wird sofort verworfen.
Nach allen \(4n\) Aufdeckungen ist die übrig gebliebene Gesamtwahrscheinlichkeit genau \(Q_t\).
Da \(M\) eine ganze Zahl zwischen \(1\) und \(n\) ist, gilt die Tail-Sum-Formel
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right).$$
Die exakte Antwort entsteht also dadurch, dass man das Schwellwert-DP für alle \(t=1,2,\dots,n\) ausführt und anschließend die Komplemente \(1-Q_t\) aufsummiert.
Für die Zukunftsverteilung ist es bedeutungslos, ob der zweimal gesehene Wert gerade \(7\) oder \(43\) heißt. Relevant ist nur, wie viele Werte noch vier, drei, zwei oder eine verdeckte Karte beitragen. Genau diese Symmetrie macht aus dem ursprünglichen Kartenprozess einen endlichen Markov-Prozess auf aggregierten Zuständen.
Bei nur zwei Werten kann das Maximum \(M\) nur \(1\) oder \(2\) sein. Also
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2).$$
Damit \(M<2\) bleibt, darf der zweite Wert nicht auftauchen, bevor der erste schon vollständig abgeschlossen ist. Ausgehend von \((2,0,0,0)\) ist die einzige sichere Zustandskette
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0), $$
denn ein früheres Öffnen des zweiten Werts würde sofort zwei offene Gruppen erzeugen. Die zugehörige Wahrscheinlichkeit ist
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35}. $$
Somit folgt
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
Genau dieser Kontrollwert wird von den Implementierungen geprüft, bevor der eigentliche Fall \(n=60\) berechnet wird.
Die C++-, Python- und Java-Implementierungen verwenden alle dasselbe Muster. Für einen festen Schwellwert \(t\) halten sie eine Wahrscheinlichkeitsabbildung für die aktuelle Aufdecktiefe und eine weitere für die nächste Tiefe. Jeder komprimierte Zustand wird als kompakter Integer-Schlüssel codiert, damit Hash-Container Wahrscheinlichkeitsmassen effizient zusammenführen können.
In jedem Schritt dekodiert die Implementierung einen Zustand, berechnet die Restkartenzahl \(r\), wendet die vier Übergänge an und verwirft jeden Nachfolger, dessen offene Gruppenzahl den Schwellwert erreicht oder überschreitet. Nach \(4n\) Ebenen ist die Wahrscheinlichkeit des terminalen leeren Zustands genau \(Q_t=\mathbb{P}(M<t)\). Eine äußere Schleife wiederholt das für alle Schwellwerte von \(1\) bis \(n\), summiert \(1-Q_t\) und rundet am Ende auf acht Nachkommastellen.
Für einen festen Schwellwert \(t\) besitzt das DP \(4n\) Ebenen und speichert nur Zustände mit weniger als \(t\) offenen Gruppen. In einer festen Ebene erzwingt die aktuelle Aufdecktiefe eine lineare Beziehung zwischen den Zustandszahlen, sodass \(O(t^3)\) zulässige Konfigurationen übrig bleiben. Daraus folgen \(O(nt^3)\) Zeit für einen Schwellwert und \(O(t^3)\) Speicher für die beiden aktiven Ebenen. Über alle \(t=1,\dots,n\) summiert ergibt das eine grobe Worst-Case-Schranke von \(O(n^5)\) Zeit und \(O(n^3)\) Speicher. Praktisch ist die aktive Front deutlich kleiner, weil unerreichbare Zustände nie in die Hash-Maps gelangen und die Schwellwert-Beschneidung stark wirkt.
Karıştırılmış \(4n\) kartlık bir destede \(n\) farklı değerin her biri tam dört kez bulunur. Kartlar tek tek açılırken, bir değer grubu en az bir kez görülmüş ama henüz dört kez tamamlanmamışsa açık kabul edilir. Eğer \(M\), süreç boyunca aynı anda görülen en büyük açık grup sayısıysa, amaç \(n=60\) için \(\mathbb{E}[M]\) değerini tam olarak hesaplayıp sonucu sekiz ondalık basamağa yuvarlamaktır.
Rastgele benzetim yalnızca yaklaşık sonuç verir. Buradaki çözüm ise gerçek etiketleri unutup yalnızca hangi aşamada kaç değer bulunduğunu izleyen sıkıştırılmış durumlar üzerinde tam olasılıklı bir dinamik programlama uygular.
Temel basitleştirme simetridir: Bir değerin tam olarak kaç kez görüldüğünü bildiğimiz sürece, o değerin hangi sayı olduğunun artık gelecekteki olasılıklar üzerinde etkisi yoktur.
\(c_0,c_1,c_2,c_3\) sırasıyla tam olarak \(0,1,2,3\) kopyası açılmış değerlerin sayıları olsun. Dört kopyası da açılan değer artık kapanmıştır; bu yüzden ayrıca izlenmesine gerek yoktur.
Böylece anlık açık grup sayısı
$$p=c_1+c_2+c_3$$
olur. Kapanmış değer sayısı ise
$$c_4=n-(c_0+c_1+c_2+c_3)$$
şeklindedir. Bu sıkıştırma tamdır; çünkü aynı \((c_0,c_1,c_2,c_3)\) dörtlüsüne sahip iki kısmi deste, bir sonraki kart için aynı olasılık dağılımına sahiptir.
\((c_0,c_1,c_2,c_3)\) durumunda hâlâ kapalı olan kart sayısı
$$r=4c_0+3c_1+2c_2+c_3$$
kadardır. Bir sonraki kart yalnızca dört tipten biri olabilir:
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{olasılık } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{olasılık } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{olasılık } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{olasılık } \frac{c_3}{r}. \end{aligned}$$
Bir değerin ilk kopyası yeni bir grubu açar; ikinci ve üçüncü kopyalar grubu açık tutar; dördüncü kopya ise o grubu kapatır.
Sabit bir tamsayı eşik \(t\) için
$$Q_t=\mathbb{P}(M<t)$$
tanımını yapalım. \(M\)'nin tüm dağılımını doğrudan kurmak yerine, dinamik programlama yalnızca açık grup sayısının her adımda kesin olarak \(t\)'den küçük kaldığı yolları taşır. Yeni açık grup sayısı \(p'\ge t\) olacak her geçiş anında atılır.
Tüm \(4n\) kart açıldıktan sonra geriye kalan toplam olasılık tam olarak \(Q_t\) olur.
\(M\), \(1\) ile \(n\) arasında bir tamsayı olduğundan kuyruk-toplam özdeşliği
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right)$$
şeklindedir. Dolayısıyla tam cevap, \(t=1,2,\dots,n\) için eşiklenmiş DP'yi ayrı ayrı çalıştırıp \(1-Q_t\) terimlerini toplamaktan elde edilir.
Gelecekteki olasılıklar açısından iki kez görülmüş değerin \(7\) mi yoksa \(43\) mü olduğu önemsizdir. Önemli olan yalnızca kaç değerin dört görünmemiş, üç görünmemiş, iki görünmemiş ya da bir görünmemiş karta katkı verdiğidir. Çözümü mümkün kılan şey tam olarak bu değiş-tokuş edilebilirliktir.
Yalnızca iki değer varken maksimum \(M\) ancak \(1\) veya \(2\) olabilir. Bu yüzden
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2)$$
yazarız. \(M<2\) kalabilmesi için ikinci değer, birinci değer tamamen bitmeden önce hiç görünmemelidir. \((2,0,0,0)\) durumundan başlayınca güvenli tek zincir
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0) $$
olur; çünkü ikinci değeri daha erken açmak iki açık gruba yol açar. Bu zincirin olasılığı
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35} $$
tır. Dolayısıyla
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
elde edilir. Bu, tam \(n=60\) hesabından önce uygulamaların kullandığı küçük doğrulama değeridir.
C++, Python ve Java uygulamalarının yapısı aynıdır. Sabit bir eşik \(t\) için biri mevcut açma derinliği, diğeri bir sonraki derinlik için olmak üzere iki olasılık haritası tutulur. Her sıkıştırılmış durum, olasılık kütlesini hash tabanlı yapılarda verimli toplamak için kompakt bir tamsayı anahtara kodlanır.
Her adımda uygulama bir durumu çözer, kalan kart sayısı \(r\)'yi hesaplar, yukarıdaki dört geçişi uygular ve açık grup sayısını eşik değerine ulaştıran ya da aşan tüm ardılları atar. \(4n\) katman sonunda boş son durum üzerindeki olasılık tam olarak \(Q_t=\mathbb{P}(M<t)\) olur. Dış döngü bunu \(1\)'den \(n\)'ye kadar tüm eşikler için tekrarlar, \(1-Q_t\) terimlerini toplar ve sonucu sekiz ondalık basamağa yuvarlar.
Sabit bir eşik \(t\) için DP'nin \(4n\) katmanı vardır ve yalnızca açık grup sayısı \(t\)'den küçük olan durumlar saklanır. Belirli bir katmanda, açılmış kart sayısı durum sayıları arasında doğrusal bir ilişki dayattığı için geriye \(O(t^3)\) kadar olası yapı kalır. Bu da tek eşik için \(O(nt^3)\) zaman ve iki aktif katman için \(O(t^3)\) bellek verir. \(t=1,\dots,n\) üzerinde toplandığında kaba üst sınır \(O(n^5)\) zaman ve \(O(n^3)\) bellektir. Pratikte etkin cephe çok daha küçüktür; çünkü erişilemeyen durumlar hash tablolarına hiç girmez ve eşik budaması kuvvetlidir.
Hay \(n\) valores distintos y cada valor aparece exactamente cuatro veces en una baraja mezclada de \(4n\) cartas. Al revelar las cartas una por una, un grupo de valor se considera abierto si ya apareció al menos una vez pero todavía no ha completado sus cuatro copias. Si \(M\) denota el mayor número de grupos abiertos observado en algún momento, el objetivo es calcular \(\mathbb{E}[M]\) exactamente para \(n=60\) y redondear el resultado a ocho decimales.
Una simulación solo daría una aproximación. Por eso la solución usa programación dinámica probabilística exacta sobre estados agregados, aprovechando que las etiquetas concretas ya no importan una vez que solo se observa cuántos valores están en cada etapa parcial.
La simplificación central es la simetría entre valores. Si sabemos cuántos valores han aparecido \(0\), \(1\), \(2\) o \(3\) veces, entonces las probabilidades futuras quedan completamente determinadas.
Sean \(c_0,c_1,c_2,c_3\) las cantidades de valores de los que ya se han visto exactamente \(0,1,2,3\) copias. Los valores con cuatro copias reveladas ya están cerrados, así que no hace falta llevar una categoría adicional explícita.
El número actual de grupos abiertos es
$$p=c_1+c_2+c_3.$$
El número de valores ya cerrados es
$$c_4=n-(c_0+c_1+c_2+c_3).$$
Esta compresión es exacta: dos barajas parciales con el mismo cuádruple \((c_0,c_1,c_2,c_3)\) tienen el mismo número de cartas ocultas de cada tipo y, por tanto, las mismas probabilidades de transición.
Desde el estado \((c_0,c_1,c_2,c_3)\), el número de cartas todavía ocultas es
$$r=4c_0+3c_1+2c_2+c_3.$$
Solo pueden ocurrir cuatro clases de siguiente extracción:
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{con probabilidad } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{con probabilidad } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{con probabilidad } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{con probabilidad } \frac{c_3}{r}. \end{aligned}$$
La primera copia de un valor abre un grupo nuevo, la segunda y la tercera lo mantienen abierto y la cuarta lo cierra.
Para un umbral entero fijo \(t\), definimos
$$Q_t=\mathbb{P}(M<t).$$
En lugar de construir directamente toda la distribución de \(M\), el DP conserva solo los caminos en los que el número de grupos abiertos permanece siempre estrictamente por debajo de \(t\). Toda transición que produzca un nuevo conteo \(p'\ge t\) se descarta de inmediato.
Después de procesar las \(4n\) cartas, la masa total de probabilidad que sobrevive es exactamente \(Q_t\).
Como \(M\) es un entero entre \(1\) y \(n\), vale la identidad de suma de colas
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right).$$
Por tanto, la respuesta exacta se obtiene ejecutando el DP con umbral para cada \(t=1,2,\dots,n\) y sumando después los complementos \(1-Q_t\).
Para las probabilidades futuras no importa si el valor visto dos veces es el \(7\) o el \(43\). Lo único relevante es cuántos valores aportan todavía cuatro, tres, dos o una carta oculta. Esa simetría convierte el proceso original de la baraja en un proceso de Markov finito sobre estados agregados.
Con solo dos valores, el máximo \(M\) solo puede ser \(1\) o \(2\). Por eso
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2).$$
Para mantener \(M<2\), el segundo valor no debe aparecer antes de que el primero ya se haya completado. Partiendo de \((2,0,0,0)\), la única cadena segura de estados es
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0), $$
porque abrir el segundo valor antes produciría dos grupos abiertos. La probabilidad correspondiente es
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35}. $$
Entonces
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
Ese es exactamente el valor de control pequeño que usan las implementaciones antes del cálculo completo con \(n=60\).
Las implementaciones en C++, Python y Java siguen la misma idea. Para un umbral fijo \(t\), mantienen un mapa de probabilidades para la profundidad actual de revelado y otro para la siguiente. Cada estado comprimido se codifica en una clave entera compacta para que las estructuras hash acumulen masa de probabilidad con eficiencia.
En cada paso, la implementación decodifica un estado, calcula el número de cartas restantes \(r\), aplica las cuatro transiciones anteriores y elimina todo sucesor cuyo número de grupos abiertos alcance o supere el umbral. Tras \(4n\) capas, la probabilidad asociada al estado terminal vacío es exactamente \(Q_t=\mathbb{P}(M<t)\). Un bucle externo repite esto para todos los umbrales desde \(1\) hasta \(n\), suma \(1-Q_t\) y redondea el resultado final a ocho decimales.
Para un umbral fijo \(t\), el DP tiene \(4n\) capas y solo guarda estados con menos de \(t\) grupos abiertos. En una capa fija, la profundidad de revelado impone una relación lineal entre los conteos del estado, de modo que quedan \(O(t^3)\) configuraciones viables. Eso da \(O(nt^3)\) tiempo para un umbral y \(O(t^3)\) memoria para las dos capas activas. Al sumar sobre \(t=1,\dots,n\), se obtiene una cota grosera de peor caso de \(O(n^5)\) tiempo y \(O(n^3)\) memoria. En la práctica, la frontera activa es mucho menor, porque los estados inalcanzables nunca entran en los mapas hash y la poda por umbral reduce mucho el espacio efectivo.
共有 \(n\) 种不同的数值，每种数值在一副洗匀后的 \(4n\) 张牌中恰好出现 4 次。按顺序翻牌时，如果某个数值已经出现过至少 1 次、但还没有凑满 4 次，就称这个数值组处于打开状态。记 \(M\) 为整个翻牌过程中“同时打开的数值组数量”的最大值，题目要求在 \(n=60\) 时精确求出 \(\mathbb{E}[M]\)，再把结果四舍五入到小数点后 8 位。
单纯做随机模拟只能得到近似值。这里使用的是精确概率动态规划：利用不同数值之间的对称性，不再区分具体是哪一个数值，只记录“有多少种数值已经出现了 0 次、1 次、2 次、3 次”。这正是实现能够精确计算的关键。
核心思想是交换性。只要知道各个“出现次数层级”里分别有多少种数值，未来一步抽到哪一类牌的概率就已经完全确定，具体牌面标签本身不再重要。
设 \(c_0,c_1,c_2,c_3\) 分别表示当前恰好已经出现了 \(0,1,2,3\) 张的数值个数。已经出现 4 张的数值说明这一组已经闭合，因此不需要单独再存一个显式桶。
于是，当前打开的数值组数量就是
$$p=c_1+c_2+c_3.$$
已经闭合的数值组数量可以由总数反推：
$$c_4=n-(c_0+c_1+c_2+c_3).$$
这种压缩没有损失信息。因为如果两个中间过程拥有同样的四元组 \((c_0,c_1,c_2,c_3)\)，那么它们各自还剩多少张“首次出现牌”“第二次出现牌”“第三次出现牌”“第四次出现牌”都是一样的，所以后续所有转移概率也完全一致。
从状态 \((c_0,c_1,c_2,c_3)\) 出发，当前仍未翻开的牌总数为
$$r=4c_0+3c_1+2c_2+c_3.$$
下一张牌只可能对应下面四类情况：
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{概率为 } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{概率为 } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{概率为 } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{概率为 } \frac{c_3}{r}. \end{aligned}$$
第一张会把某个数值组从“未开始”变成“已打开”，第二张和第三张仍然保持该组打开，而第四张会把这个组彻底关闭。
对任意固定整数阈值 \(t\)，定义
$$Q_t=\mathbb{P}(M<t).$$
也就是说，\(Q_t\) 表示整个过程中打开组数量始终严格小于 \(t\) 的概率。实现并不直接求 \(M\) 的完整分布，而是对每个阈值 \(t\) 单独做一次 DP，只保留那些在每一步都满足“新的打开组数量 \(p'\) 仍然小于 \(t\)”的转移。
如果某一步会让打开组数量达到或超过阈值，那么那条路径立刻被丢弃。等到 \(4n\) 张牌全部处理完后，剩下来的总概率质量就正好是 \(Q_t\)。
由于 \(M\) 是介于 \(1\) 和 \(n\) 之间的整数，可以使用尾和恒等式
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right).$$
这一步非常关键，因为它把“求最大值的期望”转化成了“反复计算不越过阈值的概率”。因此，程序只要把 \(t=1,2,\dots,n\) 全部扫一遍，并把每个 \(1-Q_t\) 累加起来，就得到了精确答案。
假设某个数值已经出现了两张，那么它到底是数值 \(7\) 还是数值 \(43\)，对未来的概率没有任何影响。真正决定下一步概率的是：当前有多少种数值还剩 4 张未见、多少种还剩 3 张未见、多少种还剩 2 张未见、多少种还剩 1 张未见。也正因为这种完全对称性，原问题才可以转化成一个有限状态的聚合马尔可夫过程。
当只有两个数值时，最大打开组数 \(M\) 只可能等于 \(1\) 或 \(2\)。因此
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2).$$
若要保持 \(M<2\)，就意味着第二种数值绝不能在第一种数值尚未凑满 4 张之前出现。从初始状态 \((2,0,0,0)\) 出发，唯一安全的状态链是
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0), $$
因为只要更早打开第二种数值，就会立刻出现两个同时打开的组。对应的概率为
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35}. $$
于是得到
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
这正是实现先验证的小规模检查值，然后才继续进行真正的 \(n=60\) 计算。
C++、Python 和 Java 实现的总体流程完全一致。对于固定阈值 \(t\)，程序维护两个概率映射：一个表示当前翻牌层，另一个表示下一层。每个压缩状态都会被编码成一个紧凑的整数键，这样哈希表就能把来自不同路径的概率质量高效合并。
在每一步中，实现都会解码一个状态，计算剩余牌数 \(r\)，应用上面的四种转移，并过滤掉任何会使打开组数量达到或超过阈值的后继状态。经过 \(4n\) 层之后，终止空状态上的概率就是 \(Q_t=\mathbb{P}(M<t)\)。外层再对 \(t=1\) 到 \(n\) 逐个重复这一过程，累计所有 \(1-Q_t\)，最后把答案四舍五入到小数点后 8 位。
对固定阈值 \(t\) 而言，动态规划共有 \(4n\) 层，并且只保留打开组数量小于 \(t\) 的状态。在固定的一层中，已翻开的牌数给状态计数施加了一条线性约束，因此剩余可行状态的数量是 \(O(t^3)\) 级别。于是单个阈值的时间复杂度为 \(O(nt^3)\)，两层活动哈希表的空间复杂度为 \(O(t^3)\)。把 \(t=1,\dots,n\) 全部加起来，总体最坏情况上界为 \(O(n^5)\) 时间和 \(O(n^3)\) 空间。实际运行时远没有这么大，因为不可达状态根本不会进入哈希表，而且阈值剪枝非常有效。
Есть \(n\) различных значений, и каждое значение встречается в перемешанной колоде из \(4n\) карт ровно четыре раза. При последовательном открытии карт группа значения считается открытой, если это значение уже появлялось хотя бы один раз, но еще не было собрано все четыре копии. Пусть \(M\) обозначает максимальное число одновременно открытых групп за весь процесс. Нужно точно вычислить \(\mathbb{E}[M]\) при \(n=60\) и затем округлить ответ до восьми знаков после запятой.
Прямая симуляция дала бы только приближение. Поэтому решение использует точное вероятностное динамическое программирование по агрегированным состояниям, опираясь на симметрию между значениями.
Главное упрощение состоит в том, что конкретные метки значений взаимозаменяемы. Если известно, сколько значений уже встретилось \(0\), \(1\), \(2\) или \(3\) раза, то все вероятности следующих шагов уже определены.
Пусть \(c_0,c_1,c_2,c_3\) обозначают количества значений, у которых к текущему моменту открыто ровно \(0,1,2,3\) копии. Значения с четырьмя открытыми копиями уже закрыты, поэтому отдельная явная категория для них не нужна.
Тогда текущее число открытых групп равно
$$p=c_1+c_2+c_3.$$
Число уже закрытых значений выражается как
$$c_4=n-(c_0+c_1+c_2+c_3).$$
Такое сжатие является точным: любые два частичных процесса с одинаковым четверичным состоянием \((c_0,c_1,c_2,c_3)\) имеют одинаковое число скрытых карт каждого типа, а значит, и одинаковые вероятности переходов.
Из состояния \((c_0,c_1,c_2,c_3)\) число еще не открытых карт равно
$$r=4c_0+3c_1+2c_2+c_3.$$
Следующая карта может привести только к одному из четырех типов переходов:
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{с вероятностью } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{с вероятностью } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{с вероятностью } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{с вероятностью } \frac{c_3}{r}. \end{aligned}$$
Первая копия значения открывает новую группу, вторая и третья оставляют ее открытой, а четвертая закрывает.
Для фиксированного целого порога \(t\) введем
$$Q_t=\mathbb{P}(M<t).$$
Вместо прямого вычисления полного распределения \(M\) динамика рассматривает только те траектории, на которых число открытых групп всегда остается строго меньше \(t\). Любой переход, который дал бы новое значение \(p'\ge t\), немедленно отбрасывается.
После обработки всех \(4n\) карт суммарная выжившая вероятность и есть \(Q_t\).
Так как \(M\) принимает целые значения от \(1\) до \(n\), применима формула хвостовой суммы
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right).$$
Значит, точный ответ получается так: для всех \(t=1,2,\dots,n\) отдельно вычисляются вероятности \(Q_t\), после чего суммируются величины \(1-Q_t\).
Для дальнейших вероятностей неважно, какое именно значение было открыто дважды: \(7\), \(43\) или любое другое. Важно только, сколько значений по-прежнему дают четыре скрытые карты, сколько дают три, две или одну. Именно эта симметрия превращает исходный карточный процесс в конечный марковский процесс на агрегированных состояниях.
Если значений всего два, то максимум \(M\) может быть только \(1\) или \(2\). Поэтому
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2).$$
Чтобы выполнялось \(M<2\), второе значение не должно появиться раньше, чем первое будет полностью завершено. Начиная из \((2,0,0,0)\), единственная безопасная цепочка состояний имеет вид
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0), $$
потому что более раннее открытие второго значения немедленно создало бы две открытые группы. Вероятность этой цепочки равна
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35}. $$
Следовательно,
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
Именно это небольшое контрольное значение проверяют реализации перед полным вычислением для \(n=60\).
Реализации на C++, Python и Java устроены одинаково. Для фиксированного порога \(t\) они поддерживают одно отображение вероятностей для текущей глубины раскрытия и второе для следующей. Каждое сжатое состояние кодируется компактным целочисленным ключом, чтобы хеш-структуры могли эффективно суммировать вероятностные вклады.
На каждом шаге реализация декодирует состояние, вычисляет число оставшихся карт \(r\), применяет четыре перехода, описанные выше, и отбрасывает любого потомка, у которого число открытых групп достигло бы порога или превысило бы его. После \(4n\) слоев вероятность, прикрепленная к пустому терминальному состоянию, в точности равна \(Q_t=\mathbb{P}(M<t)\). Внешний цикл повторяет это для всех порогов от \(1\) до \(n\), суммирует \(1-Q_t\) и округляет окончательный ответ до восьми знаков после запятой.
Для фиксированного порога \(t\) динамика имеет \(4n\) слоев и хранит только состояния с числом открытых групп меньше \(t\). На фиксированном слое глубина раскрытия задает одну линейную связь между счетчиками состояния, поэтому остается \(O(t^3)\) допустимых конфигураций. Отсюда получается \(O(nt^3)\) времени для одного порога и \(O(t^3)\) памяти для двух активных слоев. Суммирование по всем \(t=1,\dots,n\) дает грубую верхнюю оценку \(O(n^5)\) по времени и \(O(n^3)\) по памяти. На практике активный фронт намного меньше, потому что недостижимые состояния не попадают в хеш-таблицы, а пороговое отсечение сильно сокращает пространство поиска.
لدينا \(n\) قيم مختلفة، وكل قيمة تظهر بالضبط أربع مرات في رزمة عشوائية مكونة من \(4n\) بطاقة. أثناء كشف البطاقات واحدة بعد أخرى، نسمّي مجموعة القيمة مفتوحة إذا كانت هذه القيمة قد ظهرت مرة واحدة على الأقل ولكنها لم تكتمل بعد إلى أربع مرات. إذا رمزنا بـ \(M\) إلى أكبر عدد من المجموعات المفتوحة في أي لحظة من العملية، فالمطلوب هو حساب \(\mathbb{E}[M]\) بدقة عندما \(n=60\)، ثم تقريب النتيجة إلى ثمانية منازل عشرية.
المحاكاة العشوائية تعطي تقريبًا فقط. لذلك تعتمد الطريقة على برمجة ديناميكية احتمالية دقيقة فوق حالات مجمعة، مع الاستفادة من التناظر بين القيم بحيث لا نحتاج إلى معرفة هوية القيمة نفسها، بل فقط عدد القيم الموجودة في كل مرحلة من مراحل الظهور الجزئي.
الفكرة الحاسمة هي قابلية التبادل بين القيم. متى عرفنا كم عدد القيم التي ظهرت \(0\) أو \(1\) أو \(2\) أو \(3\) مرات، تصبح احتمالات الخطوة التالية محددة بالكامل.
لنرمز بـ \(c_0,c_1,c_2,c_3\) إلى أعداد القيم التي ظهر منها بالضبط \(0,1,2,3\) نسخ حتى اللحظة الحالية. أما القيم التي ظهرت نسخها الأربع كلها فقد أُغلقت، ولذلك لا حاجة إلى تتبعها في خانة مستقلة داخل الحالة.
إذن عدد المجموعات المفتوحة حاليًا هو
$$p=c_1+c_2+c_3.$$
أما عدد القيم التي أغلقت بالفعل فهو
$$c_4=n-(c_0+c_1+c_2+c_3).$$
هذا الضغط دقيق تمامًا، لأن أي حالتين جزئيتين لهما نفس الرباعية \((c_0,c_1,c_2,c_3)\) تمتلكان العدد نفسه من البطاقات المخفية من كل نوع، وبالتالي تمتلكان الاحتمالات نفسها لجميع الانتقالات اللاحقة.
إذا كنا في الحالة \((c_0,c_1,c_2,c_3)\)، فإن عدد البطاقات التي ما تزال مخفية يساوي
$$r=4c_0+3c_1+2c_2+c_3.$$
والبطاقة التالية لا بد أن تؤدي إلى واحد من أربعة انتقالات فقط:
$$\begin{aligned} (c_0,c_1,c_2,c_3)&\to(c_0-1,c_1+1,c_2,c_3) &&\text{with probability } \frac{4c_0}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1-1,c_2+1,c_3) &&\text{with probability } \frac{3c_1}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2-1,c_3+1) &&\text{with probability } \frac{2c_2}{r},\\ (c_0,c_1,c_2,c_3)&\to(c_0,c_1,c_2,c_3-1) &&\text{with probability } \frac{c_3}{r}. \end{aligned}$$
النسخة الأولى من قيمة ما تفتح مجموعة جديدة، والنسختان الثانية والثالثة تبقيانها مفتوحة، أما النسخة الرابعة فتغلق المجموعة نهائيًا.
من أجل حد صحيح ثابت \(t\)، نعرّف
$$Q_t=\mathbb{P}(M<t).$$
بدلًا من حساب التوزيع الكامل لـ \(M\) مباشرة، تحتفظ البرمجة الديناميكية فقط بالمسارات التي يبقى فيها عدد المجموعات المفتوحة أصغر من \(t\) بشكل صارم في كل خطوة. وكل انتقال يؤدي إلى عدد جديد \(p'\ge t\) يُحذف مباشرة.
بعد معالجة جميع البطاقات وعددها \(4n\)، تكون الكتلة الاحتمالية الباقية مساوية تمامًا لـ \(Q_t\).
بما أن \(M\) عدد صحيح بين \(1\) و\(n\)، فإن هوية مجموع الذيول تعطي
$$\mathbb{E}[M]=\sum_{t=1}^{n}\mathbb{P}(M\ge t)=\sum_{t=1}^{n}\left(1-Q_t\right).$$
وهكذا يتحول المطلوب من “حساب متوسط أكبر قيمة” إلى “حساب احتمالات عدم تجاوز الحدود المختلفة”. لهذا السبب تكرر الخوارزمية الـ DP لكل \(t=1,2,\dots,n\)، ثم تجمع المقادير \(1-Q_t\).
من ناحية الاحتمالات المستقبلية لا يهم هل القيمة التي ظهرت مرتين هي \(7\) أم \(43\). المهم فقط هو عدد القيم التي لا يزال لها أربع بطاقات مخفية، أو ثلاث، أو اثنتان، أو واحدة. هذا التناظر الكامل هو ما يحول العملية الأصلية للرزمة إلى عملية ماركوفية منتهية على حالات مجمعة قابلة للحساب بدقة.
عندما يكون لدينا قيمتان فقط، فإن \(M\) لا يمكن أن يأخذ إلا القيمتين \(1\) أو \(2\). لذلك
$$\mathbb{E}[M]=1+\mathbb{P}(M=2)=2-\mathbb{P}(M<2).$$
ولكي يبقى \(M<2\)، يجب ألا تظهر القيمة الثانية قبل اكتمال القيمة الأولى تمامًا. إذا بدأنا من الحالة \((2,0,0,0)\)، فإن السلسلة الآمنة الوحيدة للحالات هي
$$ (2,0,0,0)\to(1,1,0,0)\to(1,0,1,0)\to(1,0,0,1)\to(1,0,0,0), $$
لأن فتح القيمة الثانية في وقت أبكر سيؤدي فورًا إلى وجود مجموعتين مفتوحتين معًا. واحتمال هذه السلسلة هو
$$ 1\cdot\frac{3}{7}\cdot\frac{2}{6}\cdot\frac{1}{5}=\frac{1}{35}. $$
ومن ثم نحصل على
$$ \mathbb{P}(M<2)=\frac{1}{35},\qquad \mathbb{E}[M]=2-\frac{1}{35}=\frac{69}{35}=1.97142857\ldots $$
وهذه هي القيمة الصغيرة التي تتحقق منها التطبيقات أولًا قبل تنفيذ الحساب الكامل عند \(n=60\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. فلكل حد ثابت \(t\) تحتفظ الشيفرة بجدول احتمالات للطبقة الحالية من السحب، وجدول آخر للطبقة التالية. ويُشفَّر كل وضع مضغوط إلى مفتاح عددي صغير لكي تتمكن البنى المعتمدة على التجزئة من جمع الكتل الاحتمالية بكفاءة.
في كل خطوة تفك الشيفرة حالة واحدة، وتحسب عدد البطاقات المتبقية \(r\)، ثم تطبق الانتقالات الأربع المذكورة أعلاه، وتحذف كل حالة لاحقة يصل فيها عدد المجموعات المفتوحة إلى الحد أو يتجاوزه. بعد \(4n\) طبقة، يكون الاحتمال المرتبط بالحالة النهائية الفارغة مساويًا تمامًا لـ \(Q_t=\mathbb{P}(M<t)\). ثم تكرر الحلقة الخارجية ذلك لكل الحدود من \(1\) إلى \(n\)، وتجمع المقادير \(1-Q_t\)، وأخيرًا تقرب الجواب إلى ثمانية منازل عشرية.
لحد ثابت \(t\)، يملك الـ DP عددًا مقداره \(4n\) من الطبقات، ولا يخزن إلا الحالات التي يكون فيها عدد المجموعات المفتوحة أقل من \(t\). وفي طبقة ثابتة تفرض عمق السحب علاقة خطية بين عدادات الحالة، لذلك يبقى عدد الأوضاع الممكنة من رتبة \(O(t^3)\). ومن هنا نحصل على زمن \(O(nt^3)\) لحد واحد، وذاكرة \(O(t^3)\) للطبقتين النشطتين. وعند الجمع على جميع الحدود \(t=1,\dots,n\)، نحصل على حد أعلى إجمالي من رتبة \(O(n^5)\) زمنيًا و\(O(n^3)\) مكانيًا. عمليًا تكون الجبهة النشطة أصغر بكثير، لأن الحالات غير القابلة للوصول لا تدخل جداول التجزئة أصلًا، كما أن التقليم بالحد فعال جدًا.