Two players each choose a secret number uniformly at random. The first player chooses from \(\{1,\dots,n\}\), the second from \(\{1,\dots,m\}\). They then alternate asking yes-or-no questions of the form “is your number in this set?”, and both players choose their questions optimally. If \(p(m,n)\) denotes the first player’s winning probability, the required value is
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
The crucial observation used by the implementations is that the game value has an exact staircase structure. Because of that, each probability can be computed by a short block sum rather than by exploring a full game tree.
The solution does not simulate actual question sequences. Instead, it counts which initial secret pairs are winning for the first player and then divides by the total number of equally likely pairs.
There are exactly \(mn\) possible initial secret pairs, all with the same probability. For each pair, optimal play determines whether the first player wins or not. Let \(W(m,n)\) be the number of winning initial pairs for the first player.
Then the probability is simply
$$p(m,n)=\frac{W(m,n)}{mn}.$$
So the probabilistic problem is reduced to computing the integer quantity \(W(m,n)\).
Place the \(mn\) initial states in an \(m\times n\) grid. The exact formula used by the implementations says that in column \(t\), the number of winning cells is
$$\min(m,b_t),$$
where the boundary sequence \((b_t)\) begins as
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
After that, the sequence is constant on doubling blocks. For every integer \(r\ge 0\), if
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
then
$$b_t=3\cdot 2^{r+1}.$$
So the blocks are \([4,6]\), \([7,12]\), \([13,24]\), and so on, with corresponding heights \(6,12,24,\dots\). That staircase is the central mathematical structure behind the whole computation.
Since column \(t\) contributes \(\min(m,b_t)\) winning states, the total count is
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t).$$
This already gives an exact closed form for one game size. However, evaluating it literally one column at a time would be wasteful, because the sequence \((b_t)\) stays constant over long ranges.
For \(r\ge 0\), the block starting at \(3\cdot 2^r+1\) and ending at \(3\cdot 2^{r+1}\) has constant height \(3\cdot 2^{r+1}\). Let
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
This counts how many columns from that block are still present among the first \(n\) columns. Therefore
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
Only finitely many terms are nonzero, and the number of relevant blocks grows like \(O(\log n)\).
For \(n=5\), the first five staircase heights are
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6.$$
Because \(m=7\), the clipping \(\min(7,b_t)\) leaves these values unchanged, so
$$W(7,5)=1+2+3+6+6=18.$$
Hence
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
This is the same checkpoint used by the implementations.
The final target is
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}.$$
So the entire problem becomes 441 evaluations of the same staircase formula. The implementations also verify the natural edge cases \(p(1,n)=1\) and \(p(m,1)=1/m\), which fit the same counting rule.
The C++, Python, and Java implementations all use the same algorithm. They evaluate one pair \((m,n)\) by handling the first three columns separately, because the staircase begins with the explicit values \(1,2,3\).
After that, the implementation walks through blocks whose lengths are
$$3,6,12,24,\dots$$
and whose heights are
$$6,12,24,48,\dots$$
For each block, it takes only the part that still lies within the first \(n\) columns and adds the number of surviving columns multiplied by the clipped block height \(\min(m,\text{height})\). This directly produces the exact integer \(W(m,n)\).
Once \(W(m,n)\) is known, the implementation divides by \(mn\) using exact or high-precision arithmetic and accumulates the result into the outer double sum. High precision matters because the final answer is printed to eight decimal places after adding 441 rational values.
For one pair \((m,n)\), the number of processed blocks is proportional to the number of doublings needed to exceed \(n\), so the running time is \(O(\log n)\). Extra memory is \(O(1)\) apart from the exact-integer or high-precision decimal objects used to keep the arithmetic safe. Since the full problem needs only \(21\times 21=441\) evaluations, the overall computation is very small.
Zwei Spieler wählen jeweils gleichverteilt eine geheime Zahl. Der erste Spieler wählt aus \(\{1,\dots,n\}\), der zweite aus \(\{1,\dots,m\}\). Danach stellen sie abwechselnd Ja-Nein-Fragen der Form „liegt deine Zahl in dieser Menge?“, und beide wählen ihre Fragen optimal. Bezeichnet \(p(m,n)\) die Gewinnwahrscheinlichkeit des ersten Spielers, so ist gesucht
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
Die entscheidende Beobachtung der Implementierungen ist, dass der Spielwert eine exakte Treppenstruktur besitzt. Dadurch muss man keinen vollständigen Spielbaum durchsuchen, sondern kann jede Wahrscheinlichkeit mit einer kurzen Blocksumme berechnen.
Die Lösung simuliert nicht die konkreten Fragerunden. Stattdessen zählt sie, welche Startpaare geheimer Zahlen für den ersten Spieler gewinnend sind, und teilt anschließend durch die Gesamtzahl aller gleichwahrscheinlichen Paare.
Es gibt genau \(mn\) mögliche Startpaare geheimer Zahlen, alle mit derselben Wahrscheinlichkeit. Für jedes Paar legt optimales Spiel fest, ob der erste Spieler von diesem Zustand aus gewinnt oder nicht. Sei \(W(m,n)\) die Anzahl der gewinnenden Startpaare für den ersten Spieler.
Dann gilt einfach
$$p(m,n)=\frac{W(m,n)}{mn}.$$
Damit wird das Wahrscheinlichkeitsproblem auf die exakte Berechnung der ganzen Zahl \(W(m,n)\) reduziert.
Ordnet man die \(mn\) Startzustände in einem \(m\times n\)-Gitter an, dann besagt die in den Implementierungen verwendete exakte Formel: In Spalte \(t\) gibt es
$$\min(m,b_t)$$
gewinnende Zellen. Die Grenzfolge \((b_t)\) beginnt mit
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
Danach ist sie auf Verdopplungsblöcken konstant. Für jedes \(r\ge 0\) gilt: Wenn
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
dann ist
$$b_t=3\cdot 2^{r+1}.$$
Die Blöcke sind also \([4,6]\), \([7,12]\), \([13,24]\) usw., mit den zugehörigen Höhen \(6,12,24,\dots\). Diese Treppengrenze ist die zentrale mathematische Struktur des Problems.
Da Spalte \(t\) genau \(\min(m,b_t)\) Gewinnzustände beiträgt, ist die Gesamtzahl
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t).$$
Das ist bereits eine exakte geschlossene Form für eine Spielgröße. Trotzdem wäre eine wortwörtliche Auswertung Spalte für Spalte unnötig, weil \((b_t)\) über lange Bereiche konstant bleibt.
Für \(r\ge 0\) hat der Block von \(3\cdot 2^r+1\) bis \(3\cdot 2^{r+1}\) die konstante Höhe \(3\cdot 2^{r+1}\). Definiere
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
Dieser Ausdruck zählt, wie viele Spalten aus diesem Block noch unter den ersten \(n\) Spalten liegen. Daher folgt
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
Nur endlich viele Summanden sind ungleich null, und die Zahl der relevanten Blöcke wächst wie \(O(\log n)\).
Für \(n=5\) lauten die ersten fünf Treppenhöhen
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6.$$
Da \(m=7\) ist, verändert die Kappung \(\min(7,b_t)\) diese Werte nicht, also
$$W(7,5)=1+2+3+6+6=18.$$
Somit ist
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
Genau dieser Kontrollwert wird auch von den Implementierungen verwendet.
Das Ziel ist
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}.$$
Damit reduziert sich die gesamte Aufgabe auf 441 Auswertungen derselben Treppenformel. Die Implementierungen prüfen außerdem die natürlichen Randfälle \(p(1,n)=1\) und \(p(m,1)=1/m\), die ebenfalls zu derselben Zählregel passen.
Die C++-, Python- und Java-Implementierungen verwenden alle denselben Ablauf. Für ein Paar \((m,n)\) behandeln sie zunächst die ersten drei Spalten separat, weil die Treppe mit den expliziten Werten \(1,2,3\) beginnt.
Danach läuft die Implementierung über Blöcke mit den Längen
$$3,6,12,24,\dots$$
und den dazugehörigen Höhen
$$6,12,24,48,\dots$$
Für jeden Block wird nur der Teil genommen, der noch innerhalb der ersten \(n\) Spalten liegt. Dann wird die Anzahl dieser verbleibenden Spalten mit der gekappten Blockhöhe \(\min(m,\text{Höhe})\) multipliziert. So entsteht direkt die exakte ganze Zahl \(W(m,n)\).
Sobald \(W(m,n)\) bekannt ist, dividiert die Implementierung durch \(mn\) mit exakter oder hochpräziser Arithmetik und addiert das Ergebnis zur äußeren Doppelsumme. Hohe Präzision ist wichtig, weil am Ende nach der Summe von 441 rationalen Werten auf acht Nachkommastellen ausgegeben wird.
Für ein Paar \((m,n)\) ist die Zahl der verarbeiteten Blöcke proportional zur Anzahl der Verdopplungen, die nötig sind, um \(n\) zu überschreiten. Die Laufzeit beträgt daher \(O(\log n)\). Der zusätzliche Speicher ist \(O(1)\), abgesehen von den Ganzzahl- oder Dezimalobjekten für sichere Arithmetik. Da das vollständige Problem nur \(21\times 21=441\) Auswertungen benötigt, ist der Gesamtaufwand sehr klein.
İki oyuncu da gizli bir sayı seçer ve seçimler eşit olasılıklıdır. Birinci oyuncu \(\{1,\dots,n\}\) aralığından, ikinci oyuncu ise \(\{1,\dots,m\}\) aralığından seçer. Daha sonra sırayla “sayın bu kümenin içinde mi?” biçiminde evet-hayır soruları sorarlar ve iki taraf da sorularını en iyi biçimde seçer. Birinci oyuncunun kazanma olasılığı \(p(m,n)\) ise istenen değer
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
Uygulamaların kullandığı temel gözlem şudur: oyun değeri tam olarak bir basamak fonksiyonuna oturur. Bu sayede tam bir oyun ağacını aramak yerine her olasılık kısa bir blok toplamıyla hesaplanır.
Çözüm gerçek soru dizilerini tek tek canlandırmaz. Bunun yerine hangi başlangıç gizli sayı çiftlerinin birinci oyuncu için kazançlı olduğunu sayar ve ardından bu sayıyı tüm eş olasılıklı çiftlerin sayısına böler.
Başlangıçta tam olarak \(mn\) farklı gizli sayı çifti vardır ve hepsi aynı olasılığa sahiptir. Her bir çift için optimal oyun, birinci oyuncunun o durumdan kazanıp kazanmayacağını belirler. Birinci oyuncu için kazançlı başlangıç çiftlerinin sayısına \(W(m,n)\) diyelim.
O zaman
$$p(m,n)=\frac{W(m,n)}{mn}.$$
Böylece olasılık sorunu, tamsayı değerli \(W(m,n)\) miktarını tam hesaplama problemine indirgenir.
\(mn\) adet başlangıç durumunu \(m\times n\) boyutlu bir ızgaraya yerleştirelim. Uygulamaların kullandığı tam formül şunu söyler: \(t\). sütunda kazançlı hücre sayısı
$$\min(m,b_t)$$
kadardır. Buradaki sınır dizisi \((b_t)\) şu şekilde başlar:
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
Bundan sonra dizi, uzunluğu iki katına çıkan bloklarda sabit kalır. Her \(r\ge 0\) için eğer
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
ise
$$b_t=3\cdot 2^{r+1}.$$
Yani bloklar \([4,6]\), \([7,12]\), \([13,24]\), ... biçimindedir ve bunların yükseklikleri sırasıyla \(6,12,24,\dots\) olur. Tüm hesabın merkezindeki matematiksel yapı bu merdiven sınırıdır.
\(t\). sütun \(\min(m,b_t)\) adet kazançlı durum getirdiğine göre toplam sayı
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t)$$
olur. Bu zaten tek bir oyun boyutu için tam bir kapalı formdur. Ancak \((b_t)\) uzun aralıklarda sabit kaldığı için bunu sütun sütun hesaplamak gereksizdir.
\(r\ge 0\) için \(3\cdot 2^r+1\) ile \(3\cdot 2^{r+1}\) arasındaki blok, sabit yükseklik \(3\cdot 2^{r+1}\) taşır. Şunu tanımlayalım:
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
Bu ifade, ilk \(n\) sütun içinde bu bloktan kaç sütun kaldığını sayar. Dolayısıyla
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
Yalnızca sonlu sayıda terim sıfırdan farklıdır ve ilgili blok sayısı \(O(\log n)\) mertebesindedir.
\(n=5\) için ilk beş merdiven yüksekliği
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6$$
olur. \(m=7\) olduğundan \(\min(7,b_t)\) kırpması bu değerleri değiştirmez ve
$$W(7,5)=1+2+3+6+6=18$$
elde edilir. Buradan
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
sonucu çıkar. Bu değer, uygulamalardaki kontrol örneğiyle aynıdır.
Son hedef
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}$$
ifadesidir. Böylece bütün problem aynı merdiven formülünün 441 kez değerlendirilmesine iner. Uygulamalar ayrıca \(p(1,n)=1\) ve \(p(m,1)=1/m\) sınır durumlarını da doğrular; bunlar da aynı sayma kuralıyla uyumludur.
C++, Python ve Java uygulamalarının hepsi aynı algoritmayı izler. Önce bir \((m,n)\) çifti için ilk üç sütun ayrı ele alınır; çünkü merdiven açıkça \(1,2,3\) değerleriyle başlar.
Daha sonra uygulama uzunlukları
$$3,6,12,24,\dots$$
olan ve yükseklikleri
$$6,12,24,48,\dots$$
şeklinde giden bloklar üzerinde ilerler. Her blok için yalnızca ilk \(n\) sütun içinde kalan kısım alınır ve bu sütun sayısı, kırpılmış blok yüksekliği \(\min(m,\text{yükseklik})\) ile çarpılır. Böylece tam tamsayı \(W(m,n)\) doğrudan elde edilir.
\(W(m,n)\) bulunduğunda uygulama bunu \(mn\)'ye tam ya da yüksek duyarlıklı aritmetikle böler ve sonucu dıştaki çift toplama ekler. Yüksek duyarlık önemlidir; çünkü sonunda 441 rasyonel değerin toplamı sekiz ondalık basamakla yazdırılır.
Tek bir \((m,n)\) çifti için işlenen blok sayısı, \(n\)'yi aşmak için gereken ikiye katlama sayısıyla orantılıdır; dolayısıyla süre \(O(\log n)\) olur. Güvenli aritmetik için kullanılan tam sayı ya da yüksek duyarlıklı ondalık nesneler dışında ek bellek \(O(1)\)'dir. Tüm problem yalnızca \(21\times 21=441\) değerlendirme istediği için toplam hesaplama çok küçüktür.
Dos jugadores eligen en secreto un número con distribución uniforme. El primer jugador elige en \(\{1,\dots,n\}\) y el segundo en \(\{1,\dots,m\}\). Después hacen preguntas de sí o no del tipo “¿tu número pertenece a este conjunto?”, alternando turnos y jugando ambos de manera óptima. Si \(p(m,n)\) es la probabilidad de victoria del primer jugador, se pide calcular
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
La observación decisiva usada por las implementaciones es que el valor del juego tiene una estructura exacta en forma de escalera. Gracias a eso, cada probabilidad se obtiene con una suma corta por bloques, sin explorar un árbol completo de juego.
La solución no reproduce cada secuencia posible de preguntas. En su lugar, cuenta cuántos pares iniciales de números secretos son ganadores para el primer jugador y luego divide por el número total de pares equiprobables.
Existen exactamente \(mn\) pares iniciales posibles, todos con la misma probabilidad. Para cada par, el juego óptimo determina si el primer jugador gana o no desde ese estado. Sea \(W(m,n)\) el número de pares iniciales ganadores para el primer jugador.
Entonces
$$p(m,n)=\frac{W(m,n)}{mn}.$$
Así, la parte probabilística queda reducida a calcular con exactitud la cantidad entera \(W(m,n)\).
Colocamos los \(mn\) estados iniciales en una cuadrícula de tamaño \(m\times n\). La fórmula exacta usada por las implementaciones afirma que en la columna \(t\) el número de celdas ganadoras es
$$\min(m,b_t).$$
La sucesión de frontera \((b_t)\) comienza con
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
A partir de ahí, permanece constante en bloques que se van duplicando. Para cada entero \(r\ge 0\), si
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
entonces
$$b_t=3\cdot 2^{r+1}.$$
Por tanto, los bloques son \([4,6]\), \([7,12]\), \([13,24]\), etc., con alturas \(6,12,24,\dots\). Esa frontera escalonada es la estructura matemática central del problema.
Como la columna \(t\) aporta \(\min(m,b_t)\) estados ganadores, el total es
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t).$$
Esto ya es una forma exacta cerrada para un tamaño de juego. Sin embargo, evaluarla literalmente columna por columna sería innecesario, porque \((b_t)\) se mantiene constante en intervalos largos.
Para \(r\ge 0\), el bloque que empieza en \(3\cdot 2^r+1\) y termina en \(3\cdot 2^{r+1}\) tiene altura constante \(3\cdot 2^{r+1}\). Definimos
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
Esto cuenta cuántas columnas de ese bloque siguen presentes dentro de las primeras \(n\) columnas. Por consiguiente,
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
Solo un número finito de términos es no nulo, y la cantidad de bloques relevantes crece como \(O(\log n)\).
Para \(n=5\), las primeras cinco alturas de la escalera son
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6.$$
Como \(m=7\), el recorte \(\min(7,b_t)\) no altera estos valores, y por tanto
$$W(7,5)=1+2+3+6+6=18.$$
De aquí se obtiene
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
Este es el mismo punto de control utilizado por las implementaciones.
La cantidad final es
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}.$$
Por lo tanto, todo el problema se reduce a 441 evaluaciones de la misma fórmula en escalera. Las implementaciones también verifican los casos borde naturales \(p(1,n)=1\) y \(p(m,1)=1/m\), que encajan con la misma regla de conteo.
Las implementaciones en C++, Python y Java siguen exactamente el mismo esquema. Para cada par \((m,n)\), primero tratan por separado las tres primeras columnas, porque la escalera comienza con los valores explícitos \(1,2,3\).
Después, la implementación recorre bloques cuyas longitudes son
$$3,6,12,24,\dots$$
y cuyas alturas son
$$6,12,24,48,\dots$$
En cada bloque toma solo la parte que aún cae dentro de las primeras \(n\) columnas y suma el número de columnas restantes multiplicado por la altura recortada \(\min(m,\text{altura})\). Así obtiene directamente el entero exacto \(W(m,n)\).
Una vez conocido \(W(m,n)\), la implementación divide entre \(mn\) usando aritmética exacta o de alta precisión y añade el resultado a la doble suma exterior. La alta precisión importa porque la respuesta final se imprime con ocho decimales después de acumular 441 valores racionales.
Para un par \((m,n)\), el número de bloques procesados es proporcional al número de duplicaciones necesarias para superar \(n\), así que el tiempo es \(O(\log n)\). La memoria extra es \(O(1)\), salvo por los objetos enteros exactos o decimales de alta precisión usados para mantener segura la aritmética. Como el problema completo solo requiere \(21\times 21=441\) evaluaciones, el coste total es muy pequeño.
两位玩家各自均匀随机选择一个秘密数字。第一位玩家从 \(\{1,\dots,n\}\) 中选择，第二位玩家从 \(\{1,\dots,m\}\) 中选择。随后双方轮流提出形如“你的数字是否属于这个集合？”的真假问题，并且两边都采用最优提问策略。若第一位玩家的获胜概率记为 \(p(m,n)\)，则题目要求计算
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
实现所依赖的关键事实是：这个博弈的取值并不需要完整地展开博弈树，而是具有一个精确的“阶梯边界”结构。正因为如此，每个概率都可以通过一段很短的分块求和得到。
解法并不去模拟所有可能的提问顺序，而是先数出哪些初始秘密数字对对第一位玩家是必胜的，再除以总的等概率初始状态数。
一开始共有 \(mn\) 个可能的秘密数字对，而且它们出现的概率完全相同。对每一个初始数字对来说，在双方都最优的前提下，胜负结果是确定的。记 \(W(m,n)\) 为第一位玩家的必胜初始状态数。
那么概率就等于
$$p(m,n)=\frac{W(m,n)}{mn}.$$
因此，概率计算的核心被化成了精确求出整数 \(W(m,n)\)。
把全部 \(mn\) 个初始状态排成一个 \(m\times n\) 的网格。实现中使用的精确公式表明：在第 \(t\) 列里，第一位玩家的必胜格子数恰好是
$$\min(m,b_t).$$
其中边界序列 \((b_t)\) 的开头是
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
从这里开始，它会在长度不断翻倍的区间上保持常数。对任意整数 \(r\ge 0\)，只要
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
就有
$$b_t=3\cdot 2^{r+1}.$$
也就是说，后续区间依次是 \([4,6]\)、\([7,12]\)、\([13,24]\)、……，而对应的高度分别是 \(6,12,24,\dots\)。这个阶梯边界就是整道题最重要的数学骨架。
因为第 \(t\) 列贡献 \(\min(m,b_t)\) 个必胜状态，所以总数满足
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t).$$
这已经是单个规模 \((m,n)\) 的精确公式了。不过如果逐列相加，就会浪费掉序列 \((b_t)\) 在长区间上不变这一结构信息。
对 \(r\ge 0\)，从 \(3\cdot 2^r+1\) 到 \(3\cdot 2^{r+1}\) 的整段都具有相同的高度 \(3\cdot 2^{r+1}\)。定义
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
这个量表示在前 \(n\) 列之中，该区间实际被截取到了多少列。于是有
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
只有有限多个项非零，而且相关区间的个数只按 \(O(\log n)\) 增长。
当 \(n=5\) 时，前五个阶梯高度是
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6.$$
由于 \(m=7\)，这里的截断 \(\min(7,b_t)\) 不会改变这些数，因此
$$W(7,5)=1+2+3+6+6=18.$$
从而
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
这正好对应实现中使用的示例检查值。
最终目标是
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}.$$
因此整道题实际上只是把同一条阶梯公式计算 441 次。实现还验证了自然边界情形 \(p(1,n)=1\) 与 \(p(m,1)=1/m\)，它们同样符合这一计数规则。
C++、Python 和 Java 实现采用的是同一套思路。对于任意一组 \((m,n)\)，它们先单独处理前三列，因为阶梯序列的起点就是明确的 \(1,2,3\)。
随后，实现按块前进，这些块的长度依次为
$$3,6,12,24,\dots$$
对应的高度依次为
$$6,12,24,48,\dots$$
对每个块，只取仍然落在前 \(n\) 列之内的那一部分，再把“剩余列数”乘上截断后的块高度 \(\min(m,\text{高度})\)。这样就直接得到了精确整数 \(W(m,n)\)。
求出 \(W(m,n)\) 之后，实现再用精确整数或高精度小数计算 \(\frac{W(m,n)}{mn}\)，并把结果累加到外层双重求和中。之所以需要高精度，是因为最后要把 441 个有理数的和以八位小数输出。
对于单个 \((m,n)\)，需要处理的块数与把区间长度翻倍直到超过 \(n\) 的次数成正比，所以时间复杂度是 \(O(\log n)\)。除去为了保证数值安全而使用的精确整数或高精度小数对象，额外空间复杂度为 \(O(1)\)。整个题目只需要计算 \(21\times 21=441\) 组参数，因此总开销非常小。
Два игрока независимо и равновероятно выбирают секретные числа. Первый выбирает число из \(\{1,\dots,n\}\), второй из \(\{1,\dots,m\}\). Затем они по очереди задают вопросы вида «принадлежит ли твоё число этому множеству?», причём оба выбирают вопросы оптимально. Если \(p(m,n)\) обозначает вероятность победы первого игрока, требуется вычислить
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
Ключевой факт, на котором основаны реализации, состоит в том, что значение игры имеет точную лестничную структуру. Поэтому каждую вероятность можно получить короткой суммой по блокам, не разворачивая полный игровой граф.
Решение не моделирует все возможные цепочки вопросов. Вместо этого оно считает, какие начальные пары секретных чисел являются выигрышными для первого игрока, а затем делит на общее число равновероятных начальных состояний.
Всего существует \(mn\) возможных начальных пар секретных чисел, и все они равновероятны. Для каждой пары оптимальная игра однозначно определяет, побеждает ли первый игрок из этого состояния. Обозначим через \(W(m,n)\) число выигрышных начальных пар для первого игрока.
Тогда
$$p(m,n)=\frac{W(m,n)}{mn}.$$
Тем самым вероятностная часть задачи сводится к точному вычислению целого числа \(W(m,n)\).
Разместим все \(mn\) начальных состояний в сетке размера \(m\times n\). Точная формула, используемая реализациями, утверждает, что в столбце \(t\) число выигрышных клеток равно
$$\min(m,b_t).$$
Здесь последовательность границы \((b_t)\) начинается так:
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
Дальше она постоянна на блоках, чья длина каждый раз удваивается. Для любого целого \(r\ge 0\), если
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
то
$$b_t=3\cdot 2^{r+1}.$$
Иными словами, блоки имеют вид \([4,6]\), \([7,12]\), \([13,24]\), и так далее, а их высоты равны \(6,12,24,\dots\). Именно эта лестничная граница является центральной математической структурой задачи.
Поскольку столбец \(t\) даёт \(\min(m,b_t)\) выигрышных состояний, общее количество равно
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t).$$
Это уже точная формула для одного размера игры. Но вычислять её буквально по столбцам неэффективно, потому что последовательность \((b_t)\) остаётся постоянной на длинных промежутках.
Для \(r\ge 0\) блок от \(3\cdot 2^r+1\) до \(3\cdot 2^{r+1}\) имеет постоянную высоту \(3\cdot 2^{r+1}\). Определим
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
Это количество столбцов из данного блока, которые реально попадают в первые \(n\) столбцов. Поэтому
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
Ненулевых слагаемых лишь конечное число, а количество нужных блоков растёт как \(O(\log n)\).
При \(n=5\) первые пять высот лестницы равны
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6.$$
Так как \(m=7\), отсечение \(\min(7,b_t)\) ничего не меняет, и потому
$$W(7,5)=1+2+3+6+6=18.$$
Следовательно,
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
Это совпадает с контрольным значением, используемым в реализациях.
Искомая величина равна
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}.$$
Значит, вся задача сводится к 441 вычислению одной и той же лестничной формулы. Реализации также проверяют естественные крайние случаи \(p(1,n)=1\) и \(p(m,1)=1/m\), которые подчиняются той же самой схеме подсчёта.
Реализации на C++, Python и Java используют один и тот же алгоритм. Для каждой пары \((m,n)\) они сначала отдельно обрабатывают первые три столбца, потому что лестница начинается явными значениями \(1,2,3\).
Затем реализация проходит по блокам длины
$$3,6,12,24,\dots$$
с высотами
$$6,12,24,48,\dots$$
Для каждого блока берётся только та часть, которая ещё лежит внутри первых \(n\) столбцов, и к сумме прибавляется число оставшихся столбцов, умноженное на усечённую высоту блока \(\min(m,\text{высота})\). Так непосредственно получается точное целое число \(W(m,n)\).
После этого реализация делит \(W(m,n)\) на \(mn\) с использованием точной или высокоточной арифметики и добавляет результат к внешней двойной сумме. Высокая точность нужна потому, что в конце печатается сумма 441 рационального числа с восемью знаками после запятой.
Для одной пары \((m,n)\) число обработанных блоков пропорционально количеству удвоений, необходимых, чтобы превысить \(n\), поэтому время работы равно \(O(\log n)\). Дополнительная память равна \(O(1)\), если не считать объектов точных целых или высокоточных десятичных чисел, нужных для безопасной арифметики. Поскольку вся задача требует только \(21\times 21=441\) вычисления, общий объём работы очень мал.
يختار كل لاعب عددًا سريًا باحتمال متساوٍ. اللاعب الأول يختار من \(\{1,\dots,n\}\)، واللاعب الثاني يختار من \(\{1,\dots,m\}\). بعد ذلك يتناوبان على طرح أسئلة نعم أو لا من النوع «هل عددك ينتمي إلى هذه المجموعة؟»، مع افتراض أن كليهما يلعب على النحو الأمثل. إذا كانت \(p(m,n)\) هي احتمالية فوز اللاعب الأول، فالمطلوب هو حساب
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j).$$
الفكرة الحاسمة التي تعتمد عليها التطبيقات هي أن قيمة اللعبة لا تحتاج إلى استكشاف شجرة اللعب كاملة، لأن لها بنية درجية دقيقة تمامًا. ولهذا يمكن حساب كل احتمال بواسطة مجموع قصير على كتل متضاعفة.
الحل لا يحاكي جميع تسلسلات الأسئلة الممكنة. بدلًا من ذلك، يحسب عدد أزواج الحالات الابتدائية التي تكون رابحة للاعب الأول، ثم يقسم هذا العدد على العدد الكلي للحالات المتساوية الاحتمال.
يوجد في البداية بالضبط \(mn\) زوجًا ممكنًا من الأعداد السرية، وجميعها متساوية الاحتمال. ولكل زوج، يحدد اللعب الأمثل ما إذا كان اللاعب الأول سيفوز من تلك الحالة أم لا. لنرمز إلى عدد الأزواج الابتدائية الرابحة للاعب الأول بالرمز \(W(m,n)\).
عندئذ
$$p(m,n)=\frac{W(m,n)}{mn}.$$
وهكذا تتحول المسألة الاحتمالية إلى حساب كمية صحيحة هي \(W(m,n)\) بدقة.
لنرتب جميع الحالات الابتدائية وعددها \(mn\) في شبكة أبعادها \(m\times n\). الصيغة الدقيقة المستخدمة في التطبيقات تقول إن عدد الخلايا الرابحة في العمود \(t\) يساوي
$$\min(m,b_t).$$
وتبدأ المتتالية الحدية \((b_t)\) بالشكل
$$b_1=1,\qquad b_2=2,\qquad b_3=3.$$
وبعد ذلك تصبح ثابتة على كتل تتضاعف أطوالها. لكل عدد صحيح \(r\ge 0\)، إذا تحقق
$$3\cdot 2^r+1\le t\le 3\cdot 2^{r+1},$$
فإن
$$b_t=3\cdot 2^{r+1}.$$
أي أن الكتل تكون \([4,6]\)، ثم \([7,12]\)، ثم \([13,24]\)، وهكذا، مع ارتفاعات مقابلة \(6,12,24,\dots\). هذا الحد الدَّرَجي هو البنية الرياضية الأساسية في المسألة.
بما أن العمود \(t\) يضيف \(\min(m,b_t)\) حالة رابحة، فإن العدد الكلي يساوي
$$W(m,n)=\sum_{t=1}^{n}\min(m,b_t).$$
وهذه بالفعل صيغة دقيقة مغلقة لحجم لعبة واحد. لكن تنفيذها حرفيًا عمودًا بعد عمود غير ضروري، لأن المتتالية \((b_t)\) ثابتة على مقاطع طويلة.
لكل \(r\ge 0\)، الكتلة الممتدة من \(3\cdot 2^r+1\) إلى \(3\cdot 2^{r+1}\) لها ارتفاع ثابت مقداره \(3\cdot 2^{r+1}\). نعرّف
$$R_r(n)=\max\left(0,\min\left(n,3\cdot 2^{r+1}\right)-\left(3\cdot 2^r+1\right)+1\right).$$
وهذا المقدار يحسب عدد الأعمدة من تلك الكتلة التي ما زالت موجودة ضمن أول \(n\) أعمدة. ولذلك نحصل على
$$W(m,n)=\min(m,1)+\min(m,2)+\min(m,3)+\sum_{r\ge 0} R_r(n)\,\min\left(m,3\cdot 2^{r+1}\right).$$
عدد الحدود غير الصفرية منتهٍ، وعدد الكتل المهمة ينمو بمعدل \(O(\log n)\).
عندما \(n=5\)، تكون أول خمس ارتفاعات في السلم
$$b_1,b_2,b_3,b_4,b_5=1,2,3,6,6.$$
وبما أن \(m=7\)، فإن القص بواسطة \(\min(7,b_t)\) لا يغير هذه القيم، ومن ثم
$$W(7,5)=1+2+3+6+6=18.$$
إذًا
$$p(7,5)=\frac{18}{7\cdot 5}=\frac{18}{35}=0.51428571\dots$$
وهذه هي نفس قيمة التحقق التي تعتمدها التطبيقات.
الكمية النهائية هي
$$\sum_{i=0}^{20}\sum_{j=0}^{20} p(7^i,5^j)=\sum_{i=0}^{20}\sum_{j=0}^{20}\frac{W(7^i,5^j)}{7^i5^j}.$$
وبذلك تتحول المسألة كلها إلى 441 تقييمًا للصيغة الدرجية نفسها. كما تتحقق التطبيقات من الحالتين الطرفيتين الطبيعيتين \(p(1,n)=1\) و\(p(m,1)=1/m\)، وهما أيضًا منسجمتان مع قاعدة العد نفسها.
تتبع تطبيقات C++ وPython وJava الخوارزمية نفسها. فهي تعالج أول ثلاثة أعمدة لكل زوج \((m,n)\) بصورة مستقلة، لأن السلم يبدأ بالقيم الصريحة \(1,2,3\).
بعد ذلك تنتقل الشيفرة عبر كتل أطوالها
$$3,6,12,24,\dots$$
وارتفاعاتها
$$6,12,24,48,\dots$$
وفي كل كتلة تأخذ فقط الجزء الذي ما زال يقع ضمن أول \(n\) أعمدة، ثم تضيف عدد الأعمدة الباقية مضروبًا في الارتفاع المقصوص. وإذا رمزنا إلى ارتفاع الكتلة بالرمز \(h\)، فإن عامل القص يكون \(\min(m,h)\). وبهذه الطريقة تحصل مباشرة على العدد الصحيح الدقيق \(W(m,n)\).
بعد معرفة \(W(m,n)\)، تقسمه الشيفرة على \(mn\) باستعمال حساب صحيح دقيق أو حساب عشري عالي الدقة، ثم تجمع النتيجة في المجموع الخارجي. وتظهر أهمية الدقة العالية لأن الناتج النهائي يُطبع حتى ثماني منازل عشرية بعد جمع 441 قيمة نسبية.
بالنسبة إلى زوج واحد \((m,n)\)، فإن عدد الكتل المعالجة يتناسب مع عدد مرات التضاعف اللازمة لتجاوز \(n\)، ولذلك يكون الزمن \(O(\log n)\). أما الذاكرة الإضافية فهي \(O(1)\) باستثناء كائنات الأعداد الصحيحة الدقيقة أو الأعداد العشرية عالية الدقة المستخدمة لضمان سلامة الحساب. وبما أن المسألة الكاملة تحتاج فقط إلى \(21\times 21=441\) تقييمًا، فإن الكلفة الكلية صغيرة جدًا.